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 thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Kinh nghiệm trong việc xây dựng các hệ thống lớn cho thấy khó khăn của việc triển khai chương trình, chất lượng và hiệu năng 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ố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 thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu 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 thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình. Tri thức đó đã dẫn đến sự nổi lên của nhiều ngôn ngữ lập trình và phương pháp thiết kế được hình thức hóa, mà trong đó, nhân tố tổ chức quan trọng là các cấu trúc dữ liệu chứ không phải các thuật toán. Đa số ngôn ngữ có một tính năng thuộc dạng hệ thống module cho phép các cấu trúc dữ liệu được tái sử dụng an toàn trong các ứng dụng khác nhau, bằng cách dùng các giao diện có điều khiển để che các chi tiết cài đặt đã được kiểm thử. Đặc biệt, các ngôn ngữ lập trình hướng đối tượng như C++ và Java sử dụng lớp (class) cho mục đích 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. Hầu hết hợp ngữ và những ngôn ngữ lập trình cấp thấp, chẳng hạn BCPL (Basic Combined Programming Language), không hỗ trợ sẵn cấu trúc dữ liệu. Ngôn ngữ lập trình ở cấp cao và một số hợp ngữ ở mức cao có những cú pháp hay chức năng sẵn có hỗ trợ những cấu trúc dữ liệu nhất định như là bản ghi và mảng. Ví dụ ngôn ngữ C và Pascal hỗ trợ kiểu cấu trúc và bản ghi bên cạnh hỗ trợ 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.
Cấu trúc dữ liệu (Data Structure) là gì ?Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sửdụng một cách hiệu quả.Dưới đây là hai khái niệm nền tảng hình thành nên một cấu trúc dữ liệu: Interface: Mỗi cấu trúc dữ liệu có một Interface. Interface biểu diễn một tập hợpcác phép tính mà một cấu trúc dữ liệu hỗ trợ. Một Interface chỉ cung cấp danhsách các phép tính được hỗ trợ, các loại tham số mà chúng có thể chấp nhận vàkiểu trả về của các phép tính này. Implementation (có thể hiểu là sự triển khai): Cung cấp sự biểu diễn nội bộ củamột cấu trúc dữ liệu. Implementation cũng cung cấp phần định nghĩa của giảithuật được sử dụng trong các phép tính của cấu trúc dữ liệu. Đặc điểm của một Cấu trúc dữ liệu Chính xác: Sự triển khai của Cấu trúc dữ liệu nên triển khai Interface của nó mộtcách chính xác. Độ phức tạp về thời gian (Time Complexity): Thời gian chạy hoặc thời gianthực thi của các phép tính của cấu trúc dữ liệu phải là nhỏ nhất có thể. Độ phức tạp về bộ nhớ (Space Complexity): Sự sử dụng bộ nhớ của mỗi phéptính của cấu trúc dữ liệu nên là nhỏ nhất có thể.Tại sao Cấu trúc dữ liệu là cần thiết ?Ngày nay, các ứng dụng ngày càng phức tạp và lượng dữ liệu ngày càng lớn vớinhiều kiểu đa dạng. Việc này làm xuất hiện 3 vấn đề lớn mà mỗi lập trình viên phải đốimặt: Tìm kiếm dữ liệu: Giả sử có 1 triệu hàng hóa được lưu giữ vào trong kho hànghóa. Và giả sử có một ứng dụng cần để tìm kiếm một hàng hóa. Thì mỗi khi thựchiện tìm kiếm, ứng dụng này sẽ phải tìm kiếm 1 hàng hóa trong 1 triệu hàng hóa.Khi dữ liệu tăng lên thì việc tìm kiếm sẽ càng trở lên chậm và tốn kém hơn. Tốc độ bộ vi xử lý: Mặc dù bộ vi xử lý có tốc độ rất cao, tuy nhiên nó cũng cógiới hạn và khi lượng dữ liệu lên tới hàng tỉ bản ghi thì tốc độ xử lý cũng sẽ khôngcòn được nhanh nữa. Đa yêu cầu: Khi hàng nghìn người dùng cùng thực hiện một phép tính tìm kiếmtrên một Web Server thì cho dù Web Server đó có nhanh đến mấy thì việc phải xửlý hàng nghìn phép tính cùng một lúc là thực sự rất khó.Để xử lý các vấn đề trên, các cấu trúc dữ liệu là một giải pháp tuyệt vời. Dữ liệu cóthể được tổ chức trong cấu trúc dữ liệu theo một cách để khi thực hiện tìm kiếm một phầntử nào đó thì dữ liệu yêu cầu sẽ được tìm thấy ngay lập tức.Độ phức tạp thời gian thực thi trong cấu trúc dữ liệu và giải thuậtCó 3 trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khácnhau:•Trường hợp xấu nhất (Worst Case): là tình huống mà một phép tính của cấu trúc dữ liệu nào đótốn thời gian tối đa (thời gian dài nhất). Ví dụ với ba số 1, 2, 3 thì nếu sắp xếp theo thứ tựgiảm dần thì thời gian thực thi sẽ là dài nhất (và đây là trường hợp xấu nhất); còn nếu sắpxếp theo thứ tự tăng dần thì thời gian thực thi sẽ là ngắn nhất (và đây là trường hợp tốt nhất).•Trường hợp trung bình (Average Case): miêu tả thời gian thực thi trung bình một phép tính củamột cấu trúc dữ liệu.•Trường hợp tốt nhất (Best Case): là tình huống mà thời gian thực thi một phép tính của một cấutrúc dữ liệu là ít nhất. Ví dụ như trên.Thuật ngữ cơ bản trong Cấu trúc dữ liệu•Dữ liệu: Dữ liệu là các giá trị hoặc là tập hợp các giá trị.•Phần tử dữ liệu: Phần tử dữ liệu là một đơn vị đơn lẻ của giá trị.•Các phần tử nhóm: Phần tử dữ liệu mà được chia thành các phần tử con thì được gọi là các phầntử nhóm.•Các phần tử cơ bản: Phần tử dữ liệu mà không thể bị chia nhỏ thành các phần tử con thì gọi làcác phần tử cơ bản.•Thuộc tính và Thực thể: Một thực thể là cái mà chứa một vài thuộc tính nào đó, và các thuộctính này có thể được gán các giá trị.•Tập hợp thực thể: Các thực thể mà có các thuộc tính tương tự nhau thì cấu thành một tập hợpthực thể.•Trường: Trường là một đơn vị thông tin cơ bản biểu diễn một thuộc tính của một thực thể.•Bản ghi: Bản ghi là một tập hợp các giá trị trường của một thực thể đã cho.•File: 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ể đã cho. |
