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
热门推荐
5 初八的祝福语简短
7 入学校简短祝福语
10 给男生的简短祝福语
11 妈妈生日祝福语简短温暖
12 创业大吉祝福语简短
13 新老师祝福语 简短独特
14 祝福语美甲店员工简短
15 对睡觉的祝福语简短
16 小伙买车祝福语大全简短
17 礼盒宝宝生日祝福语简短
18 祝福语同事离职英文简短