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