數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)級(jí)

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

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

）

第3頁，共56頁，2023年，2月20日，星期六1校園導(dǎo)游程序

問題描述：用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(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ī)動(dòng)車道和人行道。③實(shí)現(xiàn)導(dǎo)游圖的仿真界面。第4頁，共56頁，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)：typedefstructmessage{ intnum;//景點(diǎn)代碼 charname[100];//景點(diǎn)名稱 charpro[500];//簡(jiǎn)介}Ciceroni;第5頁，共56頁，2023年，2月20日，星期六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ì)測(cè)分院\n"},{8,"體育館,旁邊有籃球場(chǎng)`足球場(chǎng)`還有網(wǎng)球場(chǎng)\n"},{9,"一號(hào)教學(xué)樓，主要以階梯教室為主\n"},{10,"二號(hào)教學(xué)樓，小教室為多\n"}};/*景點(diǎn)名稱和簡(jiǎn)介*/操作：/*給景點(diǎn)之間的路徑賦最大值*//*最短路徑的C語言函數(shù)*//*輸出最短路徑和最短距離函數(shù)*//*輸入景點(diǎn)代碼查景點(diǎn)名稱和簡(jiǎn)介*//*輸入景點(diǎn)代碼查到其它景點(diǎn)的最短距離*/第6頁，共56頁，2023年，2月20日，星期六2員工管理系統(tǒng)問題描述：每個(gè)員工的信息包括：編號(hào)、姓名、性別、出生年月、學(xué)歷、職務(wù)、電話、住址等。系統(tǒng)能夠完成員工信息的查詢、更新、插入、刪除、排序等功能?；疽螅号判颍喊床煌P(guān)鍵字，對(duì)所有員工的信息進(jìn)行排序；查詢：按特定條件查找員工；更新：按編號(hào)對(duì)某個(gè)員工的某項(xiàng)信息進(jìn)行修改；插入：加入新員工的信息；刪除：按編號(hào)刪除已離職的員工的信息。選作內(nèi)容：實(shí)現(xiàn)圖形用戶界面。第7頁，共56頁，2023年，2月20日，星期六要求通過鏈表實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：structworkers{ charname[15];//姓名chardepartment[18];//單位chargender;//性別unsignedintage;//年齡unsignedlongtelephone;//電話unsignedlongwage;//工資unsignedlongnum;//職工號(hào)structworkers*next;};第8頁，共56頁，2023年，2月20日，星期六操作實(shí)現(xiàn)：/*插入職工信息，通過鏈表實(shí)現(xiàn)*//*具體實(shí)現(xiàn)職工信息的插入*//*對(duì)職工信息的刪除操作*//*修改操作*//*實(shí)現(xiàn)對(duì)員工信息的查找*//*排序*//*輸出員工信息*//*顯示職工工資情況計(jì)算平均工資*/第9頁，共56頁，2023年，2月20日，星期六3算術(shù)表達(dá)式求值問題描述：一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值?；疽螅簭逆I盤讀入一個(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ù)。第10頁，共56頁，2023年，2月20日，星期六4運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)

任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1，…，n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子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)目的前三名或前五名的成績(jī)；能統(tǒng)計(jì)各學(xué)?？偡郑豢梢园磳W(xué)校編號(hào)、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。第11頁，共56頁，2023年，2月20日，星期六規(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ì)，請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)。第12頁，共56頁，2023年，2月20日，星期六參考的數(shù)據(jù)結(jié)構(gòu)：（1）項(xiàng)目信息表結(jié)構(gòu)typedefstructxm_table{intitem;//項(xiàng)目編號(hào)charname[20];//項(xiàng)目名稱intcount;

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

//姓名intscore;

//得分成績(jī)intrange;

//得分名次intitem;

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

//性別};第13頁，共56頁，2023年，2月20日，星期六（3）參賽學(xué)校信息結(jié)構(gòu)//參賽學(xué)校typedefstructSchoolStruct

{intcount;

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

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

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

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

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

//學(xué)校積分struct

STUDENTstudents[10];

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

//下一個(gè)參賽學(xué)校}SCHOOLSTRUCT;第14頁，共56頁，2023年，2月20日，星期六操作需求：//建立參賽學(xué)校鏈表//添加獲獎(jiǎng)學(xué)生//成績(jī)統(tǒng)計(jì)//按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。//按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目//在屏幕輸出數(shù)據(jù)//參數(shù)設(shè)置（設(shè)置參賽學(xué)校數(shù)n>=2，請(qǐng)輸男生項(xiàng)目總數(shù)<m<=20，請(qǐng)輸女生項(xiàng)目總數(shù)<k<=20）//項(xiàng)目資料:請(qǐng)輸入男生項(xiàng)目信息：項(xiàng)目名稱;項(xiàng)目編號(hào);該項(xiàng)目的參與人數(shù)請(qǐng)輸入女生項(xiàng)目信息：項(xiàng)目名稱;項(xiàng)目編號(hào);該項(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)目查詢";等功能。第15頁，共56頁，2023年，2月20日，星期六5一元多項(xiàng)式計(jì)算任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相乘，并將結(jié)果輸出；在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）、源程序、測(cè)試數(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

請(qǐng)實(shí)現(xiàn)求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。第16頁，共56頁，2023年，2月20日，星期六要求：1)

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

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

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

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

任務(wù)：編號(hào)是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)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。測(cè)試數(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ù)，將正確的輸出序列第26頁，共56頁，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)：typedefstructNode{ intdata; intpassword; structNode*next;}Node,*LinkList;基本操作：//初始化單鏈表//給每個(gè)人賦密碼//確定需要處理的人數(shù)//確定開始的上限值//得到正確的順序//輸出結(jié)果第27頁，共56頁，2023年，2月20日，星期六11建立二叉樹，已知二叉樹的層次序列、先序遍歷（用遞歸或非遞歸的方法都可以）

