數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)級第一頁，共五十六頁，編輯于2023年，星期三二、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要求1.學(xué)生必須仔細(xì)閱讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)方案，認(rèn)真主動完成課設(shè)的要求。有問題及時(shí)主動通過各種方式與教師聯(lián)系溝通。2.學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測自己的計(jì)劃完成情況，及時(shí)向教師匯報(bào)。3.課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成（2周共十天）。第二頁，共五十六頁，編輯于2023年，星期三三、實(shí)習(xí)基本內(nèi)容

本次課程設(shè)計(jì)完成如下模塊（共23個(gè)模塊，學(xué)生可以在其中至少挑選5-6個(gè)功能塊完成，其中8、9、10、13在做5個(gè)以下不算數(shù)，5個(gè)以上算數(shù)

）

第三頁，共五十六頁，編輯于2023年，星期三1校園導(dǎo)游程序

問題描述：用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題?；疽螅翰樵兏骶包c(diǎn)的相關(guān)信息；查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑；查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑；增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。選作內(nèi)容：①求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。②區(qū)分機(jī)動車道和人行道。③實(shí)現(xiàn)導(dǎo)游圖的仿真界面。第四頁，共五十六頁，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)：typedefstructmessage{ intnum;//景點(diǎn)代碼 charname[100];//景點(diǎn)名稱 charpro[500];//簡介}Ciceroni;第五頁，共五十六頁，編輯于2023年，星期三Ciceronischool[10]={{1,"行政樓\n"},{2,"食堂\n"},{3,"賽博樓,信息分院辦公室所在地\n"},{4,"求是樓,實(shí)驗(yàn)樓計(jì)算機(jī)中心\n"},{5,"格致樓,法學(xué)管理學(xué)院"},{6,"工程實(shí)習(xí)中心,金工實(shí)習(xí)\n"},{7,"仰儀樓,機(jī)電計(jì)測分院\n"},{8,"體育館,旁邊有籃球場`足球場`還有網(wǎng)球場\n"},{9,"一號教學(xué)樓，主要以階梯教室為主\n"},{10,"二號教學(xué)樓，小教室為多\n"}};/*景點(diǎn)名稱和簡介*/操作：/*給景點(diǎn)之間的路徑賦最大值*//*最短路徑的C語言函數(shù)*//*輸出最短路徑和最短距離函數(shù)*//*輸入景點(diǎn)代碼查景點(diǎn)名稱和簡介*//*輸入景點(diǎn)代碼查到其它景點(diǎn)的最短距離*/第六頁，共五十六頁，編輯于2023年，星期三2員工管理系統(tǒng)問題描述：每個(gè)員工的信息包括：編號、姓名、性別、出生年月、學(xué)歷、職務(wù)、電話、住址等。系統(tǒng)能夠完成員工信息的查詢、更新、插入、刪除、排序等功能。基本要求：排序：按不同關(guān)鍵字，對所有員工的信息進(jìn)行排序；查詢：按特定條件查找員工；更新：按編號對某個(gè)員工的某項(xiàng)信息進(jìn)行修改；插入：加入新員工的信息；刪除：按編號刪除已離職的員工的信息。選作內(nèi)容：實(shí)現(xiàn)圖形用戶界面。第七頁，共五十六頁，編輯于2023年，星期三要求通過鏈表實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：structworkers{ charname[15];//姓名chardepartment[18];//單位chargender;//性別unsignedintage;//年齡unsignedlongtelephone;//電話unsignedlongwage;//工資unsignedlongnum;//職工號structworkers*next;};第八頁，共五十六頁，編輯于2023年，星期三操作實(shí)現(xiàn)：/*插入職工信息，通過鏈表實(shí)現(xiàn)*//*具體實(shí)現(xiàn)職工信息的插入*//*對職工信息的刪除操作*//*修改操作*//*實(shí)現(xiàn)對員工信息的查找*//*排序*//*輸出員工信息*//*顯示職工工資情況計(jì)算平均工資*/第九頁，共五十六頁，編輯于2023年，星期三3算術(shù)表達(dá)式求值問題描述：一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。基本要求：從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果；顯示輸入序列和棧的變化過程。"(3.14159/2+sqrt(1/3^2+4)+1/2^2*ln(1/1.1*(2+sqrt(1/3^2+4))))*23.45@";選作內(nèi)容：擴(kuò)充運(yùn)算符集合；引入變量操作數(shù)；操作數(shù)類型擴(kuò)充到實(shí)數(shù)。第十頁，共五十六頁，編輯于2023年，星期三4運(yùn)動會分?jǐn)?shù)統(tǒng)計(jì)

任務(wù)：參加運(yùn)動會有n個(gè)學(xué)校，學(xué)校編號為1，…，n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號為男子1…m，女子m+1…m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20，n<=20）功能要求：可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績；能統(tǒng)計(jì)各學(xué)?？偡?；可以按學(xué)校編號、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；可以按學(xué)校編號查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。第十一頁，共五十六頁，編輯于2023年，星期三規(guī)定：輸入數(shù)據(jù)形式和范圍為20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動項(xiàng)目的名稱）；輸出形式，有中文提示，各學(xué)校分?jǐn)?shù)為整型；界面要求，有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，請?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲結(jié)構(gòu)。第十二頁，共五十六頁，編輯于2023年，星期三參考的數(shù)據(jù)結(jié)構(gòu)：（1）項(xiàng)目信息表結(jié)構(gòu)typedefstructxm_table{intitem;//項(xiàng)目編號charname[20];//項(xiàng)目名稱intcount;

//該項(xiàng)目得分人的數(shù)量}XM_TABLE;（2）學(xué)生信息表結(jié)構(gòu)structSTUDENT{charname[20];

//姓名intscore;

//得分成績intrange;

//得分名次intitem;

//得分項(xiàng)目intsex;

//性別};第十三頁，共五十六頁，編輯于2023年，星期三（3）參賽學(xué)校信息結(jié)構(gòu)//參賽學(xué)校typedefstructSchoolStruct

{intcount;

//計(jì)算實(shí)際運(yùn)動員個(gè)數(shù)intserial;

//學(xué)校編號charName[20];//學(xué)校名稱intmenscore;

//男子團(tuán)體總分intwomenscore;

//女子團(tuán)體總分inttotalscore;

//團(tuán)體總分intjifeng;

//學(xué)校積分struct

STUDENTstudents[10];

//參賽運(yùn)動員structSchoolStruct*next;

//下一個(gè)參賽學(xué)校}SCHOOLSTRUCT;第十四頁，共五十六頁，編輯于2023年，星期三操作需求：//建立參賽學(xué)校鏈表//添加獲獎(jiǎng)學(xué)生//成績統(tǒng)計(jì)//按項(xiàng)目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。//按學(xué)校編號查詢學(xué)校某個(gè)項(xiàng)目//在屏幕輸出數(shù)據(jù)//參數(shù)設(shè)置（設(shè)置參賽學(xué)校數(shù)n>=2，請輸男生項(xiàng)目總數(shù)<m<=20，請輸女生項(xiàng)目總數(shù)<k<=20）//項(xiàng)目資料:請輸入男生項(xiàng)目信息：項(xiàng)目名稱;項(xiàng)目編號;該項(xiàng)目的參與人數(shù)請輸入女生項(xiàng)目信息：項(xiàng)目名稱;項(xiàng)目編號;該項(xiàng)目的參與人數(shù)//添加學(xué)生數(shù)據(jù)intSchoolCount=0;//學(xué)?？倲?shù)intboyCount=0;//男生項(xiàng)目總數(shù)intgirlCount=0;//女生項(xiàng)目總數(shù)intxm_Count=0;//項(xiàng)目總數(shù)XM_TABLExm_T[41];//項(xiàng)目表主要實(shí)現(xiàn)："參數(shù)設(shè)置";"添加學(xué)生";"統(tǒng)計(jì)";"學(xué)校查詢";"項(xiàng)目查詢";等功能。第十五頁，共五十六頁，編輯于2023年，星期三5一元多項(xiàng)式計(jì)算任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相乘，并將結(jié)果輸出；在上交資料中請寫明：存儲結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；設(shè)有一元多項(xiàng)式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+Amxm

Bn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn

請實(shí)現(xiàn)求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。第十六頁，共五十六頁，編輯于2023年，星期三要求：1)

首先判定多項(xiàng)式是否稀疏2)

