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
struct Node {
int data;
struct Node * next;
};
typedef struct Node NODE;Tạo mới Node
NODE * CreateNewNode(int data) {
NODE * newNode = (NODE *) malloc (sizeof(NODE));
newNode -> data = data;
return newNode;
}Lấy số lượng Node
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
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.
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.
NODE * InsertAtArbitrary(NODE * tail, int data, int location) {
int len = length(tail), i;
if (location < 1 || location > len + 1) {
printf("nInvalid location to enter datan");
} 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
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
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
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
#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 datan");
} 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 = %dn", Length(cll));
printf("nnMENU OF CHOICEn1. Insert at headn2. Insert at endn3. Insert at arbitrary locationn4. Delete by valuen5. Delete by locationn6. Sortn7. Exitn");
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:
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.
#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 deletedn", 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 choicen1 Insert frontn2 Delete rearn3 Displayn4 Exitn>>> ");
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:
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!
Để lại một bình luận