《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)計(jì)劃書

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)計(jì)劃書班級(jí)：2012信計(jì)專業(yè)授課教師：馬阿曼一、課程設(shè)計(jì)目的《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心專業(yè)基礎(chǔ)課。本課程設(shè)計(jì)的目的是將數(shù)據(jù)結(jié)構(gòu)理論和實(shí)踐結(jié)合起來，鍛練學(xué)生編寫程序過程中的數(shù)據(jù)結(jié)構(gòu)使用和分析、解決實(shí)際問題的能力。1、使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?、使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。3、使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。二、課程設(shè)計(jì)內(nèi)容

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)包含以下主要內(nèi)容：

1、查閱相關(guān)資料確定課題；

2、課題所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)；

3、編寫代碼并調(diào)試；

4、完成課程設(shè)計(jì)報(bào)告；5、進(jìn)行課設(shè)答辯。三、設(shè)計(jì)地點(diǎn)及時(shí)間安排地點(diǎn)：瑞樟6-402時(shí)間：2014年6月3、4、5、6、7、8號(hào)時(shí)間安排課程設(shè)計(jì)計(jì)劃3號(hào)布置課題和要求：課題內(nèi)容介紹，課程設(shè)計(jì)安排、課程設(shè)計(jì)紀(jì)律，注意事項(xiàng)學(xué)生選題，做好課題的前期準(zhǔn)備工作4號(hào)需求分析：根據(jù)所選課題進(jìn)行總體設(shè)計(jì)，確定數(shù)據(jù)結(jié)構(gòu)，確定主要功能模塊（函數(shù)）和采用的算法等。選擇和準(zhǔn)備原始數(shù)據(jù)確定輸入和輸出方式5號(hào)—8號(hào)編碼實(shí)現(xiàn)：主要功能模塊的功能實(shí)現(xiàn)輸入和輸出數(shù)據(jù)方式的整合調(diào)試和測試程序的功能檢驗(yàn)程序是否完整，結(jié)果是否符合要求，對(duì)程序進(jìn)行驗(yàn)收進(jìn)行課程設(shè)計(jì)答辯撰寫課程設(shè)計(jì)報(bào)告并打印，整理源代碼一并上交四、課程設(shè)計(jì)報(bào)告的書寫格式1、問題描述：描述要求編程解決的問題。2、基本要求：給出程序要達(dá)到的具體的要求。3、測試數(shù)據(jù)：設(shè)計(jì)測試數(shù)據(jù)，或具體給出測試數(shù)據(jù)。要求測試數(shù)據(jù)能全面地測試所設(shè)計(jì)程序的功能。4、算法思想：描述解決相應(yīng)問題算法的設(shè)計(jì)思想。5、模塊劃分：描述所設(shè)計(jì)程序的各個(gè)模塊（即函數(shù)）功能。6、數(shù)據(jù)結(jié)構(gòu)：給出所使用的基本抽象數(shù)據(jù)類型,所定義的具體問題的數(shù)據(jù)類型,以及新定義的抽象數(shù)據(jù)類型。7、算法設(shè)計(jì)分析：給出算法的設(shè)計(jì)分析和算法流程圖。8、源程序：給出所有源程序清單，要求程序有充分的注釋語句，至少要注釋每個(gè)函數(shù)參數(shù)的含義和函數(shù)返回值的含義。9、測試情況：給出程序的測試情況，并分析運(yùn)行結(jié)果。10、收獲及體會(huì)：寫出此次課程設(shè)計(jì)過程中的收獲及體會(huì)。五、評(píng)分標(biāo)準(zhǔn)程序運(yùn)行結(jié)果（30%）設(shè)計(jì)報(bào)告（30%）設(shè)計(jì)考勤，平時(shí)上機(jī)成績，教師不定期檢查（10%）學(xué)生根據(jù)自己設(shè)計(jì)報(bào)告對(duì)教師的提問可以熟練的解釋（10%）設(shè)計(jì)課題的難易程度（20%）六、參考設(shè)計(jì)題目課程設(shè)計(jì)題一：學(xué)生成績管理系統(tǒng)

設(shè)計(jì)目的：掌握線性鏈表的建立。掌握線性鏈表的基本操作。掌握查找的基本算法。設(shè)計(jì)內(nèi)容：

