《計算機(jī)學(xué)院 13級 數(shù)據(jù)結(jié)構(gòu)課程設(shè) 3周》由會員分享，可在線閱讀，更多相關(guān)《計算機(jī)學(xué)院 13級 數(shù)據(jù)結(jié)構(gòu)課程設(shè) 3周（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書學(xué)期：14-15-1 班級：計科、網(wǎng)絡(luò)、軟件13級 一、設(shè)計目的數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門課程，必須在掌握理論知識的同時，加強(qiáng)上機(jī)實踐。本課程設(shè)計的目的就是要達(dá)到理論與實際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計技能。二、設(shè)計要求1、通過這次設(shè)計，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)

2、練。2、學(xué)生必須仔細(xì)研讀數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(實習(xí))要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，認(rèn)真、獨立地完成課程設(shè)計的任務(wù)，有問題及時主動與指導(dǎo)教師溝通。3、本次課程設(shè)計按照教學(xué)要求需要在三周時間內(nèi)獨立完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己的計劃完成情況，及時地向指導(dǎo)教師匯報。4、編程語言任選。三、設(shè)計選題選題說明：本次課設(shè)共提供若干個不同難易程度的題目，其中前面5個為必做題，滿分80分（系統(tǒng)功能完善、人機(jī)交互界面簡單、直觀、便捷，否則逐項減分）；后面為選做題，共20分，題目難度層度不等，題目*越多難度越大，根據(jù)實際選做題目的難度和數(shù)量以及實

3、現(xiàn)程序的完善性可以適當(dāng)加減分；同學(xué)們在選題時，要結(jié)合個人實際情況，確保及格，力爭多做。1、 單位員工通訊錄管理系統(tǒng)（線性表的應(yīng)用）問題描述為某個單位建立一個員工通訊錄管理系統(tǒng)，可以方便查詢每一個員工的辦公室電話、手機(jī)號、及電子郵箱。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個通訊錄表的輸出。實現(xiàn)提示可以采用單鏈表的存儲結(jié)構(gòu)，如可定義如下的存儲結(jié)構(gòu)：typedef struct /*員工通訊信息的結(jié)構(gòu)類型定義*/ char num5; /*員工編號*/ char name10; /*員工姓名*/ char phone15; /*辦公室電話號碼*/char call1

4、5; /*手機(jī)號碼*/char mail25; /*郵箱*/DataType;/*通訊錄單鏈表的結(jié)點類型*/typedef struct node DataType data; /*結(jié)點的數(shù)據(jù)域*/ struct node *next; /*結(jié)點的指針域*/ListNode,*LinkList;2、停車場管理（棧和隊列的應(yīng)用）問題描述設(shè)停車場是一個可以停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次有北向南排列（大門在最南端，最先到達(dá)的第一車停放在車場的最北端），若車場內(nèi)已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上

5、的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。實現(xiàn)提示以棧模擬停車場，以隊列模擬車場外的便道。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停車不收費）。棧以順序存儲結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實

6、現(xiàn)。3、哈夫曼編碼/譯碼系統(tǒng)（樹應(yīng)用）問題描述利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過程，實現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。實現(xiàn)提示在本例中設(shè)置發(fā)送者和接受者兩個功能，發(fā)送者的功能包括：輸入待傳送的字符信息；統(tǒng)計字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；利用以上哈夫曼樹求出各字符的哈夫曼編碼；將字符信息轉(zhuǎn)換成對應(yīng)的編碼信息進(jìn)行傳送。接受者的功能包括：接收發(fā)送者傳送來的編碼信

7、息；利用上述哈夫曼樹對編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個：（1）哈夫曼樹的建立；（2）哈夫曼編碼的生成；（3）對編碼信息的翻譯。4、校園導(dǎo)游咨詢（圖的應(yīng)用）問題描述設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。（1）設(shè)計學(xué)校的校園平面圖，所含景點不少于10個，以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息；（2）提供基本信息的修改功能；（3）為來訪客人提供圖中任意景點相關(guān)信息的查詢；（4）為來訪客人提供景點的問路查詢，即已知一個景點，查詢到某景點之間的一條最短路徑及長度。5、

