자체 구성 목록을 사용하여 검색을 수행하는 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