《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)任務(wù)書

--2015-2016(一)

?

課程設(shè)計(jì)周數(shù)：2周?????????????????????????????????????????????????????????????

?

一、課程設(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á)到以下目的：

n? 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；

n? 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；

n? 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；

n? 訓(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）需求分析：

　　在該部分中敘述，每個模塊的功能要求

　　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ì)過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調(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é)號 姓名”，如“200413498? 高魁”。該文件夾下至少包括：“源代碼”、“課程設(shè)計(jì)報(bào)告”、“可執(zhí)行文件”。由學(xué)習(xí)委員收集刻盤按規(guī)定時間統(tǒng)一上交）。

5、課程設(shè)計(jì)報(bào)告不要附原代碼，可以對重點(diǎn)函數(shù)及結(jié)構(gòu)進(jìn)行說明。報(bào)告格式見要求。

6、報(bào)告提交

時間：第18周最后一次課檢查，第19周星期一上午11:30之前由學(xué)習(xí)委員收集上交，遲交無成績。

形式：課程設(shè)計(jì)報(bào)告紙質(zhì)和電子文檔(按班級統(tǒng)一刻盤）。

三、課程設(shè)計(jì)內(nèi)容：

1、內(nèi)部排序演示

【問題描述】
設(shè)計(jì)一個測試程序比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受。
【基本要求】
(1) 對起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法進(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)劣。
(4) 界面友好，易與操作。采用菜單方式進(jìn)行選擇。
【選做內(nèi)容】
(1) 對不同表長進(jìn)行比較；
(2) 驗(yàn)證各算法的穩(wěn)定性；
(3) 輸出界面的優(yōu)化。
(4) 使用漢字顯示。

?

2、校園導(dǎo)游咨詢

【問題描述】
設(shè)計(jì)一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。
【基本要求】
(1) 設(shè)計(jì)長春理工大學(xué)的校園平面圖，所含景點(diǎn)不少于10個。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。
(2) 為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。
(3) 為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短的簡單路徑。
【選做內(nèi)容】
(1) 系統(tǒng)功能的完善；
(2) 提供求任意兩個景點(diǎn)之間的所有路徑的功能；
(3) 提供校園圖中多個景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這多個景點(diǎn)的最佳（短）路徑。
(4) 使用漢字顯示。

?

3、建通訊錄

【問題描述】

設(shè)計(jì)散列表實(shí)現(xiàn)通訊錄查找系統(tǒng)。

【基本要求】
(1) 設(shè)每個記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址；
(2) 從鍵盤輸入各記錄，分別以電話號碼為關(guān)鍵字建立散列表；
(3) 采用二次探測再散列法解決沖突；
(4) 查找并顯示給定電話號碼的記錄；

(5) 通訊錄信息文件保存；

(6) 要求人機(jī)界面友好，使用圖形化界面；
【選做內(nèi)容】
(1) 系統(tǒng)功能的完善；
(2) 設(shè)計(jì)不同的散列函數(shù)，比較沖突率；
(3) 在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。
(4) 使用漢字顯示。

【實(shí)現(xiàn)提示】

主函數(shù)：根據(jù)選單的選項(xiàng)調(diào)用各函數(shù)，并完成相應(yīng)的功能。

Menu()的功能：顯示英文提示選單。

Quit()的功能：退出選單。

Create()的功能：創(chuàng)建新的通訊錄。

Append()的功能：在通訊錄的末尾寫入新的信息，并返回選單。

Find()：查詢某人的信息，如果找到了，則顯示該人的信息，如果沒有則提示通訊錄中沒有此人的信息，并返回選單。

Alter()的功能：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。

Delete()的功能：刪除某人的信息，如果未找到要刪除的人，則提示通訊錄中沒有此人的信息，并返回選單。

List()的功能：顯示通訊錄中的所有記錄。

Save()的功能：保存通訊錄中的所有記錄到指定文件中。

Load()的功能：從指定文件中讀取通訊錄中的記錄。

?

4、哈夫曼編碼/譯碼器

【問題描述】

設(shè)計(jì)一個哈夫曼編碼/譯碼系統(tǒng)，對一個文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件（壓縮文件，后綴名.cod）；反過來，可將一個壓縮文件譯碼還原為一個文本文件(.txt)。

【基本要求】

(1) 輸入一個待壓縮的文本文件名， 統(tǒng)計(jì)文本文件中各字符的個數(shù)作為權(quán)值，生成哈夫曼樹；

(2) 將文本文件利用哈夫曼樹進(jìn)行編碼，生成壓縮文件（后綴名cod），

(3) 輸入一個待解壓的壓縮文件名稱,并利用相應(yīng)的哈夫曼樹將編碼序列譯碼；

(4) 顯示指定的壓縮文件和文本文件；

(5) 界面友好，易與操作。采用菜單方式進(jìn)行選擇。

【選做內(nèi)容】

(1) 把哈夫曼編碼用二進(jìn)制位緊縮到一個變量中，利用位運(yùn)算進(jìn)行真正的數(shù)據(jù)壓縮，并求壓縮比。
(2) 顯示哈夫曼樹；
(3) 使用漢字顯示。

?

5、運(yùn)動會分?jǐn)?shù)統(tǒng)計(jì)

