Chương 4: Tìm Hiểu Các Cấu Trúc Dữ Liệu Cơ Bản và Nâng Cao

Chuyên khảo phân tích Chuong 4 các cấu trúc dữ liệu, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo., phục vụ nghiên cứu và ứng dụng thực tiễn

• Tác giả: Nguyen Tri Tuan
• Trường học: Đại Học Khoa Học Tự Nhiên
• Chuyên ngành: Cấu Trúc Dữ Liệu
• Đề tài: Cấu Trúc Dữ Liệu Cơ Bản và Nâng Cao
• Loại tài liệu: bài giảng
• Năm xuất bản: 2013
• Địa điểm: Tp.HCM

Mục lục chi tiết

• 1. Các cấu trúc dữ liệu cơ bản
• 1.1. Các danh sách liên kết – Linked Lists
• 1.2. Ngăn xếp – Stack
• 1.3. Hàng đợi - Queue
• 2. Cây nhị phân – Binary Trees
• 3. Các cấu trúc dữ liệu nâng cao

Tóm tắt

I. Tổng quan về Cấu Trúc Dữ Liệu Cơ Bản và Nâng Cao

Cấu trúc dữ liệu là một phần quan trọng trong lập trình và phát triển phần mềm. Nó giúp tổ chức và quản lý dữ liệu một cách hiệu quả. Việc hiểu rõ về các cấu trúc dữ liệu cơ bản và nâng cao sẽ giúp lập trình viên tối ưu hóa hiệu suất của ứng dụng. Bài viết này sẽ cung cấp cái nhìn tổng quan về các loại cấu trúc dữ liệu phổ biến và ứng dụng của chúng trong thực tế.

1.1. Các loại Cấu Trúc Dữ Liệu Cơ Bản

Các cấu trúc dữ liệu cơ bản bao gồm mảng, danh sách liên kết, ngăn xếp và hàng đợi. Mỗi loại có những đặc điểm và ứng dụng riêng, giúp giải quyết các bài toán khác nhau trong lập trình.

1.2. Tại sao Cấu Trúc Dữ Liệu Quan Trọng

Cấu trúc dữ liệu giúp tối ưu hóa việc lưu trữ và truy xuất dữ liệu. Việc lựa chọn đúng cấu trúc dữ liệu có thể giảm thiểu thời gian xử lý và tăng hiệu suất của ứng dụng.

II. Vấn đề và Thách thức trong Cấu Trúc Dữ Liệu

Mặc dù có nhiều cấu trúc dữ liệu khác nhau, nhưng việc lựa chọn và triển khai chúng không phải lúc nào cũng dễ dàng. Các lập trình viên thường gặp phải những thách thức như hiệu suất, khả năng mở rộng và tính linh hoạt của cấu trúc dữ liệu.

2.1. Thách thức về Hiệu Suất

Một số cấu trúc dữ liệu có thể hoạt động kém trong các tình huống cụ thể, dẫn đến thời gian xử lý lâu hơn. Việc hiểu rõ về độ phức tạp thời gian của từng loại là rất quan trọng.

2.2. Khả Năng Mở Rộng và Tính Linh Hoạt

Khi dữ liệu tăng lên, một số cấu trúc dữ liệu có thể không còn phù hợp. Lập trình viên cần cân nhắc khả năng mở rộng và tính linh hoạt của cấu trúc dữ liệu khi thiết kế hệ thống.

III. Phương Pháp Cài Đặt Cấu Trúc Dữ Liệu Cơ Bản

Các cấu trúc dữ liệu cơ bản như danh sách liên kết, ngăn xếp và hàng đợi có thể được cài đặt bằng nhiều phương pháp khác nhau. Việc hiểu rõ cách cài đặt sẽ giúp lập trình viên tối ưu hóa hiệu suất và khả năng bảo trì của mã nguồn.

3.1. Cài Đặt Danh Sách Liên Kết

Danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản nhất. Nó cho phép thêm và xóa phần tử một cách linh hoạt mà không cần di chuyển các phần tử khác.

3.2. Cài Đặt Ngăn Xếp và Hàng Đợi

Ngăn xếp và hàng đợi là hai cấu trúc dữ liệu quan trọng trong lập trình. Ngăn xếp hoạt động theo nguyên tắc LIFO, trong khi hàng đợi hoạt động theo FIFO. Việc cài đặt chúng có thể được thực hiện bằng mảng hoặc danh sách liên kết.

IV. Ứng Dụng Thực Tiễn của Cấu Trúc Dữ Liệu

