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

兩種常用查找算法的比較與實(shí)現(xiàn)摘 要：本次課程設(shè)計(jì)主要研究幾種常用查找算法的比較與實(shí)現(xiàn)，查找的算法有很多種：靜態(tài)查找表的順序表、有序表、索引順序表等查找結(jié)構(gòu)；動(dòng)態(tài)查找表的二叉排序樹、哈希查找等查找結(jié)構(gòu)。本次的課程設(shè)計(jì)主要研究?jī)煞N常見的查找算法：順序查找和折半查找，分析比較它們的時(shí)間復(fù)雜度，并且在此基礎(chǔ)上用C語(yǔ)言對(duì)它們進(jìn)行算法編程、調(diào)試和運(yùn)行。關(guān)鍵詞：C語(yǔ)言；順序查找；折半查找;時(shí)間復(fù)雜度。1 引 言“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，“數(shù)據(jù)結(jié)構(gòu)”的研究不僅涉及到計(jì)算機(jī)硬件的研究范圍，而且和計(jì)算機(jī)軟件的研究有著密切的關(guān)系無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，一遍查找和存取數(shù)據(jù)元素更為方便。因此，可以認(rèn)為“數(shù)據(jù)結(jié)構(gòu)”是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。課程設(shè)計(jì)是我們專業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練，是實(shí)踐性教學(xué)的一個(gè)重要環(huán)節(jié)。而數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，更要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。在日常生活中，人們幾乎每天都要進(jìn)行“查找”工作。例如，在電話號(hào)碼薄中查閱“某單位”或“某人”的電話號(hào)碼；在字典中查閱“某個(gè)詞”的讀音和含義等等。而同樣地，在各種系統(tǒng)軟件和應(yīng)用軟件中，也存在“查找”：如編譯程序中符號(hào)表、信息處理表中相關(guān)信息的查找。所以，“查找”就是在一個(gè)含有眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個(gè)“特定的”數(shù)據(jù)元素（或記錄）【1】。在計(jì)算機(jī)中進(jìn)行查找的方法也會(huì)隨數(shù)據(jù)結(jié)構(gòu)不同而不同。在此，引入“查找表”的概念：同類數(shù)據(jù)元素構(gòu)成的集合。所以，這次的課程設(shè)計(jì)就可以從靜態(tài)查找表的幾種典型的算法來實(shí)現(xiàn)對(duì)數(shù)據(jù)元素的查找的算法和操作的實(shí)現(xiàn)和比較。1.1課程設(shè)計(jì)背景數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)作為獨(dú)立的教學(xué)環(huán)節(jié)，是計(jì)算機(jī)相關(guān)專業(yè)集中實(shí)踐環(huán)節(jié)系列之一，是學(xué)習(xí)完數(shù)據(jù)結(jié)構(gòu)課程后進(jìn)行的一次全面的綜合練習(xí)。所以需要我們了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，并且具備初步的獨(dú)立分析和設(shè)計(jì)能力，同時(shí)要掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼測(cè)試等基本方法和技能，提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力。所以這次課程設(shè)計(jì)的目的在于：加強(qiáng)學(xué)生對(duì)C語(yǔ)言的基本知識(shí)和技能；加深對(duì)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)理論和基本知識(shí)的理解，提高解決實(shí)際問題的實(shí)踐能力；同時(shí)幫助調(diào)動(dòng)學(xué)生的積極性和能動(dòng)性，培養(yǎng)學(xué)生的自學(xué)、動(dòng)手能力。1.2課程設(shè)計(jì)目標(biāo)本次課程設(shè)計(jì)，我準(zhǔn)備用不同的兩種常見的查找方法：針對(duì)順序查找表中查找方法，如順序查找、折半查找等。并且通過用這些算法實(shí)現(xiàn)對(duì)某個(gè)“特定的”數(shù)據(jù)元素（關(guān)鍵字）的查找，分析這些操作的性能：它們各自的時(shí)間復(fù)雜度、空間復(fù)雜度和其它的一些性能，同時(shí)記錄每種查找方法的優(yōu)缺點(diǎn)，比較得出它們的查找效率和查找范圍。2 設(shè)計(jì)概要2.1 問題描述對(duì)于不同的查找算法，它們各自的時(shí)間復(fù)雜度和空間復(fù)雜度不同，查找的思想和算法也明顯不同，所以要分析它們的特點(diǎn)和效率，我們要多方面比較：要比較時(shí)間復(fù)雜度，我們可以從它們的查找長(zhǎng)度側(cè)面比較出來；而它們算法的實(shí)現(xiàn)就要熟悉它們的查找思想，熟練應(yīng)用C語(yǔ)言編寫合適的程序。2.2 設(shè)計(jì)思路靜態(tài)查找表有順序表和鏈?zhǔn)奖韮煞N表示方法，在這次的課程設(shè)計(jì)里，我用順序存儲(chǔ)表來表示這兩種查找算法的程序。我的設(shè)計(jì)思路及步驟如下：（1）熟悉兩種算法的編程思想,畫出流程圖。（2）先編寫兩種算法的子程序，再遍寫主程序調(diào)用它們。（3）分步調(diào)試子程序和主程序，直到不再出現(xiàn)錯(cuò)誤，然后運(yùn)行程序，檢查是否和自己當(dāng)初的設(shè)想一樣，一直到結(jié)果能讓自己滿意。（4）比較得出兩種查找算法的優(yōu)缺。2.3 相關(guān)的知識(shí)點(diǎn)（1）C語(yǔ)言表示靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)typedef struct ElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空 int length; /表的長(zhǎng)度 SSTable; （2）查找算法的衡量指標(biāo)查找可能產(chǎn)生“成功”與“不成功”兩種結(jié)果，但在實(shí)際應(yīng)用的大多數(shù)情況下，查找成功的可能性比不成功的可能性大得多，特別是在記錄數(shù)中n很大時(shí)，查找不成功的概率可以忽略不計(jì)。當(dāng)查找不成功的情況不能忽視時(shí)，查找算法的平均長(zhǎng)度應(yīng)該是查找成功時(shí)的平均查找長(zhǎng)度與查找不成功時(shí)的平均查找長(zhǎng)度之和，平均查找長(zhǎng)度為： ASL= 其中，n為元素的個(gè)數(shù)； ci是查找第i 個(gè)記錄需進(jìn)行的比較次數(shù)；pi是查找第i個(gè)記錄的概率，一般可認(rèn)為查找每個(gè)記錄的概率是相等的，即p1=p2=pn=1/n【2】。3 算法分析及程序編寫3.1.順序表的查找（1） 基本思想從查找表的一端開始，逐個(gè)將記錄的關(guān)鍵字值和給定值進(jìn)行比較，如果某個(gè)記錄的關(guān)鍵字值和給定值相等，則稱查找成功；否則，說明查找表中不存在關(guān)鍵字值為給定值的記錄，則稱查找失敗。 （2）順序查找算法流程圖算法流程圖如圖3-1所示：圖3-1：順序查找算法流程圖（3）順序查找算法代碼如下int Search_Seq(SSTable *table, ElemType key) /*在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為零。*/table-elem0=key; /設(shè)置哨兵int result=0; / 找不到時(shí)，返回0int i;for (i=table-length; i=1;i-) /從后往前找 if (table-elemi=key) result=i; /找到關(guān)鍵字的時(shí)候，該元素的位置break; return result; /找不到時(shí)返回順序查找算法性能分析對(duì)于順序查找，不論給定值key為何值，查找不成功時(shí)和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)均為n+1.假設(shè)查找成功與不成功的可能性相同，對(duì)每個(gè)記錄的查找概率也相等，則Pi=1/（2n）,此時(shí)順序查找的平均查找長(zhǎng)度為3：ASL= +(1/2)(n+1)=(3/4)(n+1)結(jié)論順序查找的優(yōu)點(diǎn)是算法簡(jiǎn)單，且對(duì)表的結(jié)構(gòu)沒有任何要求。它的缺點(diǎn)是查找效率低，因此，當(dāng)表中元素個(gè)數(shù)比較多時(shí)，不宜采用順序查找。 3.2.折半查找（1）使用折半查找必須具備兩個(gè)前提條件a：要求查找表中的記錄按關(guān)鍵字有序(假設(shè)：從小到大有序) b：只能適用于順序存儲(chǔ)結(jié)構(gòu) （2）基本思想先取查找表的中間位置的關(guān)鍵字值與給定關(guān)鍵字值作比較，若它們的值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，說明要查找的記錄一定在查找表的后半部分，則在查找表的后半部分繼續(xù)使用折半查找；若給定值比該記錄的關(guān)鍵字值小，說明要查找的記錄一定在查找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找，直到查找成功，或者查找失敗。(3）查找流程圖流程圖如圖3-2所示：圖3-2：折半查找算法流程圖(4）折半查找算法的代碼int Search_Bin(SSTable *table, ElemType key)/*在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0.*/ int low=1; int high=table-length; /置區(qū)間初值 int result=0; / 找不到時(shí)，返回0 while(low elemmid=key)result=mid;break; /找到待查元素else if(keyelemmid)high=mid-1; /繼續(xù)在前半?yún)^(qū)間進(jìn)行查找elselow=mid+1; /繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 return result;5 （5）折半查找算法性能分析在折半查找的過程中，每經(jīng)過一次比較，查找范圍都要縮小一半，所以折半查找的最大查找長(zhǎng)度為 MSL=log2 n+1當(dāng)n足夠大時(shí)，可近似的表示為log2(n)。（6）結(jié)論折半查找要求查找表按關(guān)鍵字有序，而排序是一種很費(fèi)時(shí)的運(yùn)算；另外，折半查找要求表是順序存儲(chǔ)的，為保持表的有序性，在進(jìn)行插入和刪除操作時(shí)，都必須移動(dòng)大量記錄。因此，折半查找的高查找效率是以犧牲排序?yàn)榇鷥r(jià)的，它特別適合于一經(jīng)建立就很少移動(dòng)、而又經(jīng)常需要查找的線性表?？梢娫诓檎宜俣壬?，折半查找比順序查找速度要快的多，這是它的主要優(yōu)點(diǎn)4。 4 測(cè)試分析1. 輸入元素有誤（1）：若輸入的元素個(gè)數(shù)不合理，元素個(gè)數(shù)少于n，這種輸入造成的的結(jié)果是系統(tǒng)一直等待元素的輸入，即得不到結(jié)果。如圖4-1所示：圖4-1：輸入元素個(gè)數(shù)少時(shí)的運(yùn)行情況（2）若輸入元素個(gè)數(shù)大于n時(shí)，系統(tǒng)將從第一個(gè)元素起，自動(dòng)選取前n個(gè)元素作為有效元素，進(jìn)行程序的后續(xù)運(yùn)行。這種情況下的結(jié)果如圖4-2所示：圖4-2：輸入元素個(gè)數(shù)多時(shí)的運(yùn)行情況2. 查找失敗這種情況是指在n個(gè)元素中沒有與關(guān)鍵字相同的元素存在，所以程序運(yùn)行的結(jié)果是查找失敗。運(yùn)行結(jié)果如圖4-3所示：圖4-3：查找失敗時(shí)的運(yùn)行情況3. 查找成功若查找成功，即元素輸入無誤，且有關(guān)鍵字存在的情況，這個(gè)時(shí)候的運(yùn)行結(jié)果如圖4-4所示5：圖4-4：查找成功時(shí)的運(yùn)行情況5 總結(jié)和體會(huì)5.1 課程設(shè)計(jì)總結(jié)“書到用時(shí)方恨少”。在這次課程設(shè)計(jì)，我感觸最深的當(dāng)屬查閱大量的設(shè)計(jì)資料了，為了讓自己的設(shè)計(jì)更加完善，查閱這方面的設(shè)計(jì)資料是十分必要的，看著那么大疊的書籍、資料擺在自己的面前，有些時(shí)候還要上網(wǎng)查閱相關(guān)知識(shí)點(diǎn)，并且還要整理出有用的知識(shí)點(diǎn)，這對(duì)于我來說，是在是個(gè)不小的挑戰(zhàn)。所以，以后一定要多看自己專業(yè)方面的書籍，增長(zhǎng)自己的知識(shí)。而且，寫程序是一件十分需要耐心的活，一個(gè)不小心，后果就可能是幾個(gè)小時(shí)的思考和調(diào)試，幸好這次的課題我并不陌生，所以，并沒有自己想象中的艱難。但是，用的時(shí)間和精力卻絕對(duì)也不少。5.2 心得與體會(huì)這次課程設(shè)計(jì)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了更深入的了解。數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的課程，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。一個(gè)人的力量是有限的，要想把課程設(shè)計(jì)做的更好，就要學(xué)會(huì)參考一定的資料，吸取別人的經(jīng)驗(yàn)，讓自己和別人的思想有機(jī)的結(jié)合起來，得出屬于你自己的靈感。在本課程設(shè)計(jì)中，我明白了理論與實(shí)際應(yīng)用相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設(shè)計(jì)技能以及合作能力。這次課程設(shè)計(jì)同樣提高了我的綜合運(yùn)用所學(xué)知識(shí)的能力。程序的編寫需要有耐心，有些事情看起來很復(fù)雜，但問題需要一點(diǎn)一點(diǎn)去解決，分析問題，把問題一個(gè)一個(gè)劃分，劃分成小塊以后就逐個(gè)去解決。再總體解決大的問題。這樣做起來不僅有條理也使問題得到了輕松的解決。通過這兩周的課程設(shè)計(jì)，我認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程。需要多花時(shí)間上機(jī)練習(xí)。這次的程序訓(xùn)練培養(yǎng)了我實(shí)際分析問題、編程和動(dòng)手能力，使我掌握了程序設(shè)計(jì)的基本技能，提高了我適應(yīng)實(shí)際，實(shí)踐編程的能力。參考文獻(xiàn)：1嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言版 清華大學(xué)出版社，2012.52MarkAllenWeiss.數(shù)據(jù)結(jié)構(gòu)與算法分析C語(yǔ)言描述（英文版第二版）.北京：人民郵電出版社，20053李峰，謝中科.C語(yǔ)言程序設(shè)計(jì).上海：復(fù)旦大學(xué)出版社，20114Baloukas, C., Risco-Martin, J. L., Atienza, D., et al. Optimization methodology of dynamic data structures based on genetic algorithms for multimedia embedded systemsJ. Journal of Systems and Software, 2009, 82(4): 590-602.5李春葆，尹為民.數(shù)據(jù)結(jié)構(gòu)教程上機(jī)指導(dǎo)（第三版）.北京：清華大學(xué)出版社,2008附錄：程序源代碼：#include#include#includeusing namespace std;typedef int ElemType ;/用C語(yǔ)言定義順序存儲(chǔ)結(jié)構(gòu) typedef struct ElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空 int length; /表的長(zhǎng)度 SSTable; void Create(SSTable *table, int length); / 構(gòu)建順序表void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem);void Create(SSTable *table, int length) / 構(gòu)建順序表 SSTable *t = (SSTable*) malloc(sizeof(SSTable);t-elem=(ElemType*)malloc(sizeof(ElemType)*(length+1);t-length=length;*table=t;void FillTable(SSTable *table) / 無序表的輸入 ElemType *t=table-elem;for(int i=0; ilength; i+)t+;scanf(%d, t);getchar();void Destroy(SSTable *table) /銷毀表free(table-elem);free(table);void PrintTable(SSTable *table) / 打印查找表中的元素 int i;ElemType *t=table-elem;for(i=0; ilength; i+) t+;printf(%d , *t);/順序（哨兵）查找算法int Search_Seq(SSTable *table, ElemType key) /*在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為零。*/table-elem0=key; /設(shè)置哨兵int result=0; / 找不到時(shí)，返回0int i;for (i=table-length; i=1;i-) /從后往前找 if (table-elemi=key) result=i; /找到關(guān)鍵字的時(shí)候，該元素的位置break; return result; /找不到時(shí)返回 void Sort(SSTable *table ) / 排序算法 int i, j;ElemType temp; for (i=table-length; i=1 ;i-) / 從前往后找 for (j=1; jelemjtable-elemj+1) /從小到大排列temp=table-elemj;table-elemj=table-elemj+1; /元素后移table-elemj+1=temp; int Search_Bin(SSTable *table, ElemType key)/*在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0.*/ int low=1; int