Chương trình C++ triển khai danh sách liên kết đơn vòng đã sắp xếp (Sorted Circularly Singly Linked List)

Trong cấu trúc dữ liệu, Danh sách liên kết (Linked List) là tập hợp tuyến tính các phần tử dữ liệu. Mỗi phần tử hoặc nút của danh sách bao gồm hai mục - dữ liệu và tham chiếu đến nút tiếp theo. Nút cuối cùng có tham chiếu đến null. Điểm vào của danh sách liên kết được gọi là đầu (head) của danh sách.

Mỗi nút trong danh sách lưu trữ nội dung và một con trỏ hoặc tham chiếu đến nút tiếp theo trong danh sách, trong danh sách liên kết đơn (singly linked list). Danh sách liên kết đơn không lưu trữ bất kỳ con trỏ hay tham chiếu nào đến nút trước đó.

Vì là danh sách liên kết đơn đã sắp xếp, nên các mục dữ liệu trong danh sách liên kết sẽ luôn giữ thứ tự đã sắp xếp.

Dưới đây là chương trình C++ triển khai Danh sách liên kết đơn vòng đã sắp xếp.

Thuật toán

Bắt đầu
  Hàm createnode() để chèn nút vào danh sách:
    Kiểm tra danh sách có rỗng không. Nếu rỗng, đặt nút làm phần tử đầu tiên và cập nhật head.
    Nếu danh sách không rỗng:
      Tạo newnode và chèn số vào trường data của newnode.
      newnode sẽ được chèn sao cho danh sách liên kết vẫn giữ thứ tự đã sắp xếp.
      Nếu chèn ở cuối, newnode trỏ đến head.
      Nếu newnode chèn ở đầu, danh sách liên kết bắt đầu từ đó.
Kết thúc

Bắt đầu
  Hàm display() để in nội dung danh sách có n nút:
    Khởi tạo c = 0.
    Khởi tạo biến con trỏ với địa chỉ bắt đầu.
    while (c <= n)
      In thông tin nút
      Cập nhật biến con trỏ
      Tăng c.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

struct nod {
    int d;
    nod *n;
} *p = NULL, *head = NULL, *q = NULL, *np = NULL;

int c = 0;

void createnode(int n) {
    np = new nod;
    np->d = n;
    np->n = NULL;
    if (c == 0) {
        head = np;
        p = head;
        p->n = head;
        c++;
    } else if (c == 1) {
        p = head;
        q = p;
        if (np->d < p->d) {
            np->n = p;
            head = np;
            p->n = np;
        } else if (np->d > p->d) {
            p->n = np;
            np->n = head;
        }
        c++;
    } else {
        p = head;
        q = p;
        if (np->d < p->d) {
            np->n = p;
            head = np;
            do {
                p = p->n;
            } while (p->n != q);
            p->n = head;
        } else if (np->d > p->d) {
            while (p->n != head && q->d < np->d) {
                q = p;
                p = p->n;
                if (p->n == head) {
                    p->n = np;
                    np->n = head;
                } else if (np->d < p->d) {
                    q->n = np;
                    np->n = p;
                    break;
                }
            }
        }
    }
}

void display(int i) {
    nod *t = head;
    int c = 0;
    while (c <= i) {
        cout << t->d << "\t";
        t = t->n;
        c++;
    }
}

int main() {
    int i = 0, n, a;
    cout << "Nhập số nút:\n";
    cin >> n;
    while (i < n) {
        cout << "\nNhập giá trị nút:\n";
        cin >> a;
        createnode(a);
        i++;
    }
    cout << "Danh sách liên kết đơn vòng đã sắp xếp" << endl;
    display(n);
    return 0;
}

Kết quả đầu ra

Nhập số nút: 5
Nhập giá trị nút: 6
Nhập giá trị nút: 4
Nhập giá trị nút: 7
Nhập giá trị nút: 3
Nhập giá trị nút: 2
Danh sách liên kết đơn vòng đã sắp xếp
2	3	4	6	7	2