Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 15: Danh sách liên kết

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 15: Danh sách liên kết" trình bày giới thiệu chung, danh sách liên kết đơn, danh sách liên kết vòng, danh sách liên kết kép, một số ví dụ về danh sách liên kết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 15: Danh sách liên kết Cấu trúc dữ liệu và giải thuật Bài 15. Danh sách liên kết Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009Bài 15: Danh sách liên kếtNội dung: 15.1. Giới thiệu chung. 15.2. Danh sách liên kết đơn. 15.2.1. Khái niệm về danh sách liên kết đơn. 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn. 15.3. Danh sách liên kết vòng. 15.3.1. Khái niệm về danh sách liên kết vòng. 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng. 15.4. Danh sách liên kết kép. 15.4.1. Khái niệm về danh sách liên kết kép. 15.4.2. Các thao tác cơ bản của danh sách liên kết kép. 15.5. Một số ví dụ về danh sách liên kết. Tham khảo:1. Deshpande Kakde: C and Data structures.chm, Chapter 20: Linked Lists2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 4: Linked Lists3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 5 Linked Lists.4. Bài giảng TS Nguyễn Nam Hồng 2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.1. Giới thiệu chung (1/2) Với CTDL dạng mảng, bộ nhớ được sử dụng là một dãy liền kề và có kích thước cố định. Tuy nhiên, CTDL này có m ột số nhược điểm:  Thời gian cho việc thêm hay bớt phần tử trong mảng khá lâu vì phải thay đổi cả các phần tử còn lại trong mảng.  Ngay cả khi khai báo một lượng lớn các phần tử cho mảng để có thể áp dụng được cho nhiều bài toán, chúng ta cũng thấy khả năng dư thừa bộ nhớ xuất hiện.3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.1. Giới thiệu chung (2/2) Để khắc phục nhược điểm trên, có thể sử dụng danh sách liên kết như là cấu trúc dữ liệu thay thế. Trong cấu trúc này, không cần xác định kích thước cho các phần tử trước. Ta có thể định nghĩa phần tử bất cứ lúc nào, sau đó liên kết phần tử đó với danh sách đã có trước đó. Như vậy, mỗi phần tử sẽ bao gồm thông tin cần lưu trữ và liên kết với các phần tử khác.4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.2. Danh sách liên kết đơn (1/23) Trong rất nhiều trường hợp cần sử dụng đến danh sách liên kết động, danh sách liên kết động cần dùng đến khi kích thước danh sách chưa biết tại thời điểm biên dịch chương trình. Khi đó, danh sách có thể mở rộng hoặc thu hẹp lại tại thời điểm chạy chương trình. Cấu trúc dữ liệu linked list sử dụng mô hình liên kết động. Một số dạng của danh sách liên kết:  Danh sách liên kết đơn.  Danh sách liên kết vòng.  Danh sách liên kết kép.5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.2. Danh sách liên kết đơn (2/23)15.2.1. Khái niệm về danh sách liên kết đơn Danh sách liên kết đơn là một Link cấu trúc dữ liệu bao gồm một tập Data Add các nút, mà mỗi nút bao gồm:  Dữ liệu cần lưu trữ Node  Liên kết đến nút tiếp theo 60 800 45 90 55 0 NULL 1000 800 906 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.2. Danh sách liên kết đơn (3/23)15.2.1. Khái niệm về danh sách liên kết đơn Để quản lý danh sách liên kết, thông thường cần: • Start là con trỏ chỉ đến phần tử đầu tiên của danh sách liên kết. • Phần tử cuối của danh sách liên kết với vùng liên kết có nội dung NULL. start 60 800 45 90 55 0 NULL 1000 800 907 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.2. Danh sách liên kết đơn (4/23)15.2.1. Khái niệm về danh sách liên kết đơnKhai báo cấu trúc một Node của danh sách: template struct node { ListEntry data; struct node *link; };8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 200915.2. Danh sách liên kết đơn (5/23)15.2.2. Các thao tác cơ bản của danh sách liên kết đơn1. Khởi tạo danh sách.2. ...