intTypePromotion=1

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:70

0
18
lượt xem
1
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

"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.

Chủ đề:
Lưu

Nội dung Text: 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

  1. 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.com 1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  2. Bài 15: Danh sách liên kết Nộ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 Lists 2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 4: Linked Lists 3. 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 2009
  3. 15.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 2009
  4. 15.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 2009
  5. 15.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 2009
  6. 15.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 90 6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  7. 15.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 90 7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  8. 15.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 đơn Khai 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 2009
  9. 15.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 đơn 1. Khởi tạo danh sách. 2. LAdd: Thêm một node vào đầu danh sách. 3. LInsert: Chèn một node vào danh sách. 4. LAppend: Thêm một node vào cuối danh sách. 5. LFind: Tìm một node trong danh sách. 6. LDelete: Xóa một node trong danh sách. 7. LLength: Số phần tử trong danh sách. 8. LMakeEmpty: Làm rỗng danh sách. 9. LGet: Lấy thông tin về một phần tử trong danh sách. 9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  10. 15.2. Danh sách liên kết đơn (6/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn class LList { public: LList(); int LAdd(ListEntry entry); int LInsert(ListEntry value, ListEntry entry); int LAppend(ListEntry entry); int LFind(ListEntry value); int LDelete(ListEntry value); int LLength(); void LMakeEmpty(); int LGet(int pos, ListEntry *value); template friend void LPrint(LList list); private: node *start; }; 10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  11. 15.2. Danh sách liên kết đơn (7/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Khởi tạo danh sách: template LList::LList() start { start = NULL; NULL } 11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  12. 15.2. Danh sách liên kết đơn (8/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Thêm một node đầu danh sách:  Nếu danh sách rỗng, cấp phát ô nhớ và start temp 1 cho start trỏ vào ô nhớ đó.  Nếu danh sách không rỗng:  Cấp phát ô nhớ cho biến temp. data link NULL  Phần liên kết của temp trỏ vào đầu danh sách. 2  Con trỏ start trỏ vào temp. temp start data link data link NULL 12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  13. 15.2. Danh sách liên kết đơn (9/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Thêm một node đầu danh sách: else { template temp=(node *) int LList::LAdd(ListEntry entry) { malloc(sizeof(node)); int kt=0; if(temp==NULL) { node *temp; printf("Loi cap phat bo nho!\n"); if(start==NULL) { start=(node *) return kt; } malloc(sizeof(node)); kt=1; if(start==NULL) { temp->data=entry; printf("Loi cap phat bo nho!\n"); temp->link=start; return kt; } start=temp; kt=1; } start->data=entry; return kt; start->link=NULL; } } 13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  14. 15.2. Danh sách liên kết đơn (10/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Chèn 1 node vào danh sách:  Nhập thông tin về node đứng trước node thêm mới.  Sử dụng con trỏ temp để đến được node đứng trước đó.  Cấp phát ô nhớ cho biến temp1.  Phần liên kết của temp1 trỏ vào phần liên kết của con trỏ temp.  Phần liên kết của con trỏ temp trỏ vào temp1. start temp data link data link data link data link NULL 2 1 temp1 data link 14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  15. 15.2. Danh sách liên kết đơn (11/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Chèn 1 node vào danh sách : if(temp!=NULL) { template temp1=(node *) int LList::LInsert(ListEntry value, malloc(sizeof(node)); ListEntry entry) { if(temp1==NULL) { int kt=0; node *temp, *temp1; printf("Loi cap phat bo nho!\n"); if(start==NULL) printf("Danh sach rong!"); return kt; } else { kt=1; temp=start; temp1->data=entry; while(temp!=NULL) { temp1->link=temp->link; if(temp->data==value) temp->link=temp1; break; } else temp=temp->link; } } return kt; } 15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  16. 15.2. Danh sách liên kết đơn (12/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Thêm một node cuối danh sách:  Nếu danh sách rỗng, cấp phát ô nhớ và start temp 1 cho start trỏ vào ô nhớ đó.  Nếu danh sách không rỗng:  Sử dụng con trỏ temp đi đến cuối danh data link NULL sách.  Cấp phát ô nhớ cho temp->link. 2  Phần liên kết của temp->link trỏ vào NULL. start temp data link data link data link NULL 1 data link 2 16 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  17. 15.2. Danh sách liên kết đơn (13/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Thêm một node cuối danh sách: else { template temp=start; int LList::LAppend(ListEntry entry) { while(temp->link!=NULL) int kt=0; temp=temp->link; node *temp; temp->link=(node *) if(start==NULL) { start=(node *) malloc(sizeof(node)); malloc(sizeof(node)); if(temp->link==NULL) { if(start==NULL) { printf("Loi cap phat bo nho!\n"); printf("Loi cap phat bo nho!\n"); return kt; } return kt; } kt=1; temp=temp->link; kt=1; temp->data=entry; start->data=entry; temp->link=NULL; } start->link=NULL; } return kt; } 17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  18. 15.2. Danh sách liên kết đơn (14/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tìm một node trong danh sách:  Sử dụng con trỏ temp để duyệt qua danh sách.  Sử dụng thêm biến pos để lưu vị trí của node trong danh sách. Nếu danh sách rỗng hoặc không tìm thấy trả về 0, ngược lại trả về vị trí của node. start temp pos = 3 data link data link data link data link NULL 18 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  19. 15.2. Danh sách liên kết đơn (15/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tìm một node trong danh sách: template int LList::LFind(ListEntry value) { int pos=0; node *temp=start; while(temp!=NULL) { pos++; if(temp->data==value) break; temp=temp->link; } if(temp!=NULL) return pos; else return 0; } 19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  20. 15.2. Danh sách liên kết đơn (16/23) 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Xóa một node trong danh sách: prev curr  Sử dụng 2 con trỏ prev và curr để tìm 1 node cần xóa. Con trỏ prev trỏ vào node start trước node cần xóa. Con trỏ curr trỏ vào node cần xóa. NULL data link data link NULL  Nếu curr = start, cho start trỏ vào start->link và giải phóng ô nhớ của curr.  Nếu không, prev->link trỏ tới curr->link và giải phóng ô nhớ của curr. 2 start prev curr data link data link data link data link NULL 20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2