实验五--查找及排序

1实验五查找及排序实验课程名：数据结构与算法一、实验目的及要求1、掌握查找的不同方法，并能用高级语言实现查找算法。2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。3、掌握常用的排序方法，并能用高级语言实现排序算法。4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验内容任务一：顺序表的顺序查找。有序表的折半查找。完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。解答：（1）源代码：#includestdio.h//EOF(=^Z或F6),NULL#includestdlib.h//atoi()#includeio.h//eof()#includemath.h//floor(),ceil(),abs()#includeprocess.h//exit()#includeiostream.h//cout,cin//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE#defineMAX_LENGTH100#includestring.h准考证号姓名各科成绩总分政治语文外语数学物理化学生物179328何芳芳858998100938047592179325陈红858688100929045586179326陆华78759080958837543179327张平82807898849640558179324赵小怡768594577769445022#includectype.h#includemalloc.h//malloc()等#includelimits.h//INT_MAX等#includestdio.h//EOF(=^Z或F6),NULL#includestdlib.h//atoi()#includeio.h//eof()#includemath.h//floor(),ceil(),abs()#includeprocess.h//exit()#includeiostream.h//cout,cin//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE#defineN5//数据元素个数#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))typedeflongKeyType;//设关键字域为长整型#definekeynumber//定义关键字为准考证号structElemType//数据元素类型(以教科书图9.1高考成绩为例){longnumber;//准考证号，与关键字类型同charname[9];//姓名(4个汉字加1个串结束标志)intpolitics;//政治intChinese;//语文intEnglish;//英语intmath;//数学intphysics;//物理intchemistry;//化学intbiology;//生物inttotal;//总分};typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空intlength;//表长度}SSTable;3voidCreat_Seq(SSTable&ST,ElemTyper[],intn){//操作结果：由含n个数据元素的数组r构造静态顺序查找表STinti;ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间(0号单元不用)if(!ST.elem)exit(ERROR);for(i=1;i=n;i++)ST.elem[i]=r[i-1];//将数组r的值依次赋给STST.length=n;}voidAscend(SSTable&ST){//重建静态查找表为按关键字非降序排序inti,j,k;for(i=1;iST.length;i++){k=i;ST.elem[0]=ST.elem[i];//待比较值存[0]单元for(j=i+1;j=ST.length;j++)ifLT(ST.elem[j].key,ST.elem[0].key){k=j;ST.elem[0]=ST.elem[j];}if(k!=i)//有更小的值则交换{ST.elem[k]=ST.elem[i];ST.elem[i]=ST.elem[0];}}}voidCreat_Ord(SSTable&ST,ElemTyper[],intn){//操作结果：由含n个数据元素的数组r构造按关键字非降序查找表STCreat_Seq(ST,r,n);//建立无序的查找表STAscend(ST);//将无序的查找表ST重建为按关键字非降序查找表}StatusDestroy(SSTable&ST){//初始条件：静态查找表ST存在。操作结果：销毁表STfree(ST.elem);ST.elem=NULL;ST.length=0;returnOK;4}intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则返回//该元素在表中的位置，否则返回0。算法9.1inti;ST.elem[0].key=key;//哨兵for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前找returni;//找不到时，i为0}voidTraverse(SSTableST,void(*Visit)(ElemType)){//初始条件：静态查找表ST存在，Visit()是对元素操作的应用函数//操作结果：按顺序对ST的每个元素调用函数Visit()一次且仅一次ElemType*p;inti;p=++ST.elem;//p指向第一个元素for(i=1;i=ST.length;i++)Visit(*p++);}voidprint(ElemTypec)//Traverse()调用的函数{printf(%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5d\n,c.number,c.name,c.politics,c.Chinese,c.English,c.math,c.physics,c.chemistry,c.biology,c.total);}intmain(){ElemTyper[N]={{179328,何芳芳,85,89,98,100,93,80,47},{179325,陈红,85,86,88,100,92,90,45},{179326,陆华,78,75,90,80,95,88,37},{179327,张平,82,80,78,98,84,96,40},{179324,赵小怡,76,85,94,57,77,69,44}};//数组不按关键字有序SSTablest;inti;longs;for(i=0;iN;i++)//计算总分r[i].total=r[i].politics+r[i].Chinese+r[i].English+r[i].math+r[i].physics+r[i].chemistry+r[i].biology;Creat_Seq(st,r,N);//由数组r产生顺序静态查找表st5printf(准考证号姓名政治语文外语数学物理化学生物总分\n);Traverse(st,print);//按顺序输出静态查找表stprintf(请输入待查找人的考号:);scanf(%ld,&s);i=Search_Seq(st,s);//顺序查找if(i)print(st.elem[i]);elseprintf(没找到\n);Destroy(st);return0;}（2）运行结果：（3）运行结果分析：运用顺序结构完成查询。任务二：哈希表的开放定址法算法。在输出结果中显示查找成功与查找不成功信息。解答：（1）源代码：#includestring.h#includectype.h#includemalloc.h//malloc()等#includelimits.h//INT_MAX等#includestdio.h//EOF(=^Z或F6),NULL#includestdlib.h//atoi()#includeio.h//eof()#includemath.h//floor(),ceil(),abs()6#includeprocess.h//exit()#includeiostream.h//cout,cin//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineLQ(a,b)((a)=(b))#defineN11//数据元素个数#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1#defineNULL_KEY0//0为无记录标志#defineN10//数据元素个数typedefintKeyType;//设关键字域为整型structElemType//数据元素类型{KeyTypekey;intord;};inthashsize[]={11,19,29,37};//哈希表容量递增表，一个合适的素数序列intm=0;//哈希表表长，全局变量structHashTable{ElemType*elem;//数据元素存储基址，动态分配数组intcount;//当前数据元素个数intsizeindex;//hashsize[sizeindex]为当前容量};voidInitHashTable(HashTable&H){//操作结果：构造一个空的哈希表inti;H.count=0;//当前元素个数为0H.sizeindex=0;//初始存储容量为hashsize[0]m=hashsize[0];7H.elem=(ElemType*)malloc(m*sizeof(ElemType));if(!H.elem)exit(OVERFLOW);//存储分配失败for(i=0;im;i++)H.elem[i].key=NULL_KEY;//未填记录的标志}voidDestroyHashTable(HashTable&H){//初始条件：哈希表H存在。操作结果：销毁哈希表Hfree(H.elem);H.elem=NULL;H.count