《數(shù)據(jù)構(gòu)造》課程設(shè)計(jì)報告專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級3班姓名學(xué)號指導(dǎo)教師起止時間.12~.1課程設(shè)計(jì)：查找算法一、任務(wù)描述查找算法創(chuàng)立一種值域在[1，0]內(nèi)，長度為10000的整型數(shù)組；然后隨機(jī)生成10000個在[1，0]內(nèi)的整數(shù)，分別用次序查找法、二分查找法進(jìn)行10000次查找。規(guī)定程序進(jìn)行統(tǒng)計(jì)并輸出以下成果：（1）比較總次數(shù)；（2）查找成功的次數(shù)；（3）查找成功的比例；（4）每次查找的平均比較次數(shù)。二、問題分析1、功效分析分析設(shè)計(jì)課題的規(guī)定，規(guī)定編程實(shí)現(xiàn)下列功效：（1）比較總次數(shù)；（2）查找成功的次數(shù)；（3）查找成功的比例；（4）每次查找的平均比較次數(shù)。2、數(shù)據(jù)對象分析數(shù)據(jù)信息：隨機(jī)生成10000個在[1,0]范疇內(nèi)的數(shù)；用線性表存儲這10000隨機(jī)生成的數(shù)，用數(shù)組存儲進(jìn)行比較的數(shù)；三、數(shù)據(jù)構(gòu)造設(shè)計(jì)選用帶頭結(jié)點(diǎn)的線性表表實(shí)現(xiàn)。有關(guān)的定義以下：typedeflongKeyType;typedeflongInfoType;//整型typedeflongStatus;#definenum10000#defineLIST_INIT_SIZE10001//線性表存儲空間的初始分派量typedefstruct{//定義被排序統(tǒng)計(jì)構(gòu)造類型KeyTypekey;//排序碼InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RedType;typedefstruct{RedType*r;//存儲帶排序統(tǒng)計(jì)的次序表//r[0]作哨兵或緩沖區(qū)intlength;//次序表的長度}SqList;//定義次序表類型四、功效設(shè)計(jì)（一）主控菜單設(shè)計(jì)在主控菜單中實(shí)現(xiàn)線性表的建立，次序查找，冒泡排序，折半查找，程序運(yùn)行后，會顯示生成查找數(shù)！，生成鏈表！排序結(jié)束！以及比較總次數(shù)、查找成功次數(shù)、查找成功比例、查找的平均次數(shù)。（二）程序模塊構(gòu)造由課題規(guī)定可將程序劃分為下列幾個模塊（即實(shí)現(xiàn)程序功效所需的函數(shù)）：創(chuàng)立通信錄次序表函數(shù)InitList_Sq()冒泡排序函數(shù)Bubble_sort()次序查找函數(shù)search_seq()折半查找函數(shù)search_bin()（三）函數(shù)調(diào)用關(guān)系程序的重要構(gòu)造（函數(shù)調(diào)用關(guān)系）以下圖所示。Main()ImitList()Bubble_sort()search_seq()search_seq()其中main()是主函數(shù)，它進(jìn)行菜單驅(qū)動。KeyTypean[num]; printf("生成查找數(shù)!\n"); srand((unsigned)time(NULL)); for(i=0;i<num;i++) an[i]=rand()%1+1; printf("\n"); InitList_Sq(L);//創(chuàng)立線形表 intnu=0;//比較的總次數(shù) intb=0;//查找成功的次數(shù) for(i=0;i<num;i++){ inta;//查找到的位置 a=search_seq(L,an[i]); nu+=a; if(a!=0)b++; } Bubble_sort(L); printf("排序結(jié)束!\n"); printf("\n"); intnux=0;//比較的總次數(shù) intbx=0;//查找成功的次數(shù) for(i=0;i<num;i++){ intax;//查找到的位置 ax=search_bin(L,an[i]); nux+=L.length/ax; if(ax!=1)bx++; } printf("比較的總次數(shù)：次序查找%d，折半查找%d\n",nu,nux); printf("查找成功的次數(shù)：次序查找%d，折半查找%d\n",b,bx); printf("查找成功的比例:次序查找%d，折半查找%d\n",b*100/num,bx*100/num); printf("查找的平均次數(shù)：次序查找%d，折半查找%d\n",nu/num,nux/num);（四）文獻(xiàn)構(gòu)造1、search.h：次序表有關(guān)的定義與函數(shù)聲明2、search.cpp：次序表查找的運(yùn)算實(shí)現(xiàn)3、mn.cpp：主函數(shù)（五）各函數(shù)的算法設(shè)計(jì)1、InitList_Sq()算法原理：數(shù)組指針r批示線性表的基址，length批示線性表的現(xiàn)在長度，將隨機(jī)生成的數(shù)賦給線性表。流程圖：流程圖：開始申請內(nèi)存 NY隨機(jī)生成10000個數(shù)字 存入次序表中結(jié)束代碼描述：StatusInitList_Sq(SqList&L){//構(gòu)造一種的線性表 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算法的時間復(fù)雜度分析：O(n)2、Bubble_sort()算法原理：每趟不停將統(tǒng)計(jì)兩兩比較，若發(fā)現(xiàn)逆序，則交換兩個統(tǒng)計(jì)，使排序碼較小的元素逐步從后部移向前部（就象水底的氣泡同樣逐步向上冒）。流程圖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++結(jié)束代碼描述：voidBubble_sort(SqList&L){RedTypex; intn;n=L.length;//表長for(inti=1;i<n;i++){intflag=0;//進(jìn)入循環(huán)，清標(biāo)志for(intj=n-1;j>=i;j--)if(LT(L.r[j+1].key,L.r[j].key)){ flag=1;//有交換，置標(biāo)志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;//若無交換則可結(jié)束冒泡排序}}算法的時間復(fù)雜度分析：O(n2)search_seq()算法原理：從次序表的一端開始，用給定數(shù)據(jù)元素的核心字逐個與次序表中各數(shù)據(jù)元素的核心字比較，若在次序表中查找到要查找的數(shù)據(jù)元素，則查找成功，函數(shù)返回該數(shù)據(jù)元素在次序表中的位置；否則查找失敗，函數(shù)返回0。流程圖：代碼描述：intsearch_seq(SqList&L,KeyTypekey){ //在次序表ST中次序查找其核心字等于key的數(shù)據(jù)元素。若找到則函數(shù)值為該元素在表中的位置，否則為0。 L.r[0].key=key;//哨兵 for(inti=L.length;!EQ(L.r[i].key,key);--i);//從后往前找 returni;//找不屆時i為0}//search_seq算法的時間復(fù)雜度分析：O(n)4、search_bin()算法原理：先擬定待查統(tǒng)計(jì)所在的范疇（區(qū)間），然后逐步縮小范疇直到找到或找不到該統(tǒng)計(jì)為止。流程圖：代碼描述：intsearch_bin(SqList&L,KeyTypekey){ //在有序表ST中折半查找其核心字等于key的數(shù)據(jù)元素。若找到則函數(shù)為該元素在表中的位置，否則為0 intlow=1; inthigh=L.length;//置區(qū)間初值 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;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 elselow=mid+1;/