利用線性鏈表實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)，具體功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計(jì)、退出，并能在屏幕上輸出操作前后的結(jié)果。

設(shè)計(jì)要求：寫出系統(tǒng)需求分析,并建模。編程實(shí)現(xiàn),界面友好。輸出操作前后的結(jié)果。

課程設(shè)計(jì)題二：停車場管理系統(tǒng)

設(shè)計(jì)目的：掌握棧和隊(duì)列的建立。掌握棧和隊(duì)列的基本操作。3、深入了解棧和隊(duì)列的特性,以便在解決實(shí)際問題中靈活運(yùn)用它們。4、加深對(duì)棧和隊(duì)列的理解和認(rèn)識(shí)。設(shè)計(jì)內(nèi)容：

設(shè)有一個(gè)可以停放n輛汽車的狹長停車場,它只有一個(gè)大門可以供車輛進(jìn)出。車輛按到達(dá)停車場時(shí)間的早晚依次從停車場最里面向大門口處停放(最先到達(dá)的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車,則后來的車輛只能在停車場大門外的便道上等待,一旦停車場內(nèi)有車開走,則排在便道上的第一輛車就進(jìn)入停車場。停車場內(nèi)如有某輛車要開走,在他之后進(jìn)入停車場的車都必須先退出停車場為它讓路,待其開出停車場后,這些車輛在依原來的次序進(jìn)場。每輛車在離開停車場時(shí),都應(yīng)依據(jù)它在停車場內(nèi)停留的時(shí)間長短交費(fèi)。如果停留在便道上的車未進(jìn)停車場就要離去,允許其離去,不收停車費(fèi),并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。

設(shè)計(jì)要求：以棧模擬停車場,以隊(duì)列模擬車場外的便道,按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá),則輸出汽車在停車場或便道上的停車位置；若是車輛離去,則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用(在便道上停留的時(shí)間不收費(fèi)，功能可自己添加)。

課程設(shè)計(jì)題三：約瑟夫(Joseph)環(huán)

設(shè)計(jì)目的：掌握單向循環(huán)鏈表的建立。掌握單向循環(huán)鏈表的操作。設(shè)計(jì)內(nèi)容：

編號(hào)是1,2,……,n的n個(gè)人按照順時(shí)針方向圍坐一圈,每個(gè)人只有一個(gè)密碼(正整數(shù))。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù),報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列,將他的密碼作為新的m值,從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù),如此下去,直到所有人全部出列為止。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序求出出列順序。

設(shè)計(jì)要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程,按照出列的順序輸出各個(gè)人的編號(hào)。測試數(shù)據(jù)：m的初值為20,n=7,7個(gè)人的密碼依次為3,1,7,2,4,7,4,首先m=6,則正確的輸出是什么？輸入數(shù)據(jù)：建立輸入函數(shù)處理輸入的數(shù)據(jù),輸入m的初值n,輸入每個(gè)人的密碼,建立單向循環(huán)鏈表。輸出形式：建立一個(gè)輸出函數(shù),將正確的出列順序輸出。

課程設(shè)計(jì)題四：文學(xué)研究助手的實(shí)現(xiàn)

設(shè)計(jì)目的：熟悉串類型的實(shí)現(xiàn)方法和文本匹配方法。熟悉一般文字處理軟件的設(shè)計(jì)方法。設(shè)計(jì)內(nèi)容：

文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng),稱為“文學(xué)研究助手”。

設(shè)計(jì)要求：英文小說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢。3、程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào),格式自行設(shè)計(jì)。

課程設(shè)計(jì)題五：一元稀疏多項(xiàng)式計(jì)算器

設(shè)計(jì)目的：掌握稀疏矩陣的相關(guān)運(yùn)算。掌握廣義表的操作。設(shè)計(jì)內(nèi)容：

設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡單計(jì)算器。

設(shè)計(jì)要求：

