【文章內(nèi)容簡介】 設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9 鍵演示，Esc鍵退出。3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。4）本程序只求出一條成功的通路，但若對求解函數(shù)MazePath稍加更改即可求得全部路徑。此外，因受圖形界面限制，不能保存或載入測試文件（此功能可在Maze_text中實(shí)現(xiàn)）。5）當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“Error： You must set Startplace.”；未輸入終點(diǎn)時(shí)，顯示“Error： You must set Endplace.” 找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)Path found，否則消去足跡，顯示Path not ．一元稀疏多項(xiàng)式計(jì)算器*問題描述：一元多項(xiàng)式簡單計(jì)算器的基本功能是：（1）輸入并建立多項(xiàng)式；（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,?,en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei分別是第I項(xiàng)的系數(shù)和指數(shù)，序列指指數(shù)降序排列；（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；（4）多項(xiàng)式a和b相減，建立多項(xiàng)式ab。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。21．算術(shù)表達(dá)式求值演示*問題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。*基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例31演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識別處理，以及相應(yīng)的運(yùn)算。（3）在識別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。22．稀疏矩陣運(yùn)算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲和計(jì)算可以大大節(jié)省存儲空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對于所要求作的運(yùn)算是否匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過20。（2）程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。23．圖書管理*問題描述：圖書管理基本業(yè)務(wù)活動(dòng)包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。*基本要求：（1）每種書的登記內(nèi)容至少包括書號、書名、作者、現(xiàn)存量和總庫存量等五4。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過書號（即關(guān)鍵字）進(jìn)行的，所以要用B樹對書號盡力索引，以獲得高效率。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫：新購入一種書，經(jīng)分類和確定書號后登記到圖書帳目中去。如果這種書在帳目中已有，則只將總庫存量增加。②清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。③某種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。④歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。⑤顯示：以凹入表的形式顯示B樹。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。下列B樹的打印格式如下所示：50，52 70，728第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》教學(xué)大綱Data Structure Course Design一、課程的性質(zhì)、教學(xué)目的和要求《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)軟件的一門基礎(chǔ)課程，計(jì)算機(jī)科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實(shí)際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問題的能力。二、設(shè)計(jì)要點(diǎn)1．設(shè)計(jì)和調(diào)試過程要規(guī)范化。① 需求分析將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。給出實(shí)現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來。對有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書寫格式① 設(shè)計(jì)題目（任選其一）②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式可設(shè)23人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開課學(xué)期布置題目，然后在期末前兩周完成。三．設(shè)計(jì)要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上68小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來，作為評判成績的標(biāo)準(zhǔn)之一。四．設(shè)計(jì)題目校園導(dǎo)游程序[問題描述]用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。[基本要求]（1）查詢各景點(diǎn)的相關(guān)信息；（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（3）查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。[選作內(nèi)容]（1）求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。（2）區(qū)分機(jī)動(dòng)車道和人行道。（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。算術(shù)表達(dá)式求值[問題描述]一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“”，如：（7+15）*（2328/4）。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。[基本要求]（1）從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2）顯示輸入序列和棧的變化過程。[選作內(nèi)容]擴(kuò)充運(yùn)算符集合。引入變量操作數(shù)。操作數(shù)類型擴(kuò)充到實(shí)數(shù)。文學(xué)研究助手[問題描述]文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。[基本要求]英文小說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設(shè)計(jì)。[測試數(shù)據(jù)]以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計(jì)的詞匯集。[實(shí)現(xiàn)提示]設(shè)小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號可以用鏈表存儲。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號。如果讀者希望達(dá)到選作部分（1）和（2）所提出的要求，則首先應(yīng)把KMP算法改寫成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。[選作內(nèi)容]（1）模式匹配要基于KMP算法。（2）整個(gè)統(tǒng)計(jì)過程中只對小說文字掃描一遍以提高效率。（3）假設(shè)小說中的每個(gè)單詞或者從行首開始，或者前置以一個(gè)空格符。利用單詞匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。（4）推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）[問題描述]可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；[基本要求]含有兩個(gè)以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；[實(shí)現(xiàn)提示]可以用一個(gè)二維數(shù)組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。[問題描述]假設(shè)表達(dá)式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗(yàn)括號是否匹配的方法可用“期待的緊迫程度”這個(gè)概念來描述。例如：考慮下列的括號序列：[([ ] [ ])]8當(dāng)計(jì)算機(jī)接受了第1個(gè)括號以后，他期待著與其匹配的第8個(gè)括號的出現(xiàn)，然而等來的卻是第2個(gè)括號，此時(shí)第1個(gè)括號“[”只能暫時(shí)靠邊，而迫切等待與第2個(gè)括號相匹配的 第7個(gè)括號“）”的出現(xiàn)，類似的，因只等來了第3個(gè)括號“[”，此時(shí)，其期待的緊迫程度較第2個(gè)括號更緊迫，則第2個(gè)括號只能靠邊，讓位于第3個(gè)括號，顯然第3個(gè)括號的期待緊迫程度高于第2個(gè)括號，而第2個(gè)括號的期待緊迫程度高于第1個(gè)括號；在接受了第4個(gè)括號之后，第3個(gè)括號的期待得到了滿足，消解之后，第2個(gè)括號的期待匹配就成了最急迫的任務(wù)了，??，依次類推?？梢娺@個(gè)處理過程正好和棧的特點(diǎn)相吻合。[基本要求]設(shè)置一個(gè)棧，每讀入一個(gè)括號，若是左括號，則作為一個(gè)新的更急迫的期待壓入棧中，若是右括號，則或者是和當(dāng)前棧頂?shù)睦ㄌ栂嗥ヅ?，或者是不合法的情況，輸出“此串括號匹配不合法”。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。[測試數(shù)據(jù)]輸入 （[ ]（）），結(jié)果“匹配”輸入 [（）]，結(jié)果“此串括號匹配不合法”為起始和結(jié)束標(biāo)志。[問題描述]設(shè)停車場內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。[測試數(shù)據(jù)]設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時(shí)刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。[基本要求]以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時(shí)刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在