Cấu trúc dữ liệu cơ bản

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu là phương pháp tổ chức và lưu trữ thông tin trong máy tính để đạt hiệu quả cao nhất.

Khi thiết kế các chương trình, việc lựa chọn cấu trúc dữ liệu phù hợp là rất quan trọng. Kinh nghiệm trong phát triển hệ thống lớn cho thấy rằng sự thành công của chương trình, cũng như chất lượng và hiệu suất của kết quả cuối cùng, phụ thuộc rất nhiều vào việc chọn cấu trúc dữ liệu tối ưu.

Mỗi cấu trúc dữ liệu được thiết kế cho những ứng dụng khác nhau; một số được tối ưu hóa cho các nhiệm vụ cụ thể như B-tree cho cơ sở dữ liệu. Đôi khi, lựa chọn cấu trúc dữ liệu dựa trên thuật toán tối ưu cho các bài toán đặc biệt, và ngược lại, thuật toán phù hợp với cấu trúc dữ liệu đã chọn. Việc lựa chọn cấu trúc dữ liệu rất quan trọng.

Tổng quan

Việc chọn cấu trúc dữ liệu phù hợp thường dẫn đến hiệu suất tốt hơn cho thuật toán. Quá trình này bắt đầu từ việc lựa chọn cấu trúc dữ liệu trừu tượng, giúp thực hiện nhiều phép toán với ít tài nguyên hơn. Cấu trúc dữ liệu được xây dựng từ kiểu dữ liệu, tham chiếu và phép toán do ngôn ngữ lập trình cung cấp.

Những hiểu biết về cấu trúc dữ liệu đã dẫn đến sự phát triển của nhiều ngôn ngữ lập trình và phương pháp thiết kế, trong đó cấu trúc dữ liệu đóng vai trò quan trọng hơn thuật toán. Hầu hết các ngôn ngữ hiện nay hỗ trợ tái sử dụng cấu trúc dữ liệu qua các hệ thống module và giao diện, đặc biệt trong các ngôn ngữ hướng đối tượng như C++ và Java.

Vì cấu trúc dữ liệu là yếu tố quyết định trong các chương trình chuyên nghiệp, nên các ngôn ngữ lập trình hiện đại đều cung cấp hỗ trợ qua các thư viện chuẩn như C++, Java API và Microsoft .NET Framework.

Các cấu trúc dữ liệu cơ bản thường gặp bao gồm mảng, bản ghi, tổ hợp phân biệt và tham chiếu. Chẳng hạn, tham chiếu có giá trị null là sự kết hợp của tham chiếu và tổ hợp phân biệt, trong khi danh sách liên kết, một cấu trúc dữ liệu liên kết đơn giản, được tạo thành từ bản ghi và tham chiếu có thể null.

Các nguyên tắc cơ bản

Ngôn ngữ hỗ trợ

Nhiều hợp ngữ và ngôn ngữ lập trình cấp thấp như BCPL không hỗ trợ cấu trúc dữ liệu sẵn có. Tuy nhiên, ngôn ngữ lập trình cấp cao và một số hợp ngữ mức cao cung cấp cú pháp hoặc chức năng hỗ trợ các cấu trúc dữ liệu như bản ghi và mảng. Ví dụ, ngôn ngữ C và Pascal cung cấp hỗ trợ cho kiểu cấu trúc và bản ghi cùng với mảng một chiều và đa chiều.

Hầu hết các ngôn ngữ lập trình đều có thư viện hỗ trợ việc xây dựng cấu trúc dữ liệu, như bộ thư viện chuẩn C++, Java Collections Framework và .Net Framework.

Các cấu trúc dữ liệu phổ biến

- Mảng (array list) - Ngăn xếp (stack) - Hàng đợi (queue) - Bảng băm (hash table) - Danh sách liên kết (linked list) - Cây (tree) - Đồ thị (graph)

- Các cấu trúc dữ liệu - Mô hình dữ liệu - Danh sách liên kết

Đọc thêm

- Peter Brass, Advanced Data Structures, Cambridge University Press, 2008. - Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3rd edition, 1997. - Dinesh Mehta và Sartaj Sahni, Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2007. - Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985.

Liên kết tham khảo

- Khóa học video về cấu trúc dữ liệu của UC Berkeley - Mô tả từ Từ điển Cấu trúc và Thuật toán Dữ liệu - CSE.unr.edu - Khóa học cấu trúc dữ liệu với hình ảnh động - Hướng dẫn cấu trúc dữ liệu với hình ảnh động Lưu trữ 2012-06-18 tại Wayback Machine - Xem xét cấu trúc dữ liệu từ góc độ .NET - Schaffer, C. Phân tích Cấu trúc Dữ liệu và Thuật toán