Giới thiệu cấu trúc dữ liệu

Kiến thức cần biết:

Đã biết ít nhất một ngôn ngữ lập trình (nếu là C hoặc các ngôn ngữ có gốc là C càng tốt)
Đã làm việc với mảng hoặc các cấu trúc dữ liệu khác như: List/ArrayList, Vector, Set, ...

Khái niệm cấu trúc dữ liệu (Data Structure)

Như chúng ta đã biết, từ khi máy tính và phần mềm máy tính ra đời là kéo theo sự xuất hiện của việc lưu trữ dữ liệu thông qua các hệ thống lưu trữ dữ liệu trong các file.

Hiểu theo cách rộng rãi trong doanh nghiệp thì cấu trúc dữ liệu là cách thức tổ chức dữ liệu trên máy vi tính để có thể sử dụng hiệu quả. Hầu như tất cả các ứng dụng doanh nghiệp đều sử dụng một cấu trúc dữ liệu theo những cách khác nhau.

Trong ngành 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ả. Cụ thể, đó là một cách sắp xếp dữ liệu trên máy tính để nó có thể được truy cập và cập nhật một cách hiệu quả.

Tùy thuộc vào yêu cầu và dự án của bạn, điều quan trọng là chọn cấu trúc dữ liệu phù hợp cho dự án của bạn. Ví dụ, nếu bạn muốn lưu trữ dữ liệu tuần tự trong bộ nhớ, thì bạn có thể sử dụng cấu trúc dữ liệu mảng.

Ngày nay, các cấu trúc dữ liệu được sử dụng rộng rãi trong hầu hết mọi chương trình hay phần mềm đã được phát triển. Hơn nữa, các cấu trúc dữ liệu đều tuân theo các nguyên tắc cơ bản của Khoa học máy tính và Kỹ thuật phần mềm. Nó cũng là một chủ đề quan trọng trong các câu hỏi phỏng vấn ở ngành Kỹ thuật phần mềm. Do đó, là một lập trình viên, chúng ta cần phải có kiến thức tốt về các cấu trúc dữ liệu.

Những đặc trưng của một cấu trúc dữ liệu

Sự chính xác – Cấu trúc dữ liệu thực thi trên một Kiểu dữ liệu trừu tượng đã được khẳng định.
Sự phức tạp thời gian – Thời gian chạy hay thời gian thực thi của một thao tác trên cấu trúc dữ liểu phải nhỏ và có thể thực hiện được.
Sự phức tạp khoảng trống bộ nhớ – Bộ nhớ được sử dụng của cấu trúc dữ liệu và các thao tác trên nó phải nhỏ và khả thi.

Sự cần thiết của cấu trúc dữ liệu

Kiến thức về cấu trúc dữ liệu giúp bạn hiểu hoạt động của từng cấu trúc dữ liệu. Dựa vào đó bạn có thể chọn cấu trúc dữ liệu phù hợp cho dự án của mình. Điều này giúp bạn viết mã lệnh liên quan đến bộ nhớ và thời gian hiệu quả hơn.

Các ứng dụng cần khai khác sự phức tạp và dữ liệu phong phú, sau đây có 3 vấn đề mà ứng dụng phải đối mặt hàng ngày:

Tìm kiếm dữ liệu: Cân nhắc một kho hàng lưu trữ 1 triệu mặt hàng. Nếu mỗi lần tìm kiếm một mặt hàng ứng dụng sẽ phải tìm kiếm trên 1 triệu mặt hàng do đó thời gian tìm kiếm sẽ chậm. Khi dữ liệu lớn lên quá trình tìm kiểm sẽ chậm hơn.
Tốc độ bộ vi xử lý: Tốc độ bộ vi xử lý mặc dù rất cao nhưng vẫn rơi vào giới hạn nếu dữ liệu lên đến hàng tỷ bản ghi.
Nhiều yêu cầu: Hàng nghìn người dùng cùng tìm kiếm dữ liệu đồng thời trên máy chủ web, mặc dù máy chủ nhanh thì vẫn lỗi trong khi tìm kiếm dữ liệu.

Để giải quyết những vấn đề trên thì cần phải sử dụng cấu trúc dữ liệu phù hợp. Dữ liệu có thể tổ chức trong một cấu trúc dữ liệu có thể theo cách không phải tất cả dữ liệu đều có thể tìm kiếm và dữ liệu có thể tìm kiếm được thì có ngay lập tức.