任務(wù)：

要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；第28頁，共56頁，2023年，2月20日，星期六12哈夫曼編/譯碼器任務(wù)：建立最優(yōu)二叉樹函數(shù)要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；第29頁，共56頁，2023年，2月20日，星期六利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。第30頁，共56頁，2023年，2月20日，星期六[基本要求]一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件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中。第31頁，共56頁，2023年，2月20日，星期六[測(cè)試數(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第32頁，共56頁，2023年，2月20日，星期六13拓?fù)渑判?/p>

任務(wù)：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判?。?3頁，共56頁，2023年，2月20日，星期六14學(xué)生成績(jī)管理

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

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

（1）信息輸入（INPUT）

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

（3）總分排序（SORT）

（4）查詢(QUERY）

其中：

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

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

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

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

功能要求：1.從鍵盤輸入一組關(guān)鍵字插入B_樹中；2.向B_樹中插入一個(gè)關(guān)鍵字；3.從B_樹中刪除一個(gè)關(guān)鍵字；4.從B_樹中查找一個(gè)關(guān)鍵字對(duì)應(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)；第42頁，共56頁，2023年，2月20日，星期六//定義B_樹的階數(shù)和特定的最大關(guān)鍵字，可自行設(shè)定#definem3#defineMAXKEY9999//定義關(guān)鍵字類型為整型typedefintKeyType;//定義元素類型structElemType{KeyTypekey;//整型關(guān)鍵字域charrest[10]；//字符數(shù)組域};第43頁，共56頁，2023年，2月20日，星期六//定義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)鍵字對(duì)應(yīng)記錄的存儲(chǔ)位置域，下標(biāo)0位置未用};

第44頁，共56頁，2023年，2月20日，星期六18[散列文件的插入、刪除和查找]

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

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

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

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

INFO

{int

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

int

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

int

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

彼岸為1

int

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

int

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

structINFO*

pPrevious;

struct

INFO*

pNext;

};

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