Cấu trúc dữ liệu là một nhóm các phần tử dữ liệu, cung cấp một cách hiệu quả để lưu trữ và tổ chức dữ liệu trong máy tính để các dữ liệu này có thể được sử dụng một cách hiệu quả. Một số ví dụ được liệt kê bao gồm mảng, danh sách liên kết, ngăn xếp, hàng đợi. Khái niệm này được sử dụng rộng rãi trong hầu hết các mặt của khoa học máy tính, gồm hệ điều hành, thiết kế trình biên dịch, trí tuệ nhân tạo và một số lĩnh vực khác.
Trong bài viết này, ta sẽ cùng tìm hiểu qua về đơn vị kiến thức này và một số thuật ngữ khác cơ bản của nó.
Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu là một cách thức thu thập và tổ chức dữ liệu theo cách mà chúng ta có thể thực hiện các thao tác với những dữ liệu này một cách hiệu quả, liên quan tới việc tạo ra các phần tử dữ liệu dựa theo mối quan hệ, để tổ chức và lưu trữ tốt hơn.
Một số thuật ngữ sau là các thuật ngữ nền tảng.
- Giao diện (Interface): Giao diện đại diện cho tập hợp các thao tác mà một cấu trúc hỗ trợ.
- Triển khai (Implementation): Việc triển khai nhằm cung cấp các định nghĩa của các thuật toán được sử dụng trong các thao tác.
- Dữ liệu: Dữ liệu có thể được định nghĩa là một giá trị cơ bản hoặc tập hợp các giá trị, ví dụ tên của sinh viên là dữ liệu.
Đặc điểm
- Tính đúng đắn: Việc triển khai cấu trúc dữ liệu phải triển khai đúng giao diện (Interface) của nó.
- Độ phức tạp về thời gian: Thời gian chạy hoặc thời gian thực thi các thao tác phải càng nhỏ càng tốt.
- Độ phức tạp về không gian: Việc sử dụng bộ nhớ cho việc thao tác với cấu trúc dữ liệu phải càng ít càng tốt.
Các thuật ngữ cơ bản
- Dữ liệu (Data): Dữ liệu là các giá trị hoặc tập hợp các giá trị. Ví dụ tên của sinh viên là dữ liệu.
- Phần tử dữ liệu (Data item): Phần tử dữ liệu liên quan đến một đơn vị giá trị.
- Phần tử nhóm (Group item): Các phần tử dữ liệu được chia thành các phần tử con được gọi là các phần tử nhóm, ví dụ, tên của một sinh viên có thể có họ, tên đệm và tên.
- Phần tử cơ sở (Elementary item): Các phần tử dữ liệu không thể phân chia được gọi là phần tử cơ sở.
- Thuộc tính và thực thể (Attribute và Entity): Thực thể là một thực thể có chứa các thuộc tính mà có thể được gán giá trị.
- Tập hợp các thực thể (Entity Set): Các thực thể có các thuộc tính giống nhau tạo thành một tập thực thể.
- Trường (Field): Trường là một đơn vị thông tin cơ bản đại diện cho một thuộc tính của một thực thể.
- Bản ghi (Record): Bản ghi là một tập hợp các giá trị trường của một thực thể nhất định, ví dụ, nếu chúng ta nói về thực thể sinh viên, thì tên, địa chỉ, khóa học và điểm có thể được nhóm lại với nhau để tạo thành bản ghi cho sinh viên.
- Tệp (File): Tệp là một tập hợp các bản ghi của các thực thể trong một tập hợp thực thể nhất định.
Ưu điểm
- Hiệu quả: Hiệu quả của một chương trình phụ thuộc vào sự lựa chọn cấu trúc dữ liệu. Ví dụ như trong một số bài toán cần phải sử dụng cấu trúc dữ liệu mảng, nhưng ta lại sử dụng danh sách liên kết, điều này sẽ gây tới sự không hiệu quả khi thực hiện chương trình.
- Khả năng tái sử dụng: Cấu trúc dữ liệu có thể sử dụng lại, tức là khi chúng ta đã triển khai một cấu trúc dữ liệu cụ thể, chúng ta có thể sử dụng nó ở bất kỳ nơi nào khác.
- Tính trừu tượng: Cấu trúc dữ liệu cung cấp mức độ trừu tượng. Chương trình sẽ chỉ sử dụng cấu trúc dữ liệu thông qua giao diện mà không đi sâu vào chi tiết triển khai.
Một số thao tác có thể thực hiện
- Duyệt phần tử: Mọi cấu trúc đều chứa tập hợp các phần tử dữ liệu. Thao tác duyệt phần tử cho phép truy cập từng phần tử để thực hiện một số thao tác cụ thể như tìm kiếm hoặc sắp xếp.
- Chèn phần tử: Chèn có thể được định nghĩa là quá trình thêm các phần tử tại bất kỳ vị trí nào.
- Xóa: Ta có thể thực hiện thao tác xóa một phần tử tại bất kỳ vị trí ngẫu nhiên nào.
- Tìm kiếm: Ta có thể thực hiện thao tác tìm kiếm vị trí của một phần tử tại bất kỳ vị trí nào.
- Sắp xếp: Ta có thể thực hiện sắp xếp dữ liệu theo một thứ tự cụ thể trong một cấu trúc nhất định. Có nhiều giải thuật có thể được sử dụng để thực hiện sắp xếp như sắp xếp chèn, sắp xếp lựa chọn, sắp xếp nổi bọt và một số giải thuật khác.
Hy vọng mọi người có thể nắm được cơ bản các đơn vị kiến thức này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!
P/s: Cảm ơn mọi người!
Bài tiếp theo: Cấu trúc dữ liệu mảng và những vấn đề cần biết
