Danh sách liên kết vòng đơn, vòng đôi
| |

Danh sách liên kết vòng – Circular Linked List

ByNguyễn Văn Hiếu

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

Danh sách liên kết vòng có kết nối của phần tử cuối với head
Danh sách liên kết vòng có kết nối của phần tử cuối với head

Đó 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 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

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 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:

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.

Danh sách liên kết vòng đôi(Circular Doubly Linked List)
Hình ảnh mô phỏng DSLK vòng đôi(Circular Doubly Linked List)
#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:

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!

Similar Posts

Cây Đỏ Đen (Red-Black Tree) – Phần 3 (Delete)
|

Cây Đỏ Đen (Red-Black Tree) – Phần 3 (Delete)

ByNguyễn Tấn Phát

Ở bài trước, chúng ta đã hoàn thành việc insert một Node vào Red Back Tree. Còn bây giờ, hãy cũng tìm cách để xóa một node khỏi cây đỏ đen nào. Phần 1: Giới thiệu về cây đỏ đen Phần 2: Cây đỏ đen – Thao tác Chèn Xóa (Delete) là một quá trình…

Tạo dãy số ngẫu nhiên không trùng trong C/C++

Tạo dãy số ngẫu nhiên không trùng trong C/C++

ByNguyễn Văn Hiếu

Làm sao để tạo dãy số ngẫu nhiên không trùng nhau trong C/C++? Hãy cùng Nguyễn Văn Hiếu đi giải quyết bài toán sinh số ngẫu nhiên không trùng trong bài viết này nhé. Mình sẽ hướng dẫn các bạn hai cách khác nhau để tạo dãy số ngẫu nhiên không trùng lặp. Bắt đầu…

Tính tổng các chữ số trong một số – bài tập lập trình C cơ bản

Tính tổng các chữ số trong một số – bài tập lập trình C cơ bản

ByLê Xuân Huy

Viết chương trình Tính tổng các chữ số trong một số n ? Đây là một bài tập khá hay :D, tuy nó cũng khá đơn giản thôi, nhưng cái mà nó mang lại cho chúng ta không hề giản đơn như chúng  ta nghĩ là đơn giản :v. Vậy thì bài tập này cho…

Subscribe
Notify of
guest
1 Bình luận
Inline Feedbacks
View all comments