數(shù)據(jù)結(jié)構專業(yè)課程設計任務計劃書

福建工程學院計算機和信息科學系《數(shù)據(jù)結(jié)構課程設計》任務書使用班級：信管1501、1502使用學期：-第二學期指導老師：滕秀花、菜沛?zhèn)r間：17周星期四至18周星期三地點：公教6日

一、設計目標《算法和數(shù)據(jù)結(jié)構》是計算機專業(yè)關鍵課程，是一門實踐性很強課程。為了學好這門課程，必需在掌握理論知識同時，加強上機實踐。針對數(shù)據(jù)結(jié)構課程設計不僅能夠加深對課程內(nèi)容了解，而且能夠經(jīng)過實踐深入掌握程序設計技能和方法，學會數(shù)據(jù)組織方法和現(xiàn)實世界問題在計算機內(nèi)部表示方法，并針對問題應用背景分析，選擇最好數(shù)據(jù)結(jié)構和算法。同時經(jīng)過課程設計，要求學生在完成程序設計同時能夠?qū)懗霰容^規(guī)范設計匯報，初步感受軟件開發(fā)過程項目管理方法和規(guī)范，為深入學習打下基礎。二、設計題目:見附錄B三、設計要求1、每人最少選擇一題完成，每生最少完成一題。C語言成績2、獨立思索，獨立完成：課程設計中各任務設計和調(diào)試要求獨立完成，碰到問題能夠討論，但不能夠拷貝，不許可雷同。3、在處理每個題目時，要求從分析題目標需求入手，按設計抽象數(shù)據(jù)類型、構思算法、經(jīng)過類設計實現(xiàn)抽象數(shù)據(jù)類型、編制上機程序和上機調(diào)試等若干步驟完成題目，最終寫出完整分析匯報。前期準備工作完備是否直接影響到后序上機調(diào)試工作效率。在程序設計階段應盡可能利用已經(jīng)有標準函數(shù)，加大代碼重用率。4、設計出系統(tǒng)要有一個易于使用人機界面。5、源程序中應對關鍵程序?qū)懗鲎⑨屨Z句四、應提交作品設計匯報（電子稿），文檔書寫格式可參看附錄A。源程序。五、提交方法及要求每個人以自己“學號姓名”形式建立文件夾，每個人文檔及源程序存放在自己文件夾內(nèi)。答辯時拷貝給指導老師檢驗、答辯；答辯時請先去除代碼中注釋。每位同學必需經(jīng)過答辯，未答辯及答辯未經(jīng)過均為不及格。答辯結(jié)束后拷給學習委員，學習委員將全班設計匯報和程序搜集齊后交給指導老師。六、時間安排第19周星期四至20周星期三早晨，天天1-6節(jié)。時間內(nèi)容17周四早晨選定題目：明確題目要求、確定數(shù)據(jù)結(jié)構、算法描述，準備測試數(shù)據(jù)等17周四至18周二完成要求問題并測試、歸檔18周二、周三演示回復老師提問文檔及程序整理并提交作品課程設計期間不遲到，不早退，有特殊情況要事先請假，并經(jīng)相關老師同意方能有效，無故缺席者作曠課處理。進入機房，應遵守機房要求各項制度。A組：1.在次序存放實現(xiàn)以下排序算法實現(xiàn)直接插入、冒泡排序、簡單選擇排序算法?；A要求：待排序表表長為0；其中數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；最少要用5組不一樣輸入數(shù)據(jù)(包含正序、逆序、基礎有序、隨機)比較；比較指標為相關鍵字參與比較次數(shù)和關鍵字移動次數(shù)（關鍵字交換計為3次移動）2.在鏈表上實現(xiàn)排序?qū)崿F(xiàn)直接插入、冒泡排序、簡單選擇排序算法。基礎要求：待排序表表長為0；其中數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；最少要用5組不一樣輸入數(shù)據(jù)比較，比較指標為相關鍵字參與比較次數(shù)和關鍵字移動次數(shù)（關鍵字交換計為3次移動）3.二叉排序樹創(chuàng)建輸入任意數(shù)列創(chuàng)建二叉排序樹，并進行先序、中序、后序和層次遍歷（用次序隊列輔助遍歷）?；A要求：存放結(jié)構利用二叉鏈表4.鏈表基礎操作利作鏈表插入運算建立線性鏈表，然后利用鏈表查找、刪除、計數(shù)、輸出等運算反復實現(xiàn)鏈表這些操作（插入、刪除、查找、計數(shù)、輸出單獨寫成函數(shù)形式），并能在屏幕上輸出操作前后結(jié)果。5.宿舍管理查詢軟件任務：為宿舍管理人員編寫一個宿舍管理查詢軟件,程序設計要求：采取交互工作方法；建立數(shù)據(jù)文件，數(shù)據(jù)文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一個)查詢菜單:（用不一樣查找方法實現(xiàn)）按姓名查詢按學號查詢按房號查詢6.商品貨架管理商店貨架以棧方法擺放商品。商品貨架能夠看成一個棧，棧頂商品生產(chǎn)日期最早，棧底商品生產(chǎn)日期最近。生產(chǎn)日期越靠近越靠棧底，出貨時從棧頂取貨。一天營業(yè)結(jié)束，假如貨架不滿，則需上貨。入貨直接將商品擺放到貨架上，則會使生產(chǎn)日期越近商品越靠近棧頂。這么就需要倒貨架，使生產(chǎn)日期越近越靠近棧底。請編寫程序模擬商品銷售，上架倒貨架等操作。（設有5種商品，每種商品最少有商品名和生產(chǎn)日期兩個屬性）7.稀疏矩陣快速轉(zhuǎn)置**利用三元組表存放稀疏矩陣，利用快速轉(zhuǎn)置算法進行轉(zhuǎn)置，并輸出轉(zhuǎn)置之前和以后三元組表和矩陣。8．背包問題有n項可投資項目，每個項目需要投入資金s，可贏利潤為vi，現(xiàn)有可用資金總數(shù)為M，應選擇哪些項目來投資，才能取得最大利潤。9.看病排隊候診醫(yī)院各科室醫(yī)生有限，所以病人到醫(yī)院看病時必需排隊候診，而病人病情有輕重之分不能簡單地依據(jù)先來先服務標準進行診療診療，所以護士依據(jù)病人病情要求了不一樣優(yōu)先等級。醫(yī)生在診療診療時，總是選擇優(yōu)先級高病人進行診治，假如碰到兩個優(yōu)先等級相同病人，則選擇最先來排隊病人進行診治。10.恢復二叉樹已知二叉樹先根遍歷結(jié)果和中序編列結(jié)果，恢復二叉樹，并后根遍歷該二叉樹B組：1.排序算法實現(xiàn)實現(xiàn)直接插入、冒泡排序、簡單選擇、快速排序、堆排序排序算法。基礎要求：待排序表表長為0；其中數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；最少要用5組不一樣輸入數(shù)據(jù)(包含正序、逆序、基礎有序、隨機)比較；比較指標為相關鍵字參與比較次數(shù)和關鍵字移動次數(shù)（關鍵字交換計為3次移動）2．哈希表針對同班同學信息設計一個通訊錄，學生信息有姓名，學號，電話號碼等。以學生姓名為關鍵字設計哈希表，并完成對應建表和查表程序?；A要求：姓名以漢語拼音形式，待填入哈希表人名約30個，自行設計哈希函數(shù)和沖突處理方法；在查找過程中給出比較次數(shù)。完成按姓名查詢操作。要求：實現(xiàn)信息增、刪、改。將初始班級通訊錄信息存入文件，3.校園導游程序設計一個校園導游程序為來訪客人提供多種信息查詢服務。（校園平面是一個無向網(wǎng)）基礎要求：（1）)設計學校旗山校區(qū)北區(qū)校園平面圖，所含場所不少于10個。以圖中頂點表示校內(nèi)各場所，存放場所名稱、代號、介紹等信息；以邊表示路徑，存放路徑長度等相關信息。（2）為來訪客人提供圖中任意場所相關信息查詢。（3）為來訪客人提供圖中任意場所問路查詢，即查詢?nèi)我鈨蓚€景點之間一條最短簡單路徑。要求：實現(xiàn)場所和路徑增加、刪除。數(shù)據(jù)保留、調(diào)入。4.航空客運訂票系統(tǒng)經(jīng)過此系統(tǒng)能夠?qū)崿F(xiàn)以下功效：錄入：能夠錄入航班情況（數(shù)據(jù)能夠存放在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構、具體數(shù)據(jù)自定）；查詢：能夠查詢某個航線情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；能夠輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況能夠存在一個數(shù)據(jù)文件中，結(jié)構自己設定）能夠訂票，假如該航班已經(jīng)無票，能夠提供相關可選擇航班；退票：可退票，退票后修改相關數(shù)據(jù)文件；用戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當航班信息改變能夠修改航班數(shù)據(jù)文件要求：依據(jù)以上功效說明，設計航班信息，訂票信息存放結(jié)構，數(shù)據(jù)存盤和調(diào)入，設計程序完成功效；5.哈夫曼編碼和譯碼利用哈夫曼編碼進行信息通信能夠大大提升信道利用率，縮短信息傳輸時間，降低傳輸成本。不過，這要求在發(fā)送端經(jīng)過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即能夠雙向傳輸信息信道），每端全部需要一個完整編/譯碼系統(tǒng)。試為這么信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)?；A要求:一個完整系統(tǒng)應含有以下功效：（1）初始化（Initialization）。從終端讀入字符集大小n，和n個字符和n個權值，建立哈夫曼樹，(選做：并將它存于文件hfmTree中）。并顯示出每個字符編碼。（2）編碼（Encoding）。利用已建好哈夫曼樹（選做：如不在內(nèi)存，則從文件htmTree中讀入），對輸入字符串文本（選做：對文件ToBeTran中正文）進行編碼，（選做：然后將結(jié)果存入文件CodeFile中。）并顯示在屏幕上。（3）譯碼（Decoding）。利用已建好哈夫曼樹將輸入代碼進行譯碼（選做：將文件CodeFile中代碼進行譯碼，結(jié)果存入文件TextFile中。），并顯示在屏幕上。（4）打印哈夫曼樹（TreePrinting）。將程序中哈夫曼樹以直觀方法顯示在屏幕上。6.一元稀疏多項式計算器基礎功效定為

(1)輸入并建立多項式

(2)輸出多項式,輸出形式為整數(shù)序列:n,c1,e1,c2,e2,.....,Cn,en,其中n是多項式相數(shù),Ci和Ei分別是第i項系數(shù)和指數(shù),序列按指數(shù)降序排列

(3)兩個多項式相加，建立并輸出和多項式

(4)兩個多項式相減，建立并輸出差多項式

(5)兩個多項式相乘,建立乘積多項式

(6)計算多項式在x處值7.學生成績管理系統(tǒng)現(xiàn)有學生成績信息文件1（1.txt），內(nèi)容以下姓名學號語文數(shù)學英語張明明01677882李成友02789188張輝燦03688256王露04564577陳東明05673847….......…學生成績信息文件2（2.txt）,內(nèi)容以下:姓名學號語文數(shù)學英語陳果31576882李華明32889068張明東33484256李明國34504587陳道亮35475877….......…試編寫一管理系統(tǒng),要求以下:實現(xiàn)對兩個文件數(shù)據(jù)進行合并,生成新文件3.txt抽取出三科成績中有補考學生并保留在一個新文件4.txt對合并后文件3.txt中數(shù)據(jù)按總分降序排序(最少采取兩種排序方法實現(xiàn)：插入，希爾，冒泡，快速，堆)輸入一個學生姓名后,能查找到此學生信息并輸出結(jié)果(最少采取兩種查找方法實現(xiàn)：次序，折半，二叉排序，哈希表)要求使用結(jié)構體,鏈或數(shù)組等實現(xiàn)上述要求.8.教學計劃安排檢驗程序（拓撲排序）此次課程設計任務是：針對學院計算機系本科課程，依據(jù)課程之間依靠關系，制訂課程安排計劃，并滿足各學期課程數(shù)大致相同。根據(jù)用戶輸入課程數(shù)，學期數(shù)，課程間前后關系數(shù)目和課程間兩兩間前后關系，程序?qū)嵤┖髸o出每學期應學課程。