8、藥店的藥品銷售統(tǒng)計系統(tǒng)（排序應(yīng)用）問題描述設(shè)計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進(jìn)行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名。實現(xiàn)提示在本設(shè)計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進(jìn)行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進(jìn)行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售

9、額的排序采用堆排序法。藥品信息的元素類型定義：typedef struct node char num4; /*藥品編號*/ char name10; /*藥品名稱*/ float price; /*藥品單價*/ int count; /*銷售數(shù)量*/ float sale; /*本藥品銷售額*/ DataType;存儲藥品信息的順序表的定義：typedef struct DataType rMaxSize; int length;SequenList;6、散列表的設(shè)計與實現(xiàn)（*）任務(wù)：設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)。要求： （1) 設(shè)每個記錄有下列數(shù)據(jù)項：用戶名、電話號碼、地址； （2) 從

10、鍵盤輸入各記錄，以用戶名（漢語拼音形式）為關(guān)鍵字建立散列表； （3) 采用線性探測再散列法解決沖突； （4) 查找并顯示給定電話號碼的記錄；(5) 通訊錄信息文件保存；(6) 要求人機(jī)界面友好，使用圖形化界面； 選作內(nèi)容： （1) 系統(tǒng)功能的完善； （2) 設(shè)計不同的散列函數(shù)，比較沖突率； （3) 在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。7、一元稀疏多項式的計算（*）任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結(jié)果輸出；要求：以鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)多項式。8、迷宮求解（*）任務(wù)：以一個m*n的長方陣表示迷宮，0和1分別表示

11、迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。要求：首先實現(xiàn)一個棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。9、排序綜合（*） 利用隨機(jī)函數(shù)產(chǎn)生N個隨機(jī)整數(shù)（20000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：（1）至少采用三種方法（希爾排序、快速排序、堆排序）實現(xiàn)上述問題求解；（2）統(tǒng)計每一種排序方法的性能（以上機(jī)運行程序所花費的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法；（3）統(tǒng)計每種算法所用的比較次數(shù)和交換次數(shù)，最后列表顯示；（

12、4）如果采用4種或4種以上的方法者，可適當(dāng)加分。10、教學(xué)計劃編制問題（*）問題描述大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。實現(xiàn)提示1、 輸入?yún)?shù)應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號（可以是固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。2、 應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)

13、盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。3、 若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔?；否則將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設(shè)計。4、 可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中，則作為錯誤處理。11、二叉排序樹的基本操作（*）任務(wù)： 編寫算法實現(xiàn)對依次輸入的關(guān)鍵字序列建立二叉排序樹，并能實現(xiàn)二叉排序樹的查找、插入和刪除運算。12、 運動會分?jǐn)?shù)統(tǒng)計（*）任務(wù)：參加運動會有n個學(xué)校，學(xué)校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前五名

14、的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些項目取前五名或前三名由學(xué)生自己設(shè)定。（m=20,n=20）功能要求：(1)可以輸入各個項目的前三名或前五名的成績；(2)能統(tǒng)計各學(xué)?？偡?， (3)可以按學(xué)校編號、男女團(tuán)體總分排序輸出； (4)可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運動項目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要

15、求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；相關(guān)數(shù)據(jù)結(jié)構(gòu)（參考）：項目名次及分值 ：用二位數(shù)組Scorem+w5;單項獲獎情況登記表（項目編號，獲獎名次、獲獎學(xué)校，得分（自動得分）學(xué)校獲獎名次表（學(xué)校編號，團(tuán)體總分，名次）測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；13、宿舍管理查詢軟件（*）任務(wù)：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設(shè)計要求：（1）采用交互工作方式（2）可以增加、

16、刪除、修改信息（3）建立數(shù)據(jù)文件 ，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進(jìn)行排序(選擇、快速排序、堆排序等任選一種)(4) 查詢 : a.按姓名查詢 ;b.按學(xué)號查詢 ;c按房號查詢(5) 打印任一查詢結(jié)果（可以連續(xù)操作）14、最小生成樹問題（*）【問題描述】若要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價建設(shè)這個通信網(wǎng)，是一個網(wǎng)的最小生成樹問題?！鞠到y(tǒng)要求】1 利用克魯斯卡爾算法求網(wǎng)的最小生成樹。2 利用普里姆算法求網(wǎng)的最小生成樹。3 要求輸出各條邊及它們的權(quán)值。【測試數(shù)據(jù)】由學(xué)生任意指定，但報告上要求寫出多批數(shù)據(jù)測試結(jié)果。【實現(xiàn)提示】通信線路一旦建成，必然是