【問題描述】

參加運(yùn)動會有n個學(xué)校,學(xué)校編號為1……n.比賽分成m個男子項(xiàng)目,和w個女子項(xiàng)目.項(xiàng)目編號為男子1......m,女子m+1......m+w.不同的項(xiàng)目取前五名或前三名積分;取前五名的積分分別為:7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）

【功能要求】：

1)??????? 可以輸入各個項(xiàng)目的前三名或前五名的成績；

2)??????? 能統(tǒng)計(jì)各學(xué)校總分；

3)??????? 可以按學(xué)校編號、學(xué)校總分、男女團(tuán)體總分排序輸出；

4)??????? 可以按學(xué)校編號查詢學(xué)校某個項(xiàng)目的情況；可以按項(xiàng)目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。

【基本要求】

1)??????? 輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動項(xiàng)目的名稱）

2)??????? 輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形

3)??????? 界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。

4)??????? 存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。

6、文章編輯

【問題描述】

輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個數(shù)。

【基本要求】

靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求

（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；

（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；

（3）刪除某一子串，并將后面的字符前移。

存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；

輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號。
輸出形式：

（1）分行輸出用戶輸入的各行字符；

（2）分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字?jǐn)?shù)"

【選做內(nèi)容】

（1）?????? 輸出刪除某一字符串后的文章；

7、學(xué)生成績管理系統(tǒng)

【問題描述】

用c語言編寫一個簡單的學(xué)生信息管理程序，能實(shí)現(xiàn)對學(xué)生信息的簡單管理。
【具體要求】

建立一個4個學(xué)生的信息登記表，每個學(xué)生的信息包括：學(xué)號，姓名，和3門課程的成績（FOX,C,ENGLISH）。
?程序運(yùn)行時顯示一個簡單的菜單，例如：
?? （1）：信息輸入（INPUT）

?? （2）：總分統(tǒng)計(jì)（COUNT）

?? （3）：總分排序（SORT）

?? （4）：查詢(QUERY）

???? 其中：

???? （1）：對4個學(xué)生的信息進(jìn)行輸入；
???? （2）：對每個學(xué)生的3門課程統(tǒng)計(jì)總分；
????? (3)：對4個學(xué)生的總分按降序排序并顯示出來；
????? (4)：查詢輸入一個學(xué)號后，顯示出該學(xué)生的有關(guān)信息；

8、自選題

?? 允許有能力的同學(xué)自選題目，但題目必須按上面的格式寫出“問題描述”和“具體要求”，且題目的工作量要達(dá)到或超過已給題目，并經(jīng)指導(dǎo)教師審核同意才可以進(jìn)行自選題目的課程設(shè)計(jì)。

四、上交作業(yè)及成績評定

1、上交要求

上交設(shè)計(jì)報(bào)告和相關(guān)光盤。其中設(shè)計(jì)報(bào)告要以打印稿的形式上交。光盤內(nèi)容包括程序源碼設(shè)計(jì)報(bào)告的電子文檔。整個班級的設(shè)計(jì)均刻在一張光盤上，可按姓名或分組建立相關(guān)文件夾進(jìn)行存儲。

2、評分標(biāo)準(zhǔn)

根據(jù)完成任務(wù)的情況(必須進(jìn)行系統(tǒng)演示)、課程設(shè)計(jì)報(bào)告書的質(zhì)量和課程設(shè)計(jì)過程中的工作態(tài)度等按照30%、50%、20%加權(quán)綜合打分。成績評定實(shí)行優(yōu)秀、良好、中等、及格和不及格五個等級。上機(jī)程序檢查未通過者、無設(shè)計(jì)報(bào)告者以及嚴(yán)重抄襲他人設(shè)計(jì)者，成績?yōu)椴患案瘛?/p>

缺席次數(shù)	最終成績
1次	中及以下
2次及以上	不及格

?

?

?

?

注：

每班分為7-8個小組，每組4-5人。????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????? ????????????????????

設(shè)計(jì)題目：（選題：學(xué)號%7，余數(shù)為1、2、3、4、5、6、0分別做第1、2、3、4、5、6、7、題）

每小組各同學(xué)之間設(shè)計(jì)內(nèi)容和報(bào)告文檔不得雷同，否則成績不及格。

轉(zhuǎn)載于:https://www.cnblogs.com/helloaworld/p/5081616.html

總結(jié)

以上是生活随笔為你收集整理的大二第一学期期末课程设计 2015.12.28的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。