Các cấu trúc dữ liệu không chỉ là lý thuyết mà còn có nhiều ứng dụng thực tiễn trong lập trình. Chúng được sử dụng trong các thuật toán tìm kiếm, sắp xếp và quản lý dữ liệu.

4.1. Ứng Dụng trong Thuật Toán Tìm Kiếm

Các cấu trúc dữ liệu như cây nhị phân tìm kiếm giúp tối ưu hóa quá trình tìm kiếm dữ liệu. Chúng cho phép tìm kiếm nhanh chóng và hiệu quả hơn so với các phương pháp khác.

4.2. Ứng Dụng trong Quản Lý Dữ Liệu

Trong các hệ thống quản lý cơ sở dữ liệu, cấu trúc dữ liệu được sử dụng để tổ chức và truy xuất dữ liệu một cách hiệu quả. Điều này giúp cải thiện hiệu suất của hệ thống.

V. Kết Luận và Tương Lai của Cấu Trúc Dữ Liệu

Cấu trúc dữ liệu là một lĩnh vực không ngừng phát triển. Việc nắm vững các cấu trúc dữ liệu cơ bản và nâng cao sẽ giúp lập trình viên đáp ứng tốt hơn các yêu cầu của công nghệ hiện đại.

5.1. Xu Hướng Phát Triển Cấu Trúc Dữ Liệu

Với sự phát triển của công nghệ, các cấu trúc dữ liệu mới đang được nghiên cứu và phát triển. Điều này mở ra nhiều cơ hội cho lập trình viên trong việc tối ưu hóa ứng dụng.

5.2. Tương Lai của Cấu Trúc Dữ Liệu trong Lập Trình

Cấu trúc dữ liệu sẽ tiếp tục đóng vai trò quan trọng trong lập trình. Việc hiểu rõ và áp dụng đúng các cấu trúc dữ liệu sẽ giúp lập trình viên phát triển các ứng dụng hiệu quả hơn.

Trích đoạn nội dung tài liệu