一元稀疏多項(xiàng)式簡單計(jì)算器的基本功能是：輸入并建立多項(xiàng)式；輸出多項(xiàng)式,輸出形式為整數(shù)序列：n,c1,e1,,c2,e2……cn,en,其中n是多項(xiàng)式的項(xiàng)數(shù),ci和ei分別是第i項(xiàng)的系數(shù)和指數(shù),序列按指數(shù)降序排列。多項(xiàng)式a和b相加,建立多項(xiàng)式a+b多項(xiàng)式a和b相減,建立多項(xiàng)式a-b

課程設(shè)計(jì)題六：哈夫曼樹及其應(yīng)用

設(shè)計(jì)目的：熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)路徑長度的計(jì)算。設(shè)計(jì)內(nèi)容：

欲發(fā)一封內(nèi)容為AABBCAB……(共長100字符,其中:A、B、C、D、E、F分別有7、9、12、22、23、27個(gè))的電報(bào)報(bào)文,實(shí)現(xiàn)哈夫曼編碼。

設(shè)計(jì)要求：分析系統(tǒng)需求。建立哈夫曼樹。進(jìn)行哈夫曼編碼,并求出平均編碼長度。編程實(shí)現(xiàn)2、3步驟。

課程設(shè)計(jì)題七：哈夫曼編/譯碼器

設(shè)計(jì)目的：掌握建立哈夫曼樹和哈夫曼編碼的方法。掌握哈夫曼編碼的實(shí)際應(yīng)用方法。設(shè)計(jì)內(nèi)容：

利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率,縮短信息傳輸時(shí)間,降低傳輸成本。但是,這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼,在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工信道(即可以雙向傳輸信息的信道),每端都需要一個(gè)完成的編\譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編\譯碼系統(tǒng)。

設(shè)計(jì)要求：初始化。從終端讀入字符集大小n,以及n個(gè)字符和n個(gè)權(quán)值,建立哈夫曼樹。編碼。利用已建好的哈夫曼樹,對(duì)正文進(jìn)行編碼。譯碼。對(duì)編碼好的內(nèi)容進(jìn)行譯碼。打印編碼。打印哈夫曼樹。

課程設(shè)計(jì)題八：圖的遍歷演示

設(shè)計(jì)目的：理解圖的基本概念,熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法。掌握?qǐng)D的遍歷方法。設(shè)計(jì)內(nèi)容：

實(shí)現(xiàn)圖的深度優(yōu)先、廣度優(yōu)先遍歷算法,并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。

設(shè)計(jì)要求：兩種遍歷方法必須都要實(shí)現(xiàn),寫出畫圖的思路。界面友好,函數(shù)功能要?jiǎng)澐趾侠??？傮w設(shè)計(jì)應(yīng)畫一流程圖。程序要加必要的注釋。5、提供程序測試方案。

課程設(shè)計(jì)題九：交通咨詢系統(tǒng)設(shè)計(jì)

設(shè)計(jì)目的：熟練掌握迪杰斯特拉算法和費(fèi)洛伊德算法,能夠利用它們解決最短路徑問題。能夠解決工程項(xiàng)目實(shí)施過程中的關(guān)鍵路徑問題。設(shè)計(jì)內(nèi)容：

設(shè)計(jì)一個(gè)交通咨詢系統(tǒng),能讓旅客咨詢從任一個(gè)城市定點(diǎn)到另一個(gè)城市定點(diǎn)之間的最短路徑或最低花費(fèi)或最少時(shí)間等問題。對(duì)于不同的咨詢要求、可輸入城市間的路程或所需時(shí)間或所需花費(fèi)。

設(shè)計(jì)要求：1、建立交通網(wǎng)絡(luò)網(wǎng)的存儲(chǔ)結(jié)構(gòu)。2、總體設(shè)計(jì)要畫流程圖。提供程序測試方案。界面友好。

課程設(shè)計(jì)題十：航班信息的查詢與檢索

設(shè)計(jì)目的：深刻理解排序的定義和各種排序方法的特點(diǎn),并能靈活的應(yīng)用；掌握描述查找過程的判定樹的構(gòu)造方法。設(shè)計(jì)內(nèi)容：

設(shè)計(jì)民航售票處的計(jì)算機(jī)系統(tǒng)可以為客戶提供下列各項(xiàng)服務(wù)：1.

查詢航線：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號(hào)、飛機(jī)號(hào)、星期幾飛行、最近一天航班的日期和余票額；