Thời gian thao tác với cấu trúc dữ liệu

Có 3 trường hợp thường xảy ra khi so sánh sự khác nhau về thời gian thực thi các thao tác trên cấu trúc dữ liệu có liên quan:

Trường hợp tồi nhất: Đây là trường hợp đặc biệt khi thao tác trên cấu trúc dữ liệu với thời gian nhiều nhất để thực hiện thao tác này. Nếu một thao tác trong trường hợp tồi nhất là ƒ(n) thì thao tác này sẽ không nhiều hơn ƒ(n) thời gian (ở đây ƒ(n) biểu diễn hàm của n).
Trường hợp trung bình: Đây là trường hợp mô tả thời gian trung bình thể thao tác trên cấu trúc dữ liệu. Nếu một thao tác mất ƒ(n) thời gian thực thi thì m thao tác sẽ mất m*ƒ(n) thời gian.
Trường hợp tốt nhất: Đây là trường hợp mô tả thời gian thực thi tối thiểu để thao tác trên cấu trúc dữ liệu. Nếu một thao tác mất ƒ(n) thời gian thực thi, thì thao tác thực tế có thể mất thời gian là một số ngẫu nhiên với giá trị lớn nhất là ƒ(n).

Các thuật ngữ cơ bản

Dữ liệu (Data) − Dữ liệu là giá trị hoặc tập các giá trị.
Mục dữ liệu (Data Item) − Mục dữ liệu chứa một giá trị đơn.
Mục nhóm (Group Items) − Mục dữ liệu được chia ra thành các mục con được gọi là Mục nhóm.
Mục cơ bản (Elementary Items) − Mục dữ liệu không thể được chia nhỏ hơn nữa thì được gọi là Mục cơ bản.
Thuộc tính (Attribute/Property) và Thực thể (Entity) − Một thực thể sẽ chứa các thuộc tính, các thuộc tính này có thể gán được giá trị.
Tập thực thể (Entity Set) − Các thực thể có chung các thuộc tính được gọi là tập thực thể.
Trường (Field) − Trường là một khối 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 (Record) − Bản ghi là một tập hợp các trường giá trị của một thực thể xác định.
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 thực thể xác định.

Các loại cấu trúc dữ liệu

Về cơ bản, cấu trúc dữ liệu được chia thành hai loại:

Cấu trúc dữ liệu tuyến tính: Trong cấu trúc dữ liệu tuyến tính, các phần tử được sắp xếp theo thứ tự lần lượt. Vì các phần tử được sắp xếp theo thứ tự cụ thể nên chúng rất dễ thực hiện. Tuy nhiên, khi độ phức tạp của chương trình tăng lên, cấu trúc dữ liệu tuyến tính có thể không phải là lựa chọn tốt nhất vì sự phức tạp trong hoạt động. Các cấu trúc dữ liệu tuyến tính phổ biến như sau:
- Cấu trúc dữ liệu Mảng
- Cấu trúc dữ liệu Ngăn xếp (stack)
- Cấu trúc dữ liệu Hàng đợi (queue)
Cấu trúc dữ liệu phi tuyến tính: Không giống như cấu trúc dữ liệu tuyến tính, các phần tử trong cấu trúc dữ liệu phi tuyến tính không nằm trong bất kỳ trình tự nào. Thay vào đó, chúng được sắp xếp theo thứ bậc trong đó một phần tử sẽ được kết nối với một hoặc nhiều phần tử. Cấu trúc dữ liệu phi tuyến tính được chia thành các cấu trúc dữ liệu dựa trên đồ thị và cây. Các cấu trúc dữ liệu phi tuyến tính phổ biến như sau:
- Cấu trúc dữ liệu cây
- Cấu trúc dữ liệu đồ thị

Sự khác nhau giữa cấu trúc dữ liệu tuyến tính và phi tuyến tính

