【正文】 要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。要求：1）先生成一個(gè)帶權(quán)的有向圖，并打印輸出； 2）用函數(shù)形式完成佛洛依德算法； 3）打印輸出每對(duì)頂點(diǎn)的最短路徑。分塊查找問(wèn)題描述：采用分塊查找的方法查找指定的關(guān)鍵碼。關(guān)鍵路徑問(wèn)題描述：建立AOE圖，確定其拓?fù)溆行蚝笄箨P(guān)鍵路徑。二叉排序樹(shù)問(wèn)題描述：完成二叉排序樹(shù)的創(chuàng)建、查找、插入和刪除操作。1B樹(shù)問(wèn)題描述：完成B樹(shù)的創(chuàng)建、查找、插入和刪除。1哈希表查找問(wèn)題描述：定義一個(gè)哈希表和對(duì)哈希表進(jìn)行插入、查找和刪除、打印。四、指導(dǎo)方式集體輔導(dǎo)與個(gè)別輔導(dǎo)相結(jié)合。成績(jī)?cè)u(píng)定：課程設(shè)計(jì)成績(jī)分兩部分，設(shè)計(jì)報(bào)告占40％，設(shè)計(jì)作品占60％。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。二、設(shè)計(jì)要點(diǎn)1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化。給出實(shí)現(xiàn)功能的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出來(lái)。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問(wèn)題，和改進(jìn)方法。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。三．設(shè)計(jì)要求學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來(lái)，作為評(píng)判成績(jī)的標(biāo)準(zhǔn)之一。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：1，前三名的積分分別為：2；哪些取前五名或前三名由學(xué)生自己設(shè)定。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書(shū)上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用全部合法數(shù)據(jù)；整體非法數(shù)據(jù)；局部非法數(shù)據(jù)。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；一元多項(xiàng)式計(jì)算*問(wèn)題描述：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式； 能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入；在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過(guò)程的算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；訂票系統(tǒng)*問(wèn)題描述：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉(cāng)）； 可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班； 4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行。*存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。*測(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)鏈表。*輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n建立二叉樹(shù)，層序、先序遍歷（用遞歸或非遞歸的方法都可以）*問(wèn)題描述：要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹(shù)的建立*問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù)*要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；紙牌游戲*問(wèn)題描述：編號(hào)為152張牌，正面向上，從第2張開(kāi)始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開(kāi)始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開(kāi)始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過(guò)。1拓?fù)渑判?問(wèn)題描述：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉?輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。1線性表的操作*問(wèn)題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。（2）2345,6789；7654,3211；應(yīng)輸出“1,0000,0000”。（5）1,0001,0001；1,0001,0000；應(yīng)輸出“1”。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。*測(cè)試數(shù)據(jù)：由讀者指定,可自行指定一個(gè)馬的初始位置。1校園導(dǎo)游咨詢 *問(wèn)題描述：（1）設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。（2）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。*測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。頂點(diǎn)和邊均含有相關(guān)信息。*問(wèn)題描述：1）輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上。Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9 鍵演示，Esc鍵退出。4）本程序只求出一條成功的通路，但若對(duì)求解函數(shù)MazePath稍加更改即可求得全部路徑。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ì)算器*問(wèn)題描述：一元多項(xiàng)式簡(jiǎn)單計(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。21．算術(shù)表達(dá)式求值演示*問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。*基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。（3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。22．稀疏矩陣運(yùn)算器*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。注意研究教科書(shū)中的算法，以便提高計(jì)算效率。23．圖書(shū)管理*問(wèn)題描述：圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。*基本要求：（1）每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、作者、現(xiàn)存量和總庫(kù)存量等五4。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用B樹(shù)對(duì)書(shū)號(hào)盡力索引，以獲得高效率。如果這種書(shū)在帳目中已有，則只將總庫(kù)存量增加。③某種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。⑤顯示：以凹入表的形式顯示B樹(shù)。下列B樹(shù)的打印格式如下所示：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ù)據(jù)結(jié)構(gòu)上的算法，通過(guò)上機(jī)調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)，同時(shí)提高解決計(jì)算機(jī)應(yīng)用實(shí)際問(wèn)題的能力。① 需求分析將題目中要求的功能進(jìn)行敘述分析，并且設(shè)計(jì)解決此問(wèn)題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），設(shè)計(jì)或敘述解決此問(wèn)題的算法，描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度。對(duì)有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。②源程序（可以是一組源程序，即詳細(xì)設(shè)計(jì)部分）源程序要按照寫程序的規(guī)則來(lái)編寫。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫格式① 設(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)》課程開(kāi)課學(xué)期布置題目，然后在期末前兩周完成。課程設(shè)計(jì)按照教學(xué)要求需要1周時(shí)間完成，1周中每天至少要上68小時(shí)的機(jī)來(lái)調(diào)試C語(yǔ)言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。四．設(shè)計(jì)題目校園導(dǎo)游程序[問(wèn)題描述]用無(wú)向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。[基本要求]（1）查詢各景點(diǎn)的相關(guān)信息；（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（4）增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。（2）區(qū)分機(jī)動(dòng)車道和人行道。算術(shù)表達(dá)式求值[問(wèn)題描述]一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。引入表達(dá)式起始、結(jié)束符是為了方便。[基本要求]（1）從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。[選作內(nèi)容]擴(kuò)充運(yùn)算符集合。操作數(shù)類型擴(kuò)充到實(shí)數(shù)。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。[測(cè)試數(shù)據(jù)]以你的源程序模擬英文小說(shuō)，程序語(yǔ)言保留字集作為待統(tǒng)計(jì)的詞匯集。這樣，每讀入一行，就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。若某行中出現(xiàn)了不止一次，不必存多個(gè)相同的行號(hào)。[選作內(nèi)容]（1）模式匹配要基于KMP算法。（3）假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始，或者前置以一個(gè)空格符。（4）推廣到更一般的模式集匹配問(wèn)題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）[問(wèn)題描述]可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；[基本要求]含有兩個(gè)以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實(shí)現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。[問(wèn)題描述]假設(shè)表達(dá)式中允許有兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。例如：考慮下列的括號(hào)序列：[([ ] [ ])]8當(dāng)計(jì)算機(jī)接受了第1個(gè)括號(hào)以后，他期待著與其匹配的第8個(gè)括號(hào)的