折半查找與改進(jìn)算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

/折半查找及其改進(jìn)一、問題描述查找是在一個數(shù)據(jù)元素集合中查找關(guān)鍵字等于某個給個數(shù)據(jù)元素關(guān)鍵字的過程.也稱為檢索。給出一個特定的元素x.在含有n個元素的數(shù)列中判斷是否存在這個元素.如果存在.返回此元素在數(shù)列中的位置.否則返回零。數(shù)列查找在實(shí)際中的應(yīng)用十分廣泛.因此數(shù)列查找算法的好壞直接影響到程序的優(yōu)劣。本設(shè)計(jì)要求讀取文件中的數(shù)據(jù)建立查找表,并設(shè)計(jì)算法實(shí)現(xiàn)折半查找及其改進(jìn)查找。二、基本要求1、選擇合適的存儲結(jié)構(gòu).讀取已知文件數(shù)據(jù)建立查找表；2、完成基于遞歸和非逆歸的折半查找算法的設(shè)計(jì)；3、完成基于區(qū)間約束對折半查找算法的改進(jìn)算法的設(shè)計(jì)；4、完成三分查找算法的設(shè)計(jì)。三、測試數(shù)據(jù)文件in.txt中100個數(shù)據(jù)：1,2,3…98,99,100。讀取文件in.txt中前50位數(shù).查找元素:58讀取文件in.txt中前50位數(shù).查找元素:18讀取文件in.txt中前100位數(shù).查找元素：18讀取文件in.txt中前100位數(shù).待查元素：58四、算法思想1、折半查找的算法思想是以處于區(qū)間中間位置記錄的關(guān)鍵字和給定值比較.若相等.則查找成功.如不等.則縮小范圍.直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或區(qū)間大小小于零時為止。2、縮小區(qū)間查找算法的思想是先求出有序數(shù)列中每相鄰兩個元素之差的最大值的一個上界.設(shè)為m．要查找的數(shù)值為key.然后在每次循環(huán)做折半之前先進(jìn)行一次篩選工作.即將low右移<key-a[low]/m>位.high值左移<a[high]-key>/m位.從而把盡可能多的不必要的元素過濾掉.縮小查找范圍繼續(xù)查找.直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或區(qū)間大小小于零時為止。3、三分查找的算法思想是在給出n個已經(jīng)排好序的數(shù).在n/3和2n/3處各取一個數(shù).跟給定值key比較.確定待查數(shù)所在的范圍,直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或區(qū)間大小小于零時為止。五、模塊劃分1、voidread_dat<SSTable*ST,intn>,讀取文件in.dat中的數(shù)據(jù)并建立一個含文件in.dat中前n個數(shù)據(jù)的靜態(tài)查找表ST。2、voidDestroyList<SSTable*ST>,銷毀表ST。3、intSearchB1<SSTableST,KeyTypekey>,利用折半查找的非遞歸算法.查找關(guān)鍵字等于key的數(shù)據(jù)元素.若存在.返回該元素在表中的位置.否則為0。4、SearchB2<SSTableST,intkey,intlow,inthigh>,利用折半查找的遞歸算法.查找關(guān)鍵字等于key的數(shù)據(jù)元素.若存在.返回該元素在表中的位置.否則為0。5、SearchB3<SSTableST,KeyTypekey>,對折半查找算法的一種改進(jìn)6、SearchB4<SSTableST,KeyTypekey>,利用三分查找法.查找關(guān)鍵字等于key的數(shù)據(jù)元素.若存在.返回該元素在表中的位置.否則為0。7、voidMainMenue<>,主菜單。8、main<>,主函數(shù)。六、數(shù)據(jù)結(jié)構(gòu)查找表類型定義如下：typedefintKeyType;typedefstruct{KeyTypekey;/*其它域:略*/}ElemType;typedefstruct{ElemType*elem;intlength;}SSTable;七、源程序/*查找*/#include"stdio.h"#include"stdlib.h"#defineEQ<a,b><<a>==<b>>#defineLT<a,b><<a><<b>>#defineLQ<a,b><<a><=<b>>/*查找表類型定義*/typedefintKeyType;typedefstruct{KeyTypekey;/*其它域:略*/}ElemType;typedefstruct{ElemType*elem;intlength;}SSTable;/*1.讀取文件數(shù)據(jù)并建立查找表*/voidread_dat<SSTable*ST,intn>{inti;FILE*fp;ST->elem=<ElemType*>malloc<<n+1>*sizeof<ElemType>>;ST->length=n;fp=fopen<"in.txt","r">;for<i=0;i<=n;i++> fscanf<fp,"%d,",&ST->elem[i].key>;printf<"SSTable:<%d>\t",ST->elem[0].key>;for<i=1;i<=n;i++>printf<"%5d",ST->elem[i].key>;fclose<fp>;}/*2.銷毀查找表*/voidDestroyList<SSTable*ST>{free<ST->elem>;}voidDestroy<SSTable*ST>{if<ST->elem>{free<ST->elem>;ST->length=0;}}/*3.折半查找的非遞歸算法*/intSearchB1<SSTableST,KeyTypekey>{intlow,high,mid;low=1;high=ST.length;while<low<=high>{mid=<low+high>/2;if<EQ<key,ST.elem[mid].key>>returnmid;elseif<LT<key,ST.elem[mid].key>>high=mid-1;elselow=mid+1;}return0;}/*4.折半查找的遞歸算法*/intSearchB2<SSTableST,intkey,intlow,inthigh>{intmid;if<low>high>return0;mid=<low+high>/2;if<EQ<key,ST.elem[mid].key>>returnmid;elseif<LT<key,ST.elem[mid].key>>returnSearchB2<ST,key,low,mid-1>;elsereturnSearchB2<ST,key,mid+1,high>;}/*5.對折半查找算法的一種改進(jìn)*/intMAX<SSTableST>{intmax,i;max=ST.elem[2].key-ST.elem[1].key;for<i=2;i<ST.length-1;i++>if<max<ST.elem[i+1].key-ST.elem[i].key>max=ST.elem[i+1].key-ST.elem[i].key;returnmax;}intSearchB3<SSTableST,KeyTypekey>{intlow,high,mid,l=0,h=0,m=MAX<ST>;low=1;high=ST.length;while<low<=high&&l>=0&&h>=0>{l=<key-ST.elem[low].key>/m;h=<ST.elem[high].key-key>/m;mid=<low+high>/2;if<EQ<key,ST.elem[mid].key>>returnmid;elseif<LT<key,ST.elem[mid].key>>high=mid-1;elselow=mid+1;}return0;}/*6.三分查找*/intSearchB4<SSTableST,KeyTypekey>{intmid1,mid2,low=1,high=ST.length;if<ST.elem[low].key>key||ST.elem[high].key<key>return0;while<low<=high>{mid1=<high+low>/3;mid2=<2*high+low>/3;if<EQ<key,ST.elem[mid1].key>>returnmid1;elseif<LT<key,ST.elem[mid1].key>>high=mid1-1;else{if<EQ<key,ST.elem[mid2].key>>returnmid2;elseif<LT<key,ST.elem[mid2].key>>{low=mid1+1;high=mid2-1;}elselow=mid2+1;}}return0;}/*7.主菜單*/voidMainMenue<>{printf<"\n**********************MainMenue***********************\n">;printf<"**1.折半查找的非遞歸算法**\n">;printf<"**2.折半查找的遞歸算法**\n">;printf<"**3.對折半查找算法的一種改進(jìn)**\n">;printf<"**4.三分查找**\n">;printf<"**5.Exit.**\n">;printf<"********************************************************\n">;}/*主函數(shù)*/main<>{SSTableT;KeyTypex;intn,flag=1;charc;printf<"\n請輸入表長:">;scanf<"%d",&n>;read_dat<&T,n>;MainMenue<>;while<flag>{printf<"\nPleaseinputyourchoice:">;scanf<"%s",&c>;switch<c>{ case'1':printf<"\n折半查找的非遞歸算法:">printf<"\n請輸入待查元素:">;scanf<"%d",&x>;printf<"\n元素%d在表中的位置:%d",x,SearchB1<T,x>>;break;case'2':printf<"\n折半查找的遞歸算法:">;printf<"\n請輸入待查元素:">;scanf<"%d",&x>;printf<"\n元素%d在表中的位置:%d",x,SearchB2<T,x,1,T.length>；break;case'3':printf<"\n對折半查找算法的一種改進(jìn):">;printf<"\n請輸入待查元素:">;scanf<"%d",&x>;printf<"\n元素%d在表中的位置:%d",x,SearchB3<T,x>>;break;case'4':printf<"\n三分查找:">;printf<"\n請輸入待查元素:">;scanf<"%d",&x>;printf<"\n元素%d在表中的位置:%d",x,SearchB4<T,x>>;break;case'5':exit<1>;default:printf<"Inputerror!\n">;break;}}return0;Destroy<&T>;}八、測試情況測試結(jié)果：讀取文件in.txt中前50位數(shù).查找元素:58輸出文件中前50位數(shù)和主菜單.運(yùn)行正確。查找58在表中位置.因?yàn)?8不在表中.所以輸出0.程序運(yùn)行結(jié)果正確。讀取文件in.txt中前50位數(shù).查找元素:18元素18在表中位置為18.結(jié)果正確讀取文件in.txt中前100位數(shù).查找元素：18輸出文件中前100位數(shù)和主菜單.運(yùn)行正確。元素18在表中位置為18.運(yùn)行結(jié)果正確。讀取文件in.txt中前100位數(shù).待查元素：58元素58在表中位置為58.運(yùn)行結(jié)果正確。九、參考文獻(xiàn)1、嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)C語言》.清華大學(xué)出版社。2、譚浩強(qiáng).《c語言程序設(shè)計(jì)》.清華大學(xué)出版社。小結(jié)通過本次課程設(shè)計(jì).我學(xué)到了很多。它讓我真正的理解了什么是程序.程序=算法+結(jié)構(gòu)。編程的第一要務(wù)是把事物分析清楚.把事件先后的邏輯關(guān)系和依賴關(guān)系搞清楚.從而確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu).然后寫代碼去實(shí)現(xiàn)。所以只有學(xué)好數(shù)據(jù)結(jié)構(gòu).才能編好程序。編程不像做其它事.它要求編程人員有非?？b密的思維.很好的整體把握能力和很好的調(diào)試程序的能力等。決定程序成功與否的往往不是程序的整體思路和整體算法.而是細(xì)節(jié).細(xì)節(jié)錯誤往往是程序失敗的終級殺手.我在此次課程設(shè)計(jì)中深有體會。如不同輸入法下的分號不同.有個分號我是在中文輸入法下輸入的.導(dǎo)致我的程序運(yùn)行的結(jié)果出錯.花了我一定時間才檢查出來錯誤。同時我也認(rèn)識到編譯工具的重要性.我用的是VC++6.0環(huán)境.提高我編寫程序的效率.如按回車后.它能自動空出一定距離.體現(xiàn)出程序的結(jié)構(gòu).不用人工輸入空格、制表符.還有它的調(diào)試功能.不用我人工輸出中間變量來查錯.就能看到中間變量。在實(shí)驗(yàn)編寫程序的過程中.遇到了很多的問題.這些在我以前的實(shí)驗(yàn)中都是沒遇到的.比如三分查找.在給出n個已經(jīng)排好序的數(shù).在n/3和2n/3處各取一個數(shù).跟給定值key比較.由于比較時會出現(xiàn)很多的情況.每一種情況都需要仔細(xì)考慮到.在編程中.因?yàn)闆]有認(rèn)真分析.考慮不周全.導(dǎo)致一些情況遺漏了.程序出現(xiàn)了錯誤.經(jīng)過后來認(rèn)真分析.最終找到了遺漏的情況.程序運(yùn)行成功。還有在編寫基于區(qū)間約束對折半查找算法的改進(jìn)算法的設(shè)計(jì)過程中.也遇到了類似的錯誤.考慮條件不周全.程序