(1)輸入形式和輸入值范圍：輸入間用空格隔開。要求用戶輸入課程數(shù)小于20，學期數(shù)小于或是等于8，課程名長度小于等于10個字符。

(2)程序所能達成功效：根據(jù)用戶輸入，給出每學期應學課程。

(4)測試數(shù)據(jù)：輸入：學期數(shù)：５，課程數(shù)：12，課程間前后關系數(shù)：16，課程代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。課程間兩兩間前后關系：v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6

輸出：第1學期應學課程：v1v9

第2學期應學課程：v2v4v10v11

第3學期應學課程：v3v6v12

第4學期應學課程：v5v8

第5學期應學課程：v7

9.停車場問題停車場是一條能夠停放n輛車狹窄通道，且只有一個大門汽車停放安抵達時間前后依次由北向南排列（大門在最南端，最先抵達第一輛車停在最北端）若停車場已經(jīng)停滿n輛車，以后汽車在便道上等候，一旦有車開走，排在便道上第一輛車能夠開入；當停車場某輛車要離開時，停在她后面車要前后退為她讓路，等它開出后其它車在根據(jù)原次序開入車場，每兩停在車場車要安時間長短繳費。要求：以棧模擬停車場，以隊列車場外便道，根據(jù)從終端輸入數(shù)據(jù)序列進行模擬管理。每一組數(shù)據(jù)包含三個數(shù)據(jù)項：汽車“抵達”或“離去”信息、汽車牌照號碼、和抵達或離去時刻。對每一組數(shù)據(jù)進行操作后信息為：若是車輛抵達，則輸出汽車在停車場內(nèi)或便道上位置：若是車輛離去則輸出汽車在停車場內(nèi)停留時間和應繳納費用（在便道上停留時間不收費）。棧以次序結(jié)構實現(xiàn)，隊列以鏈表結(jié)構實現(xiàn)。10.括號匹配情況***假設在一個算術表示式中，能夠包含三種括號：圓括號"（"和"）"，方括號"["和"]"和花括號"{"和"}"，而且這三種括號能夠按任意次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..?，F(xiàn)在需要設計一個算法，用來檢驗在輸入算術表示式中所使用括號正當性。算術表示式中多種括號使用規(guī)則為：出現(xiàn)左括號，必有對應右括號和之匹配，而且每對括號之間能夠嵌套，但不能出現(xiàn)交叉情況。我們能夠利用一個棧結(jié)構保留每個出現(xiàn)左括號，當碰到右括號時，從棧中彈出左括號，檢驗匹配情況。在檢驗過程中，若碰到以下多個情況之一，就能夠得出括號不匹配結(jié)論。（1）當碰到某一個右括號時，棧已空，說明到現(xiàn)在為止，右括號多于左括號；（2）從棧中彈出左括號和目前檢驗右括號類型不一樣，說明出現(xiàn)了括號交叉情況；（3）算術表示式輸入完成，但棧中還有沒有匹配左括號，說明左括號多于右括號。要求用棧完成。11、最小生成樹給定一個地域n個城市間距離網(wǎng)，建立最小生成樹，并計算得到最小生成樹代價。要求以下：①城市間距離網(wǎng)采取鄰接矩陣表示，鄰接矩陣存放結(jié)構定義采取教材給出定義，若兩個城市之間不存在道路，則將對應邊權值設為自己定義無窮大值。要求在屏幕上顯示得到最小生成樹中包含了哪些城市間道路，并顯示得到最小生成樹代價；②表示城市間距離網(wǎng)鄰接矩陣（要求最少6個城市，10條邊）③最小生成樹中包含邊及其權值，并顯示得到最小生成樹代價。12.空間最近點對在空中交通控制問題中，若將飛機作為空間中移動一個點來處理，則求出含有最大碰撞危險兩架飛機。(提醒：即空間中最靠近一對點，求平面即可)13.假幣檢驗（1）在n枚外觀相同硬幣中，有一枚是假幣，而且已知假幣較輕。能夠經(jīng)過一架天平來任意比較兩組硬幣，從而得硬幣重量是否相同，或哪一組更輕部分，假幣問題要求設計一個算法來檢測出這枚假幣。（2）在120枚外觀相同硬幣中，有一枚是假幣，而且已知假幣和真幣重量不一樣，但不知道假幣和真幣相比較輕還是重。能夠經(jīng)過一架天平來任意比較兩組硬幣，最壞情況下，能不能只比較5次就檢測出這枚假幣。14.拿子游戲考慮下面這個游戲：桌子上有一堆火柴，游戲開始時共有n根火柴，兩個玩家輪番拿走1根、2根、3根或4根火柴，拿走最終火柴玩家為獲勝方。請為先走玩家設計一個制勝策略（假如該策略存在）。15.猴子分桃.問題描述:動物園里n只猴子編號為1,2,3，….，n，依次排成一隊等候喂養(yǎng)員按規(guī)則分桃。動物園分桃規(guī)則是每只猴子可分得m個桃子，但必需排隊領取。喂養(yǎng)員循環(huán)地每次取出一個，2給，…，k個桃放入筐中，由排在隊首猴子領取。取到筐中桃子數(shù)為k后，又重新從1開始。當筐中桃子數(shù)加上隊首猴子可取桃子數(shù)不超出m時，隊首猴子能夠全部取得喂養(yǎng)員手中桃子；取得桃子總數(shù)不足m個桃子，繼續(xù)到隊尾排隊等候。當筐中桃子數(shù)加上隊首猴子可取桃子數(shù)超出m時，隊首猴子只能取滿m個，然后離開隊列，筐中剩下桃子由下一直猴子取用。上述分桃過程一直進行到每只猴子全部分到m個桃子。試驗任務：對于給定n,k和m，模擬上述猴子分桃過程輸入5,3,40輸出：1352416.KMP算法求一個字符串在另一個字符串中第一次出現(xiàn)位置。17.模擬陣15812417161475232220136432119121092251811618753294魔方陣是一個古老智力問題，它要求在一個m*m矩陣中填入1~m2數(shù)字（m為奇數(shù)），使得每一行、每一列、每條對角線累加和全部相等。要求：輸入m，實現(xiàn)，輸出18.家族關系查詢系統(tǒng)建立家族關系數(shù)據(jù)庫，實現(xiàn)對家族組員關系相關查詢要求：建立家族關系能存放到文件中；實現(xiàn)家族組員添加（雙親最多2個孩子）；能夠查詢家族組員雙親、祖先、弟兄、孩子和后代信息。提醒：樹狀結(jié)構能夠用三叉鏈表。

