排序綜合數(shù)據(jù)結(jié)構(gòu)課程設(shè)計論文

1、排序綜合成都吃喝網(wǎng) 00 0 0 0二10 年 6 月1題 目 ） N 44第 3天 年月日年月日年月日遵守各項紀律，工作刻苦努力，具有良好的科學(xué)工作態(tài)度。6作表通過實驗、試驗、查閱文獻、深入生產(chǎn)實踐等渠道獲取與課程設(shè)計有關(guān)的材料。能運用所學(xué)知識和技能去發(fā)現(xiàn)與解決實際問題，能正確處理實驗數(shù)據(jù)，能對課題進行理論分析，得出有價值的結(jié)論。能獨立查閱相關(guān)文獻和從事其他調(diào)研；能提出并較好地論述課題的實施方案；有收集、加工各種信息及獲取新知識的能力。能力操作等實驗工作，數(shù)據(jù)正確、可靠；研究思路清晰、完整。水平55具有較強的數(shù)據(jù)運算與處理能力；能運用計算機進行資料搜集、加工、處理和輔助設(shè)計等。 符合本專業(yè)相

2、關(guān)規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。成果質(zhì)量綜述簡練完整，有見解；立論正確，論述充分，結(jié)論嚴謹合理；實驗正確，分析處理科學(xué)。 對前人工作有改進或突破，或有獨特見解。指導(dǎo)教師評語年 月 日- 2 -2摘 要數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式，是其在計算機內(nèi)的表示；此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運算才有意義。在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴重的依賴于是否選

3、擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。排序算型泡排序，直接插入排序，簡單選擇排序，希爾排序，快速排序，堆排序等，各有情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復(fù)雜性的度量。關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu)；算法比較；比較次數(shù)；時間復(fù)雜度- 3 -3目錄摘要. 11概要. 4 4 52排序算法 . 7 8 8 9 9 9 9 9 3流程圖及詳細算法. 10 4運行結(jié)果 . 18 5結(jié)束語 . 25參考文獻. 24- 4 -41 1.1 設(shè)計目的數(shù)據(jù)結(jié)構(gòu)與算法課程主

4、要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。1）本演示程序?qū)σ韵?6 種常用的內(nèi)部排序算法進行實測比較：冒泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序；2）待排序表的元素的關(guān)鍵字為整數(shù)。比較的指標為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換記為 3 次移動）；3）演示程序以以用戶和計算機的對話方式執(zhí)行，在計算機終端上顯示提示信息，對隨機數(shù)組進行排序，并輸出比較指標值；4）最后對結(jié)果作出簡單分析

5、。1.2 預(yù)期目標到對各算法進行比較的目的。通過此次課程設(shè)計主要達到以下目的了解并掌握數(shù)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；提高綜合運用發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。- 5 -52 2.1 各排序算法的特點1）冒泡排序 1 2 2 第 3 2 3 1 2 2）直接插入排序 , ; 3）簡單選擇排序（1）在一組元素ViVn-12）若它不是這3素中剔除這個具有最小排序碼的元素，在剩下的元素 Vi+1Vn-1中重復(fù)執(zhí)行第（12）步，直到剩余元素只有一個為止。4）快速排序放在一組，其余的放在另一組，然后分別對兩組數(shù)據(jù)排序；5） 希爾排序先取

6、一個正整數(shù) d1n，把所有序號相隔d1 的數(shù)組元素放一組，組內(nèi)進行直接插入排序；然后取d2d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止；6) 堆排序- 6 -6堆排序是一樹形選擇排序，在排序過程中，將 R1.N看成是一顆完全二叉擇最小的元素；堆的定義: N 個元素的序列 K1K2K3.，Kn.稱為堆，當且僅當該序列滿足特性：KiK2i Ki K2i+1(1 IN/2)2.2各算法的比較方法1.穩(wěn)定性比較插入排序、冒泡排序、簡單選擇排序及其他線形排序是穩(wěn)定的希爾排序、快速排序、堆排序是不穩(wěn)定的2.時間復(fù)雜性比較插入排序、冒泡排序、選擇排序的時間復(fù)雜性為 O(n2)其

7、它非線形排序的時間復(fù)雜性為 O(nlog2n)線形排序的時間復(fù)雜性為 O(n);3.輔助空間的比較線形排序的輔助空間為 O(n),其它排序的輔助空間為 O(1);4.其它比較序能達到較快的速度。反而在這種情況下，快速排序反而慢了。當 n 入或冒泡排序。若待排序的記錄的關(guān)鍵字在一個明顯有限范圍內(nèi)時 ,且空間允許是用桶排序。當 n 較大時，關(guān)鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當 n 允許的情況下，宜用歸并排序。當 n 堆排序- 7 -73 3.1流程圖函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：strandBubbleSortInsertSortSelectSortQuickSortSh