Cấu trúc dữ liệu tuyến tính	Cấu trúc dữ liệu phí tuyến tính
Các phần tử dữ liệu được sắp xếp theo thứ tự tuần tự, nối tiếp nhau.	Các phần tử dữ liệu được sắp xếp theo thứ tự không tuần tự (theo cách phân cấp).
Tất cả các phần tử đều biểu diễn trên một tầng.	Các phần tử dữ liệu được biểu diễn trên các tầng khác nhau.
Cấu trúc dữ liệu này có thể được duyệt qua trong một lần chạy. Có nghĩa là, nếu chúng ta bắt đầu từ phần tử đầu tiên, chúng ta có thể duyệt qua tất cả các phần tử một cách tuần tự trong một lần chuyển.	Cấu trúc dữ liệu này yêu cầu nhiều lần chạy. Có nghĩa là, nếu chúng ta bắt đầu từ phần tử đầu tiên thì có thể không thể duyệt qua tất cả các phần tử trong một lần chuyển.
Việc sử dụng bộ nhớ không hiệu quả.	Các cấu trúc khác nhau sử dụng bộ nhớ theo những cách hiệu quả khác nhau tùy thuộc vào nhu cầu.
Độ phức tạp về thời gian tăng theo kích thước dữ liệu.	Độ phức tạp về thời gian vẫn như lúc trước khi tăng kích thước dữ liệu.

Giới thiệu Kiểu dữ liệu trừu tượng (ADT)

Trong khoa học máy tính, một kiểu dữ liệu trừu tượng (ADT-Abatract Data Type) là một mô hình toán học cho các kiểu dữ liệu. Một kiểu dữ liệu trừu tượng được xác định theo hành vi của nó (ngữ nghĩa) từ quan điểm của người dùng, của dữ liệu, cụ thể về giá trị có thể có, các hoạt động có thể có trên dữ liệu thuộc loại này và hành vi của các hoạt động này. Mô hình toán học này tương phản với cấu trúc dữ liệu, là những đại diện cụ thể của dữ liệu và là quan điểm của người triển khai, không phải người dùng.

Về mặt hình thức, ADT có thể được định nghĩa là một "lớp đối tượng có hành vi logic được xác định bởi một tập hợp các giá trị và một tập hợp các phép toán"; điều này tương tự như một cấu trúc đại số trong toán học. Ý nghĩa của "hành vi" khác nhau tùy theo tác giả, với hai loại đặc tả chính thức cho hành vi là đặc tả tiên đề (đại số) và mô hình trừu tượng; chúng tương ứng với ngữ nghĩa tiên đề và ngữ nghĩa hoạt động của một máy trừu tượng. Một số tác giả cũng bao gồm độ phức tạp tính toán ("chi phí"), cả về thời gian (cho các hoạt động tính toán) và không gian (để biểu diễn các giá trị). Trong thực tế, nhiều kiểu dữ liệu phổ biến không phải là ADT, vì tính trừu tượng không hoàn hảo và người dùng phải nhận thức được các vấn đề như tràn số học do biểu diễn. Ví dụ: các số nguyên thường được lưu trữ dưới dạng các giá trị có độ rộng cố định (số nhị phân 32 bit hoặc 64 bit) và do đó gặp phải hiện tượng tràn số nguyên nếu giá trị lớn nhất bị vượt quá.

ADT là một khái niệm lý thuyết, trong khoa học máy tính, được sử dụng trong thiết kế và phân tích các thuật toán, cấu trúc dữ liệu và hệ thống phần mềm, và không tương ứng với các tính năng cụ thể của ngôn ngữ máy tính — các ngôn ngữ máy tính chính thống không hỗ trợ trực tiếp các ADT được chỉ định chính thức. Tuy nhiên, các đặc điểm ngôn ngữ khác nhau tương ứng với các khía cạnh nhất định của ADT và dễ bị nhầm lẫn với ADT thích hợp; chúng bao gồm các kiểu trừu tượng, kiểu dữ liệu không rõ ràng, giao thức và thiết kế theo ràng buộc. ADT lần đầu tiên được đề xuất bởi Barbara Liskov và Stephen N. Zilles vào năm 1974, như một phần của sự phát triển của ngôn ngữ CLU.

