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 - Ngô Hữu Phước

Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 15. Danh sách liên kết @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University1 Tháng 09 năm 2009 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 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University2 Tháng 09 năm 2009 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University3 Tháng 09 năm 2009 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University4 Tháng 09 năm 2009 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University5 Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (2/23)  Danh sách liên kết đơn là một cấu trúc dữ liệu bao gồm một tập các nút, mà mỗi nút bao gồm:  Dữ liệu cần lưu trữ  Liên kết đến nút tiếp theo @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University6 Link Data Node Add 60 1000 800 45 800 90 55 90 0 NULL 15.2.1. Khái niệm về danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (3/23)  Để 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University7 60 1000 800 45 800 90 55 90 0 NULL 15.2.1. Khái niệm về danh sách liên kết đơn start Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (4/23) Khai báo cấu trúc một Node của danh sách: template struct node { ListEntry data; struct node *link; }; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University8 15.2.1. Khái niệm về danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (5/23) 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University9 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (6/23) 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; }; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University10 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (7/23) Khởi tạo danh sách: template LList::LList() { start = NULL; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University11 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULL Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (8/23) Thêm một node đầu danh sách:  Nếu danh sách rỗng, cấp phát ô nhớ và cho start trỏ vào ô nhớ đó.  Nếu danh sách không rỗng:  Cấp phát ô nhớ cho biến temp.  Phần liên kết của temp trỏ vào đầu danh sách.  Con trỏ start trỏ vào temp. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University12 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULLdata link temp 1 2 start NULLdata link temp data link Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (9/23) Thêm một node đầu danh sách: template int LList::LAdd(ListEntry entry) { int kt=0; node *temp; if(start==NULL) { start=(node *) malloc(sizeof(node)); if(start==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; start->data=entry; start->link=NULL; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn else { temp=(node *) malloc(sizeof(node)); if(temp==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; temp->data=entry; temp->link=start; start=temp; } return kt; } Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (10/23) 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University14 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULL temp data linkdata link data link data link data linktemp1 12 Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (11/23) Chèn 1 node vào danh sách : template int LList::LInsert(ListEntry value, ListEntry entry) { int kt=0; node *temp, *temp1; if(start==NULL) printf("Danh sach rong!"); else { temp=start; while(temp!=NULL) { if(temp->data==value) break; else temp=temp->link; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University15 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn if(temp!=NULL) { temp1=(node *) malloc(sizeof(node)); if(temp1==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; temp1->data=entry; temp1->link=temp->link; temp->link=temp1; } } return kt; } Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (12/23) Thêm một node cuối danh sách:  Nếu danh sách rỗng, cấp phát ô nhớ và 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 sách.  Cấp phát ô nhớ cho temp->link.  Phần liên kết của temp->link trỏ vào NULL. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University16 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULLdata link temp 1 2 start NULL temp data linkdata link data link 1 2data link Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (13/23) Thêm một node cuối danh sách: template int LList::LAppend(ListEntry entry) { int kt=0; node *temp; if(start==NULL) { start=(node *) malloc(sizeof(node)); if(start==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; start->data=entry; start->link=NULL; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University17 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn else { temp=start; while(temp->link!=NULL) temp=temp->link; temp->link=(node *) malloc(sizeof(node)); if(temp->link==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; temp=temp->link; temp->data=entry; temp->link=NULL; } return kt; } Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (14/23) 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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University18 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULL temp data linkdata link data link data link pos = 3 Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (15/23) 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; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (16/23) Xóa một node trong danh sách:  Sử dụng 2 con trỏ prev và curr để tìm node cần xóa. Con trỏ prev trỏ vào node trước node cần xóa. Con trỏ curr trỏ vào node cần xóa.  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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University20 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn 1 2 start NULL curr data linkdata link data link data link prev start NULL curr data linkdata link prev NULL Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (17/23) Xóa một node trong danh sách : int LList::LDelete(ListEntry value) { node *prev, *curr; int kt=0; if(start==NULL) return kt; else { prev=NULL; curr=start; while(!kt && curr->link!=NULL) { if(curr->data==value) { kt=1; break; } else { prev=curr; curr=curr->link; } } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University21 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn if(curr->data==value) kt=1; else kt=2; if(kt==1) { if(prev==NULL) { start=start->link; free(curr); } else { prev->link=curr->link; free(curr); } } } return kt; } Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (18/23) Lấy thông tin một node ở vị trí nào đó:  Sử dụng con trỏ temp để duyệt qua danh sách.  Duyệt cho đến khi đến node thứ pos, lấy thông tin tại node đó và trả lại cho nơi gọi hàm. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University22 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULL temp data linkdata link data link data link Cho trước pos = 3 Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (19/23) Lấy thông tin một node ở vị trí nào đó : template int LList::LGet(int pos, ListEntry *value) { int i=0; node *temp=start; while(temp!=NULL && i<pos) { temp=temp->link; if(temp!=NULL) i++; } if(i!=pos) return 0; else { *value=temp->data; return 1; } } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University23 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (20/23) Xác định số phần tử trong danh sách:  Sử dụng con trỏ temp để duyệt qua danh sách, cho đến khi temp=NULL.  Sử dụng một biến length để đếm số phần tử đã duyệt. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University24 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULL temp data linkdata link data link data link length = 3 Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (21/23) Xác định số phần tử trong danh sách: template int LList::LLength() { int length=0; node *temp=start; while(temp!=NULL) { length++; temp=temp->link; } return length; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University25 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (22/23) Làm rỗng danh sách:  Xóa từng phần tử trong danh sách.  Sử dụng con trỏ temp để xác định phần tử cần xóa (từ đầu danh sách).  Dịch chuyển con trỏ start sang phần tử kế tiếp.  Thu hồi ô nhớ ứng với con trỏ temp.  Thực hiện cho đến khi start=NULL. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University26 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn start NULL temp data linkdata link data link data link Tháng 09 năm 2009 15.2. Danh sách liên kết đơn (23/23) Làm rỗng danh sách : template void LList::LMakeEmpty() { node *temp; while(start!=NULL) { temp=start; start=start->link; free(temp); } } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University27 15.2.2. Các thao tác cơ bản của danh sách liên kết đơn Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (1/20)  Được định nghĩa giống danh sách liên kết đơn, tuy nhiên, phần tử cuối thay vì trỏ vào NULL thì trỏ vào phần tử đầu tiên.  Danh sách liên kết vòng được dùng khi có nhiều thao tác với dữ liệu. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University28 Data Link Có 1 node Add 60 1000 800 45 800 90 55 90 1000 15.3.1. Khái niệm về danh sách liên kết vòng Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (2/20)  Để quản lý danh sách liên kết, thông thường cần: • Start là con trỏ chỉ đến một phần tử 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 phần tử do start quản lý. • Như vậy, từ bất kỳ vị trí nào trong danh sách cũng có thể duyệt hết danh sách.  Lưu ý: khi thêm hay bớt phần tử nào trong danh sách cần đảm bảo rằng sau thao tác đó vẫn giữ được tính liên kết vòng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University29 15.3.1. Khái niệm về danh sách liên kết vòng start 60 1000 800 45 800 90 55 90 1000 Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (3/20) template class CLList { public: CLList(); int CLAdd(ListEntry entry); int CLInsert(ListEntry value, ListEntry entry); int CLAppend(ListEntry entry); int CLFind(ListEntry value); int CLDelete(ListEntry value); int CLLength(); void CLMakeEmpty(); int CGet(int pos, ListEntry *value); template friend void LPrint(CLList list); private: node *start; }; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University30 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (4/20) Khởi tạo danh sách LKV: template CLList::CLList() { start = NULL; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University31 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng start NULL Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (5/20) Thêm một node đầu danh sách LKV:  Nếu danh sách rỗng, cấp phát ô nhớ và cho start trỏ vào ô nhớ đó, phần liên kết trỏ vào start.  Nếu danh sách không rỗng:  Sử dụng biến temp để duyệt qua danh sách, khi temp→link start.  Cấp phát ô nhớ cho temp→link.  Phần liên kết của ô nhớ mới trỏ vào start.  Start trỏ vào vùng ô nhớ mới trên. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University32 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng start data link 1 2 start 20 link temp 30 link 10 link temp->link Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (6/20) Thêm một node đầu danh sách LKV: template int CLList::CLAdd(ListEntry entry) { int kt=0; node *temp; if (start==NULL) { start=(node *) malloc(sizeof(node)); if (start==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; start->data=entry; start->link=start; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University33 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng else { temp=start; while (temp->link!=start) temp=temp->link; temp->link=(node *) malloc(sizeof(node)); if (temp->link==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; temp=temp->link; temp->data=entry; temp->link=start; start=temp; } return kt; } Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (7/20) Chèn 1 node vào danh sách LKV:  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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University34 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng start temp 20 link10 link 30 link 40 link 25 link temp1 12 Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (8/20) Chèn 1 node vào danh sách LKV : template int CLList::CLInsert(ListEntry value, ListEntry entry) { int kt=0; node *temp, *temp1; if (start==NULL) printf("Danh sach rong!"); else { temp=start; while (temp->link!=start) { if (temp->data==value) break; else temp=temp->link; } if (temp->data==value) { @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University35 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng temp1=(node *) malloc(sizeof(node)); if(temp1->link==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; temp1->data=entry; temp1->link=temp->link; temp->link=temp1; } } return kt; } Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (9/20) Thêm một node cuối danh sách LKV:  Nếu danh sách rỗng, cấp phát ô nhớ và cho start trỏ vào ô nhớ đó, phần liên kết trỏ vào start.  Nếu danh sách không rỗng:  Sử dụng biến temp để duyệt qua danh sách, khi temp→link start.  Cấp phát ô nhớ cho temp→link.  Phần liên kết của ô nhớ mới trỏ vào start. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University36 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng start data link 1 2 start 20 link temp 30 link 40 link temp->link Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (10/20) Thêm một node cuối danh sách LKV: template int CLList::CLAppend(ListEntry entry) { int kt=0; node *temp; if (start==NULL) { start=(node *) malloc(sizeof(node)); if (start==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; start->data=entry; start->link=start; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University37 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng else { temp=start; while (temp->link!=start) temp=temp->link; temp->link=(node *) malloc(sizeof(node)); if (temp->link==NULL) { printf("Loi cap phat bo nho!\n"); return kt; } kt=1; temp=temp->link; temp->data=entry; temp->link=start; } return kt; } Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (11/20) Tìm một node trong danh sách LKV:  Sử dụng con trỏ temp để duyệt qua danh sách, khi temp→link start.  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. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University38 15.3.2. Các thao tác cơ bản của danh sách liên kết vòng start temp 20 link10 link 30 link 40 link pos = 3 Tìm vị trí của phần tử có giá trị 30! Tháng 09 năm 2009 15.3. Danh sách liên kết vòng (12/20) Tìm một node trong danh sách LKV: template