Bảng băm
Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả.[1][2]
Trong phong cách thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là yếu tố quan trọng. Kinh nghiệm trong việc kiến thiết xây dựng những mạng lưới hệ thống lớn cho thấy khó khăn vất vả của việc tiến hành chương trình, chất lượng và hiệu năng của hiệu quả ở đầu cuối phụ thuộc vào rất nhiều vào việc chọn cấu trúc dữ liệu tốt nhất .
Mỗi loại cấu trúc dữ liệu phù hợp với một vài loại ứng dụng khác nhau, một số cấu trúc dữ liệu dành cho những công việc đặc biệt. Ví dụ, các B-tree đặc biệt phù hợp trong việc thiết kế cơ sở dữ liệu. Sau khi cấu trúc dữ liệu được chọn, người ta thường dễ nhận thấy thuật toán cần sử dụng. Đôi khi trình tự công việc diễn ra theo thứ tự ngược lại: cấu trúc dữ liệu được chọn do những bài toán quan trọng nhất định có thuật toán chạy tốt nhất với một số cấu trúc dữ liệu cụ thể. Trong cả hai trường hợp, việc lựa chọn cấu trúc dữ liệu là rất quan trọng.
Thông thường, một cấu trúc dữ liệu được chọn cẩn trọng sẽ được cho phép thực thi thuật toán hiệu suất cao hơn. Việc chọn cấu trúc dữ liệu thường mở màn từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được phong cách thiết kế tốt được cho phép triển khai nhiều phép toán, sử dụng càng ít tài nguyên, thời hạn giải quyết và xử lý và khoảng trống bộ nhớ càng tốt. Các cấu trúc dữ liệu được tiến hành bằng cách sử dụng những kiểu dữ liệu, những tham chiếu và những phép toán trên đó được cung ứng bởi một ngôn từ lập trình .Tri thức đó đã dẫn đến sự nổi lên của nhiều ngôn từ lập trình và chiêu thức phong cách thiết kế được hình thức hóa, mà trong đó, tác nhân tổ chức triển khai quan trọng là những cấu trúc dữ liệu chứ không phải những thuật toán. Đa số ngôn từ có một tính năng thuộc dạng mạng lưới hệ thống module cho phép những cấu trúc dữ liệu được tái sử dụng bảo đảm an toàn trong những ứng dụng khác nhau, bằng cách dùng những giao diện có tinh chỉnh và điều khiển để che những chi tiết cụ thể setup đã được kiểm thử. Đặc biệt, những ngôn từ lập trình hướng đối tượng người dùng như C + + và Java sử dụng lớp ( class ) cho mục tiêu này .
Vì cấu trúc dữ liệu có tính chất quyết định đối với các chương trình chuyên nghiệp nên có rất nhiều hỗ trợ về cấu trúc dữ liệu trong các thư viện chuẩn của các ngôn ngữ lập trình hiện đại, ví dụ thư viện mẫu chuẩn của C++, Java API, và Microsoft .NET Framework.
Các cấu trúc xây dựng căn bản của hầu hết các cấu trúc dữ liệu là mảng (array), bản ghi (record), tổ hợp phân biệt(?) (discriminated union), và tham chiếu (reference). Ví dụ, tham chiếu khả rỗng (có thể có giá trị null) là một kết hợp của tham chiếu và cấu trúc discriminated union, và cấu trúc dữ liệu liên kết đơn giản nhất, danh sách liên kết, được xây dựng từ các bản ghi và các tham chiếu khả rỗng.
Các nguyên tắc cơ bản[sửa|sửa mã nguồn]
Ngôn ngữ tương hỗ[sửa|sửa mã nguồn]
Hầu hết hợp ngữ và những ngôn từ lập trình cấp thấp, ví dụ điển hình BCPL ( Basic Combined Programming Language ), không tương hỗ sẵn cấu trúc dữ liệu. Ngôn ngữ lập trình ở cấp cao và một số ít hợp ngữ ở mức cao có những cú pháp hay tính năng sẵn có tương hỗ những cấu trúc dữ liệu nhất định như là bản ghi và mảng. Ví dụ ngôn từ C và Pascal tương hỗ kiểu cấu trúc và bản ghi bên cạnh tương hỗ mảng một chiều và mảng đa chiều .
Hầu hết những ngôn ngữ lập trình đều có những thư viện có sẵn, hỗ trợ việc xây dựng cấu trúc dữ liệu, chẳng hạn bộ thư viện chuẩn C++, Java Collections Framework và .Net Framework.
