数据结构实验报告

«数据结构»《数据构造》试验汇报五试验内容：简朴查找类算法的应用和比较——次序查找和折半查找学号：

姓名：

[题目]学生成绩表已按成绩非递增有序排列，请分别用次序查找和折半查找算法，找出指定成绩的学生信息，并分别指出所用的比较次数。给出查找成功和不成功两种状况。问题分析及设计思想：先要设计一种学生的次序表，再进行查找，次序查找（从表的一端开始，一次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败）；折半查找（从表的中间记录开始，假如给定值和中间纪录的关键字相等，则查找成功；假如给定值不小于或不不小于中间记录的关键字，则在表中不小于或不不小于中间记录的那二分之一中查找，这样反复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败）。二、存储构造定义：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>#include<math.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineMAX_LENGTH100三、函数申明：structElemType//数据元素类型typedefstructvoidCreat_Seq(SSTable&ST,ElemTyper[],intn)//操作成果：由含n个数据元素的数组r构造静态次序查找表STvoidAscend(SSTable&ST)//重建静态查找表为按关键字非降序排序StatusDestroy(SSTable&ST)//初始条件：静态查找表ST存在。操作成果：销毁表STintSearch_Seq(SSTableST,KeyTypekey)//在次序表ST中次序查找其关键字等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回0。四、完整程序示例：次序查找：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>#include<math.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;#defineMAX_LENGTH100typedeflongKeyType;//设关键字域为长整型#definekeynumber//定义关键字为学号structElemType//数据元素类型{ longnumber;//学号，与关键字类型同 charname[9];//姓名 inttotal;//总分};typedefstruct{ ElemType*elem; intlength;}SSTable;voidCreat_Seq(SSTable&ST,ElemTyper[],intn){//操作成果：由含n个数据元素的数组r构造静态次序查找表ST inti; 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的值依次赋给ST ST.length=n;}voidAscend(SSTable&ST){//重建静态查找表为按关键字非降序排序 inti,j,k; for(i=1;i<ST.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构造按关键字非降序查找表ST Creat_Seq(ST,r,n);//建立无序的查找表ST Ascend(ST);//将无序的查找表ST重建为按关键字非降序查找表}StatusDestroy(SSTable&ST){//初始条件：静态查找表ST存在。操作成果：销毁表ST free(ST.elem); ST.elem=NULL; ST.length=0; returnOK;}intSearch_Seq(SSTableST,KeyTypekey){//在次序表ST中次序查找其关键字等于key的数据元素。若找到，则返回 //该元素在表中的位置，否则返回0。 inti; 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%5d\n",c.number,,c.total);}intmain(){ ElemTyper[N]={{01,"何芳芳",85}, {02,"陈红",86}, {03,"陆华",78}, {04,"张平",82}, {05,"赵小怡",76}};//数组不按关键字有序 SSTablest; inti; longs; Creat_Seq(st,r,N);//由数组r产生次序静态查找表st printf("学号姓名总分\n"); Traverse(st,print);//按次序输出静态查找表st printf("请输入待查找人的考号:"); scanf("%ld",&s); i=Search_Seq(st,s);//次序查找 if(i) print(st.elem[i]); else printf("没找到\n"); Destroy(st); return0;}折半查找：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>#include<math.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;#defineMAX_LENGTH100typedeflongKeyType;//设关键字域为长整型#definekeynumber//定义关键字为学号structElemType//数据元素类型{ longnumber;//学号，与关键字类型同 charname[9];//姓名 inttotal;//总分};typedefstruct{ ElemType*elem; intlength;}SSTable;voidCreat_Seq(SSTable&ST,ElemTyper[],intn){//操作成果：由含n个数据元素的数组r构造静态次序查找表ST inti; 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的值依次赋给ST ST.length=n;}voidAscend(SSTable&ST){//重建静态查找表为按关键字非降序排序 inti,j,k; for(i=1;i<ST.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构造按关键字非降序查找表ST Creat_Seq(ST,r,n);//建立无序的查找表ST Ascend(ST);//将无序的查找表ST重建为按关键字非降序查找表}StatusDestroy(SSTable&ST){//初始条件：静态查找表ST存在。操作成果：销毁表ST free(ST.elem); ST.elem=NULL; ST.length=0; returnOK;}intSearch_Bin(SSTableST,KeyTypekey){ intlow,high,mid; low=1; high=ST.length; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key)returnmid; elseif(key<ST.elem[mid].key)high=mid-1; elselow=mid+1; } return0;}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%5d\n",c.number,,c.total);}intmain(){ ElemTyper[N]={{01,"何芳芳",85}, {02,"陈红",86}, {03,"陆华",78}, {04,"张平",82}, {05,"赵小怡",76}};//数组不按关键字有序 SSTablest; inti; longs; Creat_Seq(st,r,N);//由数组r产生次序静态查找表st printf("学号姓名总分\n