分別采用順序和動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)；3)

結(jié)果M(x)中無重復(fù)階項(xiàng)和無零系數(shù)項(xiàng)；4)

要求輸出結(jié)果的升冪和降冪兩種排列情況第十七頁，共五十六頁，編輯于2023年，星期三6訂票系統(tǒng)任務(wù)：通過此系統(tǒng)可以實(shí)現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；第十八頁，共五十六頁，編輯于2023年，星期三訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計(jì)程序完成功能；第十九頁，共五十六頁，編輯于2023年，星期三航班信息數(shù)據(jù)結(jié)構(gòu)typedefcharkeytype;//航班信息結(jié)構(gòu)typedefstruct{ charstart[6];//起點(diǎn)站 charend[6];//終點(diǎn)站 charsche[10];//航班期 chartime1[5];//起飛時(shí)間 chartime2[5];//到達(dá)時(shí)間 charmodel[4];//機(jī)型 intprice;//票價(jià)}infotype;第二十頁，共五十六頁，編輯于2023年，星期三//定義航班節(jié)點(diǎn)typedefstruct{ keytypekeys[keylen];//航班號 infotypeothers;//航班信息 intnext;//下一航班}slnode;//航班表(靜態(tài)鏈表)typedefstruct{ slnodesl[maxspace]; intkeynum; intlength;}sllist;第二十一頁，共五十六頁，編輯于2023年，星期三操作實(shí)現(xiàn)：（1）錄入航班信息：（2）查詢航班信息：可以查詢某個(gè)航線的情況（如，輸入航班號，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；航班信息查詢系統(tǒng)：可以按：1.航班號; 2.起點(diǎn)站； 3.終點(diǎn)站； 4.起飛時(shí)間; 5.到達(dá)時(shí)間;第二十二頁，共五十六頁，編輯于2023年，星期三以下選作：（3）航班訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；（4）航班退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。（5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件注：因?yàn)楹桨嗵枮閮晌蛔帜负蟾鷶?shù)字，所以在排序時(shí)應(yīng)該使用多關(guān)鍵字的基數(shù)排序?qū)桨嗵栠M(jìn)行排序。第二十三頁，共五十六頁，編輯于2023年，星期三7迷宮問題求解任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；第二十四頁，共五十六頁，編輯于2023年，星期三8文章編輯（不算）功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個(gè)字符，共N行；要求①分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；②統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；③刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號。輸出形式：①分行輸出用戶輸入的各行字符；②分4行輸出"全部字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù)"；③輸出刪除某一字符串后的文章；第二十五頁，共五十六頁，編輯于2023年，星期三9joseph環(huán)（不算）