17、雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點數(shù)不超過30個，并為簡單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，可利用C語言提供的隨機(jī)函數(shù)產(chǎn)生。圖的存儲結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲邊（帶權(quán)）的數(shù)組表示圖?！具x作內(nèi)容】利用堆排序?qū)崿F(xiàn)選擇權(quán)值最小的邊。15、平衡二叉排序樹的實現(xiàn)（*） 【系統(tǒng)要求】（1）用二叉鏈表作存儲結(jié)構(gòu)，以回車(n)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵平衡的二叉排序樹T，并以直觀的方式顯示在終端上；（2）對二叉排序樹T作中序遍歷，輸出結(jié)果；（3）輸入元素x,查找二叉排序樹T

18、,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”，并將x插入該二叉排序樹中。 注意：插入、刪除應(yīng)保證二叉排序樹的平衡性。16、商店存貨管理系統(tǒng)（*）功能：建立一商店存貨管理系統(tǒng)，要求每次出貨時取進(jìn)貨時間最早且最接近保質(zhì)期中止時間的貨物。分步實施：1.初步完成總體設(shè)計，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2.完成最低要求：建立一個文件，包括5個種類的貨物情況，能對商品信息進(jìn)行擴(kuò)充（追加），修改和刪除以及簡單的排序；3.進(jìn)一步要求：擴(kuò)充商品數(shù)量，以及完成系統(tǒng)查詢功能。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。17、售票處的服務(wù)系統(tǒng)（*）【問題描述】航空客運訂票的業(yè)

19、務(wù)活動包括：查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計一個航空客運訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計算機(jī)來完成?！鞠到y(tǒng)要求】設(shè)民航售票處的計算機(jī)系統(tǒng)可以為客戶提供下列各項服務(wù)：1 查詢航線：根據(jù)旅客提出的終點站名輸出下列信息：航班號、飛機(jī)號、星期幾飛行，最近一天航班的日期和余票額；2 承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（日期、航班號、訂票數(shù)額）查詢該航班票額情況，若尚有余額，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少于訂票額，則需要重新詢問客戶要求。若需要，可預(yù)約登記排隊等候。3承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況（日期、航班、退票數(shù)額），為客戶辦理退票手續(xù)，然后查詢該航班是否有人預(yù)約登記，首先

20、詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊預(yù)約的客戶?！緶y試數(shù)據(jù)】由學(xué)生任意指定，但報告上要求寫出多批數(shù)據(jù)測試結(jié)果。【實現(xiàn)提示】每條航線應(yīng)包含的信息有：終點站名、航班號、飛機(jī)號、飛行日期（星期幾）、乘員定額、余票額、已訂票的客戶名單（包括姓名、訂票額、座位號）和預(yù)約登記的客戶名單（包括日期、姓名、所需票額）。這最后兩項顯然是一個線性表和一個隊列。為查找方便、已訂票客戶的線性表應(yīng)按客戶姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作存儲結(jié)構(gòu)。由于預(yù)約人數(shù)無法預(yù)料，隊列也應(yīng)以鏈表作存儲結(jié)構(gòu)。整個系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可

21、采用順序存儲結(jié)構(gòu)，并按航班有序或按終點站名有序。每條航線是這張表上的一個記錄，包含上述八個域，其中乘員名單域為指向乘員名單鏈表的頭指針，預(yù)約登記客戶名單域為分別指向隊頭和隊尾的指針。【選做內(nèi)容】當(dāng)客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達(dá)同一目的地的其它航線情況。大家還可以充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其它服務(wù)項目。18、 中國道路交通網(wǎng)絡(luò)信息查詢系統(tǒng)（*）【問題描述】出于不同的目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)

