數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--兩種常用查找算法的比較與實現(xiàn)

1、<p><b>　　兩種常用查找算法的</b></p><p><b>　　比較與實現(xiàn)</b></p><p>　　摘 要：本次課程設(shè)計主要研究幾種常用查找算法的比較與實現(xiàn)，查找的算法有很多種：靜態(tài)查找表的順序表、有序表、索引順序表等查找結(jié)構(gòu)；動態(tài)查找表的二叉排序樹、哈希查找等查找結(jié)構(gòu)。本次的課程設(shè)計主要研究兩種常見的查找算法：順序查找

2、和折半查找，分析比較它們的時間復雜度，并且在此基礎(chǔ)上用C語言對它們進行算法編程、調(diào)試和運行。</p><p>　　關(guān)鍵詞：C語言；順序查找；折半查找;時間復雜度。</p><p><b>　　引 言</b></p><p>　　“數(shù)據(jù)結(jié)構(gòu)”在計算機科學中是一門綜合性的專業(yè)基礎(chǔ)課，“數(shù)據(jù)結(jié)構(gòu)”的研究不僅涉及到計算機硬件的研究范圍，而且和計算機軟件

3、的研究有著密切的關(guān)系無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，一遍查找和存取數(shù)據(jù)元素更為方便。因此，可以認為“數(shù)據(jù)結(jié)構(gòu)”是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。</p><p>　　課程設(shè)計是我們專業(yè)課程知識綜合應(yīng)用的實踐訓練，是實踐性教學的一個重要環(huán)節(jié)。而數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，更要求學生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇

4、和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。</p><p>　　在日常生活中，人們幾乎每天都要進行“查找”工作。例如，在電話號碼薄中查閱“某單位”或“某人”的電話號碼；在字典中查閱“某個詞”的讀音和含義等等。而同樣地，在各種系統(tǒng)軟件和應(yīng)用軟件中，也存在“查找”：如編譯程序中符號表、信息處理表中相關(guān)信息的查找。所以，

5、“查找”就是在一個含有眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄）【1】。</p><p>　　在計算機中進行查找的方法也會隨數(shù)據(jù)結(jié)構(gòu)不同而不同。在此，引入“查找表”的概念：同類數(shù)據(jù)元素構(gòu)成的集合。所以，這次的課程設(shè)計就可以從靜態(tài)查找表的幾種典型的算法來實現(xiàn)對數(shù)據(jù)元素的查找的算法和操作的實現(xiàn)和比較。</p><p><b>　　1.1課程設(shè)計背景<

6、/b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計作為獨立的教學環(huán)節(jié)，是計算機相關(guān)專業(yè)集中實踐環(huán)節(jié)系列之一，是學習完《數(shù)據(jù)結(jié)構(gòu)》課程后進行的一次全面的綜合練習。所以需要我們了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，并且具備初步的獨立分析和設(shè)計能力，同時要掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼測試等基本方法和技能，提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力。所以這次課程設(shè)計的目的在于：加強學生對

7、C語言的基本知識和技能；加深對數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)理論和基本知識的理解，提高解決實際問題的實踐能力；同時幫助調(diào)動學生的積極性和能動性，培養(yǎng)學生的自學、動手能力。</p><p>　　1.2課程設(shè)計目標</p><p>　　本次課程設(shè)計，我準備用不同的兩種常見的查找方法：針對順序查找表中查找方法，如順序查找、折半查找等。并且通過用這些算法實現(xiàn)對某個“特定的”數(shù)據(jù)元素（關(guān)鍵字）的查找，分析這些操作的

8、性能：它們各自的時間復雜度、空間復雜度和其它的一些性能，同時記錄每種查找方法的優(yōu)缺點，比較得出它們的查找效率和查找范圍。</p><p><b>　　2 設(shè)計概要</b></p><p><b>　　2.1 問題描述</b></p><p>　　對于不同的查找算法，它們各自的時間復雜度和空間復雜度不同，查找的思想和算法也

9、明顯不同，所以要分析它們的特點和效率，我們要多方面比較：要比較時間復雜度，我們可以從它們的查找長度側(cè)面比較出來；而它們算法的實現(xiàn)就要熟悉它們的查找思想，熟練應(yīng)用C語言編寫合適的程序。</p><p><b>　　2.2 設(shè)計思路</b></p><p>　　靜態(tài)查找表有順序表和鏈式表兩種表示方法，在這次的課程設(shè)計里，我用順序存儲表來表示這兩種查找算法的程序。</

