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

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

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

(1)輸入并建立多項(xiàng)式

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

(3)兩個(gè)多項(xiàng)式相加，建立并輸出和多項(xiàng)式

(4)兩個(gè)多項(xiàng)式相減，建立并輸出差多項(xiàng)式

(5)兩個(gè)多項(xiàng)式相乘,建立乘積多項(xiàng)式

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

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

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

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

輸出：第1學(xué)期應(yīng)學(xué)課程：v1v9

第2學(xué)期應(yīng)學(xué)課程：v2v4v10v11

第3學(xué)期應(yīng)學(xué)課程：v3v6v12

第4學(xué)期應(yīng)學(xué)課程：v5v8

第5學(xué)期應(yīng)學(xué)課程：v7

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

附錄B:匯報(bào)福建工程學(xué)院課程設(shè)計(jì)課程：題目：專業(yè)：班級(jí)：座號(hào)：姓名：年月日

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