Kiểu dữ liệu trừu tượng là các thực thể lý thuyết thuần túy, được sử dụng (trong số những thứ khác) để đơn giản hóa việc mô tả các thuật toán trừu tượng, để phân loại và đánh giá cấu trúc dữ liệu, và để mô tả chính thức kiểu hệ thống của ngôn ngữ lập trình. Tuy nhiên, một ADT có thể được thực hiện bởi các kiểu dữ liệu hoặc cấu trúc dữ liệu cụ thể, theo nhiều cách và trong nhiều ngôn ngữ lập trình; hoặc được mô tả bằng ngôn ngữ đặc tả chính thức. ADT thường được thực hiện dưới dạng mô-đun: giao diện của mô-đun khai báo các thủ tục tương ứng với các hoạt động ADT, đôi khi có các chú thích mô tả các ràng buộc. Chiến lược che giấu thông tin này cho phép thay đổi việc triển khai mô-đun mà không làm ảnh hưởng đến các chương trình khách.

Thuật ngữ kiểu dữ liệu trừu tượng cũng có thể được coi là một cách tiếp cận tổng quát của một số cấu trúc đại số, chẳng hạn như mạng, nhóm và vòng. Khái niệm về kiểu dữ liệu trừu tượng có liên quan đến khái niệm trừu tượng hóa dữ liệu, quan trọng trong lập trình hướng đối tượng và thiết kế theo phương pháp hợp đồng để phát triển phần mềm.

Định nghĩa của ADT chỉ đề cập đến những thao tác nào sẽ được thực hiện chứ không đề cập đến cách những hoạt động này sẽ được thực hiện. Nó không chỉ định cách dữ liệu sẽ được tổ chức trong bộ nhớ và những thuật toán nào sẽ được sử dụng để thực hiện các hoạt động. Nó được gọi là "trừu tượng" vì nó cung cấp một chế độ xem độc lập với việc triển khai. Quá trình chỉ cung cấp các yếu tố cần thiết và ẩn các chi tiết được gọi là trừu tượng hóa.

Sử dụng kiểu dữ liệu không cần biết kiểu dữ liệu đó được triển khai như thế nào, ví dụ: chúng ta đang sử dụng các giá trị Nguyên thủy như kiểu dữ liệu int, float, char chỉ với kiến thức rằng kiểu dữ liệu này có thể hoạt động và được thực hiện mà không cần bất kỳ giá trị nào. ý tưởng về cách chúng được thực hiện. Vì vậy, người dùng chỉ cần biết kiểu dữ liệu có thể làm gì chứ không cần biết nó sẽ được triển khai như thế nào. Hãy coi ADT như một hộp đen ẩn cấu trúc và thiết kế bên trong của kiểu dữ liệu.

Giới thiệu kiểu dữ liệu trừu tượng Danh sách

(List Abstract Data Type)

Trong khoa học máy tính, danh sách hoặc chuỗi là một kiểu dữ liệu trừu tượng đại diện cho một số lượng có thể đếm được của các giá trị theo thứ tự, trong đó cùng một giá trị có thể xuất hiện nhiều lần. Một thể hiện của danh sách là một biểu diễn trên máy tính của khái niệm toán học về một dãy hoặc dãy hữu hạn; tương tự vô hạn (có khả năng) của một danh sách là một dòng. Danh sách là một ví dụ cơ bản về vùng chứa, vì chúng chứa các giá trị khác. Nếu cùng một giá trị xuất hiện nhiều lần, mỗi lần xuất hiện được coi là một phần tử riêng biệt.

Tên của danh sách cũng được sử dụng cho một số cấu trúc dữ liệu cụ thể có thể được sử dụng để triển khai kiểu dữ liệu trừu tượng danh sách, đặc biệt là danh sách liên kết và mảng. Trong một số ngữ cảnh, chẳng hạn như trong lập trình Lisp, danh sách thuật ngữ có thể đề cập cụ thể đến một danh sách được liên kết hơn là một mảng. Trong lập trình dựa vào lớp (hay lập trình hướng đối tượng - OOP), danh sách thường được cung cấp dưới dạng các thể hiện của lớp con của một lớp "danh sách" chung và được duyệt qua các vòng lặp riêng biệt.

