查找、排序应用实验

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日排序、查找的应用实验报告要求1目的与要求:1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；4）本次实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。2实验内容或题目题目：对记录序列（查找表）：{287，109，063，930，589，184，505，269,008，083}分别实现如下操作：1)分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序算法对纪录序列进行排序，并显示排序结果；2)对上述纪录列表排好序，然后对其进行折半查找或顺序查找；（特别要求：使用菜单机制，在一个主程序下实现题目要求的排序和查找以及结果显示）3实验步骤与源程序#includestdio.h#includestdlib.h/*链式基数法排序声明*/#defineRADIX10#defineKEY_SIZE6#defineLIST_SIZE20#defineTRUE1#defineFALSE0typedefintKeyType;typedefintOtherType;typedefstruct{KeyTypekey[KEY_SIZE];/*子关键字数组*/OtherTypeother_data;/*其它数据项*/intnext;/*静态链域*/}RecordType1;typedefstruct{RecordType1r[LIST_SIZE+1];/*r[0]为头结点*/intlength;intkeynum;}SLinkList;/*静态链表*/typedefintPVector[RADIX];typedefstruct{intnext;KeyTypekey;OtherTypeother_data;}RecordType;voidInsSort(RecordTyper[],intlength)/*对记录数组r做直接插入排序，length为数组中待排序记录的数目*/{inti,j;for(i=2;i=length;i++){r[0]=r[i];/*将待插入记录存放到监视哨r[0]中*/j=i-1;while(r[0].keyr[j].key)/*寻找插入位置*/{r[j+1]=r[j];j=j-1;}r[j+1]=r[0];/*将待插入记录插入到已排序的序列中*/}}/*InsSort*///顺序查找voidSeqSearch(RecordTyper[],intlength,KeyTypek){inti;r[0].key=k;i=length;while(r[i].key!=k)i--;printf(该元素在数组中的位置是%d,i);}//冒泡排序voidBubbleSort(RecordTyper[],intlength)/*对记录数组r做冒泡排序，length为数组的长度*/{intn,i,j;intchange;RecordTypex;n=length;change=TRUE;for(i=1;i=n-1&&change;++i){change=FALSE;for(j=1;j=n-i;++j)if(r[j].keyr[j+1].key){x=r[j];r[j]=r[j+1];r[j+1]=x;change=TRUE;}}}/*BubbleSort*///快速排序intQKPass(RecordTyper[],intleft,intright)/*对记录数组r中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/{RecordTypex;intlow,high;x=r[left];/*选择基准记录*/low=left;high=right;while(lowhigh){while(lowhigh&&r[high].key=x.key)/*high从右到左找小于x.key的记录*/high--;if(lowhigh){r[low]=r[high];low++;}/*找到小于x.key的记录，则进行交换*/while(lowhigh&&r[low].keyx.key)/*low从左到右找大于x.key的记录*/low++;if(lowhigh){r[high]=r[low];high--;}/*找到大于x.key的记录，则交换*/}r[low]=x;/*将基准记录保存到low=high的位置*/returnlow;/*返回基准记录的位置*/}/*QKPass*/voidSelectSort(RecordTyper[],intlength)/*对记录数组r做简单选择排序，length为数组的长度*/{inti,j,k,n;RecordTypex;n=length;for(i=1;i=n-1;++i){k=i;for(j=i+1;j=n;++j)if(r[j].keyr[k].key)k=j;if(k!=i){x=r[i];r[i]=r[k];r[k]=x;}}}voidQKSort(RecordTyper[],intlow,inthigh)/*对记录数组r[low..high]用快速排序算法进行排序*/{intpos;if(lowhigh){pos=QKPass(r,low,high);/*调用一趟快速排序，将枢轴元素为界划分两个子表*/QKSort(r,low,pos-1);/*对左部子表快速排序*/QKSort(r,pos+1,high);/*对右部子表快速排序*/}}//堆排序voidsift(RecordTyper[],intk,intm)/*假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质*/{RecordTypet;inti,j;intx;intfinished;t=r[k];/*暂存根记录r[k]*/x=r[k].key;i=k;j=2*i;finished=FALSE;while(j=m&&!finished){if(jm&&r[j].keyr[j+1].key)j=j+1;/*若存在右子树，且右子树根的关键字大，则沿右分支筛选*/if(x=r[j].key)finished=TRUE;/*筛选完毕*/else{r[i]=r[j];i=j;j=2*i;}/*继续筛选*/}r[i]=t;/*r[k]填入到恰当的位置*/}voidcrt_heap(RecordTyper[],intlength)/*对记录数组r建堆，length为数组的长度*/{inti,n;n=length;for(i=n/2;i=1;--i)/*自第[n/2]个记录开始进行筛选建堆*/sift(r,i,n);}voidHeapSort(RecordTyper[],intlength)/*对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列*/{inti,n;RecordTypeb;crt_heap(r,length);n=length;for(i=n;i=2;--i){b=r[1];/*将堆顶记录和堆中的最后一个记录互换*/r[1]=r[i];r[i]=b;sift(r,1,i-1);/*进行调整，使r[1..i-1]变成堆*/}}/*HeapSort*///链式基数排序voidDistribute(RecordType1r[],inti,PVectorhead,PVectortail)/*记录数组r中记录已按低位关键字key[i+1]，…，key[d]进行过低位优先排序。本算法按第i位关键字key[i]建立RADIX个队列，同一个队列中记录的key[i]相同。head[j]和tail[j]分别指向各队列中第一个和最后一个记录（j=0，1，2，…，RADIX-1）。head[j]=0表示相应队列为空队列*/{intj;intp;for(j=0;j=RADIX-1;++j)head[j]=0;/*将RADIX个队列初始化为空队列*/p=r[0].next;/*p指向链表中的第一个记录*/while(p!=0){j=r[p].key[i];/*用记录中第i位关键字求相应队列号*/if(head[j]==0)head[j]=p;/*将p所指向的结点加入第j个队列中*/elser[tail[j]].next=p;tail[j]=p;p=r[p].next;}}/*Distribute*/voidCollect(RecordType1r[],PVectorhead,PVectortail)/*本算法从0到RADIX-1扫描各队列，将所有非空队列首尾相接，重新链接成一个链表*/{intj;intt;j=0;while(head[j]==0)/*找第一个非空队列*/++j;r[0].next=head[j];t=tail[j];while(jRADIX-1)/*寻找并串接所有非空队列*/{++j;while((jRADIX-1)&&(head[j]==0))/*找下一个非空队列*/++j;if(head[j]!=0)/*链接非空队列*/{r[t].next=head[j];t=tail[j];}}r[t].next=0;/*t指向最后一个非空队列中的最后一个结点*/}/*Collect*/voidRadixSort(RecordType1r[],intlength)/*length个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序相链接。*/{inti,n;intd;PVectorhead;PVectortail;n=length;for(i=0;i=n-1;++i)r[i].next=i+1;/*构造静态链表*/r[n].next=0;d=3;for(i=d-1;i=0;--i)/*从最低位子关键字开始，进行d趟分配和收集*/{Distribute(r,i,head,tail);/*第i趟分配*/Collect(r,head,tail);/*第i趟收集*/}}/*RadixSort*/voidmain(){intflag=1,i,j,k,b;RecordTyper[20];intlen;printf(************功能菜单************\n);printf(1.直接插入排序;2.冒泡排序;\n);printf(3.快速排序;4.简单选择排序;\n);printf(5.堆排序;6.顺序查找;\n);printf(7.链式基数排序;8.退出;\n);printf(请输入待排序记录的长度:);scanf(%d,&len);for(i=1;i=len;i++){printf(请输入第%d个记录元素:,i);fflush(stdin);scanf(%d,&j);r[i].key=j;}printf(原记录序列：);for(i=1;i=len;i++)printf(%d,r[i].key);printf(\n);while(flag){printf(请选择操作：);scanf(%d,&b);switch(b){case1://直接插入排序printf(\n直接插入排序结果：\n);InsSor