【正文】 交納費(fèi)用。[測(cè)試數(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）。[基本要求]以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。[選作內(nèi)容]（1）兩個(gè)棧共享空間，思考應(yīng)開(kāi)辟數(shù)組的空間是多少？（2）汽車(chē)可有不同種類(lèi)，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，1輛十輪卡車(chē)占地面積相當(dāng)于3輛小汽車(chē)的占地面積。（4）停放在便道上的汽車(chē)也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車(chē)場(chǎng)的車(chē)低，請(qǐng)思考如何修改結(jié)構(gòu)以滿(mǎn)足這種要求。限制這些操作以行為單位進(jìn)行的編輯程序稱(chēng)為行編輯程序。一種解決方法是逐段地編輯。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。[基本要求]實(shí)現(xiàn)以下4條基本編輯命令：（1）行插入。格式：d[□]刪除活區(qū)中第行（到第行）。格式：n將活區(qū)寫(xiě)入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。格式：p逐頁(yè)地（每頁(yè)20行）顯示活區(qū)內(nèi)容，每顯示一頁(yè)之后請(qǐng)用戶(hù)決定是否繼續(xù)顯示以后各頁(yè)（如果存在）。各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。注意測(cè)試邊界數(shù)據(jù)，如首行、尾行?？紤]到文本文件行長(zhǎng)通常為正態(tài)分布，且峰值在60到70之間，用320activemaxlen大小的字符數(shù)組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)。這些行塊可以組成一個(gè)數(shù)組，也可以利用動(dòng)態(tài) 8 鏈表連接起來(lái)。行尾可用一個(gè)特殊的ASCII字符（如(012)8）標(biāo)識(shí)。行插入將引起隨后各行行號(hào)的順序下推。然后盡可能多地從輸入文件中讀入各行，但不超過(guò)activemaxlenx。（3）在執(zhí)行行插入命令的過(guò)程中，每接收到一行時(shí)到要檢查活區(qū)大小是否已達(dá)activemaxlen。（4）若輸入文件尚未讀完，活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部，以保持閱讀連續(xù)性；否則，它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。[選作內(nèi)容]（1）對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。[問(wèn)題描述]很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。[基本要求]以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。[實(shí)現(xiàn)提示]設(shè)圖的結(jié)點(diǎn)不超過(guò)30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1,2,?,n）。注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒。（2）以鄰接多重表為存儲(chǔ)結(jié)構(gòu)建立深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)，再按凹入表或樹(shù)形打印生成樹(shù)（3）實(shí)現(xiàn)有向圖的遍歷操作。1各種排序*問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。*輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列?1圖的遍歷*問(wèn)題描述：對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。1編制一個(gè)求解迷宮通路的圖形界面演示程序。2）根據(jù)用戶(hù)界面提示，用鍵盤(pán)輸入。3）橙色的實(shí)心小圓圈表示起點(diǎn)，綠色實(shí)心圓圈表示終點(diǎn)，空心圓圈表示足跡，紅色方塊表示墻。此外，因受圖形界面限制，不能保存或載入測(cè)試文件（此功能可在Maze_text中實(shí)現(xiàn)）。*實(shí)現(xiàn)提示：用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式，多項(xiàng)式的項(xiàng)數(shù)存在頭結(jié)點(diǎn)。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例31演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。（2）在輸入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。*選作內(nèi)容：（1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算；（2）運(yùn)算量可以是變量；（3）運(yùn)算量可以是實(shí)數(shù)類(lèi)型；（4）計(jì)數(shù)器的功能和仿鎮(zhèn)界面。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。（3）在用三元組表示稀 疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。（3）系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及功能定義如下：①采編入庫(kù)：新購(gòu)入一種書(shū)，經(jīng)分類(lèi)和確定書(shū)號(hào)后登記到圖書(shū)帳目中去。②清除庫(kù)存：某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)帳目中注銷(xiāo)。④歸還：注銷(xiāo)對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行。*存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；*輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。 序列2’模式的字符序列?！?，且序列2 是序列1的逆序列。b+a’是屬該模式的字符序列，而‘１+３amp。[實(shí)現(xiàn)提示]首先，序列1進(jìn)棧，然后序列1出棧并與序列2比較。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)掌握實(shí)際編程能力是很有幫助的。二、教學(xué)基本要求1．設(shè)計(jì)和調(diào)試過(guò)程要規(guī)范化需求分析：將題目中要求的功能進(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ì)部分）源程序要按照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。2．課程設(shè)計(jì)實(shí)習(xí)報(bào)告的書(shū)寫(xiě)格式① 設(shè)計(jì)題目數(shù)據(jù)結(jié)構(gòu) 408104 計(jì)算機(jī)科學(xué)與技術(shù) 72 30 2012．6436104 軟件工程審 核 人：②運(yùn)行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計(jì)的思想 ④算法的流程圖 ⑤算法設(shè)計(jì)分析 ⑥源代碼 ⑦運(yùn)行結(jié)果分析 ⑧收獲及體會(huì) 3．實(shí)施方式可設(shè)34人一題，安排在《數(shù)據(jù)結(jié)構(gòu)》課程開(kāi)課學(xué)期布置題目，然后在期末兩周時(shí)間內(nèi)完成。例如：當(dāng)T=10，各件物品的體積{1，8，4，3，5，2}時(shí)，可找到下列4組解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒(méi)有裝滿(mǎn)，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿(mǎn)為止。由于回溯求解的規(guī)則規(guī)則是“后進(jìn)先出”因此自然要用到棧。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件（2）要求根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；迷宮求解（1）問(wèn)題描述可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；dijkstra算法求最短路徑問(wèn)題描述：從鍵盤(pán)上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結(jié)點(diǎn)數(shù)num 2)依次輸入圖的各條邊3）程序所能達(dá)到的功能：輸出用dijkstra算法求出的一條最短路徑。一開(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)求出出列順序。（3）測(cè)試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？（4）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。拓?fù)渑判颍?）問(wèn)題描述：編寫(xiě)函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉＃?）要求：輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。1線性表的操作利用鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫(xiě)成函數(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ī)定上限。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例31演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。五、組織管理1．由院、系指派經(jīng)驗(yàn)豐富的專(zhuān)業(yè)教師擔(dān)任指導(dǎo)教師。六、成績(jī)考核與評(píng)定學(xué)生課程設(shè)計(jì)結(jié)束后寫(xiě)出總結(jié)報(bào)告，對(duì)設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對(duì)每位學(xué)生寫(xiě)出評(píng)語(yǔ)和鑒定，系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計(jì)成績(jī)，課程設(shè)計(jì)成績(jī)分為優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。評(píng)分標(biāo)準(zhǔn)：① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學(xué)校的各項(xiàng)紀(jì)律。撰寫(xiě)了高質(zhì)量的總結(jié)報(bào)告。② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)。答辯較準(zhǔn)確流利。通過(guò)了答辯?；驘o(wú)實(shí)習(xí)報(bào)告，沒(méi)有通過(guò)答辯。其目的就是要達(dá)到理論與實(shí)際相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。說(shuō)明書(shū)中除了在封面中應(yīng)有題目、班級(jí)、姓名、學(xué)號(hào)和課程設(shè)計(jì)日期以外，其正文一般有如下幾個(gè)方面的內(nèi)容： 三、課程設(shè)計(jì)教學(xué)基本要求四、課程設(shè)計(jì)選題根據(jù)教材《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計(jì)題目，或選擇下列與實(shí)際應(yīng)用緊密結(jié)合的較綜合性的題目，要求通過(guò)設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。五、本課程與其它課程的聯(lián)系與分工本課程是《數(shù)據(jù)結(jié)構(gòu)》的配套課程，學(xué)完《數(shù)據(jù)結(jié)構(gòu)》后進(jìn)行的綜合性課程設(shè)計(jì)。課程設(shè)計(jì)結(jié)束時(shí)，要求學(xué)生寫(xiě)出課程設(shè)計(jì)報(bào)告，可運(yùn)行的軟件系統(tǒng)（包括源程序）。設(shè)計(jì)報(bào)告占40％，設(shè)計(jì)作品占40％。優(yōu)秀者人數(shù)一般不得超過(guò)總?cè)藬?shù)的20%。有關(guān)的考查相關(guān)材料（文字材料以及磁盤(pán)或光盤(pán)）統(tǒng)一妥善保管