Nhiều ngôn ngữ lập trình cung cấp hỗ trợ cho các kiểu dữ liệu danh sách và có cú pháp và ngữ nghĩa đặc biệt cho danh sách và các thao tác với danh sách. Một danh sách thường có thể được tạo bằng cách viết các mục theo trình tự, được phân tách bằng dấu phẩy, dấu chấm phẩy và / hoặc dấu cách, trong một cặp dấu phân cách như dấu ngoặc đơn '()', dấu ngoặc nhọn '[]', dấu ngoặc nhọn '{}' hoặc dấu ngoặc nhọn '<>'. Một số ngôn ngữ có thể cho phép các kiểu danh sách được lập chỉ mục hoặc cắt lát giống như kiểu mảng, trong trường hợp đó, kiểu dữ liệu được mô tả chính xác hơn dưới dạng mảng.

Trong lý thuyết kiểu và lập trình hàm, danh sách trừu tượng thường được định nghĩa một cách quy nạp bằng hai phép toán: nil/null tạo ra danh sách trống hoặc rỗng, thêm một phẩn tử ở đầu danh sách.

Các đặc trưng của Cấu trúc dữ liệu Danh sách

Kiểu dữ liệu trừu tượng Danh sách là một tập hợp các phần tử đồng nhất được sắp xếp theo thứ tự động như sau:
- A₀, A₁, A₂,…, A_N-1
- Trong đó: A_i là phần tử thứ i của danh sách
Vị trí của A_i là i; các vị trí từ 0 đến N-1 (các ngôn ngữ lập trình C hay bắt nguồn từ C đều có vị trí bắt đầu từ 0)
Kích thước của danh sách là N (danh sách không có phần tử nào được gọi là “danh sách trống”)

Các thao tác cơ bản của cấu trúc dữ liệu Danh sách

Việc triển khai cấu trúc dữ liệu danh sách có thể cung cấp một số hoạt động sau:

Một hàm tạo để khởi tạo một danh sách rỗng
Một thao tác để kiểm tra xem danh sách có rỗng hay không
Một thao tác để thêm một phần tử vào danh sách
Một thao tác để truy cập phần tử tại một vị trí nhất định.
Một thao tác để xóa một phần tử của danh sách
Một thao tác để xác định phần tử đầu tiên (hoặc "phần đầu") của danh sách
Một thao tác để tham chiếu đến danh sách bao gồm tất cả các phần tử còn lại của danh sách ngoại trừ phần đầu của nó (đây được gọi là "đuôi" của danh sách)

Triển khai Cấu trúc dữ liệu danh sách

Danh sách thường được triển khai dưới dạng danh sách liên kết (liên kết đơn lẻ hoặc kép) hoặc dưới dạng mảng, thường có độ dài thay đổi hoặc mảng động.

Cách chuẩn để triển khai danh sách, bắt nguồn từ ngôn ngữ lập trình Lisp, là mỗi phần tử của danh sách chứa cả giá trị của nó và một con trỏ chỉ ra vị trí của phần tử tiếp theo trong danh sách. Điều này dẫn đến một danh sách được liên kết hoặc một cây, tùy thuộc vào việc danh sách có các danh sách con lồng nhau hay không. Một số triển khai Lisp cũ hơn (chẳng hạn như triển khai Lisp của Symbolics 3600) cũng hỗ trợ "danh sách nén" (sử dụng mã hóa CDR) có một biểu diễn nội bộ đặc biệt (ẩn đối với người dùng). Danh sách có thể được điều khiển bằng cách sử dụng lặp lại hoặc đệ quy.

Danh sách có thể được triển khai dưới dạng cây tìm kiếm nhị phân tự cân bằng chứa các cặp giá trị-chỉ mục, cung cấp quyền truy cập theo thời gian như nhau vào bất kỳ phần tử nào (ví dụ: tất cả nằm ở rìa và các nút bên trong lưu trữ chỉ mục bên phải của con, được sử dụng để hướng dẫn tìm kiếm)

Các cách triển khai câu trúc dữ liệu danh sách thường gặp:

Mảng (Array)
Danh sách liên kết (Linked List)
Danh sách (List / ArrayList / Vector)
Ngăn xếp (Stack)
Hàng đợi (Queue)

Tùy thuộc từng ngôn ngữ lập trình, các cách triển cấu trúc dữ liệu có được tích hợp sẵn vào trong ngôn ngữ lập trình hay dưới dạng thư viện hay có thể Lập trình viên tự phải triển khai cấu trúc dữ liệu Danh sách. Trong đó cấu trúc dữ liệu Mảng (Array) thì ngôn ngữ lập trình nào cũng hỗ trợ.