Bài giảng Cấu trúc dữ liệu và giải thuật - Doubly/Circular linked list - Ngô Hữu Dũng

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Doubly/Circular linked list - Ngô Hữu Dũng

1. INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY Data structures and algorithms Doubly/Circular linked list Dr. Ngo Huu Dung
2. Dẫn nhập  Danh sách liên kết đôi  Hai chiều  Thêm con trỏ previous  Từ một nút có thể duyệt đến nút trước và sau nó  Các thao tác tương tự singly linked list  Xử lý thêm cho con trỏ previous  Danh sách liên kết vòng  Nút cuối trỏ đến nút đầu  Có thể là danh sách đơn hoặc đôi  Các thao tác tương tự 2 Cấu trúc dữ liệu và giải thuật - DSLK
3. prev data next prev data next prev data next tail head NULL NULL Doubly linked list Danh sách liên kết đôi
4. Doubly 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. { prev data next 3. int data; 4. struct Node *next; 5. struct Node *prev; 6. }; 7. typedef struct Node tNode; head 8. tNode *head; tail 9. tNode *tail; 4 Cấu trúc dữ liệu và giải thuật - DSLK
5. 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 5 Cấu trúc dữ liệu và giải thuật - DSLK
6. 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 đôi 6. struct Node *prev; 7. };  Các thao tác cơ bản 8. typedef struct Node tNode; trên danh sách liên kết 9. // Kiểu danh sách 10.struct List đôi 11.{ 12. tNode *head;  Menu thực hiện 13. tNode *tail; 14.}; 15.typedef struct List tList; 16.// Biến danh sách 17.tList ds; 6 Cấu trúc dữ liệu và giải thuật - DSLK
7. Một số hàm tạo, thêm và chèn phần tử 1. // Initiate a new list 2. void init(tList *); // Giống singly linked list 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 *); 7 Cấu trúc dữ liệu và giải thuật - DSLK
8. Tạo một nút mới prev data next 1. Cấp phát bộ nhớ newNode (2) (1)  Hàm malloc hoặc new (4) (3) 2. NULL NULL Nhập dữ liệu 1. // Make a new node 3. Khởi tạo next rỗng 2. tNode* makeNode() 4. Khởi tạo prev rỗng 3. { 4. tNode *newNode; 5. newNode = (tNode*)malloc(sizeof(tNode)); 6. // newNode = new tNode; // (1) 7. printf("Nhap du lieu: "); 8. scanf("%d", &newNode->data); // (2) 9. newNode->next = NULL; // (3) 10. newNode->prev = NULL; // (4) 11. return newNode; 12.} 8 Cấu trúc dữ liệu và giải thuật - DSLK
9. Thêm nút mới vào đầu danh sách  Tạo nút mới  Thêm vào đầu danh sách  Danh sách rỗng? (1) NULL head (4) (3) (2) newNode NULL NULL 9 Cấu trúc dữ liệu và giải thuật - DSLK
10. 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(); 6. if(list->head == NULL){ // (1) 7. list->head = newNode; 8. list->tail = newNode; 9. }else{ // not empty 10. newNode->next = list->head; // (2) 11. list->head->prev = newNode; // (3) 12. list->head = newNode; // (4) 13. } 14.} 10 Cấu trúc dữ liệu và giải thuật - DSLK
11. Thêm nút mới vào cuối danh sách  Tạo nút mới  Thêm vào cuối danh sách  Danh sách rỗng? (1)  Danh sách không rỗng? NULL NULL newNode (2) (3) (4) tail NULL 11 Cấu trúc dữ liệu và giải thuật - DSLK
12. 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(); 6. 7. if(!list->head){ // (1) 8. list->head = newNode; 9. list->tail = newNode; 10. }else{ // Not empty 11. newNode->prev = list->tail; // (2) 12. list->tail->next = newNode; // (3) 13. list->tail = newNode; // (4) 14. } 15.} 12 Cấu trúc dữ liệu và giải thuật - DSLK
13. Chèn một nút vào sau một nút  Chèn nút insertNode vào sau givenNode  givenNode hoặc insertNode rỗng? (1)  Trường hợp givenNode là nút cuối? (2) insertNode (6) (5) (4) (3) givenNode 13 Cấu trúc dữ liệu và giải thuật - DSLK
14. Chèn một nút vào sau một nút 1. // Insert a node after a given node 2. void insertAfter(tList *list, tNode *givenNode, tNode *insertNode) 3. { 4. if(givenNode==NULL||insertNode==NULL) //(1) 5. return; 6. if(!givenNode->next) //(2) 7. list->tail = insertNode; 8. else 9. givenNode->next->prev = insertNode; //(3) 10. insertNode->next = givenNode->next; //(4) 11. givenNode->next = insertNode; //(5) 12. insertNode->prev = givenNode; //(6) 13.} 14 Cấu trúc dữ liệu và giải thuật - DSLK
15. Một số hàm duyệt danh sách  Tương tự danh sách liên kết đơn  Có thể duyệt từ tail 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); 15 Cấu trúc dữ liệu và giải thuật - DSLK
16. Duyệt danh sách 1. tNode *node = list.head; 2. while(node){ 3. // Thao tác xử lý 4. node = node->next; 5. } 6. for(node = list.head; node; node = node->next) 7. // Thao tác xử lý 8. tNode *node = list.tail; 9. while(node){ 10. // Thao tác xử lý 11. node = node->prev; 12.} 13.for(node = list.tail; node; node = node->prev) 14. // Thao tác xử lý 16 Cấu trúc dữ liệu và giải thuật - DSLK
17. 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 any given node 8. void delNode(tList *, tNode *); 9. // Remove all list – similar to singly linked list 10.void removeList(tList *); 17 Cấu trúc dữ liệu và giải thuật - DSLK
18. Xoá nút đầu danh sách  Danh sách rỗng? (1) (2) head (3) NULL NULL  Nút cần xoá là nút cuối cùng?  Trở thành danh sách rỗng, điều chỉnh tail (4)  Giải phóng bộ nhớ (5) 18 Cấu trúc dữ liệu và giải thuật - DSLK
19. 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) // (1) 6. return; 7. // head point to next node 8. list->head = delNode->next; // (2) 9. if(list->head) 10. list->head->prev = NULL; // (3) 11. else 12. list->tail = NULL; // (4) 13. free(delNode); // (5) 14.} 19 Cấu trúc dữ liệu và giải thuật - DSLK
20. Xoá nút sau nút cho trước  givenNode hoặc givenNode next rỗng? (1) (2) givenNode (3)  givenNode là nút cuối? (4)  Giải phóng bộ nhớ (5) 20 Cấu trúc dữ liệu và giải thuật - DSLK
21. 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. if(!givenNode || !givenNode->next) //(1) 5. return; 6. tNode *delNode = givenNode->next; 7. givenNode->next = delNode->next; //(2) 8. if(delNode->next) 9. delNode->next->prev = givenNode; //(3) 10. else 11. list->tail = givenNode; //(4) 12. free(delNode); //(5) 13.} 21 Cấu trúc dữ liệu và giải thuật - DSLK
22. Xoá nút cuối danh sách  Tương tự xoá đầu danh sách  Đảo ngược, tail thay vì head, prev thay vì next  Danh sách rỗng? (1) (2) tail (3) NULL NULL  Nút cần xoá là nút cuối cùng?  Trở thành danh sách rỗng, điều chỉnh head (4)  Giải phóng bộ nhớ (5) 22 Cấu trúc dữ liệu và giải thuật - DSLK
23. Xoá nút cuối danh sách 1. // Delete the tail node 2. void delTail(tList *list) 3. { 4. tNode *delNode = list->tail; 5. if(!delNode) // (1) 6. return; 7. // tail point to previous node 8. list->tail = delNode->prev; // (2) 9. if(list->tail) // Not empty 10. list->tail->next = NULL; // (3) 11. else // Become empty 12. list->head = NULL; // (4) 13. free(delNode); // (5) 14.} 23 Cấu trúc dữ liệu và giải thuật - DSLK
24. Xoá một nút bất kỳ cho trước  Hàm tổng quát, xoá bất kỳ nút nào (1) head tail delNode prev delNode next delNode (2) 24 Cấu trúc dữ liệu và giải thuật - DSLK
25. Xoá một nút bất kỳ cho trước 1. // Delete any given node 2. void delGivenNode(tList *list, tNode *delNode) 3. { 4. if(!delNode || !list->head) 5. return; 6. if(delNode == list->head) 7. list->head = delNode->next; //(1) 8. if(delNode->prev) 9. delNode->prev->next = delNode->next;//(1) 10. if(delNode == list->tail) 11. list->tail = delNode->prev; //(2) 12. if(delNode->next) 13. delNode->next->prev = delNode->prev;//(2) 14. free(delNode); 15.} 25 Cấu trúc dữ liệu và giải thuật - DSLK
26. Sắp xếp danh sách 1. /* Tương tự danh sách đơn khi ta giữ nguyên liên kết và chỉ hoán vị dữ liệu*/ 2. // Sắp xếp tăng dần 3. void selectionSort(tList *list) 4. { 5. tNode *i, *j, *min; 6. for(i = list->head; i!=list->tail; i=i->next) 7. { 8. min = i; 9. for(j = i->next; j!=NULL; j=j->next) 10. if(min->data > j->data) 11. min = j; 12. if(i!=min) 13. swapData(i, min); 14. } 15.} 26 Cấu trúc dữ liệu và giải thuật - DSLK
27. Vận dụng  Bài tập: Quiz  Chương trình thi trắc nghiệm dễ dàng chuyển đến câu hỏi tiếp theo hoặc câu hỏi trước đó.  Thao tác cơ bản  Thêm câu hỏi,  Xoá câu hỏi,  Sửa câu hỏi,  Tiến hành thi, chấm điểm 27 Cấu trúc dữ liệu và giải thuật - DSLK
28. head head Danh sách liên kết vòng Circular linked list
29. Liên kết vòng  Có thể là danh sách đơn hoặc đôi  Không có nút cuối trỏ vào NULL  Nút “cuối” nối vào nút đầu tiên  Từ phần tử bất kỳ có thể duyệt toàn bộ danh sách  Phù hợp với các ứng dụng lặp xoay vòng  Các ứng dụng chạy trong hệ điều hành đa nhiệm  Các cấu trúc dữ liệu nâng cao  Hàng đợi ưu tiên (priority queue) 29 Cấu trúc dữ liệu và giải thuật - DSLK
30. Thao tác cơ bản – so sánh  Khởi tạo danh sách, nút mới  Tương tự Singly/Doubly linked list  Thêm phần tử  Chú ý nút cuối trỏ trở lại nút đầu  Duyệt danh sách  Điều kiện dừng là trở lại nút bắt đầu  Xoá phần tử  Chú ý nút cuối trỏ trở lại nút đầu  Sắp xếp  Điều kiện dừng của vòng lặp 30 Cấu trúc dữ liệu và giải thuật - DSLK
31. Thêm nút vào đầu danh sách 1. // Add a new node to the head of list 2. void addHead(tList *list) 3. { 4. tNode *newNode = makeNode(); 5. if(list->head == NULL){ 6. list->head = newNode; 7. list->tail = newNode; 8. newNode->next = newNode; //Link to head 9. }else{ 10. newNode->next = list->head; 11. list->head = newNode; 12. list->tail->next = newNode; //Link to head 13. } 14.} 31 Cấu trúc dữ liệu và giải thuật - DSLK
32. Duyệt danh sách 1. // Traversing a given Circular linked list 2. // Start from head and end at head 3. // Print all list 4. void printList(tList list) 5. { 6. tNode *node = list.head; 7. printf("The linked list: "); 8. if(node) // Not empty list 9. { 10. do{ 11. printf("%d ", node->data); 12. node = node->next; 13. }while(node != list.head); // !? 14. }else 15. printf("Empty."); 16.} 32 Cấu trúc dữ liệu và giải thuật - DSLK
33. 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) 6. return; 7. if(list->head == list->tail) 8. { 9. list->head = NULL; 10. list->tail = NULL; 11. }else{ 12. list->head = delNode->next; 13. list->tail->next = list->head; //!? 14. } 15. free(delNode); 16.} 33 Cấu trúc dữ liệu và giải thuật - DSLK
34. Sắp xếp danh sách 1. // Sort to ascending list 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!=list->head; j=j->next) 7. if(i->data > j->data) 8. swapData(i, j); 9. } 34 Cấu trúc dữ liệu và giải thuật - DSLK
35. Without the tail !? 1. // Add a new node at the beginning 2. void addNode(tList *list) 3. { 4. tNode *newNode = makeNode(); 5. tNode *temp = list->head; 6. newNode->next = list->head; 7. if(list->head) 8. { 9. while(temp->next != list->head) 10. temp = temp->next; 11. temp->next = newNode; 12. } 13. else 14. newNode->next = newNode; //For the first node 15. list->head = newNode; 16.} 35 Cấu trúc dữ liệu và giải thuật - DSLK