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

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

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

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

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

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

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

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

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

9、路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。4. 基于RAS算法的文本加密與解密問題描述 設(shè)計(jì)一個基于RAS加密與解密算法，并編程實(shí)現(xiàn)之?；疽?1) 熟悉RAS加密與解密算法。(2) 創(chuàng)建一個工程，對于給定文本文件(該文件作為明文，包含空格和所有文本)使用RAS加密算法進(jìn)行加密。給出密文。(3) 對于給定的密文使用RAS解密算法，給出明文(4) 對于輸入明文和經(jīng)過解密后的明文進(jìn)行判斷。(5) 給出加密和解密的時間。測試數(shù)據(jù) 測試數(shù)據(jù)見附件一。實(shí)現(xiàn)提示 本課程設(shè)計(jì)的實(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加密與解密算法 找兩素?cái)?shù)p和q 取n=p*q 取t=(p-1)*(q-1) 取一個數(shù) e（和t要互素） 要