XX年數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目及報(bào)告范例.doc

1. 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)【問(wèn)題描述】參加運(yùn)動(dòng)會(huì)的n個(gè)學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)目和w個(gè)女子項(xiàng)目，項(xiàng)目編號(hào)分別為1m和m+1m+w。由于各項(xiàng)目參加人數(shù)差別較大，有些項(xiàng)目取前五名，得分順序?yàn)?，5，3，2，1；還有些項(xiàng)目只取前三名，得分順序?yàn)?，3，2。寫(xiě)一個(gè)統(tǒng)計(jì)程序產(chǎn)生各種成績(jī)單和得分報(bào)表?！净疽蟆?) 可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)；2) 能統(tǒng)計(jì)各學(xué)?？偡郑?) 可以按學(xué)校編號(hào)或名稱、學(xué)?？偡?、男女團(tuán)體總分排序輸出；4) 可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。5) 數(shù)據(jù)存入文件并能隨時(shí)查詢 6) 規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整型。界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。測(cè)試數(shù)據(jù)：【測(cè)試數(shù)據(jù)】要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。例如，對(duì)于n=4，m=3，w =2，編號(hào)為奇數(shù)的項(xiàng)目取前五名，編號(hào)為偶數(shù)的項(xiàng)目取前三名，設(shè)計(jì)一組實(shí)例數(shù)據(jù)?！緦?shí)現(xiàn)提示】可以假設(shè)n20，m30，w20，姓名長(zhǎng)度不超過(guò) 20 個(gè)字符。每個(gè)項(xiàng)目結(jié)束時(shí)，將其 編號(hào)、類型符(區(qū)分取前五名還是前三名) 輸入，并按名次順序輸入運(yùn)動(dòng)員姓名、校名(和成 績(jī))?！具x作內(nèi)容】 允許用戶指定某項(xiàng)目采取其他名次取法。2. 集合的并、交和差運(yùn)算【問(wèn)題描述】編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序?！净疽蟆?1) 集合的元素限定為小寫(xiě)字母字符 a.z 。(2) 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行?！緶y(cè)試數(shù)據(jù)】(1)Set1=magazine，Set2=paper，Set1Set2=aegimnprz，Setl Set2=ae，Set1-Set2=gimnz。(2)Set1= 012oper4a6tion89，Set2=error data，Set1Set2=adeinoprt，Setl Set2=aeort，Set1-Set2=inp?！緦?shí)現(xiàn)提示】以有序鏈表表示集合?！具x作內(nèi)容】(1) 集合的元素判定和子集判定運(yùn)算。(2) 求集合的補(bǔ)集。(3) 集合的混合運(yùn)算表達(dá)式求值。(4) 集合的元素類型推廣到其他類型 ， 甚至任意類型。3. 一元稀疏多項(xiàng)式計(jì)算器【問(wèn)題描述】設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器?！净疽蟆恳辉∈瓒囗?xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：(1) 輸入并建立多項(xiàng)式 ；(2) 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，cl，el，c2，e2，cn，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)式a -b ?！緶y(cè)試數(shù)據(jù)】(1)(2x+5x83.1x11) + (75x8+11x9)=(3.lx11+11x9+2x+7)(2)(6x-3x+4.4x21.2x9) (-6x-3+5.4x2x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x)(3)(1 +x + x2+x3+x4+x5)+(-x3x4)=(1+x+x2+x5) (4)(x+x3)+(-xx3)=0(5)(x+x100)+(x100 +x200)=(x+2x100+x200)(6)(x+x2+x3)+0=x+x2+x3(7) 互換上述測(cè)試數(shù)據(jù)中的前后兩個(gè)多項(xiàng)式【實(shí)現(xiàn)提示】用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式?！具x作內(nèi)容】(1) 計(jì)算多項(xiàng)式在x處的值。(2) 求多項(xiàng)式 a 的導(dǎo)函數(shù) 。(3) 多項(xiàng)式a和b相乘，建立乘積多項(xiàng)式ab 。(4) 多項(xiàng)式的輸出形式為類數(shù)學(xué)表達(dá)式。例如 ，多項(xiàng)式 -3x8+6x318 的輸出形式為，x15+(8)x714的輸出形式為。注意，數(shù)值為1的非零次項(xiàng)的輸出形式中略去系數(shù)1，如項(xiàng)1x8的輸出形式為x8，項(xiàng) 1x3的輸出形式為x3。(5) 計(jì)算器的仿真界。4. 池塘夜降彩色雨【問(wèn)題描述】設(shè)計(jì)一個(gè)程序，演示美麗的“池塘夜雨”景色：色彩繽紛的雨點(diǎn)飄飄灑灑地從天而降， 滴滴入水有聲，濺起圈圈微瀾。 【基本要求】(1) 雨點(diǎn)的空中出現(xiàn)位置、降范過(guò)程的可見(jiàn)程度、入水位置、顏色、最大水圈等，都是隨機(jī)確定的 ；(2) 多個(gè)雨點(diǎn)按照各自的隨機(jī)參數(shù)和存在狀態(tài)，同時(shí)演示在屏幕上?！緶y(cè)試數(shù)據(jù)】適當(dāng)調(diào)整控制雨點(diǎn)密度、最大水圈和狀態(tài)變化的時(shí)間間隔等參數(shù)。【實(shí)現(xiàn)提示】(1) 每個(gè)雨點(diǎn)的存在周期可分為三個(gè)階段：從天而降、入水有聲和圈圈微瀾，需要一個(gè)記錄存儲(chǔ)其相關(guān)參數(shù)、當(dāng)前狀態(tài)和下一狀態(tài)的更新時(shí)刻。(2) 在圖形狀態(tài)編程。雨點(diǎn)下降的可見(jiàn)程度應(yīng)是斷斷續(xù)續(xù)、依稀可見(jiàn)；圈圈水波應(yīng)是由里至外逐漸擴(kuò)大和消失。(3) 每個(gè)雨點(diǎn)發(fā)生時(shí)，生成其記錄，并預(yù)置下一個(gè)雨點(diǎn)的發(fā)生時(shí)間。(4) 用一個(gè)適當(dāng)?shù)慕Y(jié)構(gòu)管理當(dāng)前存在的雨點(diǎn)，使系統(tǒng)能利用它按時(shí)更新每個(gè)雨點(diǎn)的狀態(tài)，一旦有雨點(diǎn)的水圈全部消失，就從結(jié)構(gòu)中刪去?！具x作內(nèi)容】(1) 增加“電閃雷鳴”景象。(2) 增加風(fēng)的效果，展現(xiàn)“風(fēng)雨飄搖”的情景。(3) 增加雨點(diǎn)密度的變化：時(shí)而“和風(fēng)細(xì)雨”， 時(shí)而“暴風(fēng)驟雨”。(4) 將“池塘”改為“荷塘”，雨點(diǎn)滴在荷葉上的效果是濺起四散的水珠，響聲也不同。5. 銀行業(yè)務(wù)模擬【問(wèn)題描述】客戶業(yè)務(wù)分為兩種。第一種是申請(qǐng)從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。銀行有兩個(gè)服務(wù)窗口，相應(yīng)地有兩個(gè)隊(duì)列。客戶到達(dá)銀行后先排第一個(gè)隊(duì)。處理每個(gè)客戶業(yè)務(wù)時(shí)，如果屬于第一種，且申請(qǐng)額超出銀行現(xiàn)存資金總額而得不到滿足，則立刻排入第二個(gè)隊(duì)等候，直至滿足時(shí)才離開(kāi)銀行；否則業(yè)務(wù)處理完后立刻離開(kāi)銀行。每接待完一個(gè)第二種業(yè)務(wù)的客戶，則順序檢查和處理(如果可能)第二個(gè)隊(duì)列中的客戶，對(duì)能滿足的申請(qǐng)者予以滿足，不能滿足者重新排到第二個(gè)隊(duì)列的隊(duì)尾。注意，在此檢查過(guò)程中，一旦銀行資金總額少于或等于剛才第一個(gè)隊(duì)列中最后一個(gè)客戶(第二種業(yè)務(wù))被接待之前的數(shù)額，或者本次已將第二個(gè)隊(duì)列檢查或處理了一遍，就停止檢查(因?yàn)榇藭r(shí)已不可能還有能滿足者)轉(zhuǎn)而繼續(xù)接待第一個(gè)隊(duì)列的客戶。任何時(shí)刻都只開(kāi)一個(gè)窗口。假設(shè)檢查不需要時(shí)間。營(yíng)業(yè)時(shí)間結(jié)束時(shí)所有客戶立即離開(kāi)銀行。寫(xiě)一個(gè)上述銀行業(yè)務(wù)的事件驅(qū)動(dòng)模擬系統(tǒng)，通過(guò)模擬方法求出客戶在銀行內(nèi)逗留的平均時(shí)間?！净疽蟆坷脛?dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)模擬。【測(cè)試數(shù)據(jù)】一天營(yíng)業(yè)開(kāi)始時(shí)銀行擁有的款額為10000(元)，營(yíng)業(yè)時(shí)間為600(分鐘)。其他模擬參量自定，注意測(cè)定兩種極端的情況：一是兩個(gè)到達(dá)事件之間的間隔時(shí)間很短，而客戶的交易時(shí)間很長(zhǎng)，另一個(gè)恰好相反，設(shè)置兩個(gè)到達(dá)事件的間隔時(shí)間很長(zhǎng)，而客戶的交易時(shí)間很短?！緦?shí)現(xiàn)提示】事件有兩類：到達(dá)銀行和離開(kāi)銀行。初始時(shí)銀行現(xiàn)存資金總額為total。開(kāi)始營(yíng)業(yè)后的第一今事件是客戶到達(dá)，營(yíng)業(yè)時(shí)間從0到closetime。到達(dá)事件發(fā)生時(shí)隨機(jī)地設(shè)置此客戶的交易時(shí)間和距下一到達(dá)事件之間的時(shí)間間隔。每個(gè)客戶要辦理的款額也是隨機(jī)確定的，用負(fù)值和正值分別表示第一類和第二類業(yè)務(wù)。變量total，closetime以及上述兩個(gè)隨機(jī)量的上下界均交互地從終端讀入，作為模擬參數(shù)。兩個(gè)隊(duì)列和一個(gè)事件表均要用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。注意弄清應(yīng)該在什么條件下設(shè)置離開(kāi)事件，以及第二個(gè)隊(duì)列用怎樣的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)時(shí)可以獲得較高的效率。注意：事件表是按時(shí)間順序有序的?！具x作內(nèi)容】自己實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)類型。例如對(duì)于客戶結(jié)點(diǎn)，定義pool為CustNodepoolfMAX；/ 結(jié)構(gòu)類型CustNode含四個(gè)域：aITHIne，durtime，amount，next或者定義四個(gè)同樣長(zhǎng)的，以上述域名為名字的數(shù)組。初始時(shí)，將所有分量的next域鏈接起來(lái)，形成一個(gè)靜態(tài)鏈找，設(shè)置一個(gè)樓頂元素下標(biāo)指示量top，top=0表示找空。動(dòng)態(tài)存儲(chǔ)分配函數(shù)可以取名為myMalloc，其作用是出錢(qián)，將錢(qián)頂元素的下標(biāo)返回。若返回的值為0，則表示無(wú)空間可分配。歸還函數(shù)可取名為myFree，其作用是把該分量入錢(qián)。用FOR-TRAN和BASIC等語(yǔ)言實(shí)現(xiàn)時(shí)只能如此地自行組織。6. 馬踏棋盤(pán)【問(wèn)題描述】 設(shè)計(jì)一個(gè)國(guó)際象棋的馬踏遍棋盤(pán)的演示程序?！净疽蟆繉ⅠR隨機(jī)放在國(guó)際象棋的88棋盤(pán)Board88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，64依次填入一個(gè)88的方陣，輸出之。7. 魔王語(yǔ)言解釋【問(wèn)題描述】有一個(gè)魔王總是使用自己的一種非常精練而抽象的語(yǔ)言講話，沒(méi)有人能昕得懂，但他的語(yǔ)言是可以逐步解釋成人能聽(tīng)懂的語(yǔ)言，因?yàn)樗恼Z(yǔ)言是由以下兩種形式的規(guī)則由人的語(yǔ)言逐步抽象上去的：(1) (2) 在這兩種形式中，從左到右均表示解釋。試寫(xiě)一個(gè)魔王語(yǔ)言的解釋系統(tǒng)，把他的話解釋成人能聽(tīng)得懂的話?！净疽蟆坑孟率鰞蓷l具體規(guī)則和上述規(guī)則形式(2)實(shí)現(xiàn)。設(shè)大寫(xiě)字母表示魔王語(yǔ)言的詞匯；小寫(xiě)字母表示人的語(yǔ)言詞匯；希臘字母表示可以用大寫(xiě)字母或小寫(xiě)字母代換的變量。魔王語(yǔ)言可含人的詞匯。(1) (2) 【測(cè)試數(shù)據(jù)】B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae若將小寫(xiě)字母與漢字建立下表所示的對(duì)應(yīng)關(guān)系，則魔王說(shuō)的話是“天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。tdsaezgxnh天地上一只鵝追趕下蛋恨【實(shí)現(xiàn)提示】將魔王的語(yǔ)言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。若是開(kāi)括號(hào)，則逐一出棧，將字母順序入隊(duì)列，直至閉括號(hào)出棧，并按規(guī)則要求逐一出隊(duì)列再處理后入棧。其他情形較簡(jiǎn)單，請(qǐng)讀者思考應(yīng)如何處理。應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本操作?！具x作內(nèi)容】(1)由于問(wèn)題的特殊性，可以實(shí)現(xiàn)棧和隊(duì)列的順序存儲(chǔ)空間共享。(2)代換變量的數(shù)目不限，則在程序開(kāi)始運(yùn)行時(shí)首先讀入一組第一種形式的規(guī)則，而不是把規(guī)則固定在程序中(第二種形式的規(guī)則只能固定在程序中)。8. 航空客運(yùn)訂票系統(tǒng)【問(wèn)題描述】航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計(jì)一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來(lái)完成?！净疽蟆?1)每條航線所涉及的信息有：終點(diǎn)站名、航班號(hào)、飛機(jī)號(hào)、飛行周日(星期幾)、乘員定額、余票量、已訂票的客戶名單(包括姓名、訂票量、艙位等級(jí)1，2或3)以及等候替補(bǔ)的客戶名單(包括姓名、所需票量)；(2)系統(tǒng)能實(shí)現(xiàn)的操作和功能如下：錄入：可以錄入航班情況，全部數(shù)據(jù)可以只放在內(nèi)存中，最好存儲(chǔ)在文件中；查詢航線：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號(hào)、飛機(jī)號(hào)、星期幾飛行，最近一天航班的日期和余票額；承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求(航班號(hào)、訂票數(shù)額)查詢?cè)摵桨嗥鳖~情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號(hào)；若已滿員或余票額少于訂票額，則需重新詢問(wèn)客戶要求。若需要，可登記排隊(duì)候補(bǔ)；承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況(日期、航班)，為客戶辦理退票手續(xù)，然后查詢?cè)摵桨嗍欠裼腥伺抨?duì)候補(bǔ)，首先詢問(wèn)排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問(wèn)其他排隊(duì)候補(bǔ)的客戶?！緶y(cè)試數(shù)據(jù)】由讀者自行指定?！緦?shí)現(xiàn)提示】?jī)蓚€(gè)客戶名單可分別由線性表和隊(duì)列實(shí)現(xiàn)。為查找方便，已訂票客戶的線性表應(yīng)按客戶姓名有序，并且，為插入和刪除方便，應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。由于預(yù)約人數(shù)無(wú)法預(yù)計(jì)，隊(duì)列也應(yīng)以鏈表作存儲(chǔ)結(jié)構(gòu)。整個(gè)系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲(chǔ)結(jié)構(gòu)，并按航班有序或按終點(diǎn)站名有序。每條航線是這張表上的一個(gè)記錄，包含上述8個(gè)域、其中乘員名單域?yàn)橹赶虺藛T名單鏈表的頭指針，等候替補(bǔ)的客戶名單域?yàn)榉謩e指向隊(duì)頭和隊(duì)尾的指針。【選作內(nèi)容】當(dāng)客戶訂票要求不能滿足時(shí)，系統(tǒng)可向客戶提供到達(dá)同一目的地的其他航線情況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項(xiàng)目。9. 藥店的藥品銷售統(tǒng)計(jì)系統(tǒng)【問(wèn)題描述】 設(shè)計(jì)一系統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對(duì)銷售各藥品的記錄進(jìn)行統(tǒng)計(jì)，可按藥品的編號(hào)、單價(jià)、銷售量或銷售額做出排名。 【基本要求】 在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲(chǔ)在順序表中。各藥品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷出數(shù)量、銷售額。藥品編號(hào)共4位，采用字母和數(shù)字混合編號(hào)，如：A125，前一位為大寫(xiě)字母，后三位為數(shù)字，按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷售量或銷售額進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排序法，對(duì)銷售量的排序采用快速排序法，對(duì)銷售額的排序采用堆排序法。10. 文學(xué)研究助手【問(wèn)題描述】文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng),稱為文學(xué)研究助手。【基本要求】英文小說(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢,即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào),格式自行設(shè)計(jì)?！緶y(cè)試數(shù)據(jù)】以你的C源程序模擬英文小說(shuō),C語(yǔ)言的保留字集作為待統(tǒng)計(jì)的詞匯集?！緦?shí)現(xiàn)提示】約定小說(shuō)中的詞匯一律不跨行。這樣,每讀入一行,就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次,不必存多個(gè)相同的行號(hào)。如果讀者希望達(dá)到選做部分(1)和(2)所提出的要求,則首先應(yīng)把KMP算法改寫(xiě)成如下的等價(jià)形式,再將它推廣到多個(gè)模式的情形。i=1;j=1;while(i!=s.curlen+1&j!=t.curlerl十1)while(j!=0&s.chi!=t.chj)j=nextj; /j=O或s.chi=t.chjj+;i+;/每次進(jìn)入循環(huán)體,i只增加一次【選作內(nèi)容】(1)模式匹配要基于KMP算法。(2)整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。(3)假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始,或者前置一個(gè)空格符。利用單詞匹配特點(diǎn)另寫(xiě)一個(gè)高效的統(tǒng)計(jì)程序,與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。(4)推廣到更一般的模式集匹配問(wèn)題,并設(shè)待查模式串可以跨行(提示:定義操作GetAChar)。11. 文本格式化【問(wèn)題描述】輸入文件中含有待格式化或稱為待排版的文本,它由多行的文字組成,例如一篇英文文章。每一行由一系列被一個(gè)或多個(gè)空格符所隔開(kāi)的字組成,任何完整的字都沒(méi)有被分割在兩行(每行最后一個(gè)字與下一行的第一個(gè)字之間在邏輯上應(yīng)該由空格分開(kāi)),每行字符數(shù)不超過(guò)80。除了上述文本類字符之外,還存在著起控制作用的字符:符號(hào)指示它后面的正文在格式化時(shí)應(yīng)另起一段排放,即空一行,并在段首縮入8個(gè)字符位置。自成一個(gè)字。一個(gè)文本格式化程序可以處理上述輸入文件,按照用戶指定的版面規(guī)格重排版面z實(shí)現(xiàn)頁(yè)內(nèi)調(diào)整、分段、分頁(yè)等文本處理功能,排版結(jié)果存入輸出文本文件中。試寫(xiě)一個(gè)這樣的程序?！净疽蟆?1)輸出文件中字與字之間只留一個(gè)空格符,即實(shí)現(xiàn)多余空格符的壓縮。(2)在輸出文件中,任何完整的字仍不能分割在兩行,行尾不齊沒(méi)關(guān)系,但行首要對(duì)齊(即左對(duì)齊)。(3)如果所要求的每頁(yè)頁(yè)底所空行數(shù)不少于3,則將頁(yè)號(hào)印在頁(yè)底空行中第2行的中間位置上,否則不印。(4)版面要求的參數(shù)要包含：頁(yè)長(zhǎng)(PageLength)一一每頁(yè)內(nèi)文字(不計(jì)頁(yè)號(hào))的行數(shù)。頁(yè)寬(PageWedth)一一每行內(nèi)文字所占最大字符數(shù)。左空白(LeftMargin)-一一每行文字前的固定空格數(shù)。頭長(zhǎng)(HeadingLength)一一每頁(yè)頁(yè)頂所空行數(shù)。腳長(zhǎng)(FootingLength)一一每頁(yè)頁(yè)底所空行數(shù)(含頁(yè)號(hào)行)。起始頁(yè)號(hào)(StartingPageNumber)一一首頁(yè)的頁(yè)號(hào)?！緶y(cè)試數(shù)據(jù)】略。注意在標(biāo)點(diǎn)之后加上空格符?！緦?shí)現(xiàn)提示】可以設(shè):左空白數(shù)2+頁(yè)寬=160,即行印機(jī)最大行寬,從而只要設(shè)置這樣大的一個(gè)行緩沖區(qū)就足夠了,每加工完一行,就輸出一行。如果輸入文件和輸出文件不是由程序規(guī)定死,而是可由用戶指定,則有兩種做法:一是像其他參量一樣,將文件名交互地讀入字符串變量中;更好的方式是讓用戶通過(guò)命令行指定,具體做法依機(jī)器的操作系統(tǒng)而定。應(yīng)該首先實(shí)現(xiàn)GetAWord(w)這一操作,把諸如行尾處理、文件尾處理、多余空格符壓縮等一系列低級(jí)事務(wù)留給它處理,使系統(tǒng)的核心部分集中對(duì)付排版要求。每個(gè)參數(shù)都可以實(shí)現(xiàn)缺省值設(shè)置。上述排版參數(shù)的缺省值可以分別取56,60,10,5,5和1?！具x作內(nèi)容】(1)輸入文件名和輸出文件名要由用戶指定。(2)允許用戶指定是否右對(duì)齊,即增加一個(gè)參量右對(duì)齊否(RightJustifying),缺省值可設(shè)為y(yes)。右對(duì)齊指每行最后一個(gè)字的字尾要對(duì)齊,多余的空格要均勻分布在本行中各字之間。(3)實(shí)現(xiàn)字符填充(characterstuffing)技術(shù)。作為分段控制符之后,限制了原文中不能有這樣的字?，F(xiàn)在去掉這一限制:如果原文中有這樣的字,改用兩個(gè)并列起來(lái)表示一個(gè)字。當(dāng)然,如果原文中此符號(hào)夾在字中,就不必特殊處理了。(4)允許用戶自動(dòng)按多欄印出一頁(yè)。12. 簡(jiǎn)單行編輯程序【問(wèn)題描述】文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具,實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大,全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的作法既不經(jīng)濟(jì),也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存,稱為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。設(shè)文件每行不超過(guò)320個(gè)字符,很少超過(guò)80個(gè)字符。【基本要求】實(shí)現(xiàn)以下4條基本編輯命令:(1) 行插入。格式:i.將插入活區(qū)中第行之后。(2) 行刪除。格式:d刪除活區(qū)中第行(到第行)。例如:d10和d1014。(3) 活區(qū)切換。格式n將活區(qū)寫(xiě)入輸出文件,并從輸入文件中讀入下一段,作為新的活區(qū)。(4) 活區(qū)顯示。格式:p逐頁(yè)地(每頁(yè)20行)顯示活區(qū)內(nèi)容,每顯示一頁(yè)之后請(qǐng)用戶決定是否繼續(xù)顯示以后備頁(yè)(如果存在)。印出的每一行要前置行號(hào)和一個(gè)空格符,行號(hào)固定占4位,增量為1。各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi),只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1,表示插入當(dāng)前屏幕中第一行之前,否則命令參數(shù)非法?！緶y(cè)試數(shù)據(jù)】自行設(shè)定,注意測(cè)試將活區(qū)刪空等特殊情況?！緦?shí)現(xiàn)提示】(1)設(shè)活區(qū)的大小用行數(shù)ActiveMULen(可設(shè)為100)來(lái)描述?？紤]到文本文件行長(zhǎng)通常為正態(tài)分布,且峰值在60到70之間,用320ActiveMULen大小的字符數(shù)組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ),每個(gè)標(biāo)準(zhǔn)行塊可含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組,也可以利用動(dòng)態(tài)鏈表連接起來(lái)。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ASCII字符(如(012)8)標(biāo)識(shí)。此外,還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。(2)初始化函數(shù)包括:請(qǐng)用戶提供輸入文件名(空串表示無(wú)輸入文件)和輸出文件名,兩者不能相同。然后盡可能多地從輸入文件中讀入各行,但不超過(guò)ActiveMULen-LX的值可以自定,例如20。(3)在執(zhí)行行插入命令的過(guò)程中,每接收到一行時(shí)都要檢查活區(qū)大小是否已達(dá)ActiveMaxLen。如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過(guò)ActiveMaxLen應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中;若插入點(diǎn)為第一行之前,則只得將新插入的這一行輸出。(4)若輸入文件尚未讀完,活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部,以保持閱讀連續(xù)性;否則,它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。(5)可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。【選作內(nèi)容】(1)對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。(2)加入更復(fù)雜的編輯操作,如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S和m。13. 串基本操作的演示【問(wèn)題描述】如果語(yǔ)言沒(méi)有把串作為一個(gè)預(yù)先定義好的基本類型對(duì)待,又需要用該語(yǔ)言寫(xiě)一個(gè)涉及串操作的軟件系統(tǒng)時(shí),用戶必須自己實(shí)現(xiàn)串類型。試實(shí)現(xiàn)串類型,并寫(xiě)一個(gè)串的基本操作的演示系統(tǒng)?！净疽蟆吭诮炭茣?shū)4.2.2節(jié)用堆分配存儲(chǔ)表示實(shí)現(xiàn)HString串類型的最小操作子集的基礎(chǔ)上,實(shí)現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作(不使用C語(yǔ)言本身提供的串函數(shù))。參數(shù)合法性檢查必須嚴(yán)格。利用上述基本操作函數(shù)構(gòu)造以下系統(tǒng):它是一個(gè)命令解釋程序,循環(huán)往復(fù)地處理用戶鍵入的每一條命令,直至終止程序的命令為止。命令定義如下:(1)賦值。 格式: A 用所表示的串的值建立新串,并顯示新串的內(nèi)部名和串值。例:A Hi!(2)判相等。格式: E 若兩串相等,則顯示EQUAL,否則顯示UNEQUAL。(3)聯(lián)接。 格式:C 將兩串拼接產(chǎn)生結(jié)果串,它的內(nèi)部名和串值都顯示出來(lái)。(4)求長(zhǎng)度。格式:L串標(biāo)識(shí) 顯示串的長(zhǎng)度。(5)求子串。格式:S +如果參數(shù)合法,則顯示子串的內(nèi)部名和串值。不帶正負(fù)號(hào)。(6)子串定位。格式:I 顯示第二個(gè)串在第一個(gè)串中首次出現(xiàn)時(shí)的起始位置。(7)串替換。格式: R 將第一個(gè)串中所有出現(xiàn)的第二個(gè)串用第三個(gè)串替換,顯示結(jié)果串的內(nèi)部名和串值,原串不變。(8)顯示。格式:P 顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對(duì)照表。(9)刪除。格式:D 刪除該內(nèi)部名對(duì)應(yīng)的串,即賦值的逆操作。(10)退出。格式:Q 結(jié)束程序的運(yùn)行。在上述命令中,如果一個(gè)自變量是串,則應(yīng)首先建立它?；静僮骱瘮?shù)的結(jié)果(即函數(shù)值)如果是一個(gè)串,則應(yīng)在尚未分配的區(qū)域內(nèi)新辟空間存放?！緶y(cè)試數(shù)據(jù)】自定。但要包括以下幾組:(1)E ,應(yīng)顯示EQUAL。(2)E abcabcd,應(yīng)顯示UNEQUAL。(3)C ,應(yīng)顯示。(4)I a ,應(yīng)報(bào)告:參數(shù)非法。(5)R aaa aa b,應(yīng)顯示ba(6)R aaabc a aab,應(yīng)顯示aabaabaabbc。(7)R Faaaaaaaa aaaaab,應(yīng)顯示abab。【實(shí)現(xiàn)提示】【選作內(nèi)容】(1) 串頭表改用單鏈表實(shí)現(xiàn)。(2) 對(duì)命令的格式(即語(yǔ)法)作嚴(yán)格檢查,使系統(tǒng)既能處理正確的命令,也能處理錯(cuò)誤的命令。注意,語(yǔ)義檢查(如某內(nèi)部名對(duì)應(yīng)的串已被刪除而無(wú)定義等)和基本操作參數(shù)合法性檢查仍應(yīng)留給基本操作去做。(3) 支持串名。將串名(可設(shè)不超過(guò)6個(gè)字符)存于串頭表中。命令(1)(3)(5)要增加命令參數(shù);命令(7)中的 改為,并用此名作為結(jié)果串名,刪除原被替串標(biāo)識(shí),用代替定義和命令解釋中的內(nèi)部名。每個(gè)命令執(zhí)行完畢時(shí)立即自動(dòng)刪除無(wú)名串。14. 程序分析【問(wèn)題描述】讀入一個(gè)C程序,統(tǒng)計(jì)程序中代碼、注釋和空行的行數(shù)以及函數(shù)的個(gè)數(shù)和平均行數(shù),并利用統(tǒng)計(jì)信息分析評(píng)價(jià)該程序的風(fēng)格。【基本要求】(1) 把 C 程序文件按字符順序讀入源程序;(2) 邊讀入程序,邊識(shí)別統(tǒng)計(jì)代碼行、注釋行和空行,同時(shí)還要識(shí)別函數(shù)的開(kāi)始和結(jié)束,以便統(tǒng)計(jì)其個(gè)數(shù)和平均行數(shù)。(3) 程序的風(fēng)格評(píng)價(jià)分為代碼、注釋和空行三個(gè)方面。每個(gè)方面分為 A,B,C 和 D 四個(gè)等級(jí) , 等級(jí)的劃分標(biāo)準(zhǔn)是 : A級(jí)B級(jí)C級(jí)D級(jí) 代碼(函數(shù)平均長(zhǎng)度)1015行89或1620行57或2124行24行 注釋(占總行數(shù)比率)1525%1014或2630%59或3135%35% 空行(占總行數(shù)比率)1525%1014或2630%59或3135%35%【測(cè)試數(shù)據(jù)】先對(duì)較小的程序進(jìn)行分析。當(dāng)你的程序能正確運(yùn)行時(shí),對(duì)你的程序本身進(jìn)行分析?！緦?shí)現(xiàn)提示】為了實(shí)現(xiàn)的方便,可作以下約定:(1) 頭兩個(gè)字符是 FFF 的行稱為注釋行(該行不含語(yǔ)句)。除了空行和注釋行外,其余均為代碼行(包括類型定義、變量定義和函數(shù)頭)。(2) 每個(gè)函數(shù)代碼行數(shù)(除去空行和注釋行)稱為該函數(shù)的長(zhǎng)度。(3) 每行最多只有一個(gè) 、switch 和struet(便于識(shí)別函數(shù)的結(jié)束行)?！具x作內(nèi)容】(1) 報(bào)告函數(shù)的平均長(zhǎng)度。(2) 找出最長(zhǎng)函數(shù)及其在程序中的位置。(3) 允許函數(shù)的嵌套定義,報(bào)告最大的函數(shù)嵌套深度。15. 稀疏矩陣運(yùn)算器【問(wèn)題描述】稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用 稀疏 特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大 節(jié)省存儲(chǔ)空間 , 提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。【基本要求】以帶行邏輯鏈接信息的三元組順序表表示稀疏矩陣,實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示 , 而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出?！緦?shí)現(xiàn)提示】1. 首先應(yīng)輸入矩陣的行數(shù)和列數(shù) , 并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò) 20 。2. 程序可以對(duì)三元組的輸入順序加以限制 , 例如 , 按行優(yōu)先。注意研究教科書(shū) 5.3.2節(jié)中的算法 , 以便提高計(jì)算效率。3. 在用三元組表示稀疏矩陣時(shí) , 相加或相減所得結(jié)果矩陣應(yīng)該另生成 , 乘積矩陣也 可用二維數(shù)組存放。【選作內(nèi)容】1. 按教科書(shū) 5.3.2 節(jié)中的描述方法 , 以十字鏈表表示稀疏矩陣。2. 增添矩陣求逆的運(yùn)算 , 包括不可求逆的情況。在求逆之前 , 先將稀疏矩陣的內(nèi)部表示改為十字鏈表。16. 多維數(shù)組【問(wèn)題描述】設(shè)計(jì)并模擬實(shí)現(xiàn)整型多維數(shù)組類型?！?基本要求】盡管 C 等程序設(shè)計(jì)語(yǔ)言已經(jīng)提供了多維數(shù)組 , 但在某些情況下 , 定義用戶所需的多維數(shù)組很有用的。通過(guò)設(shè)計(jì)并模擬實(shí)現(xiàn)多維數(shù)組類型 , 可以深刻理解和掌握多維數(shù)組。整型多維數(shù)組應(yīng)具有以下基本功能 :(1) 定義整型多維數(shù)組類型 , 各維的下標(biāo)是任意整數(shù)開(kāi)始的連續(xù)整數(shù) ;(2) 下標(biāo)變量賦值 , 執(zhí)行下標(biāo)范圍檢查 ;(3 同類型數(shù)組賦值 ;(4) 子數(shù)組賦值 , 例如 ,a1.n=a 2.n+1;a2.43.5=b1.32.4; (5) 確定數(shù)組的大小?！?測(cè)試數(shù)據(jù)】由讀者指定?！緦?shí)現(xiàn)提示】各基本功能可以分別用函數(shù)模擬實(shí)現(xiàn) , 應(yīng)仔細(xì)考慮函數(shù)參數(shù)的形式和設(shè)置。 定義整型多維數(shù)組類型時(shí) , 其類型信息可以存儲(chǔ)在如下定義的類型的記錄中：define MaxDim 5Typedef structint dim , BoundPtr lower ,Upper;ConstPtr constants;)NArray,*NarrayPtr;整型多維數(shù)組變量的存儲(chǔ)結(jié)構(gòu)類型可定義為:Typedef structElemType *elem;Int num;NArrayType TypeRecord;NArrayType;【選作內(nèi)容】(1) 各維的下標(biāo)是任意字符開(kāi)始的連續(xù)字符。(2) 數(shù)組初始化。(3) 可修改數(shù)組的下標(biāo)范圍。 17. 簡(jiǎn)單LISP算術(shù)表達(dá)式計(jì)算器【問(wèn)題描述】設(shè)計(jì)一個(gè)簡(jiǎn)單的 LISP 算術(shù)表達(dá)式計(jì)算器。簡(jiǎn)單 LISP 算術(shù)表達(dá)式(以下簡(jiǎn)稱表達(dá)式)定義如下:(1) 定義一個(gè)自然數(shù)(2)(運(yùn)算符 表達(dá)式 表達(dá)式)例如,6,(+45),(+(+25)8) 都是表達(dá)式,其值分別為6,9和15?！净疽蟆繉?shí)現(xiàn)LISP加法表達(dá)式的求值?！緶y(cè)試數(shù)據(jù)】6,(+45),(+(+25)8),(+2(+58),(+(+(+12)(+34)(+(+56)(+78)【 實(shí)現(xiàn)提示】寫(xiě)一個(gè)遞歸函數(shù):int Evaluate(FILE * CharFile)字符文件 CharFile 的每行是一個(gè)如上定義的表達(dá)式。每讀入CharFile 的一行,求出并返回表達(dá)式的值?？梢栽O(shè)計(jì)以下輔助函數(shù)status isNumber(char ReadInChar); /視ReadInchar 是否是數(shù)字而返回 TRUE 或 FALSE 。int TurnToInteger(char IntChar); / 將字符0.9 轉(zhuǎn)換為整數(shù) 0.9【選做內(nèi)容】(1) 標(biāo)準(zhǔn)整數(shù)類型的 LISP 加法表達(dá)式的求值。(2) 標(biāo)準(zhǔn)整數(shù)類型的 LISP 四則運(yùn)算表達(dá)式的求值。(3) LISP 算術(shù)表達(dá)式的語(yǔ)法檢查。18. 重言式判別【問(wèn)題描述】一個(gè)邏輯表達(dá)式如果對(duì)于其變?cè)娜我环N取值都為真，則稱為重言式；反之，如果對(duì)于其變?cè)娜我环N取值都為假，則稱為矛盾式；然而，更多的情況下，既非重言式，也非矛盾式。試寫(xiě)一個(gè)程序，通過(guò)真值表判別一個(gè)邏輯表達(dá)式屬于上述哪一類?！净疽蟆?1) 邏輯表達(dá)式從終端輸入，長(zhǎng)度不超過(guò)一行。邏輯運(yùn)算符包括 |，& 和 ，分別表示或、與和非，運(yùn)算優(yōu)先程度遞增，但可由括號(hào)改變，即括號(hào)內(nèi)的運(yùn)算優(yōu)先。邏輯變?cè)?為大寫(xiě)字母。表達(dá)式中任何地方都可以含有多個(gè)空格符。(2) 若是重言式或矛盾式，可以只顯示True forever，或False forever，否則顯示 Satisfactible 以及變量名序列，與用戶交互。若用戶對(duì)表達(dá)式中變?cè)《ㄒ唤M值，程序就求出并顯示邏輯表達(dá)式的值。【測(cè)試數(shù)據(jù)】(1) (A|A)&(B|B)(2) (A&A)&C(3) A|B|C|D|E|A(4) A&B&C&B(5) (A|B)&(A|B)(6) A&B|A&B;O ,0;0,1;1,0;1,1 。19. 哈夫曼編/譯碼器【問(wèn)題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成 本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個(gè)完整的編 /譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1)I：初始化(Initialization)。從終端讀入字符集大小n , 以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。(2)E：編碼(Encoding)。利用已建好的哈夫曼樹(shù)(如不在內(nèi)存，則從文件hfmTree中讀人)，對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。(3)D: 譯碼(Decoding)。利用已建好的哈夫曼樹(shù)將文件 CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。(4)P：打印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件 CodePrin 中。(5)T：打印哈夫曼樹(shù)(Tree printing)。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式(樹(shù)或凹入表形式)顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中?！緶y(cè)試數(shù)據(jù)】(1)利用教科書(shū)例 6-2 中的數(shù)據(jù)調(diào)試程序。(2)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù) , 并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：THIS PROGRAM IS MY FAVORITE。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161【選作內(nèi)容】(1)上述文件CodeFile中的每個(gè)0或1實(shí)際上占用了一個(gè)字節(jié)的空間，只起到示意或模擬的作用。為最大限度地利用編碼存儲(chǔ)能力，試改寫(xiě)你的系統(tǒng)，將編碼結(jié)果以二進(jìn)制形式存放在文件CodeFile中。(2)修改你的系統(tǒng)，實(shí)現(xiàn)對(duì)你的系統(tǒng)的原程序的編碼和譯碼(主要是將行尾符編/譯碼問(wèn)題)。(3)實(shí)現(xiàn)各個(gè)轉(zhuǎn)換操作的源/目文件，均由用戶在選擇此操作時(shí)指定。20. 圖遍歷的演示【問(wèn)題描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫(xiě)一個(gè)程序，演示在連通的無(wú)向圖上訪問(wèn)全部結(jié)點(diǎn)的操作。【基本要求】以鄰接多重表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列和相應(yīng)生成樹(shù)的邊集?！緶y(cè)試數(shù)據(jù)】任選國(guó)內(nèi)城市，起點(diǎn)為合肥，暫時(shí)忽略里程?！緦?shí)現(xiàn)提示】設(shè)圖的結(jié)點(diǎn)20-30個(gè)，每個(gè)結(jié)點(diǎn)用一個(gè)編號(hào)表示(如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號(hào)分別為1，2，n)。通過(guò)輸入圖的全部邊(存于數(shù)據(jù)文件中，從文件讀寫(xiě))輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對(duì)，可以對(duì)邊的輸入順序作出某種限制。注意，生成樹(shù)的邊是有向邊，端點(diǎn)順序不能顛倒。【選作內(nèi)容】(1)借助于棧類型(自己定義和實(shí)現(xiàn))，用非遞歸算法實(shí)現(xiàn)深度優(yōu)先遍歷。(2)以鄰接表為存儲(chǔ)結(jié)構(gòu)，建立深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)，再按凹入表或樹(shù)形打印生成樹(shù)。21. 教學(xué)計(jì)劃編制問(wèn)題【問(wèn)題描述】大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開(kāi)設(shè)的課程都是確定的，而且課程在開(kāi)設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門(mén)課程有哪些先修課程是確定的，可以有任意多門(mén)，也可以沒(méi)有。每門(mén)課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序?！净疽蟆?1)輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門(mén)課的課程號(hào)(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號(hào)。(2)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。(3)若根據(jù)給定的條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔?，否則將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式自行設(shè)計(jì)。【測(cè)試數(shù)據(jù)】學(xué)期總數(shù)：65；學(xué)分上限：103；該專業(yè)共開(kāi)設(shè)12門(mén)課，課程號(hào)從CO1到C12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見(jiàn)教科書(shū)圖7.26。22. 校園導(dǎo)游咨詢【問(wèn)題描述】設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)?！净疽蟆?1) 設(shè)計(jì)你所在學(xué)校的校園平面圖,所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn),存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息;以邊表示路徑,存放路徑長(zhǎng)度等相關(guān)信息。(2)為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。(3)為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢,即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑?！緶y(cè)試數(shù)據(jù)】以合肥學(xué)院南艷湖校區(qū)為例。【實(shí)現(xiàn)提示】一般情況下,校園的道路是雙向通行的,可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn)和邊均 含有相關(guān)信息?！具x作內(nèi)容】(1) 求校園圖的關(guān)節(jié)點(diǎn)。(2) 提供圖中任意景點(diǎn)問(wèn)路查詢 , 即求任意兩個(gè)景點(diǎn)之間的所有路徑。(3) 提供校園圖中多個(gè)景點(diǎn)的最佳訪問(wèn)路線查詢 , 即求途經(jīng)這多個(gè)景點(diǎn)的最佳 ( 短 )路徑。(4) 校園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。(5) 擴(kuò)充道路信息 , 如道路類別 ( 車(chē)道、人行道等 ) 、沿途景色等級(jí) , 以至可按客人所需分別查詢?nèi)诵新窂交蜍?chē)行路徑或觀景路徑等。(6) 擴(kuò)充每個(gè)景點(diǎn)的鄰接景點(diǎn)的方向等信息 , 使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。(7) 實(shí)現(xiàn)校園導(dǎo)游圖的仿真界面。23. 圖書(shū)管理【問(wèn)題描述】圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括:對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。【基本要求】1每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、著者、現(xiàn)存量和總庫(kù)存量等五項(xiàng)。2作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào)(即關(guān)鍵字進(jìn)行的，所以要用B樹(shù)24樹(shù)對(duì)書(shū)號(hào)建立索引，以獲得高效率。3系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及其功能定義如下: 采編入庫(kù)z新購(gòu)入一種書(shū)，經(jīng)分類和確定書(shū)號(hào)之后登記到圖書(shū)賬目中去。如果這種書(shū)在賬中已有，則只將總庫(kù)存量增加。 清除庫(kù)存:某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)賬目中注銷。 借閱:如果一種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。 歸還z注銷對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。 顯示:以凹入表的形式顯示B樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的?！緶y(cè)試數(shù)據(jù)】入庫(kù)書(shū)號(hào):35，16，18，70，5，50，22，60，13，17，12，45，25，氈，15，90，30，7然后清除:45，90，50，22，42其余數(shù)據(jù)自行設(shè)計(jì)。由空樹(shù)開(kāi)始，每插入刪除一個(gè)關(guān)鍵字后就顯示B樹(shù)的狀態(tài)。【實(shí)現(xiàn)提示】(1)24樹(shù)的查找算法是基礎(chǔ)，入庫(kù)和清除操作都要調(diào)用。難點(diǎn)在于刪除關(guān)鍵字的算法，因而只要算法對(duì)2-3樹(shù)適用就可以了，暫時(shí)不必追求高階B樹(shù)也適用的刪除算法。(2)每種書(shū)的記錄可以用動(dòng)(或靜)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。借閱登記信息可以鏈接在相應(yīng)的那種書(shū)的記錄之后。【選作內(nèi)容】(l)將一次會(huì)話過(guò)程(即程序一次運(yùn)行)中的全部人機(jī)對(duì)話記入一個(gè)日志文件log中去。(2)增加列出某著者全部著作名的操作。思考如何提高這一操作的效率，參閱教科書(shū)12.6.2節(jié)。(3增加列出某種書(shū)狀態(tài)的操作。狀態(tài)信息除了包括這種書(shū)記錄的全部信息外還包括最早到期(包括已逾期)的借閱者證號(hào)，日期可用整數(shù)實(shí)現(xiàn)，以求簡(jiǎn)化。(4)增加預(yù)約借書(shū)功能。24. 多關(guān)鍵字排序【問(wèn)題描述】多關(guān)鍵字的排序有其一定的實(shí)用范圍。例如:在進(jìn)行高考分?jǐn)?shù)處理時(shí)，除了需對(duì)總分進(jìn)行排序外，不同的專業(yè)對(duì)單科分?jǐn)?shù)的要求不同，因此尚需在總分相同的情況下，按用戶提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序?！净疽蟆?1)假設(shè)待排序的記錄數(shù)不超過(guò)10000，表中記錄的關(guān)鍵字?jǐn)?shù)不超過(guò)5，各個(gè)關(guān)鍵字的范圍均為0至100。按用戶給定的進(jìn)行排序的關(guān)鍵字的優(yōu)先關(guān)系，輸出排序結(jié)果。(2)約定按LSD法進(jìn)行多關(guān)鍵字的排序。在對(duì)各個(gè)關(guān)鍵字進(jìn)行排序時(shí)采用兩種策略:其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用分配和收集的方法。并綜合比較這兩種策略?！緶y(cè)試數(shù)據(jù)】由隨機(jī)數(shù)產(chǎn)生器生成。【實(shí)現(xiàn)提示】用5至8組數(shù)據(jù)比較不同排序策略所需時(shí)間。由于是按LSD方法進(jìn)行排序，則對(duì)每個(gè)關(guān)鍵字均可進(jìn)行整個(gè)序列的排序，但在利用通常的內(nèi)部排序方法進(jìn)行排序時(shí)，必須選用穩(wěn)定的排序方法。借助分配和收集策略進(jìn)行的排序，如同一趟基數(shù)排序，由于關(guān)鍵字的取值范圍為0至100，則分配時(shí)將得到104個(gè)鏈表?！具x作內(nèi)容】增添按MSD策略進(jìn)行排序，并和上述兩種排序策略進(jìn)行綜合比較。25手機(jī)通訊錄的制作設(shè)計(jì)目的：用數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)。編寫(xiě)一個(gè)手機(jī)通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)應(yīng)用到實(shí)際軟件開(kāi)發(fā)中去。設(shè)計(jì)內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能：（1）. 添加信息（2）. 顯示信息：它可以按按固定電話排列、按手機(jī)、聯(lián)系人名字的拼音順序排列。（3）. 查找：可以不同的關(guān)鍵字作為查找的依據(jù)，進(jìn)行查找;（4）. 編輯信息（5）. 刪除信息（6）. 保存到文件：將以上信息保存到文件，以便下次運(yùn)行程序時(shí)能載入此通信錄設(shè)計(jì)要求：（1）. 每條信息至包含 ：姓名（NAME ）,手機(jī)號(hào)，固定電話號(hào)，電子郵箱，QQ號(hào)碼，城市（CITY）郵編（EIP）幾項(xiàng)（2）. 作為一個(gè)完整的系統(tǒng)，應(yīng)具有友好的界面和較強(qiáng)的容錯(cuò)能力（3）. 上機(jī)能正常運(yùn)行，并寫(xiě)出課程設(shè)計(jì)報(bào)告26 奇數(shù)階幻方求解要求必須在空間復(fù)雜度為O(N)的要求下實(shí)現(xiàn)N階幻方的輸出。Problem description 幻方是一種很有意思的數(shù)字矩陣，在很早著名的九宮八卦陣就與幻方有關(guān)?；梅降亩x為： 1 到 N*N 的整數(shù)填入N*N的方格中，每行和每列以及對(duì)角線的數(shù)字之和必須是相等的。你作為八卦公司的頂級(jí)程序員，現(xiàn)在需要你解決一個(gè)問(wèn)題，將任意奇數(shù)階的幻方找出來(lái)。 Input 輸入包括多個(gè)測(cè)試集，每行為一個(gè)正奇數(shù)N(1 = N 1000)，0作為輸入的結(jié)束且不需要處理。 Output 對(duì)于輸入的每一個(gè)N， 輸出一個(gè)它所對(duì)應(yīng)的N階幻方，如果存在多個(gè)，任意一個(gè)即可。每個(gè)幻方為N*N的矩陣，