數據結構專業(yè)課程設計任務計劃書

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

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

(1)輸入并建立多項式

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

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

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

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

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

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

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

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

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

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