10、p><p>　　我的設(shè)計思路及步驟如下：</p><p>　　（1）熟悉兩種算法的編程思想,畫出流程圖。</p><p>　?。?）先編寫兩種算法的子程序，再遍寫主程序調(diào)用它們。</p><p>　　（3）分步調(diào)試子程序和主程序，直到不再出現(xiàn)錯誤，然后運行程序，檢查是否和自己當初的設(shè)想一樣，一直到結(jié)果能讓自己滿意。</p><

11、;p>　?。?）比較得出兩種查找算法的優(yōu)缺。</p><p>　　2.3 相關(guān)的知識點</p><p>　?。?）C語言表示靜態(tài)查找表的順序存儲結(jié)構(gòu)</p><p>　　typedef struct {</p><p>　　ElemType *elem; //數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，0號單元留空</p&g

12、t;<p>　　int length; //表的長度</p><p>　　} SSTable; </p><p>　　（2）查找算法的衡量指標</p><p>　　查找可能產(chǎn)生“成功”與“不成功”兩種結(jié)果，但在實際應(yīng)用的大多數(shù)情況下，查找成功的可能性比不成功的可能性大得多，特別是在記錄數(shù)中n很大時，查找不成功的概率可以忽略不計。當查找不

13、成功的情況不能忽視時，查找算法的平均長度應(yīng)該是查找成功時的平均查找長度與查找不成功時的平均查找長度之和，平均查找長度為：</p><p><b>　　ASL= </b></p><p>　　其中，n為元素的個數(shù)； ci是查找第i 個記錄需進行的比較次數(shù)；pi是查找第i個記錄的概率，一般可認為查找每個記錄的概率是相等的，即p1=p2=…=pn=1/n【2】。</

14、p><p>　　3 算法分析及程序編寫</p><p>　　3.1.順序表的查找</p><p><b>　　基本思想</b></p><p>　　從查找表的一端開始，逐個將記錄的關(guān)鍵字值和給定值進行比較，如果某個記錄的關(guān)鍵字值和給定值相等，則稱查找成功；否則，說明查找表中不存在關(guān)鍵字值為給定值的記錄，則稱查找失敗。<

15、/p><p>　?。?）順序查找算法流程圖</p><p>　　算法流程圖如圖3-1所示：</p><p>　　圖3-1：順序查找算法流程圖</p><p>　?。?）順序查找算法代碼如下</p><p>　　int Search_Seq(SSTable *table, ElemType key)</p>&

16、lt;p>　　{ /*在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為零。*/</p><p>　　table->elem[0]=key; //設(shè)置哨兵</p><p>　　int result=0; // 找不到時，返回0</p><p><b&

17、gt;　　int i;</b></p><p>　　for (i=table->length; i>=1;i--) </p><p>　　{ //從后往前找</p><p>　　if (table->elem[i]==key) </p><p><b>　　{</b>

18、</p><p>　　result=i; //找到關(guān)鍵字的時候，該元素的位置</p><p>　　break; </p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　return result; //找不到

19、時返回</p><p><b>　　}</b></p><p>　　<4>順序查找算法性能分析</p><p>　　對于順序查找，不論給定值key為何值，查找不成功時和給定值進行比較的關(guān)鍵字個數(shù)均為n+1.假設(shè)查找成功與不成功的可能性相同，對每個記錄的查找概率也相等，則Pi=1/（2n）,此時順序查找的平均查找長度為[3]：<

20、/p><p>　　ASL= +(1/2)(n+1)</p><p>　　=(3/4)(n+1)</p><p><b>　　<5>結(jié)論</b></p><p>　　順序查找的優(yōu)點是算法簡單，且對表的結(jié)構(gòu)沒有任何要求。它的缺點是查找效率低，因此，當表中元素個數(shù)比較多時，不宜采用順序查找。 </p>

21、<p><b>　　3.2.折半查找</b></p><p>　?。?）使用折半查找必須具備兩個前提條件</p><p>　　a：要求查找表中的記錄按關(guān)鍵字有序(假設(shè)：從小到大有序)</p><p>　　b：只能適用于順序存儲結(jié)構(gòu) </p><p><b>　?。?）基本思想</b>&

22、lt;/p><p>　　先取查找表的中間位置的關(guān)鍵字值與給定關(guān)鍵字值作比較，若它們的值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，說明要查找的記錄一定在查找表的后半部分，則在查找表的后半部分繼續(xù)使用折半查找；若給定值比該記錄的關(guān)鍵字值小，說明要查找的記錄一定在查找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找，直到查找成功，或者查找失敗。</p><p><b>　　(3）

23、查找流程圖</b></p><p>　　流程圖如圖3-2所示：</p><p>　　圖3-2：折半查找算法流程圖</p><p>　　(4）折半查找算法的代碼</p><p>　　int Search_Bin(SSTable *table, ElemType key)</p><p>　　{/*在有序表S

24、T中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0.*/</p><p>　　int low=1;</p><p>　　int high=table->length; //置區(qū)間初值</p><p>　　int result=0; // 找不到時，返回0</p><p>　　wh

25、ile(low <= high)</p><p><b>　　{</b></p><p>　　int mid=(low+high)/2; //中間的數(shù)據(jù)元素</p><p>　　if(table->elem[mid]==key)</p><p><b>　　{</b></

26、p><p>　　result=mid;</p><p><b>　　break;</b></p><p>　　} //找到待查元素</p><p>　　else if(key<table->elem[mid])</p><p><b>　　{&l

27、t;/b></p><p>　　high=mid-1;</p><p>　　} //繼續(xù)在前半?yún)^(qū)間進行查找</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　low=mid+1;</p>

28、<p>　　} //繼續(xù)在后半?yún)^(qū)間進行查找</p><p><b>　　}</b></p><p>　　return result;</p><p><b>　　}[5]</b></p><p>　?。?）折半查找算法性能分析</p><p>　　在

29、折半查找的過程中，每經(jīng)過一次比較，查找范圍都要縮小一半，所以折半查找的最大查找長度為</p><p>　　MSL=[log2 n]+1</p><p>　　當n足夠大時，可近似的表示為log2(n)。</p><p><b>　　（6）結(jié)論</b></p><p>　　折半查找要求查找表按關(guān)鍵字有序，而排序是一種很費時的

30、運算；另外，折半查找要求表是順序存儲的，為保持表的有序性，在進行插入和刪除操作時，都必須移動大量記錄。因此，折半查找的高查找效率是以犧牲排序為代價的，它特別適合于一經(jīng)建立就很少移動、而又經(jīng)常需要查找的線性表。</p><p>　　可見在查找速度上，折半查找比順序查找速度要快的多，這是它的主要優(yōu)點[4]。 </p><p><b>　　4 測試分析</b></p

31、><p><b>　　輸入元素有誤</b></p><p>　　（1）：若輸入的元素個數(shù)不合理，元素個數(shù)少于n，這種輸入造成的的結(jié)果是系統(tǒng)一直等待元素的輸入，即得不到結(jié)果。如圖4-1所示：</p><p>　　圖4-1：輸入元素個數(shù)少時的運行情況</p><p>　?。?）若輸入元素個數(shù)大于n時，系統(tǒng)將從第一個元素起，自動選

32、取前n個元素作為有效元素，進行程序的后續(xù)運行。這種情況下的結(jié)果如圖4-2所示：</p><p>　　圖4-2：輸入元素個數(shù)多時的運行情況</p><p><b>　　查找失敗</b></p><p>　　這種情況是指在n個元素中沒有與關(guān)鍵字相同的元素存在，所以程序運行的結(jié)果是查找失敗。運行結(jié)果如圖4-3所示：</p><p&

33、gt;　　圖4-3：查找失敗時的運行情況</p><p><b>　　查找成功</b></p><p>　　若查找成功，即元素輸入無誤，且有關(guān)鍵字存在的情況，這個時候的運行結(jié)果如圖4-4所示[5]：</p><p>　　圖4-4：查找成功時的運行情況</p><p><b>　　5 總結(jié)和體會</b>

34、;</p><p>　　5.1 課程設(shè)計總結(jié)</p><p>　　“書到用時方恨少”。在這次課程設(shè)計，我感觸最深的當屬查閱大量的設(shè)計資料了，為了讓自己的設(shè)計更加完善，查閱這方面的設(shè)計資料是十分必要的，看著那么大疊的書籍、資料擺在自己的面前，有些時候還要上網(wǎng)查閱相關(guān)知識點，并且還要整理出有用的知識點，這對于我來說，是在是個不小的挑戰(zhàn)。所以，以后一定要多看自己專業(yè)方面的書籍，增長自己的知識。而

35、且，寫程序是一件十分需要耐心的活，一個不小心，后果就可能是幾個小時的思考和調(diào)試，幸好這次的課題我并不陌生，所以，并沒有自己想象中的艱難。但是，用的時間和精力卻絕對也不少。</p><p><b>　　5.2 心得與體會</b></p><p>　　這次課程設(shè)計，使我對《數(shù)據(jù)結(jié)構(gòu)》這門課程有了更深入的了解?！稊?shù)據(jù)結(jié)構(gòu)》是一門實踐性較強的課程，為了學好這門課程，必須在掌握

36、理論知識的同時，加強上機實踐。一個人的力量是有限的，要想把課程設(shè)計做的更好，就要學會參考一定的資料，吸取別人的經(jīng)驗，讓自己和別人的思想有機的結(jié)合起來，得出屬于你自己的靈感。</p><p>　　在本課程設(shè)計中，我明白了理論與實際應(yīng)用相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設(shè)計技能以及合作能力。這次課程設(shè)計同樣提高了我的綜合運用所學知識的能力。程序的編寫需要有耐心，有些事情

37、看起來很復雜，但問題需要一點一點去解決，分析問題，把問題一個一個劃分，劃分成小塊以后就逐個去解決。再總體解決大的問題。這樣做起來不僅有條理也使問題得到了輕松的解決。</p><p>　　通過這兩周的課程設(shè)計，我認識到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程。需要多花時間上機練習。這次的程序訓練培養(yǎng)了我實際分析問題、編程和動手能力，使我掌握了程序設(shè)計的基本技能，提高了我適應(yīng)實際，實踐編程的能力。</p><p

38、><b>　　參考文獻：</b></p><p>　　[1]嚴蔚敏，吳偉民. 《數(shù)據(jù)結(jié)構(gòu):C語言版》 清華大學出版社，2012.5</p><p>　　[2]Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述（英文版第二版）.北京：人民郵電出版社，2005</p><p>　　[3]李峰，謝中科.C語

39、言程序設(shè)計.上海：復旦大學出版社，2011</p><p>　　[4]Baloukas, C., Risco-Martin, J. L., Atienza, D., et al. Optimization methodology of dynamic data structures based on genetic algorithms for multimedia embedded systems[J]. Jo

40、urnal of Systems and Software, 2009, 82(4): 590-602.</p><p>　　[5]李春葆，尹為民.數(shù)據(jù)結(jié)構(gòu)教程上機指導（第三版）.北京：清華大學出版社,2008</p><p><b>　　附錄：程序源代碼：</b></p><p>　　#include<iostream></

41、p><p>　　#include<stdlib.h></p><p>　　#include<stdio.h></p><p>　　using namespace std;</p><p>　　typedef int ElemType ;</p><p>　　//用C語言定義順序存儲結(jié)構(gòu) </

42、p><p>　　typedef struct {</p><p>　　ElemType *elem; //數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，0號單元留空</p><p>　　int length; //表的長度</p><p>　　} SSTable; </p><p>　　void Creat

43、e(SSTable *table, int length); // 構(gòu)建順序表</p><p>　　void Destroy(SSTable *table);</p><p>　　int Search_Seq(SSTable *table, ElemType key);</p><p>　　void Traverse(SSTable *table, voi

44、d (*visit)(ElemType elem));</p><p>　　void Create(SSTable **table, int length)</p><p>　　{ // 構(gòu)建順序表</p><p>　　SSTable *t = (SSTable*) malloc(sizeof(SSTable));</p><

45、;p>　　t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));</p><p>　　t->length=length;</p><p><b>　　*table=t;</b></p><p><b>　　}</b></p><p

