当前位置：首页 > news >正文

【王道数据结构】【chapter7查找】【P285t5】

news 2025/9/10 22:24:37

线性表中各节点的检索概率不等时，可用如下策略提高顺序检索的效率；若找到指定的结点，则将该结点和其前驱结点（若存在）交换，使得经常被访问的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表盘上实现上述策略的顺序检索算法。

#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;
}

对于顺序结构上的测试结果