任務(wù)：編號是1，2，……，n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。要求：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號。測試數(shù)據(jù)：m的初值為20，n=7，7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6，則正確的輸出是什么？要求：輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列第二十六頁，共五十六頁，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)：typedefstructNode{ intdata; intpassword; structNode*next;}Node,*LinkList;基本操作：//初始化單鏈表//給每個(gè)人賦密碼//確定需要處理的人數(shù)//確定開始的上限值//得到正確的順序//輸出結(jié)果第二十七頁，共五十六頁，編輯于2023年，星期三11建立二叉樹，已知二叉樹的層次序列、先序遍歷（用遞歸或非遞歸的方法都可以）

任務(wù)：

要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；第二十八頁，共五十六頁，編輯于2023年，星期三12哈夫曼編/譯碼器任務(wù)：建立最優(yōu)二叉樹函數(shù)要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；第二十九頁，共五十六頁，編輯于2023年，星期三利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。第三十頁，共五十六頁，編輯于2023年，星期三[基本要求]一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P：打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。（5）T：打印哈夫曼樹（Treeprinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。第三十一頁，共五十六頁，編輯于2023年，星期三[測試數(shù)據(jù)]（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符空格

A

B

C

D

E

F

G

H

I

J

K

L

M頻度186

64

13

22

