【正文】 ) 、沿途景色等級 , 以至可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等。(6) 擴(kuò)充每個景點的鄰接景點的方向等信息 , 使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。(7) 實現(xiàn)校園導(dǎo)游圖的仿真界面。6. 最小生成樹問題【問題描述】若要在n個城市之間建設(shè)通信網(wǎng)絡(luò),只需要架設(shè)n1條線路即可。如何以最低的經(jīng)濟(jì)代價建設(shè)這個通信網(wǎng),是一個網(wǎng)的最小生成樹問題?！净疽蟆?1) 利用克魯斯卡爾算法求網(wǎng)的最小生成樹。(2) 實現(xiàn)教科書 節(jié)中定義的抽象數(shù)據(jù)類型 MFSet 。以此表示構(gòu)造生成樹過程中的連通分量。(3)以圖形和文本兩種形式輸出生成樹中各條邊以及他們的權(quán)值?！緦崿F(xiàn)提示】通信線路一旦建立,必然是雙向的。因此,構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖 的頂點數(shù)不超過 30 個 , 并為簡單起見、網(wǎng)中邊的權(quán)值設(shè)成小于 100 的整數(shù) , 可利用 C 語言 提供的隨機(jī)數(shù)函數(shù)產(chǎn)生。圖的存儲結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊 , 此題的存儲 結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法 , 也不選用鄰接表 , 而是以存儲邊 ( 帶權(quán) ) 的數(shù)組表示 圖。【選作內(nèi)容】 利用堆排序 ( 參見教科書 節(jié) ) 實現(xiàn)選擇權(quán)值最小的邊。7. 表達(dá)式類型的實現(xiàn)【問題描述】一個表達(dá)式和一棵二叉樹之間,存在著自然的對應(yīng)關(guān)系。寫一個程序,實現(xiàn)基于二叉樹表示的算術(shù)表達(dá)式Expression的操作?！净疽蟆考僭O(shè)算術(shù)表達(dá)式 Expression 內(nèi)可以含有變量 (a~z) 、常量 (0~9) 和二元運算符 (+, ,*, /,^(乘冪))。實現(xiàn)以下操作：(1)ReadExpk(E) 一一以字符序列的形式輸入語法正確的前綴表示式并構(gòu)造表達(dá)式E。(2)WriteExpk(E) 一一用帶括弧的中綴表示式輸出表達(dá)式 E 。(3)Assign(V,c) 一一實現(xiàn)對變量 V 的賦值 (V=c), 變量的初值為 0 。(4)Value(E) 一一對算術(shù)表達(dá)式E求值。(5)CompoundExpr(P,E1,E2) 一一構(gòu)造一個新的復(fù)合表達(dá)式(E1)P(E２)．【測試數(shù)據(jù)】(1) 分別輸入 0。　a。91。+a*bc。+*5^x2 *8x。+++ *3^ X3*2^ x2x6并輸出。(2) 每當(dāng)輸入一個表達(dá)式后,對其中的變量賦值,然后對表達(dá)式求值?！緦崿F(xiàn)提示】(1) 在讀入表達(dá)式的字符序列的同時,完成運算符和運算數(shù)(整數(shù))的識別處理以及相應(yīng)的運算。(2) 在識別出運算數(shù)的同時,要將其字符形式轉(zhuǎn)換成整數(shù)形式。(3) 用后根遍歷的次序?qū)Ρ磉_(dá)式求值。(4) 用中綴表示輸出表達(dá)式E時 ,適當(dāng)添加括號,以正確反映運算的優(yōu)先次序?！具x作內(nèi)容】(1) 增加求偏導(dǎo)數(shù)運算 Diff (E,V)一一求表達(dá)式 E 對變量V的導(dǎo)數(shù)。(2) 在表達(dá)式中添加三角函數(shù)等初等函數(shù)的操作。(3) 增加常數(shù)合并操作MergeConskE) 一一合并表達(dá)式 E 中所有常數(shù)運算。例如 , 對表達(dá)式 E=(2+3a) *(b+3*4)進(jìn)行合并常數(shù)的操作后,求得 E=(5a)*(b+12) 。(4)以表達(dá)式的原書寫形式輸入。8. 全國交通咨詢模擬【問題描述】出于不同目的的旅客對交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的時間盡可能短,出門旅游的游客則期望旅費盡可能省,而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個全國城市間的交通咨詢程序,為旅客提供兩種或三種最優(yōu)決策的交通咨詢。【基本要求】(1) 提供對城市信息進(jìn)行編輯 ( 如 : 添加或刪除 ) 的功能。(2) 城市之間有兩種交通工具、火車和飛機(jī)。提供對列車時刻表和飛機(jī)航班進(jìn)行編輯( 增設(shè)或刪除 ) 的功能。(3) 提供兩種最優(yōu)決策 : 最快到達(dá)或最省錢到達(dá)。全程只考慮一種交通工具。(4) 旅途中耗費的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間。(5) 咨詢以用戶和計算機(jī)的對話方式進(jìn)行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具 , 輸出信息 : 最快需要多長時間才能到達(dá)或者最少需要多少旅費才能到達(dá) , 并詳細(xì)說明依次于何時乘坐哪一趟列車或哪一次班機(jī)到何地?！緶y試數(shù)據(jù)】參考教科書 節(jié)圖 的全國交通圖 , 自行設(shè)計列車時刻表和飛機(jī)航班。【實現(xiàn)提示】(1) 對全國城市交通圖和列車時刻表及飛機(jī)航班表的編輯 , 應(yīng)該提供文件形式輸入 和鍵盤輸入兩種方式。飛機(jī)航班表的信息應(yīng)包括 : 起始站的出發(fā)時間、終點站的到達(dá)時間 和票價 。 列車時刻表則需根據(jù)交通圖給出各個路段的詳細(xì)信息；例如：。圖 的交通圖 , 對從北京到上海的火車 , 需給出北京至天津、天津至徐州及徐州至上海 各段的出發(fā)時間、到達(dá)時間及票價等信息。(2 )以鄰接表作交通圖的存儲結(jié)構(gòu)，表示邊的結(jié)點內(nèi)除含有鄰接點的信息外，還應(yīng)包 括交通工具、路程中消耗的時間和花費以及出發(fā)和到達(dá)的時間等多項屬性。【選作內(nèi)容】增加旅途中轉(zhuǎn)次數(shù)最少的最優(yōu)決策。ch6 存儲管理、查找和排序與前五個實習(xí)單元不同，本實習(xí)單元旨在集中對幾個專門的問題作較為深入的探討和理解，不強調(diào)對某些特定的編程技術(shù)的訓(xùn)練。動態(tài)存儲管理問題的實習(xí)遇到高級語言限制方面的困難。盡管與實際情況有差距，例如，求得伙伴地址以后不能用它尋址得到伙伴的頭，但還是較完整地體現(xiàn)了伙伴系統(tǒng)的主要框架和意圖。希望選擇此題的讀者認(rèn)真思考:如何修改自己的程序才能得到實用的系統(tǒng)。散列技術(shù)是索引技術(shù)中的一種非常重要和有效的技術(shù)，但與實際問題(主要是關(guān)鍵字集的形態(tài)和特點)關(guān)系甚密。哈希函數(shù)的選擇和沖突解決方法的選用都帶有較強的技巧性和經(jīng)驗性，自己動手試一試是非常有益的：平衡樹和鍵樹有其一定的實用范圍：B樹是動態(tài)索引文件的一種極好的組織方式，也是物理數(shù)據(jù)庫實現(xiàn)的基本技術(shù)。盡管此題難度大了一些，但給讀者帶來的提高也相應(yīng)地大些，其中所含的程序設(shè)計技巧也比較多。，還可以給讀者以啟發(fā):對于一個一般的問題而言，開發(fā)高效算法的可能性如何?應(yīng)該如何尋找和構(gòu)造高效算法?，的排序問題。1. 伙伴存儲管理系統(tǒng)演示【問題描述】伙伴存儲管理系統(tǒng)是一種巧妙而有效的方法。試寫一個演示系統(tǒng)，演示分配和回收存儲塊前后的存儲空間狀態(tài)變化?！净疽蟆砍绦驊?yīng)不斷地從終端讀取整數(shù)n。每個整數(shù)是一個請求。如果n0，則表示用戶申請大小為n的空間：如果n0，則表示歸還起始地址(即下標(biāo))為n的塊才日果n=0，則表示結(jié)束運行。每讀入一個數(shù)，就處理相應(yīng)的請求，并顯示處理之后的系統(tǒng)狀態(tài)。系統(tǒng)狀態(tài)由占用表和空閑表構(gòu)成。顯示系統(tǒng)狀態(tài)意味著顯示占用表中各塊的始址和長度，以及空閑表中各種大小的空閑塊的始址和長度?！緶y試數(shù)據(jù)】l，一①1，3，4，4，4，一①4，一①3，2，2，2，2，一②4，一①2，一②2，一③2，一④2，一③4，40，0。其中，③，2表示第③次申請大小為2的空間使得塊的始址。其余類推?！緦崿F(xiàn)提示】可以取m=5，即Spacesize=25，數(shù)據(jù)結(jié)構(gòu)如下:Typedef struct BlkHeader{BlkHeader *llink，*rlink；int tag；Int kvalue；Int blkstart； //塊起始地址}BlkHeader，*Link；Typedef struct{ Int blksize； Link first；}ListHeader；Typedef char ell； //cell也可以是其他單位主要變量是: cell space[Spacesize] //被管理的空間 ListHeader avail[m+1]； //可用空間表 Link ailocated；.//占用表的表頭指針在這里，我們把每塊的塊頭分離出來，通過blkstart域與相應(yīng)的塊建立聯(lián)系。每個塊一旦被分配，其塊頭就進(jìn)入占用表，其中的各塊頭由rlink域鏈接在一起。tag域?qū)嶋H上不起作用，但為了與實際伙伴管理系統(tǒng)更接近，沒有把它去掉。顯然，在這種模擬實現(xiàn)方法中，不對數(shù)組space作任何引用或賦值?！具x作內(nèi)容】(1)同時還用直觀的圖示方式顯示狀態(tài)。(2)寫一個隨機(jī)地申請和歸還各種規(guī)格的存儲塊的函數(shù)考驗?zāi)愕幕锇橄到y(tǒng)。2. 哈希表設(shè)計【問題描述】針對某個集體(比如你所在的班級)中的人名設(shè)計一個哈希表，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序?！净疽蟆考僭O(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測再散列法處理沖突。【測試數(shù)據(jù)】取讀者周圍較熟悉的30個人的姓名。【實現(xiàn)提示】如果隨機(jī)函數(shù)自行構(gòu)造，則應(yīng)首先調(diào)整好隨機(jī)函數(shù)，使其分布均勻。人名的長度均不超過19個字符(最長的人名如z莊雙雙(ZhangStmarlgShang〉。字符的取碼方法可直接利用C語言中的toascii函數(shù)，并可對過長的人名先作折疊處理。【選作內(nèi)容】(1)從教科書上介紹的幾種晗希函數(shù)構(gòu)造方法中選出適用者并設(shè)計幾個不同的哈希函數(shù)，比較它們的地址沖突率(可以用更大的名字集合作試驗〉。(2)研究這30個人名的特點，努力找一個晗希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。(3)在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考查平均查找長度的變化和造好的晗希表中關(guān)鍵字的聚簇性。3. 圖書管理【問題描述】圖書管理基本業(yè)務(wù)活動包括:對一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計一個圖書管理系統(tǒng)，將上述業(yè)務(wù)活動借助于計算機(jī)系統(tǒng)完成?！净疽蟆俊?〉每種書的登記內(nèi)容至少包括書號、書名、著者、現(xiàn)存量和總庫存量等五項?！?〉作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項基本業(yè)務(wù)活動都是通過書號(即關(guān)鍵字〉進(jìn)行的，所以要用B樹〈24樹〉對書號建立索引，以獲得高效率?！?〉系統(tǒng)應(yīng)實現(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)。【實現(xiàn)提示】(1)24樹的查找算法是基礎(chǔ)，入庫和清除操作都要調(diào)用。難點在于刪除關(guān)鍵字的算法，因而只要算法對23樹適用就可以了，暫時不必追求高階B樹也適用的刪除算法。(2)每種書的記錄可以用動(或靜)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。借閱登記信息可以鏈接在相應(yīng)的那種書的記錄之后?！具x作內(nèi)容】 (l)將一次會話過程(即程序一次運行)中的全部人機(jī)對話記入一個日志文件log中去。 (2)增加列出某著者全部著作名的操作。思考如何提高這一操作的效率。 (3〉增加列出某種書狀態(tài)的操作。狀態(tài)信息除了包括這種書記錄的全部信息外還包括最早到期(包括已逾期)的借閱者證號，日期可用整數(shù)實現(xiàn)，以求簡化。 (4)增加預(yù)約借書功能。4. 平衡二叉樹操作的演示【問題描述】利用平衡二叉樹實現(xiàn)一個動態(tài)查找表?！净疽蟆繉崿F(xiàn)動態(tài)查找表的三種基本功能:查找、插入和刪除?！緶y試數(shù)據(jù)】 由讀者自行設(shè)定?！緦崿F(xiàn)提示】 (1)初始，平衡二叉樹為空樹，操作界面給出查找、插入和刪除三種操作供選擇。每種操作均要提示輸入關(guān)鍵字。每次插入或刪除一個結(jié)點后，應(yīng)更新平衡二叉樹的顯示。 (2)，也可以采用圖形界面畫出樹形。(3)教科書已給出查找和插入算法，本題重點在于對刪除算法的設(shè)計和實現(xiàn)。假設(shè)要刪除關(guān)鍵字為x的結(jié)點。如果x不在葉子結(jié)點上，則用它左子樹中的最大值或右子樹中的最小值取代x。如此反復(fù)取代，直到刪除動作傳遞到某個葉子結(jié)點。刪除葉子結(jié)點時，若需要進(jìn)行平衡變換，可采用插入的平衡變換的反變換(如，左子樹變矮對應(yīng)于右子樹長高)。【選作內(nèi)容】(1)合并兩棵平衡二叉樹。(2)把一棵平衡二叉樹分裂為兩棵平衡二叉樹，使得在一棵樹中的所有關(guān)鍵字都小于或等于工，另一棵樹中的任一關(guān)鍵字都大于幾5. 英語詞典的維護(hù)和識別【問題描述】Trie樹通常作為一種索引樹，這種結(jié)構(gòu)對于大小變化很大的關(guān)鍵字特別有用。利用Trie樹實現(xiàn)一個英語單詞輔助記憶系統(tǒng)，完成相應(yīng)的建表和查表程序?！净疽蟆坎幌薅═rie樹的層次，每個葉子結(jié)點只含一個關(guān)鍵字，采用單字符逐層分割的策略，實現(xiàn)Trie樹的插入、刪除和查詢的算法，查詢可以有兩種方式:查詢一個完整的單詞或者查詢以某幾個字母開頭的單詞?！緶y試數(shù)據(jù)】 自行設(shè)定?！緦崿F(xiàn)提示】以實習(xí)三中已實現(xiàn)的串類型或C語言中提供的長度不限的串類型表示關(guān)鍵字，葉子結(jié)點內(nèi)應(yīng)包括英語單詞及其注音、釋義等信息?！具x作內(nèi)容】限定Trie樹的層次，每個葉子結(jié)點可以包含多個關(guān)鍵字。6. 內(nèi)部排序算法比較【問題描述】在教科書中，各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受?！净疽蟆?1)對以下6種常用的內(nèi)部排序算法進(jìn)行比較z起泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序、堆排序。(2)待排序表的表長不小于1005其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生：至少要用5組不同的輸入數(shù)據(jù)作比較：比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)(關(guān)鍵字交換計為3次移動)。(