46、>　　void FillTable(SSTable *table)</p><p>　　{ // 無序表的輸入 </p><p>　　ElemType *t=table->elem;</p><p>　　for(int i=0; i<table->length; i++)</p><p><b&g

47、t;　　{</b></p><p><b>　　t++;</b></p><p>　　scanf("%d", t);</p><p>　　getchar();</p><p><b>　　}</b></p><p><b>　　}&l

48、t;/b></p><p>　　void Destroy(SSTable *table)</p><p>　　{ //銷毀表</p><p>　　free(table->elem);</p><p>　　free(table);</p><p><b>　　}</b>&

49、lt;/p><p>　　void PrintTable(SSTable *table)</p><p>　　{ // 打印查找表中的元素</p><p><b>　　int i;</b></p><p>　　ElemType *t=table->elem;</p><p>　　

50、for(i=0; i<table->length; i++)</p><p><b>　　{</b></p><p><b>　　t++;</b></p><p>　　printf("%d ", *t);</p><p><b>　　}</b>&

51、lt;/p><p><b>　　}</b></p><p>　　//順序（哨兵）查找算法</p><p>　　int Search_Seq(SSTable *table, ElemType key)</p><p>　　{ /*在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則

52、為零。*/</p><p>　　table->elem[0]=key; //設(shè)置哨兵</p><p>　　int result=0; // 找不到時，返回0</p><p><b>　　int i;</b></p><p>　　for (i=table->le

53、ngth; i>=1;i--) </p><p>　　{ //從后往前找</p><p>　　if (table->elem[i]==key) </p><p><b>　　{</b></p><p>　　result=i; //找到關(guān)鍵字的時候，該元素的位置</p>

54、<p>　　break; </p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　return result; //找不到時返回</p><p><b>　　}</b></p><p

55、>　　void Sort(SSTable *table )</p><p>　　{ // 排序算法 </p><p><b>　　int i, j;</b></p><p>　　ElemType temp;</p><p>　　for (i=table->length; i>=1 ;i-

56、-) // 從前往后找</p><p><b>　　{</b></p><p>　　for (j=1; j<i; j++)</p><p>　　{ </p><p>　　if(table->elem[j]>table->elem[j+1])</p><p&

57、gt;　　{ //從小到大排列</p><p>　　temp=table->elem[j];</p><p>　　table->elem[j]=table->elem[j+1]; //元素后移</p><p>　　table->elem[j+1]=temp;</p><p><b>　　}<

58、;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int Search_Bin(SSTable *table, ElemType key)</p><p

59、>　　{/*在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0.*/</p><p>　　int low=1;</p><p>　　int high=table->length; //置區(qū)間初值</p><p>　　int result=0; // 找不到時，返回0</p>

60、<p>　　while(low <= high)</p><p><b>　　{</b></p><p>　　int mid=(low+high)/2; //中間的數(shù)據(jù)元素</p><p>　　if(table->elem[mid]==key)</p><p><b>　　{

61、</b></p><p>　　result=mid;</p><p><b>　　break;</b></p><p>　　} //找到待查元素</p><p>　　else if(key<table->elem[mid])</p><p>

62、;<b>　　{</b></p><p>　　high=mid-1;</p><p>　　} //繼續(xù)在前半?yún)^(qū)間進行查找</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　low=mi

63、d+1;</p><p>　　} //繼續(xù)在后半?yún)^(qū)間進行查找</p><p><b>　　}</b></p><p>　　return result;</p><p><b>　　}</b></p><p><b>　　// 主函數(shù) </b>

64、;</p><p>　　int main(int argc, char* argv[])</p><p><b>　　{</b></p><p>　　SSTable *table;</p><p>　　int r; //元素的位置</p><p><b>　　intn;</b

65、></p><p>　　ElemType key;</p><p>　　printf("輸入 n:");</p><p>　　scanf("%d",&n);</p><p>　　Create(&table, n);//建立表</p><p>　　cout&l

66、t;<"請輸入"<<n<<"個值"<<endl;</p><p>　　FillTable(table);//輸入無序表的值</p><p>　　printf("您輸入的 %d 個值是：\n",n);</p><p>　　PrintTable(table);//打印無

67、序表</p><p>　　cout<<endl;</p><p>　　printf("請輸入關(guān)鍵字的值:\n");</p><p>　　scanf("%d",&key);</p><p>　　printf("順序法查找運行結(jié)果如下：\n ");</p>

68、<p>　　Search_Seq(table,key);//順序（哨兵）查找算法</p><p>　　r=Search_Seq(table,key);</p><p>　　if( r>0) </p><p>　　printf(" 關(guān)鍵字 %d 在表中的位置是： %d\n",key, r);</p><p

69、><b>　　else </b></p><p>　　printf ("查找失敗，表中無此數(shù)據(jù)。\n"); </p><p>　　Sort(table);//對無序表進行排序</p><p>　　printf("數(shù)據(jù)排序后的順序如下：\n ");</p><p>　　P

70、rintTable(table);//打印有序表</p><p>　　printf("\n");</p><p>　　printf("折半查找法運行結(jié)果如下：\n ");</p><p>　　r=Search_Bin(table,key);//折半查找算法</p><p><b>　　if(

71、r>0)</b></p><p>　　printf(" 關(guān)鍵字 %d 在表中的位置是： %d\n",key, r);</p><p><b>　　else {</b></p><p>　　printf ("查找失敗，表中無此數(shù)據(jù)。\n");}</p><p>