Danh sách liên kết vòng(Circular Linked List) là danh sách liên kết có thêm sự kết nối giữa 2 phần tử đầu tiên và phần tử cuối cùng để tạo thành vòng khép kín. Bài viết này Nguyễn Văn Hiếu sẽ hướng dẫn bạn cách cài đặt DSLK vòng trong C/C++ nhé.
1. Lý thuyết về danh sách liên kết vòng
Đó là sự khác biệt giữa DSLK vòng và danh sách liên kết đơn. Tất nhiên, bạn cũng có thể cài đặt DSLK vòng trên danh sách liên kết đôi. Tuy nhiên, trong bài này tôi sẽ hướng dẫn bạn cài đặt trên danh sách liên kết đơn trước nhé.
2. Cài đặt DSLK vòng đơn
Khai báo kiểu dữ liệu Node
Khai báo Node của DSLK vòng trong bài này giống với danh sách liên kết đơn
|
1 2 3 4 5 6 |
struct Node { int data; struct Node * next; }; typedef struct Node NODE; |
Tạo mới Node
|
1 2 3 4 5 |
NODE * CreateNewNode(int data) { NODE * newNode = (NODE *) malloc (sizeof(NODE)); newNode -> data = data; return newNode; } |
Lấy số lượng Node
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int Length(NODE * tail) { NODE * current = tail; int i = 1; if (tail == NULL) { return 0; } else { current = current -> next; while (current != tail) { i++; current = current -> next; } } return i; } |
Thêm vào đầu
|
1 2 3 4 5 6 7 8 9 10 11 |
NODE * InsertAtHead(NODE * tail, int data) { NODE * newNode = CreateNewNode(data); if (tail == NULL) { tail = newNode; newNode -> next = newNode; } else { newNode -> next = tail -> next; tail -> next = newNode; } return tail; } |
Thêm vào cuối
Trong Circular Linked List, để thêm vào cuối bạn có thể thêm vào đầu và trả về đầu mới là next của node mới thêm vào.
|
1 2 3 4 |
NODE * InsertAtEnd(NODE * tail, int data) { // simply insert at head and return the next node pointed by tail return InsertAtHead(tail, data) -> next; } |
Thêm vào vị trí bất kỳ
Các bạn lưu ý là vị trí, không phải chỉ số nhé. Do đó, phần tử đầu tiên có vị trí là 1 và phần tử cuối là len.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
NODE * InsertAtArbitrary(NODE * tail, int data, int location) { int len = length(tail), i; if (location < 1 || location > len + 1) { printf("\nInvalid location to enter data\n"); } else { if (tail == NULL) return InsertAtHead(tail, data); NODE * newNode = CreateNewNode(data), * current = tail; for (i = 1; i != location; i++) current = current -> next; newNode -> next = current -> next; current -> next = newNode; if (location == len + 1) tail = newNode; } return tail; } |
Xóa theo giá trị chỉ định
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
NODE * DeleteByValue(NODE * tail, int data) { NODE * current = tail, * previous; if (tail == NULL) return tail; else if (tail == tail -> next) { if (tail -> data == data) { tail = NULL; free(current); } return tail; } do { previous = current; current = current -> next; if (current -> data == data) { previous -> next = current -> next; if (current == tail) tail = previous; free(current); current = previous -> next; } } while (current != tail); return tail; } |
Xóa theo vị trí chỉ định
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
NODE * DeleteByLocation(NODE * tail, int location) { NODE * current, * previous = tail; int len = Length(tail), i; if (location < 1 || location > len) { printf("Invalid Location to delete"); } else if (len == 1) { tail = NULL; free(current); } else { current = tail -> next; for (i = 1; i < location; i++) { previous = current; current = current -> next; } previous -> next = current -> next; if (current == tail) tail = previous; free(current); } return tail; } |
Sắp xếp theo giá trị tăng dần
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
NODE * Sort(NODE * tail) { if (Length(tail) < 2) return tail; NODE * ptr1 = tail -> next, * ptr2, * min; int temp; // selection sort implementation while (ptr1 -> next != tail -> next) { min = ptr1; ptr2 = ptr1 -> next; while (ptr2 != tail -> next) { if (min -> data > ptr2 -> data) min = ptr2; ptr2 = ptr2 -> next; } if (min != ptr1) { temp = min -> data; min -> data = ptr1 -> data; ptr1 -> data = temp; } ptr1 = ptr1 -> next; } return tail; } |
3. Full code DSLK vòng đơn
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 |
#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node * next; }; typedef struct Node NODE; NODE * CreateNewNode(int data) { NODE * newNode = (NODE *) malloc (sizeof(NODE)); newNode -> data = data; return newNode; } void Display(NODE * tail) { NODE * current = tail; if (tail != NULL) { do { current = current -> next; printf(" %d -> ", current -> data); } while (current != tail); } } int Length(NODE * tail) { NODE * current = tail; int i = 1; if (tail == NULL) { return 0; } else { current = current -> next; while (current != tail) { i++; current = current -> next; } } return i; } NODE * InsertAtHead(NODE * tail, int data) { NODE * newNode = CreateNewNode(data); if (tail == NULL) { tail = newNode; newNode -> next = newNode; } else { newNode -> next = tail -> next; tail -> next = newNode; } return tail; } NODE * InsertAtEnd(NODE * tail, int data) { // simply insert at head and return the next node pointed by tail return InsertAtHead(tail, data) -> next; } NODE * InsertAtArbitrary(NODE * tail, int data, int location) { int len = Length(tail), i; if (location < 1 || location > len + 1) { printf("\nInvalid location to enter data\n"); } else { if (tail == NULL) return InsertAtHead(tail, data); NODE * newNode = CreateNewNode(data), * current = tail; for (i = 1; i != location; i++) current = current -> next; newNode -> next = current -> next; current -> next = newNode; if (location == len + 1) tail = newNode; } return tail; } NODE * DeleteByValue(NODE * tail, int data) { NODE * current = tail, * previous; if (tail == NULL) return tail; else if (tail == tail -> next) { if (tail -> data == data) { tail = NULL; free(current); } return tail; } do { previous = current; current = current -> next; if (current -> data == data) { previous -> next = current -> next; if (current == tail) tail = previous; free(current); current = previous -> next; } } while (current != tail); return tail; } NODE * DeleteByLocation(NODE * tail, int location) { NODE * current, * previous = tail; int len = Length(tail), i; if (location < 1 || location > len) { printf("Invalid Location to delete"); } else if (len == 1) { tail = NULL; free(current); } else { current = tail -> next; for (i = 1; i < location; i++) { previous = current; current = current -> next; } previous -> next = current -> next; if (current == tail) tail = previous; free(current); } return tail; } NODE * sort(NODE * tail) { if (Length(tail) < 2) return tail; NODE * ptr1 = tail -> next, * ptr2, * min; int temp; // selection sort implementation while (ptr1 -> next != tail -> next) { min = ptr1; ptr2 = ptr1 -> next; while (ptr2 != tail -> next) { if (min -> data > ptr2 -> data) min = ptr2; ptr2 = ptr2 -> next; } if (min != ptr1) { temp = min -> data; min -> data = ptr1 -> data; ptr1 -> data = temp; } ptr1 = ptr1 -> next; } return tail; } int main() { NODE * cll = NULL; int option, data, location; while (1) { Display(cll); printf("\nlength = %d\n", Length(cll)); printf("\n\nMENU OF CHOICE\n1. Insert at head\n2. Insert at end\n3. Insert at arbitrary location\n4. Delete by value\n5. Delete by location\n6. Sort\n7. Exit\n"); printf("Your choice: "); scanf("%d", &option); if (option == 1) { printf("Enter data to be inserted: "); scanf("%d", &data); cll = InsertAtHead(cll, data); } else if (option == 2) { printf("Enter data to be inserted at end: "); scanf("%d", &data); cll = InsertAtEnd(cll, data); } else if (option == 3) { printf("Enter data to be inserted: "); scanf("%d", &data); printf("Enter location to be inserted into: "); scanf("%d", &location); cll = InsertAtArbitrary(cll, data, location); } else if (option == 4) { printf("Enter value to be deleted: "); scanf("%d", &data); cll = DeleteByValue(cll, data); } else if (option == 5) { printf("Enter location to be deleted: "); scanf("%d", &location); cll = DeleteByLocation(cll, location); } else if(option == 6) { sort(cll); } else if (option == 7) { break; } } return 0; } |
Kết quả chạy:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: 1 Enter data to be inserted: 1 1 -> length = 1 MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: 1 Enter data to be inserted: 2 2 -> 1 -> length = 2 MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: 1 Enter data to be inserted: 3 3 -> 2 -> 1 -> length = 3 MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: 1 Enter data to be inserted: 4 4 -> 3 -> 2 -> 1 -> length = 4 MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: 1 Enter data to be inserted: 5 5 -> 4 -> 3 -> 2 -> 1 -> length = 5 MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: 6 1 -> 2 -> 3 -> 4 -> 5 -> length = 5 MENU OF CHOICE 1. Insert at head 2. Insert at end 3. Insert at arbitrary location 4. Delete by value 5. Delete by location 6. Sort 7. Exit Your choice: |
4. Danh sách liên kết vòng đôi
Với dslk vòng đôi, nếu bạn nào quan tâm có thể tham khảo source code sau đây. Mình xin phép không đi sâu giải thích nữa.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <stdio.h> #include <stdlib.h> struct node{ int data; struct node *llink; struct node *rlink; }; typedef struct node *Node; Node CreateNode(int data){ Node temp = (Node) malloc(sizeof(struct node)); temp->llink = temp; temp->rlink = temp; temp->data = data; return temp; } void DeleteNode(Node temp) { printf("%d deleted\n", temp->data); free(temp); return; } void InsertFront(Node head, int data) { Node newNode = CreateNode(data); Node first = head->rlink; head->rlink = newNode; newNode->rlink = first; newNode->llink = head; if(first !=NULL) first->llink = newNode; } void DeleteRear(Node head) { if(head->rlink == head) { puts("List is empty"); return; } Node last = head->llink; Node slast = last->llink; slast->rlink = head; head->llink = slast; DeleteNode(last); } void Display(Node head) { Node current = head->rlink; if(current == head) { puts("List is empty"); return; } puts("Contents of the Circular Doubly Linked list are"); while(current!=head) { printf("%d ", current->data); current = current->rlink; } puts(""); } int main() { int choice, ex=0, data; Node head = CreateNode(0); while(!ex) { printf("Enter your choice\n1 Insert front\n2 Delete rear\n3 Display\n4 Exit\n>>> "); scanf("%d",&choice); switch(choice) { case 1: printf("Enter the data: "); scanf("%d", &data); InsertFront(head, data); break; case 2: DeleteRear(head); break; case 3: Display(head); break; default: ex=1; } } return 0; } |
Kết quả chạy:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
Enter your choice 1 Insert front 2 Delete rear 3 Display 4 Exit >>> 1 Enter the data: 5 Enter your choice 1 Insert front 2 Delete rear 3 Display 4 Exit >>> 1 Enter the data: 4 Enter your choice 1 Insert front 2 Delete rear 3 Display 4 Exit >>> 1 Enter the data: 3 Enter your choice 1 Insert front 2 Delete rear 3 Display 4 Exit >>> 1 Enter the data: 2 Enter your choice 1 Insert front 2 Delete rear 3 Display 4 Exit >>> 3 Contents of the Circular Doubly Linked list are 2 3 4 5 Enter your choice 1 Insert front 2 Delete rear 3 Display 4 Exit >>> |
Như vậy, sau bài này mình đã hoàn thành phần hướng dẫn về cấu trúc dữ liệu danh sách liên kết. Ở bài viết tiếp theo, mình sẽ hướng dẫn các bạn kiến thức về cấu trúc dữ liệu Cây(Tree). Mong được các bạn quan tâm và chia sẻ cho bạn bè của mình. Thân ái!
