《试验报告排序与查找》由会员分享，可在线阅读，更多相关《试验报告排序与查找（8页珍藏版）》请在金锄头文库上搜索。
1、电子科技大学信息与软件工程学院实验报告电子科技大学实验报告课程名称：数据结构与算法学生姓名：学 号：点名序号：指导教师：实验地点：基础实验大楼实验时间：5月20日2014-2015-2 学期信息与软件工程学院实 验 报 告（二）学生姓名 学 号：指导教师：实验地点：基础实验大楼实验时间：5月20日一、实验室名称：软件实验室二、 实验项目名称：数据结构与算法一排序与查找三、实验学时：4四、实验原理：快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达
2、到整个数据变成有序序列。假设要排序的数组是 A1AN,首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：1） 设置两个变量I、J,排序开始的时候I : =1 , J： =N2）以第一个数组元素作为关键数据，赋值给 X，即X : =A1;3） 从J开始向前搜索，即（J: =J-1）,找到第一个小于 X的值，两者交换；4） 从I开始向后搜索，即（I : =1+1 ）,找到第一个大于 X的值，两者交换；5）重复第3、4步，直到l=J。二分法查找（折半查找）的基本思想：（1） 确定该区间的
3、中点位置：mid= （low+high ） /2min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2） 将待查a值与结点mid的关键字（下面用Rmid.key ）比较，若相等，则查找成功， 否则确定新的查找区间：A）如果Rmid.keya，则由表的有序性可知，Rmid.key右侧的值都大于 a,所以等于a的关键字如果存在，必然在Rmid.key左边的表中，这时high=mid-1;B）如果Rmid.keya,则等于a的关键字如果存在，必然在 Rmid.key右边的表中。这 时 low=mid ;C）如果Rmid.key=a，则查找成功。（3） 下一次查找
4、针对新的查找区间，重复步骤（1）和（2）（4） 在查找过程中，low逐步增加，high逐步减少，如果highlow，则查找失败。五、实验目的：本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查 找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。六、实验内容：(1) 实现数据序列的输入；(2) 实现快速排序算法，并对输入的序列排序后输出；(3) 实现折半查找算法,并在步骤(2)排序后的序列上，进行任意地 查找,并输出查询结果。七、实验器材(设备、元器件)：PC机一台，装有C语言集成开发环境。八、数据结构与程序：#in clude#in clude#defi ne MA
5、X 1000#defi ne FROMFILE 1typedef struct JDint key;JD;int binsrch(JD r,int n,int k) int low,high,mid,found;low=1; high=n; foun d=0;while(lowrmid.key) low=mid+1;else if(k=rmid.key) foun d=1;else high=mid-1;if(foun d=1)return(mid);elsereturn(O);void quicksort(JD r,i nt low,i nt high) int i,j,k;JD x;if(
6、low=high)return;i=low;j=high;x=ri;while(ij)while(i=x.key)j-;if(ij)ri=rj;i+;while(ij)&(ri.key=x.key)i+;if(ij)rj=ri;j-;ri=x;quicksort(r,low,j-1);quicksort(r,j+1,high);/快速排序int mai n()nn);:);prin tf(欢迎使用快速排序与二分查找。#ifdef FROMFILEprin tf(请输入你所要查找的数组长度int len gth;scan f(%d, &len gth);getchar();JD ale ngth
7、+1;a0.key=0;int i;for(i=1;i=le ngth;i+)printf(输入第d个数字:,i);sca nf(%d,&ai.key);getchar();#elseFILE *fp;fp = fope n(test.txt,r);if(!fp)printf( 文件不存在!);return 0;JD aMAX;a0.key=0;int i=1;while (fscan f(fp,%d,&ai+.key)!=EOF);int len gth=i-1;prin tf(文件内的信息：”)；for (i=1;ile ngth;i+) prin tf(%d ”,ai.key);prin
8、 tf(n ”);len gth-;fclose(fp);#en difquicksort(a,0,le ngth);prin tf(n ”);int key;prin tf(请输入你想查找的数字：”);scan f(%d, &key);getchar();prin tf(n ”);int locatio n=bin srch(a,le ngth,key);printf(位置:);for(i=1;i=le ngth;i+)prin tf(%3d ,i);prin tf(n ”);printf(数字:);for(i=1;i=le ngth;i+)prin tf(%3d ”,ai.key);pri
9、n tf(n ”);if(locati on)int coun t=0;prin tf(目标数字出现的位置:);for (i=1;i=le ngth;i+) if (ai.key=alocation.key) prin tf(%d ”,i);coun t+;printf(n数字 d出现的次数：dn,alocation.key,count);elseprintf(该数字不存在!nn);return 0;L_J 03九、程序运行结果：CiUsersAdrni ni stratorDesktop：S l.exe：1MNT 1 2 3 4 -5 b ? 8 9 1 I _.n rtfaTflr?ffFffparrgrlnrgrj 积入入IAIAIA入IAIAIA 土 UZaJizeJ 耳冃一冃 j 冃 ：? .Imf j IE? j 冃.心 ED0-第#页请输入你想查找的数字油S78910555G7十、实验结论：此次操作证明可以用编程实现快速排序并在其后进行二分查找，实验结果正确。十一、总结及心得体会：通过本次实验，我对快速排序与二分查找有了更加深刻的了解。我尝试了书上没有的结构体，使自己的感觉丰富了许多，耳目一新，加深了我对学习编程的兴趣。练习了结构体、 指针排序、查找等操作，熟练掌握树的操作。对知识的巩固与加深起到了很大的作用，我受益匪浅。
