数据结构实验报告-排序与查找

1、数据结构实验报告-排序与查找 电 子 科 技 大 学实 验 报 告学生姓名：XXX 学 号：xxxx220501018 指导教师：刘峤实验地点：信软机房306 实验时间：xxxx/6/20一、实验室名称：软件实验室二、实验项目名称：数据结构与算法排序与查找三、实验学时：4四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A1AN，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然

2、后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A1； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2?min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置

3、（2）将待查a值与结点mid的关键字（下面用Rmid.key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果Rmid.keya，则由表的有序性可知，Rmid.key右侧的值都大于a，所以等于a的关键字如果存在，必然在Rmid.key左边的表中,这时high=mid-1; B)如果Rmid.key#define MAX_LEN 100void Sort(int *data,int left,int right) int i,j,temp; i=left; j=right; temp=dataleft; if(leftright) return; while(i!=j) while(d

4、ataj=temp&ji) j-; if(ji) datai+=dataj; while(dataii) i+; if(ji) dataj-=datai; datai=temp; Sort(data,left,i-1); Sort(data,i+1,right);int Search(int *data,int start,int end,int key,int num) int result; int p = (start + end) / 2; if (datap = key&start key) result = Search(data, start, p, key,num); else

5、 result = Search(data, p + 1, end, key,num); return result; else if (num=0&startend) result = -1; printf(n 404 NO FOUNDn); return result; else if (num!=0&startend) result=-1; if (num=1) printf(nFounded number only one); else printf(nFounded number more than one); return result; else if (result!=-1)

6、if (datap key) result = Search(data, start, p - 1, key, num); else result = Search(data, p + 1, end, key, num); return result; else result=-1; return result; void loadFile(int *data,char *filename,int n) int i; FILE *pfile=NULL; pfile=fopen(filename,r); if (!pfile) printf(Open file failn); exit(0);

7、else printf(Open file success!n); for(i = 0 ; i n; i+) fscanf(pfile , %d ,&datai);int main(int argc, const char * argv) int input=1,dataMAX_LEN,num=0,key=1,i,cmd; char filename100; printf(Choose Mode :n 1.Input Mode 2.File Moden); scanf(%d,&cmd); if (cmd=1) printf(Input data :(Enter 0 to detemine)n)

8、; while (input!=0) printf(Enter the %d data :,num+1); scanf(%d,&input); if (input!=0) datanum=input; num+; else printf(nInput the address of the file: ); scanf(%s,filename); printf(nInput the number of elem: ); scanf(%d,&num); loadFile(data,filename,-num); Sort(data, 0, num); printf(nSort result: );

9、 for (i=1; i=num; i+) printf(%d ,datai); printf(nn); while (key!=0) printf(nInput a key to search :(Enter 0 to detemine); scanf(%d,&key); if (key!=0) Search(data, 0, num, key, 0); return 0;九、程序运行结果：1.打开程序：2.尝试手动输入模式：3.搜索已存在数：4.搜索不存在数：5.尝试文件读入模式并搜索实验成功。十、实验结论：使用好的排序与查找算法对于程序的运行效率至关重要，一个好的算法，适合的算法能使计算机对数据的处理事半功倍，而选用错误的算法，不但可能事倍功半，还有可能造成不稳定因素。快速排序的时间复