查找实验报告

《数据构造》课程设计报告专业计算机科学与技术班级3班姓名学号指导教师起止时间.12~.1课程设计：查找算法一、任务描述查找算法创立一种值域在[1，0]内，长度为10000的整型数组；然后随机生成10000个在[1，0]内的整数，分别用次序查找法、二分查找法进行10000次查找。规定程序进行统计并输出以下成果：（1）比较总次数；（2）查找成功的次数；（3）查找成功的比例；（4）每次查找的平均比较次数。二、问题分析1、功效分析分析设计课题的规定，规定编程实现下列功效：（1）比较总次数；（2）查找成功的次数；（3）查找成功的比例；（4）每次查找的平均比较次数。2、数据对象分析数据信息：随机生成10000个在[1,0]范畴内的数；用线性表存储这10000随机生成的数，用数组存储进行比较的数；三、数据构造设计选用带头结点的线性表表实现。有关的定义以下：typedeflongKeyType;typedeflongInfoType;//整型typedeflongStatus;#definenum10000#defineLIST_INIT_SIZE10001//线性表存储空间的初始分派量typedefstruct{//定义被排序统计构造类型KeyTypekey;//排序码InfoTypeotherinfo;//其它数据项}RedType;typedefstruct{RedType*r;//存储带排序统计的次序表//r[0]作哨兵或缓冲区intlength;//次序表的长度}SqList;//定义次序表类型四、功效设计（一）主控菜单设计在主控菜单中实现线性表的建立，次序查找，冒泡排序，折半查找，程序运行后，会显示生成查找数！，生成链表！排序结束！以及比较总次数、查找成功次数、查找成功比例、查找的平均次数。（二）程序模块构造由课题规定可将程序划分为下列几个模块（即实现程序功效所需的函数）：创立通信录次序表函数InitList_Sq()冒泡排序函数Bubble_sort()次序查找函数search_seq()折半查找函数search_bin()（三）函数调用关系程序的重要构造（函数调用关系）以下图所示。Main()ImitList()Bubble_sort()search_seq()search_seq()其中main()是主函数，它进行菜单驱动。KeyTypean[num]; printf("生成查找数!\n"); srand((unsigned)time(NULL)); for(i=0;i<num;i++) an[i]=rand()%1+1; printf("\n"); InitList_Sq(L);//创立线形表 intnu=0;//比较的总次数 intb=0;//查找成功的次数 for(i=0;i<num;i++){ inta;//查找到的位置 a=search_seq(L,an[i]); nu+=a; if(a!=0)b++; } Bubble_sort(L); printf("排序结束!\n"); printf("\n"); intnux=0;//比较的总次数 intbx=0;//查找成功的次数 for(i=0;i<num;i++){ intax;//查找到的位置 ax=search_bin(L,an[i]); nux+=L.length/ax; if(ax!=1)bx++; } printf("比较的总次数：次序查找%d，折半查找%d\n",nu,nux); printf("查找成功的次数：次序查找%d，折半查找%d\n",b,bx); printf("查找成功的比例:次序查找%d，折半查找%d\n",b*100/num,bx*100/num); printf("查找的平均次数：次序查找%d，折半查找%d\n",nu/num,nux/num);（四）文献构造1、search.h：次序表有关的定义与函数声明2、search.cpp：次序表查找的运算实现3、mn.cpp：主函数（五）各函数的算法设计1、InitList_Sq()算法原理：数组指针r批示线性表的基址，length批示线性表的现在长度，将随机生成的数赋给线性表。流程图：流程图：开始申请内存 NY随机生成10000个数字 存入次序表中结束代码描述：StatusInitList_Sq(SqList&L){//构造一种的线性表 L.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType)); if(!L.r)exit(OVERFLOW);//存储分派失败 L.length=LIST_INIT_SIZE;//表长度为10001 printf("生成链表!\n"); srand((unsigned)time(NULL)); for(inti=1;i<=L.length;i++) L.r[i].key=rand()%01+1; printf("\n"); returnOK;}//InitList_Sq算法的时间复杂度分析：O(n)2、Bubble_sort()算法原理：每趟不停将统计两两比较，若发现逆序，则交换两个统计，使排序码较小的元素逐步从后部移向前部（就象水底的气泡同样逐步向上冒）。流程图i=1i<n NYflag=0j=n-1j<=i N YL.r[j+1].key<L.r[j].key)flag=1L.r[j]←→L.r[j+1]j--flag=0i++结束代码描述：voidBubble_sort(SqList&L){RedTypex; intn;n=L.length;//表长for(inti=1;i<n;i++){intflag=0;//进入循环，清标志for(intj=n-1;j>=i;j--)if(LT(L.r[j+1].key,L.r[j].key)){ flag=1;//有交换，置标志x=L.r[j];//L.r[j]←→L.r[j+1]L.r[j]=L.r[j+1];L.r[j+1]=x;}if(flag==0)break;//若无交换则可结束冒泡排序}}算法的时间复杂度分析：O(n2)search_seq()算法原理：从次序表的一端开始，用给定数据元素的核心字逐个与次序表中各数据元素的核心字比较，若在次序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在次序表中的位置；否则查找失败，函数返回0。流程图：代码描述：intsearch_seq(SqList&L,KeyTypekey){ //在次序表ST中次序查找其核心字等于key的数据元素。若找到则函数值为该元素在表中的位置，否则为0。 L.r[0].key=key;//哨兵 for(inti=L.length;!EQ(L.r[i].key,key);--i);//从后往前找 returni;//找不届时i为0}//search_seq算法的时间复杂度分析：O(n)4、search_bin()算法原理：先拟定待查统计所在的范畴（区间），然后逐步缩小范畴直到找到或找不到该统计为止。流程图：代码描述：intsearch_bin(SqList&L,KeyTypekey){ //在有序表ST中折半查找其核心字等于key的数据元素。若找到则函数为该元素在表中的位置，否则为0 intlow=1; inthigh=L.length;//置区间初值 while(low<=high){ intmid=(low+high)/2; if(EQ(key,L.r[mid].key))returnmid;//找到待查元素 elseif(LT(key,L.r[mid].key))high=mid-1;//继续在前半区间进行查找 elselow=mid+1;/