[數(shù)據(jù)結(jié)構(gòu)課程設(shè)計] 排序算法比較 - 天津科技大學(xué)

1、數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計教學(xué)任務(wù)書一、課程設(shè)計的目的 數(shù)據(jù)結(jié)構(gòu)與算法課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法是為了將實際問題中涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的： 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和

2、設(shè)計能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風。 二、課程設(shè)計的基本要求 1. 獨立思考，獨立完成：課程設(shè)計中各任務(wù)的設(shè)計和調(diào)試要求獨立完成，遇到問題可以討論，但不可以拷貝。 2. 做好上機準備：每次上機前，要事先編制好準備調(diào)試的程序，認真想好調(diào)試步驟和有關(guān)環(huán)境的設(shè)置方法，準備好有關(guān)的文件。 3. 按照課程設(shè)計的具體要求建立功能模塊，每個模塊要求按照如下幾個內(nèi)容認真完成： a）需求分析： 在該部分中敘述，每個

3、模塊的功能要求 b）概要設(shè)計： 在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義） c）詳細設(shè)計： 各個算法實現(xiàn)的源程序，對每個題目要有相應(yīng)的源程序（可以是一組程序，每個功能模塊采用不同的函數(shù)實現(xiàn)） 源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋 d）調(diào)試分析： 測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是那些，問題如何解決？），算法的改進設(shè)想 課程設(shè)計總結(jié)：（保存在word文檔中）總結(jié)可以包括：課程設(shè)計過程的收獲、遇到的

4、問題、解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計過程中對數(shù)據(jù)結(jié)構(gòu)課程的認識等內(nèi)容 4. 實現(xiàn)的結(jié)果必須進行檢查和演示，程序源代碼和程序的說明文件必須上交，作為考核內(nèi)容的一部分。（上交時每人交一份，文件夾的取名規(guī)則為：“學(xué)號 姓名”，如“06105198高魁”。該文件夾下至少包括：“源代碼”、“課程設(shè)計報告”、“可執(zhí)行文件”。由學(xué)習(xí)委員收集按規(guī)定時間統(tǒng)一上交） 5. 課程設(shè)計報告不要附源代碼，可以對重點函數(shù)及結(jié)構(gòu)進行說明。 6. 報告提交時間：第18周星期四檢查，第18周星期五由學(xué)習(xí)委員收集上交，遲交無成績。形式：課程設(shè)計報告（要求手寫）。 三. 課程設(shè)計內(nèi)容

5、1. 內(nèi)部排序演示 問題描述設(shè)計一個測試程序比較幾種排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受?；疽螅?）對起（冒）泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序、堆排序算法進行比較；（2）待排序的元素的關(guān)鍵字為整數(shù)。其中的數(shù)據(jù)要用偽隨機產(chǎn)生程序產(chǎn)生（如10000個），至少用5組不同的輸入數(shù)據(jù)做比較，再使用各種算法對其進行排序，記錄其排序時間，再匯總比較；（3）演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標值的列表，用條形圖（星號表示）進行表示，以便比較各種排序的優(yōu)劣。測試數(shù)據(jù)由隨機數(shù)產(chǎn)生器生成實現(xiàn)提示 主要工作是設(shè)法在已知算法中的適當位置插入對關(guān)鍵字的比較次數(shù)和

6、移動次數(shù)的計數(shù)操作。程序還可以考慮幾組數(shù)據(jù)的典型性，如：正序、逆序和不同程度的亂序。注意采用分塊調(diào)試的方法。選作內(nèi)容（1）對不同表長進行比較（2）驗證各算法的穩(wěn)定性2. 建通訊錄 問題描述設(shè)計散列表實現(xiàn)通訊錄查找系統(tǒng)，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序。 基本要求（1）設(shè)每個記錄有下列數(shù)據(jù)項：用戶名、電話號碼、地址；（2）從鍵盤輸入各記錄，分別以姓名為關(guān)鍵字建立散列表；（3）假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2；（4）哈希函數(shù)用除留余數(shù)法構(gòu)造，采用二次探測再散列法解決沖突；（5）查找并顯示給定電話號碼的記錄；（6）通訊錄信息

