數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書學(xué)期：14-15-1 班級(jí)：計(jì)科、網(wǎng)絡(luò)、軟件13級(jí) 一、設(shè)計(jì)目的數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課程，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。二、設(shè)計(jì)要求1、通過(guò)這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2、學(xué)生必須仔細(xì)研讀數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(實(shí)習(xí))要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，認(rèn)真、獨(dú)立地完成課程設(shè)計(jì)的任務(wù)，有問(wèn)題及時(shí)主動(dòng)與指導(dǎo)教師溝通。3、本次課程設(shè)計(jì)按照教學(xué)要求需要在三周時(shí)間內(nèi)獨(dú)立完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)地向指導(dǎo)教師匯報(bào)。4、編程語(yǔ)言任選。三、設(shè)計(jì)選題選題說(shuō)明：本次課設(shè)共提供若干個(gè)不同難易程度的題目，其中前面5個(gè)為必做題，滿分80分（系統(tǒng)功能完善、人機(jī)交互界面簡(jiǎn)單、直觀、便捷，否則逐項(xiàng)減分）；后面為選做題，共20分，題目難度層度不等，題目*越多難度越大，根據(jù)實(shí)際選做題目的難度和數(shù)量以及實(shí)現(xiàn)程序的完善性可以適當(dāng)加減分；同學(xué)們?cè)谶x題時(shí)，要結(jié)合個(gè)人實(shí)際情況，確保及格，力爭(zhēng)多做。1、 單位員工通訊錄管理系統(tǒng)（線性表的應(yīng)用）問(wèn)題描述為某個(gè)單位建立一個(gè)員工通訊錄管理系統(tǒng)，可以方便查詢每一個(gè)員工的辦公室電話、手機(jī)號(hào)、及電子郵箱。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個(gè)通訊錄表的輸出。實(shí)現(xiàn)提示可以采用單鏈表的存儲(chǔ)結(jié)構(gòu)，如可定義如下的存儲(chǔ)結(jié)構(gòu)：typedef struct /*員工通訊信息的結(jié)構(gòu)類型定義*/ char num5; /*員工編號(hào)*/ char name10; /*員工姓名*/ char phone15; /*辦公室電話號(hào)碼*/char call15; /*手機(jī)號(hào)碼*/char mail25; /*郵箱*/DataType;/*通訊錄單鏈表的結(jié)點(diǎn)類型*/typedef struct node DataType data; /*結(jié)點(diǎn)的數(shù)據(jù)域*/ struct node *next; /*結(jié)點(diǎn)的指針域*/ListNode,*LinkList;2、停車場(chǎng)管理（棧和隊(duì)列的應(yīng)用）問(wèn)題描述設(shè)停車場(chǎng)是一個(gè)可以停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次有北向南排列（大門在最南端，最先到達(dá)的第一車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛車，那么后來(lái)的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。實(shí)現(xiàn)提示以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停車不收費(fèi)）。棧以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。3、哈夫曼編碼/譯碼系統(tǒng)（樹應(yīng)用）問(wèn)題描述利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時(shí)間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過(guò)程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。實(shí)現(xiàn)提示在本例中設(shè)置發(fā)送者和接受者兩個(gè)功能，發(fā)送者的功能包括：輸入待傳送的字符信息；統(tǒng)計(jì)字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；利用以上哈夫曼樹求出各字符的哈夫曼編碼；將字符信息轉(zhuǎn)換成對(duì)應(yīng)的編碼信息進(jìn)行傳送。接受者的功能包括：接收發(fā)送者傳送來(lái)的編碼信息；利用上述哈夫曼樹對(duì)編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個(gè)：（1）哈夫曼樹的建立；（2）哈夫曼編碼的生成；（3）對(duì)編碼信息的翻譯。4、校園導(dǎo)游咨詢（圖的應(yīng)用）問(wèn)題描述設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)。（1）設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)，以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息；（2）提供基本信息的修改功能；（3）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢；（4）為來(lái)訪客人提供景點(diǎn)的問(wèn)路查詢，即已知一個(gè)景點(diǎn)，查詢到某景點(diǎn)之間的一條最短路徑及長(zhǎng)度。5、藥店的藥品銷售統(tǒng)計(jì)系統(tǒng)（排序應(yīng)用）問(wèn)題描述設(shè)計(jì)一系統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對(duì)銷售各藥品的記錄進(jìn)行統(tǒng)計(jì)，可按藥品的編號(hào)、單價(jià)、銷售量或銷售額做出排名。實(shí)現(xiàn)提示在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲(chǔ)在順序表中。各藥品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷出數(shù)量、銷售額。藥品編號(hào)共4位，采用字母和數(shù)字混合編號(hào)，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷售量或銷售額進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排序法，對(duì)銷售量的排序采用快速排序法，對(duì)銷售額的排序采用堆排序法。藥品信息的元素類型定義：typedef struct node char num4; /*藥品編號(hào)*/ char name10; /*藥品名稱*/ float price; /*藥品單價(jià)*/ int count; /*銷售數(shù)量*/ float sale; /*本藥品銷售額*/ DataType;存儲(chǔ)藥品信息的順序表的定義：typedef struct DataType rMaxSize; int length;SequenList;6、散列表的設(shè)計(jì)與實(shí)現(xiàn)（*）任務(wù)：設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。要求： （1) 設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：用戶名、電話號(hào)碼、地址； （2) 從鍵盤輸入各記錄，以用戶名（漢語(yǔ)拼音形式）為關(guān)鍵字建立散列表； （3) 采用線性探測(cè)再散列法解決沖突； （4) 查找并顯示給定電話號(hào)碼的記錄；(5) 通訊錄信息文件保存；(6) 要求人機(jī)界面友好，使用圖形化界面； 選作內(nèi)容： （1) 系統(tǒng)功能的完善； （2) 設(shè)計(jì)不同的散列函數(shù)，比較沖突率； （3) 在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長(zhǎng)度的變化。7、一元稀疏多項(xiàng)式的計(jì)算（*）任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸出；要求：以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)多項(xiàng)式。8、迷宮求解（*）任務(wù)：以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。要求：首先實(shí)現(xiàn)一個(gè)棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。9、排序綜合（*） 利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：（1）至少采用三種方法（希爾排序、快速排序、堆排序）實(shí)現(xiàn)上述問(wèn)題求解；（2）統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法；（3）統(tǒng)計(jì)每種算法所用的比較次數(shù)和交換次數(shù)，最后列表顯示；（4）如果采用4種或4種以上的方法者，可適當(dāng)加分。10、教學(xué)計(jì)劃編制問(wèn)題（*）問(wèn)題描述大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒(méi)有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。實(shí)現(xiàn)提示1、 輸入?yún)?shù)應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)（可以是固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號(hào)。2、 應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。3、 若根據(jù)給定的條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式可以自己設(shè)計(jì)。4、 可設(shè)學(xué)期總數(shù)不超過(guò)12，課程總數(shù)不超過(guò)100。如果輸入的先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中，則作為錯(cuò)誤處理。11、二叉排序樹的基本操作（*）任務(wù)： 編寫算法實(shí)現(xiàn)對(duì)依次輸入的關(guān)鍵字序列建立二叉排序樹，并能實(shí)現(xiàn)二叉排序樹的查找、插入和刪除運(yùn)算。12、 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)（*）任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1m，女子m+1m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些項(xiàng)目取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）功能要求：(1)可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)；(2)能統(tǒng)計(jì)各學(xué)校總分， (3)可以按學(xué)校編號(hào)、男女團(tuán)體總分排序輸出； (4)可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；相關(guān)數(shù)據(jù)結(jié)構(gòu)（參考）：項(xiàng)目名次及分值 ：用二位數(shù)組Scorem+w5;單項(xiàng)獲獎(jiǎng)情況登記表（項(xiàng)目編號(hào)，獲獎(jiǎng)名次、獲獎(jiǎng)學(xué)校，得分（自動(dòng)得分）學(xué)校獲獎(jiǎng)名次表（學(xué)校編號(hào)，團(tuán)體總分，名次）測(cè)試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；13、宿舍管理查詢軟件（*）任務(wù)：為宿舍管理人員編寫一個(gè)宿舍管理查詢軟件, 程序設(shè)計(jì)要求：（1）采用交互工作方式（2）可以增加、刪除、修改信息（3）建立數(shù)據(jù)文件 ，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號(hào)、房號(hào)）進(jìn)行排序(選擇、快速排序、堆排序等任選一種)(4) 查詢 : a.按姓名查詢 ;b.按學(xué)號(hào)查詢 ;c按房號(hào)查詢(5) 打印任一查詢結(jié)果（可以連續(xù)操作）14、最小生成樹問(wèn)題（*）【問(wèn)題描述】若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問(wèn)題?！鞠到y(tǒng)要求】1 利用克魯斯卡爾算法求網(wǎng)的最小生成樹。2 利用普里姆算法求網(wǎng)的最小生成樹。3 要求輸出各條邊及它們的權(quán)值?！緶y(cè)試數(shù)據(jù)】由學(xué)生任意指定，但報(bào)告上要求寫出多批數(shù)據(jù)測(cè)試結(jié)果?！緦?shí)現(xiàn)提示】通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無(wú)向網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過(guò)30個(gè)，并為簡(jiǎn)單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，可利用C語(yǔ)言提供的隨機(jī)函數(shù)產(chǎn)生。圖的存儲(chǔ)結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖?！具x作內(nèi)容】利用堆排序?qū)崿F(xiàn)選擇權(quán)值最小的邊。15、平衡二叉排序樹的實(shí)現(xiàn)（*） 【系統(tǒng)要求】（1）用二叉鏈表作存儲(chǔ)結(jié)構(gòu)，以回車('n')為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵平衡的二叉排序樹T，并以直觀的方式顯示在終端上；（2）對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；（3）輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無(wú)x”，并將x插入該二叉排序樹中。 注意：插入、刪除應(yīng)保證二叉排序樹的平衡性。16、商店存貨管理系統(tǒng)（*）功能：建立一商店存貨管理系統(tǒng)，要求每次出貨時(shí)取進(jìn)貨時(shí)間最早且最接近保質(zhì)期中止時(shí)間的貨物。分步實(shí)施：1.初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對(duì)話的界面，確定函數(shù)個(gè)數(shù)；2.完成最低要求：建立一個(gè)文件，包括5個(gè)種類的貨物情況，能對(duì)商品信息進(jìn)行擴(kuò)充（追加），修改和刪除以及簡(jiǎn)單的排序；3.進(jìn)一步要求：擴(kuò)充商品數(shù)量，以及完成系統(tǒng)查詢功能。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。17、售票處的服務(wù)系統(tǒng)（*）【問(wèn)題描述】航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計(jì)一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來(lái)完成。【系統(tǒng)要求】設(shè)民航售票處的計(jì)算機(jī)系統(tǒng)可以為客戶提供下列各項(xiàng)服務(wù)：1 查詢航線：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號(hào)、飛機(jī)號(hào)、星期幾飛行，最近一天航班的日期和余票額；2 承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（日期、航班號(hào)、訂票數(shù)額）查詢?cè)摵桨嗥鳖~情況，若尚有余額，則為客戶辦理訂票手續(xù)，輸出座位號(hào)；若已滿員或余票額少于訂票額，則需要重新詢問(wèn)客戶要求。若需要，可預(yù)約登記排隊(duì)等候。3承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況（日期、航班、退票數(shù)額），為客戶辦理退票手續(xù)，然后查詢?cè)摵桨嗍欠裼腥祟A(yù)約登記，首先詢問(wèn)排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問(wèn)其他排隊(duì)預(yù)約的客戶?！緶y(cè)試數(shù)據(jù)】由學(xué)生任意指定，但報(bào)告上要求寫出多批數(shù)據(jù)測(cè)試結(jié)果?！緦?shí)現(xiàn)提示】每條航線應(yīng)包含的信息有：終點(diǎn)站名、航班號(hào)、飛機(jī)號(hào)、飛行日期（星期幾）、乘員定額、余票額、已訂票的客戶名單（包括姓名、訂票額、座位號(hào)）和預(yù)約登記的客戶名單（包括日期、姓名、所需票額）。這最后兩項(xiàng)顯然是一個(gè)線性表和一個(gè)隊(duì)列。為查找方便、已訂票客戶的線性表應(yīng)按客戶姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。由于預(yù)約人數(shù)無(wú)法預(yù)料，隊(duì)列也應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。整個(gè)系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲(chǔ)結(jié)構(gòu)，并按航班有序或按終點(diǎn)站名有序。每條航線是這張表上的一個(gè)記錄，包含上述八個(gè)域，其中乘員名單域?yàn)橹赶虺藛T名單鏈表的頭指針，預(yù)約登記客戶名單域?yàn)榉謩e指向隊(duì)頭和隊(duì)尾的指針。【選做內(nèi)容】當(dāng)客戶訂票要求不能滿足時(shí)，系統(tǒng)可向客戶提供到達(dá)同一目的地的其它航線情況。大家還可以充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其它服務(wù)項(xiàng)目。18、 中國(guó)道路交通網(wǎng)絡(luò)信息查詢系統(tǒng)（*）【問(wèn)題描述】出于不同的目的的旅客對(duì)交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時(shí)間盡可能短，出門旅游的游客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個(gè)全國(guó)城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢?！净疽蟆浚?） 提供對(duì)城市信息進(jìn)行編輯（如：添加或刪除）的功能。（2） 城市之間有兩種交通工具：火車和飛機(jī)。提供對(duì)列車時(shí)刻表和飛機(jī)航班進(jìn)行編輯（增設(shè)或刪除）的功能。（3） 提供兩種最優(yōu)決策：最快到達(dá)或最省錢到達(dá)。全程只考慮一種交通工具；（4） 旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間；（5） 咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。由用戶輸入起始站、終點(diǎn)站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長(zhǎng)時(shí)間才能到達(dá)或者最少需要多少旅費(fèi)才能到達(dá)，并詳細(xì)說(shuō)明依次于何時(shí)乘坐哪一趟列車或哪一次班機(jī)到何地?！緶y(cè)試數(shù)據(jù)】參考數(shù)據(jù)結(jié)構(gòu)清華版7.6節(jié)圖7.33的全國(guó)交通圖,自行設(shè)計(jì)列車時(shí)刻表和飛機(jī)航班?！緦?shí)現(xiàn)提示】(1)對(duì)時(shí)刻表和飛機(jī)航班進(jìn)行編輯,應(yīng)提供文件輸入和鍵盤輸入兩種形式。飛機(jī)航班信息包括:起始站的出發(fā)時(shí)間,終點(diǎn)站的到達(dá)時(shí)間和票價(jià);列車時(shí)刻表則需 根據(jù)交通圖給出各個(gè)路段的詳細(xì)信息,如:對(duì)從北京到上海的火車,給出北京至天 津,天津至徐州及徐州至上海各段的出發(fā)時(shí)間,到達(dá)時(shí)間及票價(jià)等信息。(2)以鄰接表作交通圖的存儲(chǔ)結(jié)構(gòu),表示邊的結(jié)構(gòu)內(nèi)除含有鄰接點(diǎn)的信息外,還包括交通工具,路途中耗費(fèi)的時(shí)間和花費(fèi)以及出發(fā)和到達(dá)時(shí)間等多種屬性。【選做內(nèi)容】增加旅途中中轉(zhuǎn)次數(shù)最少的最優(yōu)決策。19. 英語(yǔ)單詞學(xué)習(xí)助手【問(wèn)題描述】掌握線性表、串、查找表等數(shù)據(jù)結(jié)構(gòu)的物理存儲(chǔ)結(jié)構(gòu)與基本算法，通過(guò)解決較復(fù)雜的實(shí)際問(wèn)題，提高學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)綜合運(yùn)用的技能與實(shí)踐能力。設(shè)計(jì)內(nèi)容：以大學(xué)英語(yǔ)相關(guān)英語(yǔ)文章為語(yǔ)料素材，設(shè)計(jì)有效的數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)結(jié)構(gòu)表示英語(yǔ)單詞表，并建立相應(yīng)的倒排索引，幫助英語(yǔ)學(xué)習(xí)者在遇到生詞時(shí)能方便找到生詞的相應(yīng)例句，熟悉其應(yīng)用語(yǔ)境與地道的用法；設(shè)計(jì)有效的算法對(duì)語(yǔ)料進(jìn)行清理與分句處理，實(shí)現(xiàn)基于索引的快速例句搜索程序。 【基本要求】（1）輸入某一個(gè)（或若干個(gè)）英語(yǔ)單詞，要求返回相應(yīng)的英語(yǔ)例句。 （2）根據(jù)單詞與語(yǔ)句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次啟動(dòng)程序時(shí)不必重新建立索引，只需將索引文件導(dǎo)入內(nèi)存。 （3）采用圖形界面，便于輸入單詞，例句展現(xiàn)直觀，界面布局合理?！驹O(shè)計(jì)提示】按三步進(jìn)行：（1）準(zhǔn)備英語(yǔ)語(yǔ)料。尋找英語(yǔ)文章，可下載英語(yǔ)新聞，托福、GRE文章，或大學(xué)英語(yǔ)課文等。（2）處理語(yǔ)料。對(duì)語(yǔ)料進(jìn)行清理、分句、索引、生成字典。需要進(jìn)行取詞干的操作，分句可以直接根據(jù)標(biāo)點(diǎn)符號(hào)處理。（3）根據(jù)索引進(jìn)行查詢。支持一個(gè)或多個(gè)查詢，基于對(duì)詞干的處理，當(dāng)查go、going等時(shí)也能夠有返回。由于查詢的結(jié)果是語(yǔ)句，如果直接按照詞與文章的關(guān)系建立索引，這樣需要從文章中找句子，太多的串匹配操作可能導(dǎo)致查詢較慢，所以要設(shè)計(jì)好索引的粒度。 p大學(xué)校區(qū)（*）【題目描述】當(dāng)前，中原工學(xué)院共有四個(gè)校區(qū)：北校區(qū)（North）、南校區(qū)（South）、西校區(qū)（West）和東校區(qū)（信商新區(qū)）（East），每一個(gè)校區(qū)都有若干個(gè)建筑物，如公園、廣場(chǎng)、科研院所、實(shí)驗(yàn)中心、禮堂等，每個(gè)建筑物之間都有一定的距離，因此，在平時(shí)的教學(xué)和生活中，教師和學(xué)生都會(huì)經(jīng)常面臨這樣的問(wèn)題：在同一個(gè)校區(qū)或不同校區(qū)之間，從一個(gè)地點(diǎn)到另一個(gè)地點(diǎn)往來(lái)的需要?，F(xiàn)在，他們需要找到從出發(fā)點(diǎn)S到目的地T的一條最短路徑，以便節(jié)省時(shí)間，你能幫助他們嗎？假設(shè)任兩個(gè)建筑物之間至多存在一條直接相連的道路，并且都有具體的長(zhǎng)度?！据斎搿枯斎氲牡谝恍惺且粋€(gè)正整數(shù)C，表示下面測(cè)試案例數(shù)目。在每一種測(cè)試?yán)?，第一行的正整?shù) N(0<N100)表示道路的數(shù)目，其后的N行：第i行表示第i（1iN）條道路的起點(diǎn)Si 和終點(diǎn)Ti及其之間的距離Di（0Di100），第N+1行表示教師或?qū)W生的出發(fā)地S與目的地T,你必須幫找出他們從出發(fā)地S到目的地T之間的最短路徑。每個(gè)校區(qū)分別使用North、South、West和East，每一個(gè)建筑物名稱用長(zhǎng)度不超出100個(gè)小寫字符（a-z）串表示?！据敵觥枯敵鰬?yīng)包括C行，每行對(duì)應(yīng)一個(gè)測(cè)試?yán)?，輸出從起點(diǎn)到目的地的最短距離。如果兩地點(diǎn)間無(wú)路徑則輸出-1。系統(tǒng)沒(méi)有多余的內(nèi)存空間可利用。【輸入樣例】12South.litang South.lab 2South.lab West.guangchang 100South.lab South.litang 【輸出樣例】2四、學(xué)生自選課題學(xué)生原則上可以結(jié)合個(gè)人愛(ài)好自選課題，要求自選課題必須覆蓋數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，有一定的深度與難度，有一定的算法復(fù)雜性，能明確體現(xiàn)數(shù)據(jù)抽象與組織、算法設(shè)計(jì)與性能分析以及編碼實(shí)現(xiàn)等過(guò)程。學(xué)生自選課題需提前報(bào)課程設(shè)計(jì)指導(dǎo)教師批準(zhǔn)方可生效。五、指導(dǎo)教師 苗鳳君、高艷霞、吳志剛、田繼鵬六、時(shí)間安排 第17-19 每天上午8:30-12:00下午13:00-16：30七、完成課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)報(bào)告書封面用學(xué)校的統(tǒng)一封面。課程設(shè)計(jì)報(bào)告的內(nèi)容：設(shè)計(jì)題目、需求分析、算法設(shè)計(jì)（包含算法思想、算法設(shè)計(jì)分析、流程圖等）、調(diào)試分析、測(cè)試結(jié)果、課設(shè)總結(jié)（收獲及體會(huì)）、附錄（源代碼）。八、成績(jī)考核根據(jù)完成任務(wù)的情況(必須進(jìn)行系統(tǒng)驗(yàn)收 + 答辯)、課程設(shè)計(jì)報(bào)告書的質(zhì)量和課程設(shè)計(jì)過(guò)程中的工作態(tài)度等按照50%、30%、20%加權(quán)綜合打分。上機(jī)程序檢查未通過(guò)者、無(wú)設(shè)計(jì)報(bào)告者以及嚴(yán)重抄襲他人設(shè)計(jì)者，成績(jī)?yōu)椴患案?。缺席次?shù)最終成績(jī)2次中等及以下3次及以上不及格其它情況根據(jù)界面設(shè)計(jì)、實(shí)現(xiàn)方法、功能效果、設(shè)計(jì)報(bào)告來(lái)評(píng)定。主要從以下幾個(gè)方面考察：項(xiàng)目得分備注程序運(yùn)行情況25分程序的結(jié)構(gòu)合理與否15分算法說(shuō)明的清晰程度20分總結(jié)的深刻程度10分獨(dú)立完成情況20分加分因素10分九、上交報(bào)告及相關(guān)源代碼上交課程設(shè)計(jì)報(bào)告和相關(guān)光盤。其中設(shè)計(jì)報(bào)告要以打印文稿的形式上交。光盤內(nèi)容包括程序源碼和課程設(shè)計(jì)報(bào)告的電子文檔。整個(gè)班級(jí)的設(shè)計(jì)均刻在一張光盤上。（上交時(shí)每人交一份，文件夾的取名規(guī)則為：“班級(jí)_學(xué)號(hào)_姓名”，如“計(jì)科131_學(xué)號(hào)_張三”。該文件夾下至少包括：“源代碼”、“課程設(shè)計(jì)報(bào)告”。由以班為單位收集刻盤按規(guī)定時(shí)間統(tǒng)一上交）。 數(shù)據(jù)結(jié)構(gòu)課程組 2014-12-1012/7