22、決策的交通咨詢。【基本要求】（1） 提供對城市信息進(jìn)行編輯（如：添加或刪除）的功能。（2） 城市之間有兩種交通工具：火車和飛機(jī)。提供對列車時刻表和飛機(jī)航班進(jìn)行編輯（增設(shè)或刪除）的功能。（3） 提供兩種最優(yōu)決策：最快到達(dá)或最省錢到達(dá)。全程只考慮一種交通工具；（4） 旅途中耗費的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間；（5） 咨詢以用戶和計算機(jī)的對話方式進(jìn)行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達(dá)或者最少需要多少旅費才能到達(dá)，并詳細(xì)說明依次于何時乘坐哪一趟列車或哪一次班機(jī)到何地。【測試數(shù)據(jù)】參考數(shù)據(jù)結(jié)構(gòu)清華版7.6節(jié)圖7.33的全國交通圖,自行設(shè)計列車時刻表和

23、飛機(jī)航班?！緦崿F(xiàn)提示】(1)對時刻表和飛機(jī)航班進(jìn)行編輯,應(yīng)提供文件輸入和鍵盤輸入兩種形式。飛機(jī)航班信息包括:起始站的出發(fā)時間,終點站的到達(dá)時間和票價;列車時刻表則需 根據(jù)交通圖給出各個路段的詳細(xì)信息,如:對從北京到上海的火車,給出北京至天 津,天津至徐州及徐州至上海各段的出發(fā)時間,到達(dá)時間及票價等信息。(2)以鄰接表作交通圖的存儲結(jié)構(gòu),表示邊的結(jié)構(gòu)內(nèi)除含有鄰接點的信息外,還包括交通工具,路途中耗費的時間和花費以及出發(fā)和到達(dá)時間等多種屬性?！具x做內(nèi)容】增加旅途中中轉(zhuǎn)次數(shù)最少的最優(yōu)決策。19. 英語單詞學(xué)習(xí)助手【問題描述】掌握線性表、串、查找表等數(shù)據(jù)結(jié)構(gòu)的物理存儲結(jié)構(gòu)與基本算法，通過解決較復(fù)雜的實

24、際問題，提高學(xué)生對數(shù)據(jù)結(jié)構(gòu)知識綜合運用的技能與實踐能力。設(shè)計內(nèi)容：以大學(xué)英語相關(guān)英語文章為語料素材，設(shè)計有效的數(shù)據(jù)結(jié)構(gòu)及其存儲結(jié)構(gòu)表示英語單詞表，并建立相應(yīng)的倒排索引，幫助英語學(xué)習(xí)者在遇到生詞時能方便找到生詞的相應(yīng)例句，熟悉其應(yīng)用語境與地道的用法；設(shè)計有效的算法對語料進(jìn)行清理與分句處理，實現(xiàn)基于索引的快速例句搜索程序。 【基本要求】（1）輸入某一個（或若干個）英語單詞，要求返回相應(yīng)的英語例句。 （2）根據(jù)單詞與語句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次啟動程序時不必重新建立索引，只需將索引文件導(dǎo)入內(nèi)存。 （3）采用圖形界面，便于輸入單詞，例句展現(xiàn)直觀，界面布局合理?！驹O(shè)計提

25、示】按三步進(jìn)行：（1）準(zhǔn)備英語語料。尋找英語文章，可下載英語新聞，托福、GRE文章，或大學(xué)英語課文等。（2）處理語料。對語料進(jìn)行清理、分句、索引、生成字典。需要進(jìn)行取詞干的操作，分句可以直接根據(jù)標(biāo)點符號處理。（3）根據(jù)索引進(jìn)行查詢。支持一個或多個查詢，基于對詞干的處理，當(dāng)查go、going等時也能夠有返回。由于查詢的結(jié)果是語句，如果直接按照詞與文章的關(guān)系建立索引，這樣需要從文章中找句子，太多的串匹配操作可能導(dǎo)致查詢較慢，所以要設(shè)計好索引的粒度。 p大學(xué)校區(qū)（*）【題目描述】當(dāng)前，中原工學(xué)院共有四個校區(qū)：北校區(qū)（North）、南校區(qū)（South）、西校區(qū)（West）和東校區(qū)（信商新區(qū)）（East