7、保存。測試數(shù)據(jù)取周圍熟悉的30個人的姓名及相關(guān)信息。實現(xiàn)提示人名長度均不超過19個字符，字符的取碼方法可直接利用C語言中的函數(shù)，并對過長的人名先作折疊處理。選做內(nèi)容（1）系統(tǒng)功能的完善（2）設(shè)計不同的散列函數(shù)，比較沖突率（3）在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化3. 校園導(dǎo)游咨詢 問題描述 設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)?；疽螅?）設(shè)計你所在的學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點的名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。（2）為來訪客人提供圖中任意景點相關(guān)信息的查詢

8、。（3）為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的最短的簡單路徑。測試數(shù)據(jù)由讀者根據(jù)實際情況指定實現(xiàn)提示一般情況下，校園的道路是由雙向通行的，可設(shè)校園平面圖是一個無向圖。頂點和邊均含有相關(guān)信息。選作內(nèi)容：（1）求校園圖的關(guān)節(jié)點（2）提供圖中任意景點問踟查詢，即求任意兩個景點之間的所有路徑。（3）提供校園圖中多個景點的最佳路線查詢，即求途經(jīng)這多個景點的最佳（短）路徑。（4）校園導(dǎo)游圖的景點和道路的修改擴充功能。（5）擴充道路信息，如道路類別（車道、人行道等），沿途景色等級，以至可按客人所需分別查詢?nèi)诵新窂交蜍嚱稚下窂交蛴^景路徑等。（6）擴充每個景點的鄰接景點的方向等信息，使得

9、路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。4. 基于RAS算法的文本加密與解密問題描述 設(shè)計一個基于RAS加密與解密算法，并編程實現(xiàn)之。基本要求(1) 熟悉RAS加密與解密算法。(2) 創(chuàng)建一個工程，對于給定文本文件(該文件作為明文，包含空格和所有文本)使用RAS加密算法進行加密。給出密文。(3) 對于給定的密文使用RAS解密算法，給出明文(4) 對于輸入明文和經(jīng)過解密后的明文進行判斷。(5) 給出加密和解密的時間。測試數(shù)據(jù) 測試數(shù)據(jù)見附件一。實現(xiàn)提示 本課程設(shè)計的實現(xiàn)主要包括以下主要過程：(1) 關(guān)于文件的操作（主要是讀寫操作！）(2) RAS加密與解密(3) 大整數(shù)相乘選做內(nèi)容 如果同學(xué)感興趣，可

10、以做成一個windows程序。附件1: 明文 I became what I am today at the age of twelve, on a frigid overcast day in the winter of 1975. I remember the precise moment, crouching behind a crumbling mud wall, peeking into the alley near the frozen creek. That was a long time ago, but its wrong what they say about the pa

11、st, Ive learned, about how you can bury it. Because the past claws its way out. Looking back now, I realize I have been peeking into that deserted alley for the last twenty-six years.One day last summer, my friend Rahim Khan called from Pakistan. He asked me to come see him. Standing in the kitchen

12、with the receiver to my ear, I knew it wasnt just Rahim Khan on the line. It was my past of unatoned sins. After I hung up, I went for a walk along Spreckels Lake on the northern edge of Golden Gate Park. The early-afternoon sun sparkled on the water where dozens of miniature boats sailed, propelled

13、 by a crisp breeze. Then I glanced up and saw a pair of kites, red with long blue tails, soaring in the sky. They danced high above the trees on the west end of the park, over the windmills, floating side by side like a pair of eyes looking down on San Francisco, the city I now call home. And sudden

14、ly Hassans voice whispered in my head: _For you, a thousand times over_. Hassan the harelipped kite runner. I sat on a park bench near a willow tree. I thought about something Rahim Khan said just before he hung up, almost as an after thought. _There is a way to be good again_. I looked up at those twin kites. I thought about Hassan. Thought about Baba. Ali. Kabul. I thought of the life I had lived until the winter of 1975 came and changed everything. And made me what I am today.附件2: RAS加密與解密算法 找兩素數(shù)p和q 取n=p*q 取t=(p-1)*(q-1) 取一個數(shù) e（和t要互素） 要