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

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

1. TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Cấu trúc dữ liệu và giải thuật Danh sách liên kết TS. Ngô Hữu Dũng
2. Dẫn nhập  Mảng (array)  Kích thước khó thay đổi  Cần cấp phát trước một vùng nhớ liên tục  Mất nhiều thao tác để chèn/xoá phần tử  Phù hợp với dữ liệu nhỏ, truy xuất nhanh  Danh sách liên kết (linked list)  Kích thước thay đổi linh động  Cấp phát bộ nhớ động, không cần vùng nhớ liên tục  Chèn/xoá dễ dàng  Cho phép dữ liệu lớn hơn, cấu trúc linh hoạt 2 Cấu trúc dữ liệu và giải thuật - DSLK
3. Linked list – Khái niệm  Dãy phần tử nối với nhau bởi con trỏ (pointer)  Mỗi phần tử là một nút (node)  Phần dữ liệu (int, float, char, struct )  Phần liên kết (pointer)  Con trỏ head trỏ vào nút đầu tiên  Con trỏ tail trỏ vào nút cuối cùng  Nút cuối cùng trỏ vào NULL data next data next data next tail head NULL 3 Cấu trúc dữ liệu và giải thuật - DSLK
4. Các loại danh sách liên kết  Danh sách liên kết đơn (Singly linked list) data next data next data next tail head NULL  Danh sách liên kết đôi/kép (Doubly linked list) prev data next prev data next prev data next tail head NULL NULL  Danh sách liên kết vòng (Circular linked list) data next data next data next head 4 Cấu trúc dữ liệu và giải thuật - DSLK
5. Một vài ứng dụng  Tổ chức các cấu trúc dữ liệu khác nhau  Stack, queue, tree, graph, hash table  Lưu dấu  Lịch sử truy cập web (history)  Lưu các tác vụ (undo)  Quản lý các thành phần trong máy tính  Bộ nhớ, tiến trình, tập tin  Phù hợp với các ứng dụng  Dữ liệu lớn, cấu trúc linh động 5 Cấu trúc dữ liệu và giải thuật - DSLK
6. data next data next data next tail head NULL Danh sách liên kết đơn Singly linked list 6 Cấu trúc dữ liệu và giải thuật - DSLK
7. Singly linked list – Khai báo  Khai báo nút kiểu cấu trúc  Phần dữ liệu (int, float, char, struct )  Phần liên kết (pointer)  Khai báo con trỏ head và tail 1. struct Node 2. { data next 3. int data; 4. struct Node *next; 5. }; 6. struct Node *head; head 7. struct Node *tail; tail 7 Cấu trúc dữ liệu và giải thuật - DSLK
8. Định nghĩa kiểu nút  Dùng typedef định nghĩa kiểu cấu trúc nút  Có nhiều cách khai báo biến kiểu nút 1. struct Node 2. { 3. int data; 4. struct Node *next; 5. }; 6. // Định nghĩa kiểu nút 7. typedef struct Node tNode; 8. tNode *head; 9. struct Node *tail; 10.Node *temp; // C++ 8 Cấu trúc dữ liệu và giải thuật - DSLK
9. Kiểu danh sách  Khai báo kiểu danh sách 1. // Kiểu nút 2. struct Node  Con trỏ head và tail 3. { 4. int data;  Phù hợp với bài toán 5. struct Node *next; cần dùng nhiều danh 6. }; sách 7. // Kiểu danh sách  Truy xuất? 8. struct List 9. {  ds1.tail data (?) 10. struct Node *head;  ds1.head next (?) 11. struct Node *tail; data next 12.}; head tail 13.// Biến danh sách 14.struct List ds1, ds2; NULL 9 Cấu trúc dữ liệu và giải thuật - DSLK
10. Khai báo – Ví dụ  Danh sách sinh viên 1. struct SV{ 2. int ID;  Cấu trúc sinh viên 3. char ten[50];  ID, ten 4. bool gioiTinh; 5. float diem;  Cấu trúc nút 6. };  Dữ liệu: Kiểu cấu trúc 7. struct Node{ sinh viên 8. struct SV data; 9. struct Node *next;  Liên kết: Con trỏ kiểu 10.}; nút 11.struct List{ 12. struct Node *head;  Truy xuất? 13. struct Node *tail;  ds.tail data.ID 14.};  ds.head next data.ID 15.struct List ds; 10 Cấu trúc dữ liệu và giải thuật - DSLK
11. Vận dụng  Bài tập: Container tracking  Một nhà vận chuyển sở hữu một số lượng container chưa xác định. Mỗi container chứa các thông số như ID, khối lượng hàng đang chứa, tình trạng đang dùng hay không, toạ độ GPS hiện tại (kinh độ, vĩ độ) ví dụ (10.823, 106.629).  Hãy thiết lập cấu trúc dữ liệu để quản lý số container trên. 11 Cấu trúc dữ liệu và giải thuật - DSLK
12. Thao tác cơ bản  Khởi tạo danh sách, nút mới  Thêm phần tử  Vào đầu, vào cuối, chèn vào sau một phần tử  Duyệt danh sách  Xuất, trích xuất, đếm, tính toán  Tìm kiếm  Min, max, giá trị X  Xoá phần tử  Ở đầu, ở cuối, ở giữa  Sắp xếp 12 Cấu trúc dữ liệu và giải thuật - DSLK
13. Bài toán đặt ra  1. // Kiểu nút Danh sách các số 2. struct Node nguyên 3. { 4. int data;  Cấu trúc dữ liệu danh 5. struct Node *next; sách liên kết đơn 6. }; 7. typedef struct Node tNode;  Các thao tác cơ bản 8. // Kiểu danh sách trên danh sách liên kết 9. struct List 10.{ đơn 11. tNode *head;  Menu thực hiện 12. tNode *tail; 13.}; 14.typedef struct List tList; 15.// Biến danh sách 16.tList ds; 13 Cấu trúc dữ liệu và giải thuật - DSLK
14. Một số hàm tạo, thêm và chèn phần tử 1. // Initiate a new list 2. void init(tList *); 3. // Make a new node 4. tNode* makeNode(); 5. // Add a new node to the head of list 6. void addHead(tList *); 7. // Add a new node to the tail of list 8. void addTail(tList *); 9. // Insert a node after a given node 10.void insertAfter(tList *, tNode *, tNode *); 14 Cấu trúc dữ liệu và giải thuật - DSLK
15. Khởi tạo danh sách  Danh sách ban đầu là 1. void init(tList *list) 2. { danh sách rỗng 3. list->head = NULL;//(1)  head và tail trỏ vào 4. list->tail = NULL;//(2) 5. } NULL 6. // Gọi hàm: init(&list); head NULL tail 7. //Hoặc dùng tham chiếu (1) (2) 8. void init(tList &list) 9. { 10. list.head = NULL;//(1)  Chú ý cách dùng con 11. list.tail = NULL;//(2) 12.} trỏ kiểu cấu trúc 13.// Gọi hàm: init(list); 15 Cấu trúc dữ liệu và giải thuật - DSLK
16. Tạo một nút mới data next 1. Cấp phát bộ nhớ newNode (2) (1)  Hàm malloc hoặc new (3) 2. NULL Nhập dữ liệu 1. tNode* makeNode() 3. Khởi tạo next rỗng 2. { 3. tNode *newNode; 4. newNode = (tNode*)malloc(sizeof(tNode)); 5. //Or: newNode = new tNode; (1) 6. printf("Nhap du lieu: "); 7. scanf("%d", &newNode->data); // (2) 8. newNode->next = NULL; // (3) 9. return newNode; 10.} 11.// How to call? tNode *newNode = makeNode(); 16 Cấu trúc dữ liệu và giải thuật - DSLK
17. Tạo một nút mới – Dùng kiểu pointer  Để thay đổi giá trị của một con trỏ  Dùng con trỏ của con trỏ data next newNode *newNode (2) 1. // Make a new node (1) 2. void makeNode(tNode newNode) (3) 3. { NULL 4. *newNode=(tNode*)malloc(sizeof(tNode));//(1) 5. printf("Input data: "); 6. scanf("%d", &(*newNode)->data); //(2) 7. (*newNode)->next = NULL; //(3) 8. } 9. // How to call it? tNode *node; 10.// makeNode(&node); 17 Cấu trúc dữ liệu và giải thuật - DSLK
18. Thêm nút mới vào đầu danh sách  Tạo nút mới data next newNode  Tạo thế nào? NULL  Thêm vào đầu danh sách  Danh sách đang rỗng? head NULL tail  Kiểm tra điều kiện rỗng?  Thêm nút thế nào?  Danh sách không rỗng? data next  Kiểm tra điều kiện? head  Thêm nút thế nào? 18 Cấu trúc dữ liệu và giải thuật - DSLK
19. Thêm nút mới vào đầu danh sách  Tạo nút mới data next 1. Gọi hàm makeNode() newNode NULL (1)  Thêm vào đầu danh sách (2) (3)  Danh sách rỗng? head NULL tail 2. head trỏ vào nút mới 3. tail trỏ vào nút mới  Danh sách không rỗng? data next 4. next của nút mới trỏ newNode đến nút đầu danh sách (5) (4) data next 5. head trỏ vào nút mới head 19 Cấu trúc dữ liệu và giải thuật - DSLK
20. Thêm nút mới vào đầu danh sách 1. // Add a new node into the head of list 2. void addHead(tList *list) 3. { 4. // Make a new node 5. tNode *newNode = makeNode(); // (1) 6. if(list->head == NULL){ // List is empty 7. list->head = newNode; // (2) 8. list->tail = newNode; // (3) 9. }else{ // not empty 10. newNode->next = list->head; // (4) 11. list->head = newNode; // (5) 12. } 13.} 20 Cấu trúc dữ liệu và giải thuật - DSLK
21. Thêm nút mới vào cuối danh sách  Tạo nút mới data next 1. Gọi hàm makeNode() newNode NULL (1)  Thêm vào cuối danh sách (2) (3)  Danh sách rỗng head NULL tail 2. head trỏ vào nút mới 3. tail trỏ vào nút mới data next  Danh sách không rỗng? tail 4. next của tail trỏ vào nút (4) (5) data next mới 5. tail trỏ vào nút mới NULL 21 Cấu trúc dữ liệu và giải thuật - DSLK
22. Thêm nút mới vào cuối danh sách 1. // Add a new node into the tail of list 2. void addTail(tList *list) 3. { 4. // Make a new node 5. tNode *newNode = makeNode(); // (1) 6. 7. if(!list->head){ // List is empty 8. list->head = newNode; // (2) 9. list->tail = newNode; // (3) 10. }else{ // Not empty 11. list->tail->next = newNode; // (4) 12. list->tail = newNode; // (5) 13. } 14.} 22 Cấu trúc dữ liệu và giải thuật - DSLK
23. Chèn một nút vào sau một nút  Chèn nút insertNode vào sau givenNode? 1. insertNode next = givenNode next 2. givenNode next = insertNode  Trường hợp givenNode rỗng?  Trường hợp givenNode là nút cuối? data next (2) insertNode (1) data next data next data next head givenNode 23 Cấu trúc dữ liệu và giải thuật - DSLK
24. Chèn một nút vào sau một nút 1. // Insert insNode after givenNode 2. void insertAfter(tList *list, tNode *givenNode, tNode *insertNode) 3. { 4. // Add after a NULL? return 5. if(givenNode==NULL) 6. return; 7. insertNode->next = givenNode->next; // (1) 8. givenNode->next = insertNode; // (2) 9. // Add after the tail? update the tail 10. if(givenNode==list->tail) 11. list->tail = insertNode; 12.} 24 Cấu trúc dữ liệu và giải thuật - DSLK
25. Vận dụng  Bài tập: Container tracking  Một nhà vận chuyển sở hữu một số lượng container chưa xác định. Mỗi container chứa các thông số như ID, khối lượng hàng đang chứa, tình trạng đang dùng hay không, toạ độ GPS.  Hãy thiết lập thao tác nhập container mới. 25 Cấu trúc dữ liệu và giải thuật - DSLK
26. Một số hàm duyệt danh sách 1. // Print all list 2. void output(tList); 3. // Count a list 4. int count(tList); 5. // Calculate a list 6. int total(tList); 7. // Search an item on a list 8. tNode *search(tList, int); 9. // Find the max node on a list 10.tNode* maxNode(tList); 26 Cấu trúc dữ liệu và giải thuật - DSLK
27. Duyệt danh sách  Phần tử bắt đầu: tNode *node = list.head;  Phần tử tiếp theo: node = node next  Phần tử kết thúc: NULL 1. tNode *node = list.head; 2. while(node!=NULL) 3. { 4. // Thao tác xử lý 5. node = node->next; // Đến nút kế tiếp 6. } 7. // Hoặc: 8. for(node = list.head; node; node = node->next) 9. // Thao tác xử lý 27 Cấu trúc dữ liệu và giải thuật - DSLK
28. Xuất toàn bộ danh sách 1. // Print all list 2. void output(tList list) 3. { 4. tNode *node = list.head; 5. printf("List: "); 6. if(!list.head) // Empty list 7. { 8. printf("Empty.\n"); 9. return; 10. } 11. while(node) 12. { 13. printf("%d ",node->data); 14. node = node->next; 15. } 16. printf("\n"); 17.} 28 Cấu trúc dữ liệu và giải thuật - DSLK
29. Đếm danh sách 1. // Count elements of list 2. int count(tList list) 3. { 4. tNode *node; 5. int dem = 0; 6. for(node = list.head; node; node = node->next) 7. dem++; 8. return dem; 9. } Tương tự, hãy viết các hàm sau: int total(tList); tNode *search(tList, int); tNode* maxNode(tList); 29 Cấu trúc dữ liệu và giải thuật - DSLK
30. Tính tổng 1. // Calculate the sum of list 2. int total(tList list) 3. { 4. tNode *node = list.head; 5. int tong = 0; 6. while(node) 7. { 8. tong += node->data; 9. node = node->next; 10. } 11. return tong; 12.} 30 Cấu trúc dữ liệu và giải thuật - DSLK
31. Tìm kiếm 1. // Search a node 2. tNode *search(tList list, int x) 3. { 4. tNode *node = list.head; 5. while(node) 6. { 7. if(node->data == x) 8. return node; 9. node = node->next; 10. } 11. return NULL; 12.} 31 Cấu trúc dữ liệu và giải thuật - DSLK
32. Tìm max 1. // Find the max node on list 2. tNode* maxNode(tList list) 3. { 4. tNode *node = list.head; 5. tNode *max = node; 6. while(node) 7. { 8. if(node->data > max->data) 9. max = node; 10. node = node->next; 11. } 12. return max; 13.} 32 Cấu trúc dữ liệu và giải thuật - DSLK
33. Vận dụng  Bài tập: Container tracking  Bổ sung các thao tác báo cáo  Xuất thông tin các container  Liệt kê các container đang dùng  Đếm số lượng container rỗi  Tính tổng khối lượng hàng hoá của tất cả các container.  Tìm địa chỉ GPS của một container (nhập ID)  Cập nhật thông tin của một container 33 Cấu trúc dữ liệu và giải thuật - DSLK
34. Một số hàm xoá node 1. // Delete the head node 2. void delHead(tList *); 3. // Delete the node after a given node 4. void delAfter(tList *, tNode *); 5. // Delete the tail node 6. void delTail(tList *); 7. // Delete a given node 8. void delGivenNode(tList *, tNode *); 9. // Remove all list 10.void removeList(tList *); 34 Cấu trúc dữ liệu và giải thuật - DSLK
35. Xoá nút đầu danh sách (2)  Danh sách rỗng!? data next data next 1. Kết thúc head  Thay đổi liên kết delNode 2. head = delNode next  Nút cần xoá là nút cuối cùng? 3. Trở thành danh sách rỗng, cập nhật tail  Giải phóng bộ nhớ 4. free() hoặc delete 35 Cấu trúc dữ liệu và giải thuật - DSLK
36. Xoá nút đầu danh sách 1. // Delete the head node 2. void delHead(tList *list) 3. { 4. tNode *delNode = list->head; 5. if(delNode==NULL) // Empty list 6. return; // (1) 7. list->head = delNode->next;// (2) 8. if(list->head == NULL) // Become empty 9. list->tail = NULL; // (3) 10. free(delNode); // (4) 11.} 36 Cấu trúc dữ liệu và giải thuật - DSLK
37. Xoá nút sau nút cho trước  Nút cho trước rỗng hoặc nút cần xoá rỗng!? 1. Kết thúc  Thay đổi liên kết 2. delNode = givenNode next 3. givenNode next = delNode next  Nút cần xoá là nút cuối cùng? 4. Cập nhật tail  Giải phóng bộ nhớ 5. free() hoặc delete (3) data next data next data next data next givenNode delNode 37 Cấu trúc dữ liệu và giải thuật - DSLK
38. Xoá nút sau nút cho trước 1. // Delete the node after a given node 2. void delAfter(tList *list, tNode *givenNode) 3. { 4. tNode *delNode; 5. if(givenNode==NULL || givenNode->next == NULL) 6. return; // (1) 7. delNode = givenNode->next; // (2) 8. givenNode->next = delNode->next; // (3) 9. if(delNode==list->tail) 10. list->tail = givenNode; // (4) 11. free(delNode); // (5) 12.} 38 Cấu trúc dữ liệu và giải thuật - DSLK
39. Xoá nút cuối danh sách (3) tail data next data next data  Danh sách rỗng? 1. Kết thúc NULL NULL  Danh sách chỉ có một nút? 2. Danh sách trở thành rỗng  Ngược lại, danh sách có nhiều nút? 3. Tìm nút áp cuối (trước nút cuối) 4. Nút áp cuối trở thành nút cuối cùng  Giải phóng bộ nhớ 5. free() hoặc delete 39 Cấu trúc dữ liệu và giải thuật - DSLK
40. Xoá nút cuối danh sách 1. // Delete the tail node 2. void delTail(tList *list){ 3. tNode *delNode = list->tail; 4. if(delNode==NULL) // (1) 5. return; 6. tNode *i = list->head; 7. if(i==delNode){ // (2) 8. list->head=NULL; 9. list->tail=NULL; 10. }else{ 11. while(i->next!=delNode) // (3) 12. i = i->next; 13. i->next = NULL; // (4) 14. list->tail = i; // (4) 15. } 16. free(delNode); // (5) 17.} 40 Cấu trúc dữ liệu và giải thuật - DSLK
41. Xoá một nút bất kỳ cho trước  Xoá một nút bất kỳ cho trước  Có thể vận dụng các hàm đã biết  Ví dụ:  Nút cần xoá là head?  Gọi delHead  Nút cần xoá là tail?  Gọi delTail  Tìm nút trước nút cần xoá  Gọi delAfter 41 Cấu trúc dữ liệu và giải thuật - DSLK
42. Xoá một nút bất kỳ cho trước 1. // Delete a given node 2. void delGivenNode(tList *list, tNode *delNode) 3. { 4. if(delNode == list->head) 5. delHead(list); 6. else if(delNode == list->tail) 7. delTail(list); 8. else{ 9. tNode *tempNode = list->head; 10. while(tempNode && tempNode->next!=delNode) 11. tempNode = tempNode->next; 12. if(tempNode) 13. delAfter(list, tempNode); 14. } 15.} 42 Cấu trúc dữ liệu và giải thuật - DSLK
43. Xoá toàn bộ danh sách 1. // Remove all list 2. void removeList(tList *list) 3. { 4. tNode *node; 5. while(list->head) 6. { 7. node=list->head; 8. list->head = node->next; 9. free(node); 10. } 11. list->tail = NULL; 12.} 43 Cấu trúc dữ liệu và giải thuật - DSLK
44. Xoá toàn bộ danh sách  Đơn giản hơn 1. // Remove all list 2. void removeList(tList *list) 3. { 4. while(list->head) 5. delHead(list); 6. } 44 Cấu trúc dữ liệu và giải thuật - DSLK
45. Vận dụng  Bài tập: Container tracking  Bổ sung thao tác xoá container  Xoá một container bất kỳ (Nhập ID)  Xoá toàn bộ danh sách 45 Cấu trúc dữ liệu và giải thuật - DSLK
46. Sắp xếp danh sách – Interchange sort 1. // Sắp xếp tăng dần 2. void interchangeSort(tList *list) 3. { 4. tNode *i, *j; 5. for(i = list->head; i!=list->tail; i=i->next) 6. for(j = i->next; j!=NULL; j=j->next) 7. if(i->data > j->data) 8. swapData(i, j); 9. } 46 Cấu trúc dữ liệu và giải thuật - DSLK
47. Sắp xếp danh sách – Selection sort 1. // Sắp xếp giảm dần 2. void selectionSort(tList *list) 3. { 4. tNode *i, *j, *max; 5. for(i = list->head; i!=list->tail; i=i->next) 6. { 7. max = i; 8. for(j = i->next; j!=NULL; j=j->next) 9. if(max->data data) 10. max = j; 11. if(i!=max) 12. swapData(i, max); 13. } 14.} 47 Cấu trúc dữ liệu và giải thuật - DSLK
48. Sắp xếp danh sách  Một số thuật toán không được ưa thích trên danh sách liên kết đơn  Danh sách liên kết đơn khó duyệt lùi  Vẫn có thể cài đặt được các thuật toán 48 Cấu trúc dữ liệu và giải thuật - DSLK
49. Vận dụng  Bài tập: Container tracking  Bổ sung tác vụ sắp xếp container  Theo khối lượng đang chứa  Tạo menu để thực hiện các tác vụ đã tạo. 49 Cấu trúc dữ liệu và giải thuật - DSLK
50. Menu 1. Nhập container mới 2. Xuất thông tin các container 3. Liệt kê các container đang dùng 4. Đếm số lượng container rỗi 5. Tính tổng khối lượng hàng hoá 6. Tìm địa chỉ GPS của một container 7. Cập nhật thông tin của một container 8. Sắp xếp danh sách theo khối lượng 9. Xoá một container 10. Xoá toàn bộ danh sách 11. Thoát chương trình 50 Cấu trúc dữ liệu và giải thuật - DSLK