Đặt vấn đề (5)  Thao tác thêm phần tử chỉ cần thay đổi các mối liên kết tại chỗ 10 20 30 … … 18  Chi phí O(1) 09/2013 9 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết là gì ? (1)  Hãy viết ra các đặc điểm của DSLK  Ít nhất 5 đặc điểm 09/2013 10 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết là gì ? (2)  Đặc điểm của DSLK  Sử dụng con trỏ (pointer)  Cấp phát bộ nhớ động  Dãy tuần tự các node  Giữa hai node có 1 hay nhiều con trỏ liên kết  Các node không cần phải lưu trữ liên tiếp nhau trong bộ nhớ  Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)  Thao tác Thêm/Xóa không cần phải dịch chuyển phần tử 09/2013 11 (C) Nguyen Tri Tuan - DH.HCM So sánh Mảng và Danh sách liên kết Mảng Danh sách liên kết Kích thước cố định Số phần tử thay đổi tùy ý Các phần tử lưu trữ tuần tự Các phần tử lưu trữ rời rạc, (địa chỉ tăng dần) trong bộ liên kết với nhau bằng con trỏ nhớ Phải tịnh tiến các phần tử khi Chỉ cần thay đổi con trỏ liên muốn Thêm/Xóa 1 phần tử - kết khi muốn Thêm/Xóa 1 chi phí O(n) phần tử - chi phí O(1) Truy xuất ngẫu nhiên (nhanh) Truy xuất tuần tự (chậm) Sử dụng ít bộ nhớ hơn Sử dụng nhiều bộ nhớ hơn 09/2013 12 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (1)  Đặc điểm:  Mỗi node chỉ có 1 con trỏ liên kết (đến node kế tiếp trong danh sách) 09/2013 13 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (2)  Các thao tác cơ bản  Khởi tạo danh sách  Xóa danh sách  Kiểm tra danh sách rỗng  Đếm số phần tử trong danh sách  Thêm node  Xóa node  Tìm một node  Lấy thông tin một node 09/2013 14 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (3) Minh họa thao tác thêm node Minh họa thao tác xóa node 09/2013 15 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đơn (4) template <class T> class LINKED_LIST { private: struct ListNode { T data; // data of node ListNode *next; // pointer to next node }; int size; // number of node in list ListNode *head; // pointer to 1st node in list public: LINKED_LIST(); // default constructor LINKED_LIST(const LINKED_LIST &aList); // copy constructor ~LINKED_LIST(); // destructor // operations bool isEmpty(); int getLength(); bool insert(int index, T newItem); // insert after “index” bool remove(int index); int findNode(T key); // return node index or -1 bool retrieve(int index, T &itemData); }; // end class 09/2013 16 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (1)  Đặc điểm:  Mỗi node có 2 con trỏ liên kết đến node kế tiếp (next) và node phía trước (prev) trong danh sách 09/2013 17 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (2)  Các thao tác cơ bản  Khởi tạo danh sách  Xóa danh sách  Kiểm tra danh sách rỗng  Đếm số phần tử trong danh sách  Thêm node  Xóa node  Tìm một node  Lấy thông tin một node 09/2013 18 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (3) Minh họa thao tác thêm node 09/2013 19 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (4) Minh họa thao tác xóa node 09/2013 20 (C) Nguyen Tri Tuan - DH.HCM Danh sách liên kết đôi (5) template <class T> class DLINKED_LIST { private: struct ListNode { T data; // data of node ListNode *prev, *next; }; int size; // number of node in list ListNode *head; // pointer to 1st node in list public: DLINKED_LIST(); // default constructor DLINKED_LIST(const DLINKED_LIST &aList);// copy constructor ~DLINKED_LIST(); // destructor // operations bool isEmpty(); int getLength(); bool insert(int index, T newItem); // insert after “index” bool remove(int index); int findNode(T key); // return node index, or -1 int retrieve(int index, T &itemData); }; // end class 09/2013 21 (C) Nguyen Tri Tuan - DH.HCM Các cấu trúc dữ liệu cơ bản (Fundamental Data Structures) 1.1 Các danh sách liên kết – Linked Lists 1.2 Ngăn xếp – Stack 1.3 Hàng đợi - Queue 09/2013 22 (C) Nguyen Tri Tuan - DH.HCM Ngăn xếp - Stack  Định nghĩa  Các thao tác cơ bản  Cài đặt Stack bằng mảng  Cài đặt Stack bằng DSLK đơn  Ứng dụng Stack 09/2013 23 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa  Stack là một cấu trúc dữ liệu:  Dùng để lưu trữ nhiều phần tử dữ liệu  Hoạt động theo cơ chế “Vào sau – Ra trước” (Last In/First Out – LIFO) ** Cấu trúc Stack được phát minh năm 1955, được đăng ký bản quyền năm 1957, bởi tác giả Friedrich L. Bauer (người Đức) 09/2013 24 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (1)  Khởi tạo Stack rỗng  Xóa Stack  Kiểm tra Stack rỗng  Thêm một phần tử vào đỉnh Stack (Push)  Xóa một phần tử ở đỉnh Stack (Pop)  Lấy phần tử ở đỉnh Stack mà không loại bỏ nó 09/2013 25 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (2)  Push: thêm 1 phần tử vào đỉnh Stack  Pop: lấy ra 1 phần tử ở đỉnh Stack 09/2013 26 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng mảng template <class T> class STACK { private: T *items; // array of stack items int top; // index to top of stack int maxSize; // maximum size of stack public: STACK(int size); // create stack with // ‘size’ items STACK(const STACK &aStack);// copy constructor ~STACK(); // destructor // operations bool isEmpty(); bool push(T newItem); bool pop(T &item); bool topValue(T &item); }; // end class 09/2013 27 (C) Nguyen Tri Tuan - DH.HCM Áp dụng  Viết lệnh để thực hiện các yêu cầu sau đây:  Khai báo biến stack S, và khởi tạo S có N phần tử  Đưa các giá trị sau vào S: 15, 8, 6, 21  Lấy 21 ra khỏi S  Lấy 8 ra khỏi S  Gán các giá trị 1->99 vào S  Lần lượt lấy các phần tử trong S ra và in lên màn hình  Cho mảng a chứa dãy số nguyên từ 1->N, hãy đảo ngược các phần tử của mảng a 09/2013 28 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng DSLK đơn (1) Hình minh họa cấu trúc Stack sử dụng DSLK đơn 09/2013 29/203 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng DSLK đơn (2) Push(): chính là thêm node vào đầu DSLK 09/2013 30/203 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Stack bằng DSLK đơn (3) template <class T> class STACK { private: struct StackNode { T data; // data of item on the stack StackNode *next; // pointer to next node }; StackNode *top; // pointer to top of stack public: STACK(); // default constructor STACK(const STACK &aStack); // copy constructor ~STACK(); // destructor // operations bool isEmpty(); bool push(T newItem); bool pop(T &item); bool topValue(T &item); }; // end class 09/2013 31 (C) Nguyen Tri Tuan - DH.HCM So sánh 2 cách cài đặt Stack  So sánh  Cài đặt Stack bằng mảng (array-based stack)  Cài đặt Stack bằng Danh sách liên kết đơn (pointer- based stack) 09/2013 32 (C) Nguyen Tri Tuan - DH.HCM Ứng dụng của Stack  Tính giá trị biểu thức toán học (thuật toán Balan ngược – Reverse Polish notation)  Bài toán tìm đường đi trong mê cung, bài toán mã đi tuần, bài toán 8 quân hậu,…  Khử đệ qui … 09/2013 33 (C) Nguyen Tri Tuan - DH.HCM Thuật toán Balan ngược  Cho 1 biểu thức ở dạng chuỗi:  S = “5 + ((1 + 2) * 4) − 3”  Biểu thức gồm các toán tử +,-,*,/ và dấu ngoặc ()  Tính giá trị biểu thức trên 09/2013 34 (C) Nguyen Tri Tuan - DH.HCM Các cấu trúc dữ liệu cơ bản (Fundamental Data Structures) 1.1 Các danh sách liên kết – Linked Lists 1.2 Ngăn xếp – Stack 1.3 Hàng đợi - Queue 09/2013 35 (C) Nguyen Tri Tuan - DH.HCM Hàng đợi - Queue  Định nghĩa  Các thao tác cơ bản  Cài đặt Queue bằng mảng  Cài đặt Queue bằng DSLK đơn  Ứng dụng Queue 09/2013 36 (C) Nguyen Tri Tuan - DH.HCM Định nghĩa  Queue là một cấu trúc dữ liệu:  Dùng để lưu trữ nhiều phần tử dữ liệu  Hoạt động theo cơ chế “Vào trước – Ra trước” (First In/First Out – FIFO) 09/2013 37 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (1)  Khởi tạo Queue rỗng  Xóa Queue  Kiểm tra Queue rỗng ?  Thêm 1 phần tử vào cuối Queue (EnQueue)  Lấy ra 1 phần tử ở đầu Queue (DeQueue)  Lấy phần tử ở đầu Queue mà không loại bỏ nó 09/2013 38 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (2)  EnQueue: thêm 1 phần tử vào cuối Queue  DeQueue: lấy ra 1 phần tử ở đầu Queue 09/2013 39/203 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (3) Minh họa thao tác EnQueue 09/2013 40/203 (C) Nguyen Tri Tuan - DH.HCM Các thao tác cơ bản (4) Minh họa thao tác DeQueue 09/2013 41 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (1) Cấu tạo của Queue 09/2013 42 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (2) Minh họa hình ảnh các phần tử đang chứa trong Queue 09/2013 43 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (3) Khi thêm nhiều phần tử, sẽ làm “tràn” mảng  “Tràn giả” 09/2013 44 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (4) Giải pháp cho tình huống “tràn giả”: xử lý mảng như là 1 danh sách vòng 09/2013 45 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng mảng (5) template <class T> class QUEUE { private: T *items; // array of queue items int front; int rear; int count; int maxSize; // maximum size of queue public: QUEUE(int size); // create queue with // ‘size’ items QUEUE(const QUEUE &aQueue); // copy constructor ~QUEUE(); // destructor // operations bool isEmpty(); bool enqueue(T newItem); bool dequeue(T &item); bool frontValue(T &item); }; // end class 09/2013 46 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng DSLK đơn (1) - Enqueue: thêm node vào cuối DSLK đơn - Dequeue: xóa node ở đầu DSLK đơn 09/2013 47 (C) Nguyen Tri Tuan - DH.HCM Cài đặt Queue dùng DSLK đơn (2) template <class T> class QUEUE { private: struct QueueNode { T data; // data of item on the queue QueueNode *next; // pointer to next node }; QueueNode *front; QueueNode *rear; public: QUEUE(); // default constructor QUEUE(const QUEUE &aStack); // copy constructor ~QUEUE(); // destructor // operations bool isEmpty(); bool enqueue(T newItem); bool dequeue(T &item); bool frontValue(T &item); }; // end class 09/2013 48 (C) Nguyen Tri Tuan - DH.HCM Ứng dụng của Queue  Quản lý xếp hàng (theo số thứ tự). Tại các ngân hàng, bệnh viện,…  Quản lý phục vụ in ấn (máy in) 09/2013 49 (C) Nguyen Tri Tuan - DH.