【正文】 2767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當(dāng)于按 32768 進(jìn) 制存放，在十進(jìn)制與 32768 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個結(jié)點中僅存十進(jìn)制的 4 位，即不超過 9999 的非負(fù)整數(shù)，整個鏈表表示為萬進(jìn)制。 （ 2）可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。 、并、差運算 問題描述：編制一個能演示執(zhí)行集合的交、并和差運算的程序。 基本要求：集合元素用小寫英文字母，執(zhí)行各種操作應(yīng)以對話方式執(zhí)行。 算法要點：利用單鏈表 表示集合；理解好三種運算的含義 問題描述：文字研究人員需要統(tǒng)計某篇英文小說中某些特定單詞的出現(xiàn)次數(shù)和位置，試寫出一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)。這稱為“文學(xué)研究助手”。 算法輸入：文本文件和詞集。 算法輸出：單詞出現(xiàn)的次數(shù)，出現(xiàn)位置所在行的行號（同一行出現(xiàn)兩次的只輸出一個行號）。 算法要點：（ 1）文本串非空且以文件形式存放。 （ 2）單詞定義：用字母組成的字符序列，中間不含空格，不區(qū)分大小寫。 （ 3）待統(tǒng)計的單詞不跨行出現(xiàn)，它或者從行首開始，或者前置 一個空格。 （ 4）數(shù)據(jù)結(jié)構(gòu)采用二維鏈表，單詞結(jié)點鏈接成一個鏈表，每個單詞的行號組成一個鏈表，單詞結(jié)點作為行號鏈表的頭結(jié)點。 60 關(guān)鍵路徑算法 [問題描述 ] AOE 網(wǎng) (即邊表示活動的網(wǎng)絡(luò) )，在某些工程估算方面非常有用。它可以使人們了解：（ 1）研究某個工程至少需要多少時間？（ 2）哪些活動是影響工程進(jìn)度的關(guān)鍵 ? 在 AOE 網(wǎng)絡(luò)中，從源點到匯點的有向路徑可能不止一條，但只有各條路徑上所有活動都完成了，這個工程才算完成。因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有 活動的持續(xù)時間之和，這條路徑就叫做關(guān)鍵路徑（ critical path）。 [設(shè)計步驟 ] 1 以某一工程為藍(lán)本，采用圖的結(jié)構(gòu)表示實際的工程計劃時間。 2 調(diào)查并分析和預(yù)測這個工程計劃每個階段的時間。 3 用調(diào)查的結(jié)果建立 AOE 網(wǎng)，并用圖的形式表示。 4 用 CreateGraphic ()函數(shù)建立圖的鄰接表存儲結(jié)構(gòu)，能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中。 5 用 SearchMaxPath()函數(shù)求出最大路徑，并打印出關(guān)鍵路徑。 6 編寫代碼并調(diào)試、測試通過。 [測試數(shù)據(jù) ] 利用教材 p185 的圖 （ a）中的數(shù)據(jù)調(diào)試程序。 [實現(xiàn)提示 ] 實現(xiàn)的關(guān)鍵和難點在于對四個術(shù)語的理解和應(yīng)用即： ei表示頂點 vi 所代表的事件的最早發(fā)生時間； li 表示頂點 vi所代表的事件的最遲發(fā)生時間； Tes(i,j)表示活動 ak 的最早開工時間； Tls(i,j)表示活動 ak 的最遲開工時間。活動 ak 為關(guān)鍵活動的充分必要條件是活動 ak的最早開工時間與它的最遲開工時間相等。 61. 表達(dá)式求值 [問題描述 ] 當(dāng)用戶輸入一個合法的算術(shù)表達(dá)式后，能夠返回正確的結(jié)果。能夠計算的運算符包括：加、減、乘、除、括號；能夠計算的操作數(shù)要求在實 數(shù)范圍內(nèi)；對于異常表達(dá)式能給出錯誤提示。 [設(shè)計步驟 ] 1 首先置操作數(shù)棧為空棧，表達(dá)式起始符＃為運算符棧的棧底元素； 2 依次掃描表達(dá)式中每個字符，若是操作數(shù)則進(jìn) OPND 棧；若是運算符，則和 OPTR 棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達(dá)式求值完畢。 3 先做一個適合個位的 +*/運算 , 其次就要考慮到對 n 位和小數(shù)點的運算。 [測試數(shù)據(jù) ] （ 1）請輸入您所求的表達(dá)式 3*(72)+5 多項式的結(jié)果是 : 20 （ 2）請輸入您所求的表達(dá)式 *(12+18)23 多項式的結(jié)果是 : [實現(xiàn)提示 ] 可以參考教材 p53 的算法 的描述。 假定在一舞會上，男士排成一隊，女士排成一隊。跳舞開始時，依次從男隊和女隊的隊頭各出一人配成舞伴。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲。 設(shè)計要求：模擬上述舞伴系統(tǒng)，并能計算對于任何男士 A 和女士 B在哪一輪舞曲中的 k次跳舞？ 設(shè)計要求：給定一個二元樹的先序遍歷或后序遍歷結(jié)果，判定其是否為平衡二元樹。 64. 停車場管理系統(tǒng) 設(shè)計一個停車場管理系統(tǒng)，模擬停車場的運作，通過此程序具備以下功能： 要求以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理； 要求處理的數(shù)據(jù)元素包括三個數(shù)據(jù)項：汽車 “到達(dá) ”或 “離去 ”信息、汽車牌照號碼及到達(dá)或離去的時刻； 該系統(tǒng)完成以下功能：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）； 要求棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。 。 每條航線所涉及的信息有：終點站名、航班號、飛機號、飛機周日（星期幾）、乘員定 額、余票量、訂定票的客戶名單（包括姓名、訂票量、艙位等級 1， 2 或 3）以及等候替補的客戶名單（包括姓名、所需數(shù)量）。 系統(tǒng)能實現(xiàn)的操作和功能如下： 查詢航線：根據(jù)客戶提出的終點站名輸出如下信息：航班號、飛機號、星期幾飛行，最近一天航班的日期和余票額； 承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求（航班號、訂票數(shù)額）查詢該航班票額情況，若有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票少余訂票額，則需重新詢問客戶要求。若需要，可登記排隊候補； 承辦退票業(yè)務(wù)：根據(jù)客戶提出的情況（日期、航班號），為客戶辦理退票手續(xù)，然 后查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其它排隊候補的客戶。 實現(xiàn)提示：兩個客戶名單可分別由線性表和隊列實現(xiàn)。為查找方便，已訂票客戶的線性表應(yīng)按客戶姓名有序，并且，為了插入和刪除方便，應(yīng)以鏈表作為存儲結(jié)構(gòu)。由于預(yù)約人數(shù)無法預(yù)計，隊列也應(yīng)以鏈表作為存儲結(jié)構(gòu)。 [問題描述 ] 設(shè)有一個可以停放 n 輛汽車的狹長停車場，它只有一個大門可以供車輛進(jìn)出。車輛按到達(dá)停車場時間的早晚依次從停車場最里面向大門口處停放 (最先到達(dá)的第一輛 車放在停車場的最里面 )。如果停車場已放滿 n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進(jìn)入停車場。停車場內(nèi)如有某輛車要開走，在它之后進(jìn)入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進(jìn)場。每輛車在離開停車場時，都應(yīng)根據(jù)它在停車場內(nèi)停留的時間長短交費。如果停留在便道上的車未進(jìn)停車場就要離去，允許其離去，不收停車費，并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。 [實現(xiàn)要求 ] 要求程序輸出每輛車到達(dá)后的停 車位置 (停車場或便道上 )，以及某輛車離開停車場時應(yīng)交納的費用和它在停車場內(nèi)停留的時間。 [實現(xiàn)提示 ] 汽車的模擬輸入信息格式可以是： (到達(dá)／離去，汽車牌照號碼，到達(dá)／離去的時刻 )。例如， (?A?， 1， 5)表示 1 號牌照車在 5 這個時刻到達(dá)，而 (?D?， 5， 20)表示 5 號牌照車在 20 這個時刻離去。整個程序可以在輸入信息為 (?E?， 0， 0)時結(jié)束。本題可用棧和隊列來實現(xiàn)。 【問題描述】處于對不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的 游客則希望旅費盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。 【基本要求】（ 1）提供對城市信息進(jìn)行編輯（如：添加或刪除）的功能。 （ 2）城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班進(jìn)行編輯（增設(shè)或刪除）的功能。 （ 3）提供兩種最優(yōu)決策：最快到達(dá)或最省錢到達(dá)。全程只考慮一種交通工具。 （ 4）旅途中耗費的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間。 （ 5）咨詢以用戶和計算機的對話方式進(jìn)行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達(dá)或者最少需要多少旅費才能到達(dá)，并詳細(xì)說明依次于何時乘坐哪一趟列車或哪一次班機到何地。 【測試數(shù)據(jù)】 【實現(xiàn)提示】（ 1）對全國城市交通圖和班車時刻表及飛機航班表的編輯，應(yīng)該提供文件形式輸入和鍵盤輸入兩種方式。飛機航班表的信息應(yīng)包括：起始站的出發(fā)時間、終點站的到達(dá)時間和票價；列車時刻表則需根據(jù)交通圖 給出各個路段的詳細(xì)信息，例如：對于從北京到上海的火車，需給出北京至天津、天津至徐州及徐州至各段的出發(fā)時間、到達(dá)時間和票價信息。 呼和浩特 北京 大連 西寧 武漢 南昌 842 137 674 825 672 徐州 397 烏魯木齊 哈爾濱 長春 沈陽 天津 鄭州西安 蘭州 成都 上海 昆明 貴陽 株州 福州 柳州 廣州 深圳 南寧 1892 216 1145 668 1100 967 639 907 349 676 511 242 305 704 651 622 367 409 255 607 675 140 534 （ 2）以鄰接表作交通圖的存儲結(jié)構(gòu)，表示邊的結(jié)點內(nèi)除含有鄰接點的信息外，包括交通工具、路程中消耗的時間和花費以及出發(fā)和到達(dá)的時間等多項屬性。 /解壓器 【問題描述】 為了節(jié)省存儲空間，常常需要把文本文件采用壓縮編碼的方式儲存。例如：一個包含 1000 個 x的字符串和 2021 個 y 的字符串的文本文件在不壓縮時占用的空間為 3002 字節(jié)（每個 x 或每個y 占用一個字節(jié)，兩個字節(jié)用來表示串 的結(jié)尾）。同樣是這個文件，采用游程長度編碼（ runlength coding），可以存儲為字符串 1000x2021y，僅為 10 個字母，占用 12 個字節(jié)。若采用二進(jìn)制表示游程長度（ 1000 和 2021）可以進(jìn)一步節(jié)約空間。如果每個游程長度占用 2個字節(jié)，則可以表示的最大游程長度為 2*pow(16)，這樣，上例中的字符串只需要用 8 個字節(jié)來存儲。當(dāng)要讀取編碼文件時，需要對其進(jìn)行解碼。由壓縮器（ pressor）對文件進(jìn)行編碼，由解壓器（ depressor）進(jìn)行解碼。 ①（ 1）長度 游程編碼的壓縮 /解壓； +（ 2） LZW 壓縮 /解壓（散列）； ②（ 1）長度 游程編碼的壓縮 /解壓； +（ 3）霍夫曼編碼壓縮 /解壓 (霍夫曼樹 ) 【基本要求】 要求選用二種壓縮 /解壓策略實現(xiàn)壓縮 /解壓器 [（ 1）為必選 ]。輸入的為本文文件（ .txt），輸出的為一種自定義的文件（ .nz）?？紤]當(dāng)構(gòu)成文本的字符集合為 {a,b,c,……,z,0,1,2,…9} 時，請用實例測試你的壓縮 /解壓器。你的壓縮器會不會出現(xiàn)抖動？（壓縮后的文本比原來的還要大）。擴充構(gòu)成文本的字符集合以便使它適應(yīng)更一般的情況。 【實現(xiàn)提示】 LZW：由 Lempel、 Ziv 和 Welch 這三位科學(xué)家所開發(fā)的技術(shù)。該方法把文本的字符串映射為編碼，首先，為該文本中所有可能出現(xiàn)的字母分別分配一個代碼。例如：要壓縮的對象是aaabbbbbbbaabaaba，由 a 和 b 組成。為 a 分配代碼 0,為 b 分配代碼 1。字符串和編碼的關(guān)系被存儲在字典中。 字典如下： Key 0 1 2 3 4 5 6 7 Code A b Aa aab bb bbb bbba aaba LZW 壓縮器不斷的在輸入文件中尋找在字典中出現(xiàn)的最長的前綴 p,并輸出其相應(yīng)的代碼。若輸入文件的下一個字符為 c，則為 pc 分配下一個 代碼，并插入字典，這種策略稱為 LZW 規(guī)則。相反，在解壓時，編碼表由壓縮文件重新構(gòu)造， LZW 原則使這種重建成為可能。 如上例子，壓縮時，文件中第一個在字典中出現(xiàn)的最長前綴是 a, 輸出其編碼 0,然后為字符串 aa 分配代碼 2，并插入到字典中。余下的字符串在字典中出現(xiàn)的最長前綴是 aa,輸出 aa 的對應(yīng)代碼 2，同時為字符串 aab 分配代碼 3 并將其插入到字典中。依次類推，由此，輸出 0214537 解壓時，要輸入代碼，然后用代碼所表示的文本來替換這些代碼。代碼到文本的映射可按下面的方法重建：首先把分配給單一字母 的代碼插入到字典中。象前面一樣，字典的入口為keycode 對。然而此時是根據(jù)給定的代碼（ key）去尋找相應(yīng)的入口（而不是根據(jù)文本 Code）。壓縮文件中的第一個代碼對應(yīng)于單一的字母，因此可以由該字母代替。對于壓縮文件中的其他代碼 p,要考慮兩種情況： 1）在字典中； 2）不在字典中。 在 1）情況下，找到 p 對應(yīng)的文本 text(p)輸出。并且，根據(jù)壓縮原理可知，若在壓縮文件中代碼 q 寫在 p 之前且 text(q)是與 q 對應(yīng)的文本，則壓縮器會為文本 text(q)（其后緊跟 fc(p)， text(p)的第一個字符）分配一新代碼。 因此在字