โปรแกรม C++ เพื่อทำการค้นหาโดยใช้รายการจัดระเบียบตนเอง

การจัดรายการด้วยตนเองโดยทั่วไปจะอัปเดตรายการของช่วงที่กำหนดโดยพิจารณาจากรายการที่ค้นหาล่าสุด ในวิธีนี้จะใช้วิธีการค้นหาตามลำดับ อัลกอริธึมนี้จะย้ายข้อมูลที่สำคัญกว่าไปยังจุดเริ่มต้นของรายการ ความซับซ้อนของเวลาของเทคนิคการค้นหานี้คือ O(n)

อัลกอริทึม

Begin
   Function FibonacciSearch().
   Calculate the mid value using ‘start+fib[index-2]’ expression.
   If the chosen item is equal to the value at mid index, print result and return to main.
   If it is lesser than the value at mid index, proceed with the left sub-array.
   If it is more than the value at mid index, proceed with the right sub-array.
   If the calculated mid value is equal to either start or end then the item is not found in the array.
End

โค้ดตัวอย่าง

#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 = new 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 = new node;
   temp = head;
   cout<<"\n The list state is :";
   while(temp->next != NULL) {
      cout<<"->"<<temp->d;
      temp = temp->next;
   }
}
node* SearchItem(node *head, int item) {
   int flag = 0;
   node *temp = new node;
   node *t = new node;
   temp = head;
   if(temp->d == item) {
      cout<<"\nItem found at head node";
      flag = 5;
      Display(head);
      return head;
   } else {
      while((temp->next)->next != NULL) {
         if((temp->next)->d == item) {
            cout<<"\nItem found";
            flag = 5;
            break;
         }
         temp = temp->next;
      }
      t = (temp->next)->next;
      (temp->next)->next = head;
      head = temp->next;
      temp->next = t;
      if(flag == 5)
         Display(head);
      else
         cout<<"\nItem not found.";
   }
   return head;
}
int main() {
   int i, n;
   char ch;
   node *head = new node;
   head = NULL;
   for(i = 1; i < 20; i++)
      head = InsertIntoList(head, i);
      Display(head);
   up:
      cout<<"\nEnter the Element to be searched: ";
      cin>>n;
      head = SearchItem(head, n);
      cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
      cin>>ch;
      if(ch == 'y' || ch == 'Y')
         goto up;
      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.
Do you want to search more...enter choice(y/n)?n