附錄B:匯報福建工程學院課程設計課程：題目：專業(yè)：班級：座號：姓名：年月日

試驗題目：求迷宮最短路徑一、要處理問題這是試驗心理學中一個經(jīng)典問題，心理學家把一只老鼠從一個無頂蓋大盒子入口處趕進迷宮。迷宮中設置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋求通路以達成出口。我們要處理是怎樣找到了一條迷宮最短路徑。二、算法基礎思想描述：要用到回溯思想。從迷宮入口點出發(fā)，向四面搜索，記下全部一步能抵達坐標點；然后依次從這些點出發(fā)，再記下全部一步能抵達坐標點，……..依這類推，直到抵達迷宮出口點為止，然后從迷宮出口點沿搜索路徑回溯。這么就找到了一條迷宮最短路徑，不然迷宮無路徑。因為先抵達點先搜索，故用優(yōu)異先出數(shù)據(jù)結(jié)構——隊列來保留已抵達坐標點。三、設計1.數(shù)據(jù)結(jié)構設計（1）迷宮表示設迷宮為m行n列，利用maze[m][n]來表示迷宮，maze[m][n]=0或1，其中0表示通路，1表示不通。入口坐標（1，1），出口坐標（m,n）.迷宮定義以下：#definem6#definen8intmaze[m+2][n+2]；（2）試探方向表示在迷宮中有8個方向能夠試探，要求：從目前位置向前試探方向為從正東開始沿順時針方向進行。為了簡化問題，將這8個方向坐標增量放在一個結(jié)構數(shù)組move[8]中。在move數(shù)組中，每個元素有兩個域組成，X：橫坐標增量；Y：縱坐標增量。序號序號XY00111121031-140-15-1-16-107-11(x,y)(x-1,y)(x+1,y)(x-1,y+1)(x,y+1)(x+1,y+1)(x-1,y-1)(x,y-1)(x+1,y-1)Move數(shù)組定義以下：typedefstruct{intx,y;}item;itemmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};（3）隊列表示在找到出口點以后，需要沿搜索路徑回溯，所以抵達某點時，不僅要記下該點坐標，還要記下該點前驅(qū)。用一個結(jié)構數(shù)組sq[num]作為隊列存放空間。Sq每一個結(jié)構有三個域：x,y,pre,其中x，y分別為所抵達點坐標，pre為前驅(qū)點坐標。還設隊頭front和隊尾rear指針。#definenum50typedefstruct{intx,y；intpre;}SqType;SqTypesq[num]；intfront，rear；2.算法設計（1）求最短路徑算法設計初始狀態(tài)，隊列中只有一個元素sq[1],統(tǒng)計是入口點坐標（1，1），因為該點是出發(fā)點，所以沒有直接前驅(qū)點，pre域為-1，隊頭指針front隊尾指針rear均指向它，以后搜索時全部是以front所指點為搜索出發(fā)點，立即該點坐標及front所指點位置入隊，這么不僅記下了抵達點坐標，還記下了它前驅(qū)點。Front所指向點8個方向搜索完成后，則出隊，繼續(xù)對下一點搜索。搜索過程中碰到出口點則成功，搜索結(jié)束，打印出迷宮最短路徑，算法結(jié)束；或目前隊空，既沒有搜索點了，表明沒有路徑，算法也結(jié)束。（2）預防反復抵達某點考慮為避免發(fā)生死循環(huán)，當?shù)诌_某點（i，j）后，使maze[i][j]置-1，方便區(qū)分未抵達過頂點。算法結(jié)束前可恢復原迷宮。（3）隊列頭、尾指針指向隊頭指針指向搜索出發(fā)點，當找到一個可抵達點，就入隊；當8個方位全部搜索完成，隊頭指針往后移一個（出隊，但原位置值仍然存在，方便最終回溯）。（4）模塊結(jié)構及功效：主程序主程序隊列初始化打印路徑入隊迷宮初始化求最短路經(jīng)出隊判隊空voidmain()//主程序viodinit_maze(int)//迷宮初始化voidinit_queue(SqType)//隊列初始化intpath(int,int)//求迷宮最短路徑voidprint_path(SqType,rear)//打印路徑voidin_queue(SqType,datatype)//入隊操作voidout