32103

21

15

47

57

1

5

32

20字符

N

O

P

Q

R

S

T

U

V

W

X

Y

Z頻度

57

63

15

1

48

51

80

23

8

18

1

16

1第三十二頁，共五十六頁，編輯于2023年，星期三13拓?fù)渑判?/p>

任務(wù)：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉５谌?，共五十六頁，編輯?023年，星期三14學(xué)生成績管理

實(shí)現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計(jì)、退出。能實(shí)現(xiàn)對學(xué)生信息的簡單管理。具體要求：建立一個(gè)4個(gè)學(xué)生的信息登記表，每個(gè)學(xué)生的信息包括：學(xué)號，姓名，和3門課程的成績（FOX,C,ENGLISH）。

程序運(yùn)行時(shí)顯示一個(gè)簡單的菜單，例如：

（1）信息輸入（INPUT）

（2）總分統(tǒng)計(jì)（COUNT）

（3）總分排序（SORT）

（4）查詢(QUERY）

其中：

（1）對4個(gè)學(xué)生的信息進(jìn)行輸入；

（2）對每個(gè)學(xué)生的3門課程統(tǒng)計(jì)總分；

(3)對4個(gè)學(xué)生的總分按降序排序并顯示出來；

(4)查詢輸入一個(gè)學(xué)號后，顯示出該學(xué)生的有關(guān)信息；第三十四頁，共五十六頁，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)：structstudent{intnum;//學(xué)號charname[20];//姓名intfoxscore;//fox成績intcscore;//C語言intenglishscore;//英語成績structstudent*next;};操作：1.成績信息輸入; 2.統(tǒng)計(jì)總分; 3.排序; 4.查詢第三十五頁，共五十六頁，編輯于2023年，星期三15[停車場管理]設(shè)停車場（如下圖所示）內(nèi)只有一個(gè)可停放幾量汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時(shí)的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已經(jīng)停滿幾量汽車，則后來的汽車只能在門外的便道上等候，一旦停車場內(nèi)有車開走，則排在便道上的第一輛汽車即可開入；當(dāng)停車場內(nèi)某車輛要離開時(shí)，由于停車場是狹長的通道，在它之后開入車場的車輛必須先退出車場為它讓路，待該車輛開出大門外后，為它讓路的車輛再按原次序進(jìn)入車場。在這里假設(shè)汽車不能從便道上開走。試設(shè)計(jì)一個(gè)停車場管理程序（這里只是一個(gè)假想的停車場管理，并不代表實(shí)際的停車場管理）。第三十六頁，共五十六頁，編輯于2023年，星期三分析：汽車在停車場內(nèi)進(jìn)出是按照棧的運(yùn)算方式來實(shí)現(xiàn)的，先到的先進(jìn)停車場；停車場的汽車離開停車場時(shí)，汽車場內(nèi)其它汽車為該輛汽車讓路，也是按棧的方式進(jìn)行；汽車在便道上等候是按隊(duì)列的方式進(jìn)行的。因此，將停車場設(shè)計(jì)成一個(gè)棧，汽車讓路也需要另一個(gè)棧來協(xié)助完成，汽車進(jìn)出便道用隊(duì)列來實(shí)現(xiàn)。第三十七頁，共五十六頁，編輯于2023年，星期三本設(shè)計(jì)，棧采用順序棧結(jié)構(gòu)，隊(duì)列用鏈?zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)構(gòu)定義如下：#definestacksize10typedefstructsqstack{intdata[stacksize];inttop;}SqStackTp;typedefstructlinked_queue{intdata;structlinked_queue*next;}LqueueTp;typedefstruct{LqueueTp*front,*rear;}QueptrTp;第三十八頁，共五十六頁，編輯于2023年，星期三停車場管理的算法描述如下：1）接受命令和車號，若是汽車要進(jìn)停車場，先判斷停車場棧是否滿，若不滿，則汽車入棧，否則汽車進(jìn)入便道隊(duì)列等候。2）若是汽車要離開停車場，為給汽車讓路，將停車場棧上若干輛汽車入臨時(shí)棧，等這輛車出停車場后，臨時(shí)棧中的汽車出棧，在回到停車場棧，然后看便道隊(duì)列是否為空，若不空則說明有汽車等候，從隊(duì)頭取出汽車號，讓該車進(jìn)入停車場棧。3）重復(fù)1），2）直到為退出命令（車號為0或負(fù)數(shù)）。第三十九頁，共五十六頁，編輯于2023年，星期三16[二叉排序樹與文件操作]功能要求：（1）從鍵盤輸入一組學(xué)生記錄建立二叉排序樹；（2）二叉排序樹存盤；（3）由文件恢復(fù)內(nèi)存的二叉排序樹；（4）中序遍歷二叉排序樹；（5）求二叉排序樹深度；（6）求二叉排序樹的所有節(jié)點(diǎn)數(shù)和葉子節(jié)點(diǎn)數(shù)；（7）向二叉排序樹插入一條學(xué)生記錄；（8）從二叉排序樹中刪除一條學(xué)生記錄；（9）從二叉排序樹中查詢一條學(xué)生記錄；（10）以廣義表的形式輸出二叉排序樹第四十頁，共五十六頁，編輯于2023年，星期三//定義學(xué)生記錄類型structstudent{charnum[6];//學(xué)號intgrade;//成績};//定義二叉排序樹節(jié)點(diǎn)值的類型為學(xué)生記錄類型typedefstudentElemType;//定義二叉排序樹的節(jié)點(diǎn)類型typedefstructBSTNode{ElemTypedata;StructBSTNode*left;StructBSTNode*rchild;}BSTNode;第四十一頁，共五十六頁，編輯于2023年，星期三17[B_樹索引文件的插入、刪除和查找]

功能要求：1.從鍵盤輸入一組關(guān)鍵字插入B_樹中；2.向B_樹中插入一個(gè)關(guān)鍵字；3.從B_樹中刪除一個(gè)關(guān)鍵字；4.從B_樹中查找一個(gè)關(guān)鍵字對應(yīng)記錄的位置；5.遍歷輸出B_樹中所有關(guān)鍵字；6.求出一棵B_樹的深度；7.求出一棵B_樹的節(jié)點(diǎn)數(shù)；8.內(nèi)存B_樹存盤；9.由文件中保存的B_樹恢復(fù)到內(nèi)存中；10.清除B_樹，即收回B_樹中的所有節(jié)點(diǎn)；第四十二頁，共五十六頁，編輯于2023年，星期三//定義B_樹的階數(shù)和特定的最大關(guān)鍵字，可自行設(shè)定#definem3#defineMAXKEY9999//定義關(guān)鍵字類型為整型typedefintKeyType;//定義元素類型structElemType{KeyTypekey;//整型關(guān)鍵字域charrest[10]；//字符數(shù)組域};第四十三頁，共五十六頁，編輯于2023年，星期三//定義B_樹的節(jié)點(diǎn)類型structMBNode{intkeynum;//關(guān)鍵字個(gè)數(shù)域MBNode*parent;//指向父節(jié)點(diǎn)的指針域KeyTypekey[m+1]；//保存n個(gè)關(guān)鍵字域，下標(biāo)0位置未用MBNode*ptr[m+1];//保存n+1個(gè)指向子樹的指針域Intrecptr[m+1];//保存每個(gè)關(guān)鍵字對應(yīng)記錄的存儲位置域，下標(biāo)0位置未用};

第四十四頁，共五十六頁，編輯于2023年，星期三18[散列文件的插入、刪除和查找]

功能要求：（1）初始化三列文件；（2）向散列文件中插入一個(gè)元素；（3）從散列文件中刪除一個(gè)元素；（4）從散列文件中查找一個(gè)元素。散列文件通常采用鏈接法處理沖突，并且把保存每個(gè)單鏈表表頭指針的表頭向量用一個(gè)文件單獨(dú)存儲起來，稱此為散列表文件，把所有單鏈表中的結(jié)點(diǎn)用一個(gè)文件單獨(dú)存儲起來，稱為散列主文件。第四十五頁，共五十六頁，編輯于2023年，星期三

散列文件中每個(gè)節(jié)點(diǎn)的類型定義為：structFLNode{//散列主文件中的節(jié)點(diǎn)類型ElemTypedata;//值域intnext;//指向下一個(gè)節(jié)點(diǎn)的指針域};其中data域用來存儲待散列的元素，next域用來存儲下一個(gè)同義詞元素在散列主文件中的存儲位置，即所在節(jié)點(diǎn)的位置號。第四十六頁，共五十六頁，編輯于2023年，星期三19模擬旅館管理系統(tǒng)中的床位的分配與回收；

問題描述：某旅館有n個(gè)等級的房間，第i等級有a個(gè)房間，每個(gè)等級有b個(gè)床位（１<=i<=n）.模擬旅館個(gè)管理系統(tǒng)中床位的分配和回收功能，設(shè)計(jì)能為單個(gè)旅客分配床位，在其離店便回收床位（供下次分配）的算法。第四十七頁，共五十六頁，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)：１．structRoom{Introomgrade;//房間等級introomprice;introomnumber;intbed[N];//每個(gè)等級i的每個(gè)房間有對應(yīng)等級i鋪床intsex;intpeoplein;intarrtime;}room[100];數(shù)據(jù)結(jié)構(gòu)的具體說明：程序中假設(shè)有N（10）個(gè)不同等級的房間，每個(gè)等級i有對應(yīng)i個(gè)房間，每個(gè)房有第i鋪床，如等級為３的房間有３個(gè)房間，每個(gè)房間有３鋪床．并且程序用靜態(tài)room[100]數(shù)組來實(shí)現(xiàn).第四十八頁，共五十六頁，編輯于2023年，星期三２．程序設(shè)計(jì)思路及其測試提示：（１）首先先創(chuàng)建旅館房間的信息，即對房間信息進(jìn)行初始化，用函數(shù)creat()來實(shí)現(xiàn)．并且創(chuàng)建的信息保存在文件里，每執(zhí)行一次服務(wù)都對文件重新寫入，保持著最近更新的數(shù)據(jù)．（２）先令t=1，滿足條件，緊接著輸入s的值，第一次輸入s的值時(shí)輸入非０的數(shù)，滿足進(jìn)行訂房服務(wù)的條件，接著進(jìn)行旅客訂房登記服務(wù)，需要注意的是本程序只適合對單個(gè)旅客進(jìn)行服務(wù)．（３）根據(jù)程序的提示，一直對輸入s的值進(jìn)行測試，如果輸入s的值為０則進(jìn)行退房服務(wù)，接著輸入t的值，如果輸入t的值非０，則可以繼續(xù)進(jìn)行服務(wù)，接下去是輸入s的值，如果輸入的s為０，則可以進(jìn)行退房服務(wù)，否則進(jìn)行訂房登記服務(wù)．（４）程序中實(shí)現(xiàn)連續(xù)多次訂房服務(wù)是利用輸入s的非０來實(shí)現(xiàn)的，如果想連續(xù)多次進(jìn)行退房服務(wù)，則在輸入t（非０）之后，輸入s的值為０，循環(huán)這種操作，即可實(shí)現(xiàn)連續(xù)多次的退房服務(wù)。第四十九頁，共五十六頁，編輯于2023年，星期三20銀行業(yè)務(wù)活動的模擬；問題描述:客戶業(yè)務(wù)分為兩種。一種是申請從銀行得到一筆資金，即取款或借款。一種是向銀行投入一筆資金，即存款或還款。銀行有兩個(gè)服務(wù)窗口，相應(yīng)地有兩個(gè)隊(duì)列。客戶到達(dá)銀行后先排第一個(gè)隊(duì)列。處理每個(gè)客戶業(yè)務(wù)時(shí)，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立刻排入第二個(gè)隊(duì)等候，直至滿足時(shí)才離開銀行；否則業(yè)務(wù)處理完后立刻離開銀行。每接待完一個(gè)第二種業(yè)務(wù)的客戶，則順序檢查和處理（如果可能）第二個(gè)隊(duì)列中的客戶，對能滿足的申請者予以滿足，不能滿足者重新排列第二個(gè)隊(duì)列的隊(duì)尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個(gè)隊(duì)列中最后一個(gè)客戶(第二種業(yè)務(wù))被接待之前的數(shù)額，或者本次已將第二個(gè)隊(duì)列檢查或處理了一遍，就停止檢查（因?yàn)榇藭r(shí)已不可能還有能滿足者）轉(zhuǎn)而繼續(xù)接待第一個(gè)對列的客戶。任何時(shí)刻都只開一個(gè)窗口，假設(shè)檢查不需要時(shí)間。營業(yè)時(shí)間結(jié)束時(shí)所有客戶立即離開銀行。寫一個(gè)上述銀行業(yè)務(wù)的模擬程序，通過模擬方法求出用戶在銀行內(nèi)逗留的平均時(shí)間。要求:利用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)模擬

第五十頁，共五十六頁，編輯于2023年，星期三21修道士野人問題；這是一個(gè)古典問題。假設(shè)有N個(gè)修道士和N個(gè)野人準(zhǔn)備渡河，但只有一天能容納C人的小船，為了防止野人吃掉修道士，要求無論在何處（即兩岸、船上），修道士的人數(shù)不得少于野人的人數(shù)（除非修道士人數(shù)為0）。如果兩種人都會劃船，試設(shè)計(jì)一個(gè)程序，確定他們能否渡過河去，若能，則給出一個(gè)小船來回次數(shù)最少的最佳方案，并打印出船來回的狀態(tài)及野人和修道士人數(shù)變化狀態(tài)。struct

INFO

{int

nSavage;//岸邊野人的數(shù)量開始為3全部到對岸為0

int

nBoanerges;//岸邊傳教士的數(shù)量開始為3全部到對岸為0

int

nSide;//船的位置在此岸為-1

彼岸為1

int

nMoveSavage;//渡河的野人的數(shù)量，用于遞歸時(shí)記錄操作狀態(tài)

int

nMoveBoanerges;//渡河的傳教士的數(shù)量，用于遞歸時(shí)記錄操作狀態(tài)

structINFO*

pPrevious;

struct

INFO*

pNext;

};

第五十一頁，共五十六頁，編輯于2023年，星期三22索引文件的插入、刪除和查找操作假定一個(gè)以ElemType為記錄類型的主文件MAINFILE.DAT存于當(dāng)前目錄中，他的索引文件IndexFile,idx也存于此目錄中。索引文件中的每個(gè)索引項(xiàng)對應(yīng)主文件中的一個(gè)記錄，每個(gè)索引項(xiàng)包含兩個(gè)域：一是索引值域，又稱關(guān)鍵字域（KEY），用來存儲對應(yīng)記錄的關(guān)鍵字；二是記錄位置域（NEXT），用來存儲對應(yīng)記