【正文】 關(guān)數(shù)據(jù)文件可供演示檢查外，應(yīng)強調(diào)文檔的分量、完善性和規(guī)范性要求，文檔應(yīng)有相當?shù)恼挤直壤Ｐ率兰o需要具有豐富科學(xué)知識、獨立解決實際問題、有創(chuàng)造能力的新型人才，這也是該課程設(shè)計的最終目的。普里姆算法求最小生成樹問題描述：用普里姆算法求有向網(wǎng)圖或無向網(wǎng)圖的最小生成樹。要求：1）先生成一個帶權(quán)的有向圖，并打印輸出； 2）用函數(shù)形式完成佛洛依德算法； 3）打印輸出每對頂點的最短路徑。1B樹問題描述：完成B樹的創(chuàng)建、查找、插入和刪除。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。比賽分成m個男子項目，和w個女子項目。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；一元多項式計算*問題描述：能夠按照指數(shù)降序排列建立并輸出多項式； 能夠完成兩個多項式的相加、相減，并將結(jié)果輸入；在上交資料中請寫明：存儲結(jié)構(gòu)、多項式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改進方法；訂票系統(tǒng)*問題描述：通過此系統(tǒng)可以實現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達城市，查詢飛機航班情況；3）訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班； 4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。設(shè)計一個程序來求出出列順序。*輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。（2）2345,6789；7654,3211；應(yīng)輸出“1,0000,0000”。相加過程中不要破壞兩個操作數(shù)鏈表。1校園導(dǎo)游咨詢 *問題描述：（1）設(shè)計你的學(xué)校的校園平面圖，所含景點不少于10個。*問題描述：1）輸入一個任意大小的迷宮，任設(shè)起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。21．算術(shù)表達式求值演示*問題描述：表達式求值是實現(xiàn)程序設(shè)計語言的基本問題之一，也是棧的應(yīng)用的一個典型例子。22．稀疏矩陣運算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。注意研究教科書中的算法，以便提高計算效率。如果這種書在帳目中已有，則只將總庫存量增加。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點，同時提高解決計算機應(yīng)用實際問題的能力。程序能夠運行，要有基本的容錯功能。[基本要求]（1）查詢各景點的相關(guān)信息；（2）查詢圖中任意兩個景點間的最短路徑。引入表達式起始、結(jié)束符是為了方便。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學(xué)研究助手”。若某行中出現(xiàn)了不止一次，不必存多個相同的行號。[問題描述]假設(shè)表達式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。輸入數(shù)據(jù)按到達或離去的時刻有序。一種解決方法是逐段地編輯。格式：n將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)?？紤]到文本文件行長通常為正態(tài)分布，且峰值在60到70之間，用320activemaxlen大小的字符數(shù)組實現(xiàn)存儲將造成大量浪費。然后盡可能多地從輸入文件中讀入各行，但不超過activemaxlenx。[問題描述]很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。注意，生成樹的邊是有向邊，端點順序不能顛倒。1編制一個求解迷宮通路的圖形界面演示程序。*實現(xiàn)提示：用帶頭結(jié)點的單鏈表存儲多項式，多項式的項數(shù)存在頭結(jié)點。*選作內(nèi)容：（1）擴充運算符集，如增加乘方、單目減、賦值等運算；（2）運算量可以是變量；（3）運算量可以是實數(shù)類型；（4）計數(shù)器的功能和仿鎮(zhèn)界面。（2）程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。（3）系統(tǒng)應(yīng)實現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號后登記到圖書帳目中去。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行。b+a’是屬該模式的字符序列，而‘１+３amp。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。例如：當T=10，各件物品的體積{1，8，4，3，5，2}時，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。（2）要求：輸入的數(shù)據(jù)形式為任何一個正整數(shù)，大小不限。（2）2345,6789；7654,3211；應(yīng)輸出“1,0000,0000”。相加過程中不要破壞兩個操作數(shù)鏈表。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。（3）在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。撰寫了高質(zhì)量的總結(jié)報告?；驘o實習(xí)報告，沒有通過答辯。答辯較準確流利。六、成績考核與評定學(xué)生課程設(shè)計結(jié)束后寫出總結(jié)報告，對設(shè)計的內(nèi)容和效果進行總結(jié)，按照學(xué)生在設(shè)計期間的表現(xiàn)，指導(dǎo)老師對每位學(xué)生寫出評語和鑒定，系課程設(shè)計領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計成績，課程設(shè)計成績分為優(yōu)、良、中、及格和不及格五個等級。*實現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否匹配。設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達式求值的過程。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。*基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整形變量。（3）測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？（4）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個人的密碼，建立單循環(huán)鏈表。由于回溯求解的規(guī)則規(guī)則是“后進先出”因此自然要用到棧。程序能夠運行，要有基本的容錯功能。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。 序列2’模式的字符序列。④歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。試設(shè)計一個圖書管理系統(tǒng)，將上述業(yè)務(wù)活動借助于計算機系統(tǒng)完成。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實現(xiàn)兩個矩陣相加、相減和相乘的運算。利用教材中給出的算符優(yōu)先關(guān)系，實現(xiàn)對算術(shù)四則混合運算表達式的求值，并仿照教材例31演示在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。3）橙色的實心小圓圈表示起點，綠色實心圓圈表示終點，空心圓圈表示足跡，紅色方塊表示墻。1各種排序*問題描述：對30000個隨機整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進行排序，并統(tǒng)計每一種排序上機所花費的時間。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開始編輯另一個文件。行尾可用一個特殊的ASCII字符（如(012)8）標識。各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數(shù)非法。[基本要求]實現(xiàn)以下4條基本編輯命令：（1）行插入。（4）停放在便道上的汽車也收費，收費標準比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。[基本要求]以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。[基本要求]設(shè)置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中，若是右括號，則或者是和當前棧頂?shù)睦ㄌ栂嗥ヅ?，或者是不合法的情況，輸出“此串括號匹配不合法”。（3）假設(shè)小說中的每個單詞或者從行首開始，或者前置以一個空格符。[測試數(shù)據(jù)]以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。[選作內(nèi)容]擴充運算符集合。（2）區(qū)分機動車道和人行道。課程設(shè)計按照教學(xué)要求需要1周時間完成，1周中每天至少要上68小時的機來調(diào)試C語言設(shè)計的程序，總共至少要上機調(diào)試程序30小時。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。⑤顯示：以凹入表的形式顯示B樹。*基本要求：（1）每種書的登記內(nèi)容至少包括書號、書名、作者、現(xiàn)存量和總庫存量等五4。稀疏矩陣的輸入形式采用三元組表示，而運算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。*實現(xiàn)提示：（1）設(shè)置運算棧和運算數(shù)棧輔助分析算符優(yōu)先關(guān)系。4）本程序只求出一條成功的通路，但若對求解函數(shù)MazePath稍加更改即可求得全部路徑。*測試數(shù)據(jù)：由讀者根據(jù)實際情況指定。要求每個方格上只進入一次，走遍棋盤上全部64個方格。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。*基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整形變量。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問題描述：要求能夠輸入樹的各個結(jié)點，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立*問題描述：建立建立最優(yōu)二叉樹函數(shù)*要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改進方法；紙牌游戲*問題描述：編號為152張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過。*存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運動項目的名稱）輸出形式：有中文提示，各學(xué)校分數(shù)為整形界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。三．設(shè)計要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課設(shè)的時間計劃，并在課設(shè)過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進行測試的結(jié)果列出來。四、指導(dǎo)方式集體輔導(dǎo)與個別輔導(dǎo)相結(jié)合。關(guān)鍵路徑問題描述：建立AOE圖，確定其拓撲有序后求關(guān)鍵路徑。狄杰斯特算法求最短路徑問題描述：采用狄杰斯特算法求一個頂點到其它頂點的最短路徑。要求：1）各功能模塊必須是單獨的函數(shù)； 2）線索二叉樹是動態(tài)生存的； 3）輸入數(shù)據(jù)進行必要的合法性檢查；4）執(zhí)行每一個功能后，按二叉樹廣義表的表達方式打印輸出，檢查結(jié)果是否正確； 5）每一個函數(shù)要有必要的注釋，在課程設(shè)計論文中有流程圖。（一）課程設(shè)計性質(zhì)