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
热门推荐
6 保研的祝福语简短
10 年轻20岁祝福语简短
11 朋友结婚祝福语信息简短
12 女孩婚礼贺卡祝福语简短
13 30段点歌简短祝福语
14 虎年春节祝福语图文简短
15 写给后妈祝福语大全简短
16 简短回复生日祝福语
17 校长送毕业祝福语简短
18 毕业立体贺卡祝福语简短