โปรแกรม C++ ค้นหาด้วย Self-Organizing List (Move-to-Front)

ภาพรวม

Self-Organizing List เป็นโครงสร้างข้อมูลที่จัดเรียงตัวเองตามความถี่ในการเข้าถึง วิธี Move-to-Front จะย้ายโหนดที่เพิ่งค้นหาพบ ไปอยู่ที่หัวลิสต์ ทำให้การค้นหาครั้งต่อไปเร็วขึ้น ความซับซ้อนด้านเวลา O(n) แต่ประสิทธิภาพดีขึ้นสำหรับข้อมูลที่เข้าถึงบ่อย

อัลกอริธึม (Move-to-Front)

1. สร้าง Linked List จากข้อมูล
2. ค้นหาแบบ Sequential จากหัวลิสต์
3. ถ้าพบโหนดที่ต้องการ:
   • ถ้าอยู่หัวแล้ว → ไม่ต้องทำอะไร
   • ถ้าไม่ใช่หัว → ตัดโหนดออกและต่อที่หัวลิสต์
4. ถ้าไม่พบ → ลิสต์คงเดิม

โค้ดตัวอย่าง (แก้ไขลอจิก Move-to-Front ให้ถูกต้อง)

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* createNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;
    return newNode;
}

Node* insertAtEnd(Node* head, int data) {
    Node* newNode = createNode(data);
    if (head == nullptr) return newNode;
    
    Node* current = head;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

void display(Node* head) {
    cout << "\nThe list state is: ";
    Node* current = head;
    while (current != nullptr) {
        cout << current->data;
        if (current->next) cout << " -> ";
        current = current->next;
    }
}

Node* searchAndMoveToFront(Node* head, int item) {
    if (head == nullptr) {
        cout << "\nItem not found.";
        return head;
    }
    
    // พบที่หัว
    if (head->data == item) {
        cout << "\nItem found at head node";
        display(head);
        return head;
    }
    
    // ค้นหาและจดจำโหนดก่อนหน้า
    Node* prev = head;
    Node* current = head->next;
    
    while (current != nullptr) {
        if (current->data == item) {
            cout << "\nItem found";
            // Move to front
            prev->next = current->next;
            current->next = head;
            head = current;
            display(head);
            return head;
        }
        prev = current;
        current = current->next;
    }
    
    cout << "\nItem not found.";
    display(head);
    return head;
}

int main() {
    Node* head = nullptr;
    for (int i = 1; i <= 18; i++) {
        head = insertAtEnd(head, i);
    }
    display(head);
    
    char choice;
    do {
        int item;
        cout << "\nEnter the Element to be searched: ";
        cin >> item;
        head = searchAndMoveToFront(head, item);
        
        cout << "\n\nDo you want to search more...enter choice(y/n)? ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

The list state is: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18
Enter the Element to be searched: 7
Item found
The list state is: 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18

Do you want to search more...enter choice(y/n)? y
Enter the Element to be searched: 20
Item not found.
The list state is: 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18

Do you want to search more...enter choice(y/n)? n

กลยุทธ์ Self-Organizing อื่นๆ

• Transpose: สลับกับโหนดก่อนหน้า (ช้ากว่า Move-to-Front แต่เสถียรกว่า)
• Count: นับความถี่ และจัดเรียงตามความถี่ (ต้องการพื้นที่เก็บ counter)
• Move-to-Front: เรียบง่าย ที่สุด และมีคุณสมบัติ "Working Set Property"