Chương trình C++ thực hiện tìm kiếm sử dụng Danh sách tự tổ chức (Self-Organizing Lists)

Danh sách tự tổ chức (Self-Organizing list) cơ bản cập nhật danh sách các mục trong phạm vi đã cho dựa trên mục được tìm kiếm gần đây nhất. Trong phương pháp này, phương pháp tìm kiếm tuần tự được sử dụng. Thuật toán này dịch chuyển dữ liệu quan trọng hơn đến đầu danh sách. Độ phức tạp thời gian của kỹ thuật tìm kiếm này là O(n).

Thuật toán

Bắt đầu
  Hàm SearchItem().
  Duyệt danh sách để tìm mục.
  Nếu tìm thấy tại nút đầu, in thông báo và trả về.
  Nếu tìm thấy tại nút khác, di chuyển nút đó lên đầu danh sách (Move-to-front heuristic).
  Nếu không tìm thấy, in thông báo.
  Hiển thị trạng thái danh sách sau mỗi lần tìm kiếm.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

struct node {
    int d;
    node *next;
};

node* CreateNode(int d) {
    node *newnode = new node;
    newnode->d = d;
    newnode->next = NULL;
    return newnode;
}

node* InsertIntoList(node *head, int d) {
    node *temp = CreateNode(d);
    node *t = head;
    if (head == NULL) {
        head = temp;
        return head;
    } else {
        while (t->next != NULL)
            t = t->next;
        t->next = temp;
    }
    return head;
}

void Display(node *head) {
    node *temp = head;
    cout << "\n Trạng thái danh sách là :";
    while (temp != NULL) {
        cout << "->" << temp->d;
        temp = temp->next;
    }
}

node* SearchItem(node *head, int item) {
    int flag = 0;
    node *temp = head;
    node *t = new node;
    if (temp->d == item) {
        cout << "\nMục tìm thấy tại nút đầu";
        flag = 5;
        Display(head);
        return head;
    } else {
        while (temp->next != NULL) {
            if (temp->next->d == item) {
                cout << "\nMục tìm thấy";
                flag = 5;
                break;
            }
            temp = temp->next;
        }
        if (temp->next != NULL) {
            t = temp->next->next;
            temp->next->next = head;
            head = temp->next;
            temp->next = t;
        }
        if (flag == 5)
            Display(head);
        else
            cout << "\nMục không tìm thấy.";
    }
    return head;
}

int main() {
    int i, n;
    char ch;
    node *head = NULL;
    for (i = 1; i < 20; i++)
        head = InsertIntoList(head, i);
    Display(head);
    up:
    cout << "\nNhập phần tử cần tìm: ";
    cin >> n;
    head = SearchItem(head, n);
    cout << "\n\n\tBạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?";
    cin >> ch;
    if (ch == 'y' || ch == 'Y')
        goto up;
    return 0;
}

Kết quả

Trạng thái danh sách là :->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18
Nhập phần tử cần tìm: 7
Mục tìm thấy
Trạng thái danh sách là :->7->1->2->3->4->5->6->8->9->10->11->12->13->14->15->16->17->18
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?y
Nhập phần tử cần tìm: 20
Mục không tìm thấy.
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?n