8、ellSortHeapSorInitLinkListRandomNuLTDisplay圖 3.21）Main 為主函數(shù)模塊2bubblesortinsertsortselectsortquicksortshellsortheansort分別對應(yīng)冒泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序的各函數(shù)模塊3）在初始化數(shù)據(jù)之后，選擇對應(yīng)的排序模塊進行排序，并對排序做出比較3.3 可排序表的抽象數(shù)據(jù)類型定義：typedef structint key;/定義一個RedType型結(jié)構(gòu)體，存放關(guān)鍵字/關(guān)鍵字為整型 RedType;class LinkList/定義一個順序表- 8 -8p

9、ublic:RedType rMAXSIZE+1;為RedType/長度為MAXSIZE+1的數(shù)組r，數(shù)組里每個元素均int Length;/數(shù)組長度int CmpNum, ChgNum;LinkList();/關(guān)鍵字的比較次數(shù)，移動次數(shù)/構(gòu)造函數(shù)bool LT(int i, int j);void Display();void Insert( int dk);void ShellSort();/比較i和j的大小/輸出數(shù)組元素/插入排序/希爾排序int Partition( int low, int high); /比基準小的數(shù)放左邊，比起大的數(shù)放右邊，返回基準位置void QSort( in

10、t low, int high); /從low到high位置進行快速排序void QuickSort();/對有序表進行快速排序void HeapAdjust( int s, int m); /將無序堆調(diào)整為大頂堆void HeapSort();/堆排序，將大頂堆轉(zhuǎn)換為小頂堆/冒泡排序void BubbleSort();int SelectMinKey( int k);void SelSort();/找到數(shù)組中最小值，返回最小值位置/對順序表進行選擇排序void SelectSort();void AllAbove();/界面設(shè)計/統(tǒng)計以上所有排序關(guān)鍵字的比較次數(shù)、移動次數(shù)及所消耗的時間;3.

11、4 程序代碼3.4.1 函數(shù)聲明- 9 -910 = i =- 10 -10 4.3.2 六種排序算法代碼/插入排序 = i - =i- j0 j + + - 11 -11/希爾排序 /快速排序 = = - + - 12 -12 -/堆排序 j= - =2* j j - - i-/冒泡排序 = i = j- +- 13 -13 + + /選擇排序 = k = = i j= 4.3.3 排序算法的選擇 - 14 -14 = - = - = - = - 15 -15 = - = -4.3.4主函數(shù)程序代碼 = = = - - 16 -16 = - = - = - =- 17 -17= - = -

12、4 4.1 調(diào)試分析1對正序、逆序和若干不同程度隨機打亂的可排序表，進行各種排序方法定程序的隨機亂序算法，對偽隨機數(shù)序列的產(chǎn)生有了具體的認識和實踐。2將排序算法中的關(guān)鍵字比較和交換分別由 Less 和 Swap 兩個內(nèi)部操作實- 18 -18圖 1圖 2圖 3圖 4圖 5圖 6圖 74.3 排序算法的評價對各種表長和測試組數(shù)進行了測試，程序運行正常。分析實測得到的數(shù)值，6插入排序 希爾排序 快速排序 堆排序 冒泡排序 選擇排序第三多第二多 亂否差異 亂否差異 亂否差異 與亂否無很小稍多移動次數(shù) 排序的兩 亂否差異 亂否差異 正和逆序越多 較小 很小 越多(1)若n較小(如n50)，可采用直接插

13、入或直接選擇排序。倍少于直接插人，應(yīng)選直接選擇排序為宜。(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜；(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。在一個學(xué)期后的基礎(chǔ)理論知識的學(xué)習(xí)后進入實踐的操作雖然仍就有些困難會通過實習(xí)我的收獲如下1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。3、通過實際編譯系統(tǒng)- 23 -23的分析設(shè)計、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。4、通過課全局觀念。

14、根據(jù)我在實習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴密。3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。4、認真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。5、在課余時程序的能力，學(xué)習(xí)文檔編寫規(guī)范，培養(yǎng)獨立學(xué)習(xí)、吸取他人經(jīng)驗，樹立團隊協(xié)作得深入了解剖析它以便得到提高。細心、耐心、團結(jié)、求知，是我這次課程設(shè)計最大的收獲。同時要感謝老師這幾天的悉心教導(dǎo)。1 寧正元，王秀麗.算法與數(shù)據(jù)的結(jié)構(gòu)，2006：29322 楊輝.楊輝的縱橫圖論，2003：12143 唐王希.太乙金鏡式經(jīng)，2000：35374 王力柱。與數(shù)據(jù)結(jié)構(gòu)。棧，2003（81