26、），每一個校區(qū)都有若干個建筑物，如公園、廣場、科研院所、實驗中心、禮堂等，每個建筑物之間都有一定的距離，因此，在平時的教學(xué)和生活中，教師和學(xué)生都會經(jīng)常面臨這樣的問題：在同一個校區(qū)或不同校區(qū)之間，從一個地點到另一個地點往來的需要?，F(xiàn)在，他們需要找到從出發(fā)點S到目的地T的一條最短路徑，以便節(jié)省時間，你能幫助他們嗎？假設(shè)任兩個建筑物之間至多存在一條直接相連的道路，并且都有具體的長度?！据斎搿枯斎氲牡谝恍惺且粋€正整數(shù)C，表示下面測試案例數(shù)目。在每一種測試?yán)?，第一行的正整?shù) N(0N100)表示道路的數(shù)目，其后的N行：第i行表示第i（1iN）條道路的起點Si 和終點Ti及其之間的距離Di（0Di100

27、），第N+1行表示教師或?qū)W生的出發(fā)地S與目的地T,你必須幫找出他們從出發(fā)地S到目的地T之間的最短路徑。每個校區(qū)分別使用North、South、West和East，每一個建筑物名稱用長度不超出100個小寫字符（a-z）串表示。【輸出】輸出應(yīng)包括C行，每行對應(yīng)一個測試?yán)?，輸出從起點到目的地的最短距離。如果兩地點間無路徑則輸出-1。系統(tǒng)沒有多余的內(nèi)存空間可利用?！据斎霕永?2South.litang South.lab 2South.lab West.guangchang 100South.lab South.litang 【輸出樣例】2四、學(xué)生自選課題學(xué)生原則上可以結(jié)合個人愛好自選課題，要求自選

28、課題必須覆蓋數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，有一定的深度與難度，有一定的算法復(fù)雜性，能明確體現(xiàn)數(shù)據(jù)抽象與組織、算法設(shè)計與性能分析以及編碼實現(xiàn)等過程。學(xué)生自選課題需提前報課程設(shè)計指導(dǎo)教師批準(zhǔn)方可生效。五、指導(dǎo)教師 苗鳳君、高艷霞、吳志剛、田繼鵬六、時間安排 第17-19 每天上午8:30-12:00下午13:00-16：30七、完成課程設(shè)計報告課程設(shè)計報告書封面用學(xué)校的統(tǒng)一封面。課程設(shè)計報告的內(nèi)容：設(shè)計題目、需求分析、算法設(shè)計（包含算法思想、算法設(shè)計分析、流程圖等）、調(diào)試分析、測試結(jié)果、課設(shè)總結(jié)（收獲及體會）、附錄（源代碼）。八、成績考核根據(jù)完成任務(wù)的情況(必須進(jìn)行系統(tǒng)驗收 + 答辯)、課程設(shè)計報告書的質(zhì)量

29、和課程設(shè)計過程中的工作態(tài)度等按照50%、30%、20%加權(quán)綜合打分。上機(jī)程序檢查未通過者、無設(shè)計報告者以及嚴(yán)重抄襲他人設(shè)計者，成績?yōu)椴患案?。缺席次?shù)最終成績2次中等及以下3次及以上不及格其它情況根據(jù)界面設(shè)計、實現(xiàn)方法、功能效果、設(shè)計報告來評定。主要從以下幾個方面考察：項目得分備注程序運行情況25分程序的結(jié)構(gòu)合理與否15分算法說明的清晰程度20分總結(jié)的深刻程度10分獨立完成情況20分加分因素10分九、上交報告及相關(guān)源代碼上交課程設(shè)計報告和相關(guān)光盤。其中設(shè)計報告要以打印文稿的形式上交。光盤內(nèi)容包括程序源碼和課程設(shè)計報告的電子文檔。整個班級的設(shè)計均刻在一張光盤上。（上交時每人交一份，文件夾的取名規(guī)則為：“班級_學(xué)號_姓名”，如“計科131_學(xué)號_張三”。該文件夾下至少包括：“源代碼”、“課程設(shè)計報告”。由以班為單位收集刻盤按規(guī)定時間統(tǒng)一上交）。 數(shù)據(jù)結(jié)構(gòu)課程組 2014-12-1012/7