【正文】 年7月執(zhí) 筆：劉科峰、李小英、高學(xué)軍課程性質(zhì)：設(shè)計(jì)（論文）/必修 開課學(xué)期：5 總學(xué)分?jǐn)?shù)：1 修訂年月：2007年7月一、課程設(shè)計(jì)的性質(zhì)和目的《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是本學(xué)院本科專業(yè)的集中實(shí)踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進(jìn)行的一次全面的綜合應(yīng)用練習(xí)。課程設(shè)計(jì)成績：上機(jī)情況（20%）包括出勤情況、調(diào)試表現(xiàn)。（二）主要先修課程和后續(xù)課程 ：《C語言程序設(shè)計(jì)》 ：《計(jì)算機(jī)組成原理》、《操作系統(tǒng)》、《數(shù)據(jù)庫系統(tǒng)原理》二、課程設(shè)計(jì)目的及基本要求《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性強(qiáng)的課程，其中對算法設(shè)計(jì)和程序編寫的掌握尤為重要。根據(jù)哈夫曼樹的原理求n個(gè)自然數(shù)相加減后結(jié)果最小（中間結(jié)果、最后結(jié)果不能負(fù)）。要求：1）先生成一個(gè)帶權(quán)的有向圖，并打印輸出； 2）用函數(shù)形式完成狄杰斯特算法；3）打印輸出最后的該頂點(diǎn)到其它頂點(diǎn)的路徑，并打印最短路徑。要求：1）建立一個(gè)AOE圖，并輸出結(jié)果確保創(chuàng)建成功；2）判斷AOE圖是一個(gè)拓?fù)溆行蛐蛄校绻皇峭負(fù)溆行騽t報(bào)錯(cuò)； 3）編寫函數(shù)求AOE圖的關(guān)鍵路徑； 4）打印輸出關(guān)鍵路徑；5）每一個(gè)函數(shù)要有必要的注釋，在課程設(shè)計(jì)論文中有流程圖。五、課程設(shè)計(jì)考核方法及成績評定程序清單：代碼應(yīng)具有詳細(xì)注釋，用來說明程序的功能、結(jié)構(gòu)；設(shè)計(jì)報(bào)告：報(bào)告中應(yīng)包含上機(jī)時(shí)遇到的問題及解決辦法，觀察到的現(xiàn)象及其分析，對程序設(shè)計(jì)技巧的總結(jié)及分析等；程序的輸出結(jié)果及對結(jié)果的分析；實(shí)驗(yàn)的心得體會，以及其它信息；提交時(shí)，須向指導(dǎo)教師說明：程序的使用方法，調(diào)用方法、操作步驟等；要求輸入信息的類型及格式；出錯(cuò)信息的含義及程序的適用范圍等。對有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天至少要上34小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的成成，總共至少要上機(jī)調(diào)試程序30小時(shí)。*存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。*輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；joseph環(huán)*問題描述：編號是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。輸出：這時(shí)正面向上的牌有哪些？1圖的建立及輸出*問題描述：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。任何整形變量的范圍是(2^151)。*實(shí)現(xiàn)提示：（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768 5 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，?，64依次填入個(gè)8 8的方陣，輸出之。*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)。此外，因受圖形界面限制，不能保存或載入測試文件（此功能可在Maze_text中實(shí)現(xiàn)）。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識別處理，以及相應(yīng)的運(yùn)算。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對于所要求作的運(yùn)算是否匹配。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。如果程序不能正常運(yùn)行，寫出實(shí)現(xiàn)此算法中遇到的問題，和改進(jìn)方法。為保證質(zhì)量，需要每個(gè)學(xué)生將每天的上機(jī)調(diào)試程序的時(shí)間記錄下來，作為評判成績的標(biāo)準(zhǔn)之一。（3）實(shí)現(xiàn)導(dǎo)游圖的仿真界面。引入變量操作數(shù)。[實(shí)現(xiàn)提示]設(shè)小說中的詞匯一律不跨行。利用單詞匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。在初始和結(jié)束時(shí)，棧應(yīng)該是空的。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時(shí)刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。[問題描述]文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對文本文件的插入、刪除等修改操作。格式：i將插入活區(qū)中第行之后（2）行刪除。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。此外，還應(yīng)記住活區(qū)起始行號。（5）可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示。注意測試邊界數(shù)據(jù)，如單個(gè)結(jié)點(diǎn)。*輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。4）本程序只求出一條成功的通路，但若對求解函數(shù)MazePath稍加更改即可求得全部路徑。*實(shí)現(xiàn)提示：（1）設(shè)置運(yùn)算棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。*基本要求：（1）每種書的登記內(nèi)容至少包括書號、書名、作者、現(xiàn)存量和總庫存量等五4。⑤顯示：以凹入表的形式顯示B樹。其中序列1和序列2 中都不含字符‘a(chǎn)mp。為了學(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í)際問題的能力。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。訂票系統(tǒng)（1）問題描述通過此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個(gè)航線的情況（如，輸入航班號，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。（5）輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問題描述：建立二叉樹，并實(shí)行層序、先序遍歷等算法（2）要求：能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立（1）問題描述：建立建立最優(yōu)二叉樹函數(shù)（2）要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；圖的建立及輸出（1）問題描述：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型）（2）要求：能夠輸入圖的頂點(diǎn)和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。任何整形變量的范圍是(2^151)。*實(shí)現(xiàn)提示：（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬進(jìn)制。（2）基本要求：以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)表達(dá)式?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。課程設(shè)計(jì)成績?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù)，無大的違紀(jì)違規(guī)現(xiàn)象；撰寫了實(shí)習(xí)報(bào)告。④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過失。工作認(rèn)真，積極 主動，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。注意研究教科書中的算法，以便提高計(jì)算效率。16．稀疏矩陣運(yùn)算器*問題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。用其絕對值表示元素結(jié)點(diǎn)數(shù)目。*測試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。（2）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點(diǎn)各種排序（1）問題描述：對30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。joseph環(huán)（1）問題描述編號是1，2，??,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。4．答辯：課題的論述、測試及問題回答三、課程設(shè)計(jì)內(nèi)容背包問題的求解：假設(shè)有一個(gè)能裝入總體積為T的背包和n件體積分別為w1 , w2 , … , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。給出實(shí)現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來。例如，‘a(chǎn)+bamp。下列B樹的打印格式如下所示：1文章編輯*問題描述：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。但是由于上述四項(xiàng)基本業(yè)務(wù)活動都是通過書號（即關(guān)鍵字）進(jìn)行的，所以要用B樹對書號盡力索引，以獲得高效率?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20。（3）在識別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式。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。1線性表的操作*問題描述：利作鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。通過輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對，可以對邊的輸入順序作出某種限制。（2）加入更復(fù)雜的編輯操作，如對某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S和m。（2）初始化過程包括：請用戶提供輸入文件名（空串表示無輸入文件）和輸出文件名，兩者不能相同。[實(shí)現(xiàn)提示]（1）設(shè)活區(qū)的大小用行數(shù)activemaxlen（可設(shè)為100）來描述。兩種格式的例子是：“d10↙”和“d10□14↙”（3）活區(qū)切換。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的做法既不經(jīng)濟(jì)，也不總能實(shí)現(xiàn)。[實(shí)現(xiàn)提示]需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。[問題描述]設(shè)停車場內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；[實(shí)現(xiàn)提示]可以用一個(gè)二維數(shù)組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。出現(xiàn)位置所在行的