Các kiểu tập hợp (Collection) trong C#: khái niệm, phân loại

    0

    Khi lập trình có thể để ý rằng chúng ta thường phải làm việc với các nhóm/tập hợp/danh sách thông tin mà chúng ta thường gọi chung là dữ liệu. Cách tổ chức, quản lý và xử lý dữ liệu là trọng tâm của hầu hết các chương trình. Trong C# nói riêng, dữ liệu ở dạng nhóm như vậy có tên gọi chung là collection.

    Collection (tạm dịch là tập hợp) là các kiểu dữ liệu đặc biệt trong C# dùng để lưu trữ một nhóm dữ liệu, thay vì từng dữ liệu riêng rẽ. Trong C# (và .NET framework) đã xây dựng sẵn rất nhiều kiểu collection khác nhau để đáp ứng các yêu cầu về lập trình. Trong bài học này chúng ta sẽ xem xét khái niệm và phân loại các kiểu dữ liệu tập hợp (collection) và các class thuộc loại collection trong C# và .NET Framework. Bài học này mang tính chất giới thiệu tổng quát và hệ thống hóa các kiểu dữ liệu collection quan trọng và class thực thi tương ứng trong C#. Trong các bài học tiếp theo chúng ta sẽ lần lượt đi vào xem xét chi tiết của từng kiểu cụ thể.

    Quay lại khóa học Cấu trúc dữ liệu và thuật toán với C#

    Định nghĩa collection

    Collection là những kiểu dữ liệu có cấu trúc được dùng để lưu trữ (một nhóm) dữ liệu và cung cấp các phép toán trên các dữ liệu đó. Các phép toán cơ bản thường bao gồm thêm dữ liệu, xóa dữ liệu, cập nhật dữ liệu, gán và lấy giá trị của các thuộc tính.

    Một số vấn đề thuật ngữ. Từ collection trong tiếng anh có thể dịch sang là tập hợp nhưng có thể gây nhầm lẫn với set – vốn cũng được dịch sang là tập hợp. Set là một trường hợp cụ thể của collection. Do đó, trong tài liệu này chúng ta sẽ dùng thuật ngữ gốc collection. Đối với kiểu dữ liệu set chúng ta sẽ dùng thuật ngữ tiếng Việt tập hợp cho quen thuộc.

    Collection luôn xác định một tập các thuộc tính (Property) đặc trưng cho nó và các phép toán (Operation) thực hiện được trên dữ liệu. Ví dụ, một thuộc tính thường gặp nhất là số lượng phần tử (Count) đang lưu trong collection. Các phép toán (còn gọi là phương thức – Method) thường gặp như thêm phần tử mới (Add), chèn phần tử vào một vị trí (Insert), xóa phần tử (Remove), xóa toàn bộ dữ liệu (Clear), v.v..

    Phân loại collection

    Collection có thể chia làm hai nhóm: tuyến tính (linear) và phi tuyến (nonlinear).

    Linear collection chứa danh sách các phần tử trong đó mỗi phần tử nối tiếp phần tử trước nó. Các phần tử trong linear collection có thể được sắp xếp theo thứ tự (1, 2, 3, v.v.). Để dễ hình dung, trong thực tế, danh sách mua hàng có thể thể xem là một linear collection. Trong lập trình, mảng (array) là một dạng linear collection.

    Linear collection lại phân chia thành các loại: (1) truy xuất trực tiếp (direct access), (2) truy xuất tuần tự (sequential access), (3) dùng chỉ số (indexed).

    Nonlinear collection lưu trữ các phần tử nhưng không thể sắp xếp theo thứ tự. Ví dụ sơ đồ tổ chức (organizational chart) là một loại nonlinear collection. Trong lập trình, cây, heap, đồ thị, hay tập hợp là những kiểu dữ liệu thuộc loại nonlinear collection.

    Nonlinear collection cũng phân chia thành hai loại: (1) phân cấp (hierarchical), (2) phân nhóm (grouped).

    Bạn có thể đọc thêm về khái niệm và phân loại collection trên wikipedia.

    Các kiểu linear collection trong C#

    Trong phần này chúng ta sẽ điểm qua các kiểu dữ liệu collection thường gặp cũng như phiên bản thực hiện trong C#. Các nội dung này chỉ mang tính chất giới thiệu. Phần chi tiết sẽ đề cập đến trong các bài học riêng tương ứng.

    Collection truy xuất trực tiếp

    Loại collection truy xuất trực tiếp quen thuộc nhất trong lập trình là mảng (array). Mảng chứa một tập hợp phần tử thuộc cùng một kiểu (gọi là kiểu cơ sở). Có thể truy xuất (trực tiếp) các phần tử của mảng qua chỉ số (index) của nó. Mảng có thể là mảng tĩnh (static) nếu số phần tử của nó được xác định cứng và không thay đổi được, hoặc là mảng động (dynamic) nếu số lượng phần tử của nó có thể thay đổi tự do.

    Trong C# mảng là kiểu dữ liệu dựng sẵn, đồng thời cũng là một class (lớp Array). Đây là kiểu collection có hiệu suất thuộc loại cao nhất trong C#. Mảng trong C# phù hợp nhất với việc lưu trữ (và truy xuất) nhóm giá trị có số lượng cố định.

    Chuỗi ký tự (String) trong C# cũng được xem là một loại collection truy xuất trực tiếp. Từ khía cạnh nào đó String cũng được xem là một loại array nhưng thuộc loại immutable. Chúng ta sẽ xem xét chi tiết String trong một bài khác.

    Một kiểu dữ liệu khác được xem như collection trong C# là struct. Struct chứa một tập hợp phần tử thuộc nhiều kiểu khác nhau và cho phép truy xuất trực tiếp qua tên phần tử.

    Collection truy xuất tuần tự

    Loại collection này chứa các phần tử theo một dãy tuần tự và thường được gọi là danh sách tuyến tính (linear list).

    Đặc điểm của collection truy xuất tuần tự là nếu muốn truy xuất phần tử nào đó, chúng ta bắt buộc phải duyệt qua danh sách để đến phần tử cần truy xuất. Việc duyệt này có thể theo một chiều (từ phần tử đầu => phần tử cuối, từ phần tử cuối => phần tử đầu), hoặc theo cả hai chiều. Một đặc điểm khác của linear list là các phần tử của nó có thể đã được sắp xếp (ordered list) hoặc chưa được sắp xếp (unordered list). Việc sắp xếp này có ảnh hưởng rất lớn đến tìm kiếm dữ liệu trong danh sách.

    Có hai loại danh sách thuộc kiểu này hay gặp nhất là ngăn xếp (Stack) và hàng đợi (Queue). Stack chứa và truy xuất dữ liệu theo mô hình Last-in First-out (LIFO). Stack dùng đặc biệt phổ biến trong lập trình để lưu trữ biến, tính toán số học, v.v..

    Queue chứa và truy xuất dữ liệu theo mô hình First-in First-out (FIFO). Queue sử dụng rất nhiều trong lập trình hệ thống (ví dụ, để lập lịch cho hệ điều hành). Hai loại danh sách này sẽ có các bài học riêng.

    Collection dùng chỉ số

    Đây là nhóm collection đặc biệt trong đó dữ liệu được lưu dưới dạng các cặp khóa – giá trị. Có hai loại thường gặp là bảng băm (HashTable) và từ điển (Dictionary).

    Trong bảng băm, một loại hàm đặc biệt gọi là hàm băm (Hash function) biến một giá trị của khóa thành chỉ số (một số nguyên). Chỉ số này dùng để truy xuất giá trị.

    Kiểu từ điển, giống như các từ điển ngôn ngữ, chứa các cặp khóa-giá trị. Trong đó, khóa đóng vai trò giống như từ gốc, còn giá trị tương tự như nghĩa của từ đó.

    Các kiểu nonlinear collection

    Collection phân cấp

    Collection phân cấp có đặc điểm là các phần tử của nó được phân chia thành các cấp độ và có quan hệ với nhau.

    Loại collection phân cấp thường gặp là cây (tree). Mỗi cây có một phần tử ở cấp cao nhất gọi là gốc (root), phân chia thành các nhánh. Mỗi phần tử được gọi là một node. Node ở cuối mỗi nhánh gọi là lá (leaf). Có thể hình dung cấu trúc tree giống như một cái cây (cây thực vật ấy nhé) lộn ngược lại.

    Cấu trúc cây được sử dụng rất phổ biến. Ví dụ hệ thống file của các hệ điều hành đều tổ chức theo dạng cây. Sơ đồ tổ chức của một công ty cũng có thể hình dung như một cây.

    Collection phân nhóm

    Trong collection phân nhóm, các phần tử của nó không thể sắp xếp theo trật tự nào. Ba loại collection phân nhóm quen thuộc nhất là tập hợp (set), đồ thị (graph), và mạng (network).

    Tập hợp là loại cấu trúc quen thuộc nhất với học sinh vì được học trong chương trình toán phổ thông. Tập hợp chứa các giá trị không trùng lặp và vô trật tự.

    Đồ thị là một tập hợp các nút (node) và cạnh (edge), trong đó cạnh kết nối các nút. Đồ thị được sử dụng rất phổ biến trong thực tế, ví dụ trong logistics hay lập lịch công việc.

    Mạng là một dạng đặc biệt của đồ thị trong đó mỗi cạnh được gán một trọng số. Có thể hình dung nó giống một mạng lưới các thành phố kết nối nhau bởi đường giao thông. Mỗi thành phố là một node, đường giao thông là edge, còn độ dài con đường là trọng số của edge.

    Kết luận

    Trong bài học này chúng ta đã xem xét một cách tổng quát và hệ thống của các loại collection quan trọng nhất. Đây là bài học cơ sở để các bài sau chúng ta sẽ đi vào chi tiết của từng loại cấu trúc dữ liệu cụ thể và cách xây dựng/vận dụng chúng trong C# .NET.

    Bình luận

    avatar
      Đăng ký theo dõi  
    Thông báo về