Chương trình C++ triển khai danh sách liên kết đơn đã sắp xếp (Sorted 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 đó.

Phát triển chương trình C++ triển khai danh sách liên kết đơn đã 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.
    Khởi tạo con trỏ next với NULL.
    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 NULL.
      Nếu 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 đã 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 đã sắp xếp
2	3	4	6	7	2