查找算法的实现(C语言版).docx

实验五 查找的实现 一、 实验目的1通过实验掌握查找的基本概念；2掌握顺序查找算法与实现；3掌握折半查找算法与实现。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 保存程序的运行结果，并结合程序进行分析。三、 实验内容1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。一、顺序查找顺序查找代码：#includestdio.h#includestdlib.htypedef struct nodeint key;keynode;typedef struct Nodekeynode r50;int length;list,*sqlist;int Createsqlist(sqlist s)int i;printf(请输入您要输入的数据的个数:n);scanf(%d,&(s-length);printf(请输入您想输入的%d个数据;nn,s-length);for(i=0;ilength;i+)scanf(%d,&(s-ri.key);printf(n);printf(您所输入的数据为:nn);for(i=0;ilength;i+)printf(%-5d,s-ri.key);printf(nn);return 1;int searchsqlist(sqlist s,int k)int i=0; s-rs-length.key=k;while(s-ri.key!=k)i+;if(i=s-length)printf(该表中没有您要查找的数据！n);return -1;elsereturn i+1;sqlist Initlist(void)sqlist p;p=(sqlist)malloc(sizeof(list);if(p)return p;else return NULL;main()int keyplace,keynum;/sqlist T;/T=Initlist();Createsqlist(T);printf(请输入您想要查找的数据的关键字:nn);scanf(%d,&keynum);printf(n);keyplace=searchsqlist(T,keynum);printf(您要查找的数据的位置为:nn%dnn,keyplace);return 2;顺序查找的运行结果：二、折半查找折半查找代码：#includestdio.h#includestdlib.htypedef struct nodeint key;keynode;typedef struct Nodekeynode r50;int length;list,*sqlist;int Createsqlist(sqlist s)int i;printf(请输入您要输入的数据的个数:n);scanf(%d,&(s-length);printf(请由大到小输入%d个您想输入的个数据;nn,s-length);for(i=0;ilength;i+)scanf(%d,&(s-ri.key);printf(n);printf(您所输入的数据为:nn);for(i=0;ilength;i+)printf(%-5d,s-ri.key);printf(nn);return 1;int searchsqlist(sqlist s,int k)int low,mid,high;low=0;high=s-length-1;while(lowrmid.key=k)return mid+1;else if(s-rmid.keyk) high=mid-1; else low=mid+1;printf(该表中没有您要查找的数据!n);return -1;sqlist Initlist(void)sqlist p;p=(sqlist)malloc(sizeof(list);if(p)return p;else return NULL;main()int keyplace,keynum;/sqlist T;/T=Initlist();Createsqlist(T);printf(请输入您想要查找的数据的关键字:nn);scanf(%d,&keynum);printf(n);keyplace=searchsqlist(T,keynum);printf(您要查找的数据的位置为:nn%dnn,keyplac