線性表中各節(jié)點(diǎn)的檢索概率不等時(shí)，可用如下策略提高順序檢索的效率；若找到指定的結(jié)點(diǎn)，則將該結(jié)點(diǎn)和其前驅(qū)結(jié)點(diǎn)（若存在）交換，使得經(jīng)常被訪問(wèn)的結(jié)點(diǎn)盡量位于表的前端。試設(shè)計(jì)在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的線性表盤(pán)上實(shí)現(xiàn)上述策略的順序檢索算法。

#include <iostream>typedef struct node{struct node* next;int data;
}node,*pnode;pnode buynode(int x)
{pnode tmp=(pnode) malloc(sizeof (node));tmp->data=x,tmp->next= nullptr;return tmp;
}
typedef struct link_list{pnode head;
}link_list;void init_array(int* data,int size)
{printf("the original array is:");for(int i=0;i<size;i++) data[i]=i+1, printf("%3d",data[i]);puts("");
}void print(int*data,int size)
{for(int i=0;i<size;i++) printf("%3d",data[i]);puts("");
}
int array_visit(int* &data,int size,int search)
{for(int i=0;i<size;i++){if(data[i]==search&&i!=0){data[i]=data[i-1];data[i-1]=search;printf("after find number %3d:",search);print(data,10);return i-1;}if(data[i]==search&&i==0) return 0;}return -1;}
void link_init(link_list &l,int size)
{l.head= buynode(-1);pnode tmp=l.head;for(int i=0;i<size;i++) tmp->next= buynode(i+1),tmp=tmp->next;
}int link_find(link_list &l ,int search)
{pnode tmp=l.head;int count=0;while(tmp->next){if(tmp->next->data==search){if(tmp->data==-1) return count;else{tmp->next->data=tmp->data;tmp->data=search;return count-1;}}else{count++;tmp=tmp->next;}}return -1;
}void print_list(link_list l)
{for(pnode tmp=l.head->next;tmp;tmp=tmp->next){printf("%3d",tmp->data);}puts("");
}
int main() {//順序表int * data=(int*) malloc(sizeof (int)*10);init_array(data,10);for(int i=0;i<5;i++){int p1= array_visit(data,10,5);printf("the position of '5' is :%3d\n",p1);}for(int i=0;i<5;i++){int p1= array_visit(data,10,10);printf("the position of '10' is :%3d\n",p1);}printf("-------------------------------------------------\n");//鏈表link_list l1;link_init(l1,10);print_list(l1);for(int i=0;i<5;i++){int p1= link_find(l1,5);printf("the position of '5' is :%3d\n",p1);print_list(l1);}for(int i=0;i<5;i++){int p1= link_find(l1,10);printf("the position of '10' is :%3d\n",p1);print_list(l1);}return 0;
}

對(duì)于順序結(jié)構(gòu)上的測(cè)試結(jié)果

在鏈?zhǔn)浇Y(jié)構(gòu)上的搜索結(jié)構(gòu)