【正文】 書例 62 中的數(shù)據(jù)調(diào)試程序。 （ 2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“ THIS PROGRAM IS MY FAVORITE ”。 字符 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 實(shí)現(xiàn)提示： （ 1）編碼結(jié)果以文本方式存儲(chǔ)在文件 CodeFile 中。 （ 2） 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“ Q”，表示行 Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“ Q”為止。 （ 3）在程序的一次執(zhí)行過程中，第一次執(zhí)行 I， D 或 C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行 I 命令，因?yàn)槲募?hfmTree 可 能早已建好。 選做內(nèi)容 ： （ 1）上述文件 CodeFile 中的每個(gè)“ 0”或“ 1”實(shí)際上占用了一個(gè)字節(jié)的空間，只起到示意或模擬的作用。為最大限度的利用碼點(diǎn)存儲(chǔ)能力，試改寫你的系統(tǒng)，將編碼結(jié)果以二進(jìn)制形式存放在文件 CodeFile 中。 （ 2） 修改你的系統(tǒng)，實(shí)現(xiàn)對(duì)你的系統(tǒng)的原程序的編碼和譯碼 （主要是將行尾符編 /譯碼問題）。 （ 3） 實(shí)現(xiàn)各個(gè)轉(zhuǎn)換操作的源 /目文件，均由用戶在選擇此操作時(shí)指定。 15. 稀疏矩陣運(yùn)算器 問題描述：（需求分析和背景意義） 稀疏矩陣是指那些多數(shù)元素為零的 矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 以“帶行邏輯鏈接信息”的三元組順表示稀疏矩陣，實(shí)現(xiàn)兩矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出。 測試數(shù)據(jù)： + = = = 實(shí)現(xiàn)提示： 首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別兩個(gè)矩陣的行、列數(shù)對(duì)于所要求做的運(yùn)算是否相匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過 20。 程序可以對(duì)輸入的三元組進(jìn)行限制，例如，按行優(yōu)先。注意研究教科書 節(jié)中的算法，以便提高計(jì)算效率。 在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可用二維數(shù)組存放。 選做內(nèi)容 ： 按教科書 節(jié) 中的描述方法，以十字鏈表表示稀疏矩陣。 增添矩陣求逆的運(yùn)算，包括不可求逆的情況。在求逆之前，先將稀疏矩陣的內(nèi)部表改為十字鏈表。 16. 迷宮問題的求解及演示 問題描述：（需求分析和背景意義） 以一個(gè) m n 的長方陣表示迷宮 ,0 和 1 分別表示迷宮中的道路和障礙 .設(shè)計(jì)一個(gè)程序 ,對(duì)任意設(shè)定的迷宮 ,求出一條從入口到出口的通路 ,或得出沒有通路的結(jié)論 . 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 首先實(shí)現(xiàn)一個(gè)以鏈表做存儲(chǔ)結(jié)構(gòu)的棧類型 ,然后編寫一個(gè)求解迷宮的非遞歸程序 .求得的通路以三元組 (i,j,d)的形式輸出 ,其中 :(i,j)指示迷宮中的一個(gè)坐標(biāo) ,d 表示走到下一坐標(biāo)的方向 .如 :對(duì)于下列數(shù)據(jù)的迷宮 ,輸出的一條通路為 (1,1,1),(1,1,2),(2,2,2),(3,2,3),(3,1,2),? . 測試數(shù)據(jù)： 迷宮測試數(shù)據(jù)如下 :左上角 (1,1)為入口 ,右下角 (8,9)為出口 1 2 3 4 5 6 7 8 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 10 0 0 0 0 9 1 0 0 0 0 0 0 0 1 1 0 3 10 0 0 0 0 8 0 0 3 10 0 0 9 1 0 0 0 0 1 1 3 10 0 0 10 2 3 4 3 0 0 1 0 0 0 8 0 0 0 1 0 0 0 0 0 0 70 3 0 0 4 2 0 0 1 0 1 0 0 0 0 0 0 6 0 8 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 實(shí)現(xiàn)提示： 計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所 設(shè)定的迷宮沒有通路。 可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口的下標(biāo)為（ 1， 10，出口點(diǎn)的下標(biāo)為（ n， n）。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。 選做內(nèi)容 ： （ 1）編寫遞歸形式的算法，求得迷宮中所有可能的通路； （ 2）以方陣形式輸出迷宮及其通路。 1串基本操作的演示 問題描述：（需求分析和背景意義） 如果語言沒有把串作為一個(gè)預(yù)先定義好的基本類型對(duì)待，又需要用該語言寫一個(gè)涉及串操作的軟件系統(tǒng)時(shí)，用戶必須自 己實(shí)現(xiàn)串類型。試實(shí)現(xiàn)串類型，并寫一個(gè)串的基本操作的演示系統(tǒng)。 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 在教科書 節(jié)用堆分配存儲(chǔ)表示實(shí)現(xiàn) HString 串的最小操作子集的基礎(chǔ)上，實(shí)現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作， （不使用 C 語言本身提供的串函數(shù)）。 參數(shù)合法性檢查必須嚴(yán)格。 說明：（在格式中，Φ表示 0 個(gè)、 1 個(gè)或多個(gè)空格所組成的串。 〈串標(biāo)識(shí)〉表示一個(gè)內(nèi)部名或一個(gè)串文字。前者是一個(gè)串的唯一標(biāo)識(shí)，是一種內(nèi)部形式的（而不是字符形式的）標(biāo)識(shí)符。 后者是兩端由單引號(hào)括起來的僅可打印字符組成的序列。 串內(nèi)每兩個(gè)連續(xù)的單引號(hào)表示一個(gè)單引號(hào)符。） 利用上述基本操作函數(shù)構(gòu)造以下系統(tǒng)：它是一個(gè)命令解釋程序，循環(huán)往復(fù)地處理用戶鍵入的每一條命令，直至終止程序的命令為止。命令定義如下： 賦值。格式： AΦ〈串標(biāo)識(shí)〉Φ〈回車〉 用〈串標(biāo)識(shí)〉所表示的值建立新串，并顯示新串的內(nèi)部名和串值。如： A′ Hi！′ 判相等。 格式： EΦ〈串標(biāo)識(shí) 1〉Φ〈串標(biāo)識(shí) 2〉Φ〈回車〉 若兩串相等，則顯示“ EQUAL”，否則顯示“ UNEQUAL”。 聯(lián)接。 格式： CΦ〈串標(biāo)識(shí) 1〉Φ〈串標(biāo)識(shí) 2〉Φ〈回車〉 將兩串聯(lián)接產(chǎn)生 結(jié)果串，它的內(nèi)部名和串值都顯示出來。 （ 4） 求長度 格式： LΦ〈串標(biāo)識(shí)〉Φ〈回車〉 顯示串的長度。 （ 5） 求子串 格式： SΦ〈串標(biāo)識(shí)〉Φ +〈數(shù) 1〉Φ +〈數(shù) 2〉Φ〈回車〉 如果參數(shù)合法，則顯示子串的內(nèi)部名和串值?！磾?shù)〉不帶正負(fù)號(hào)。 （ 6）子串定位。 格式： IΦ〈串標(biāo)識(shí) 1〉Φ〈串標(biāo)識(shí) 2〉Φ〈回車〉 顯示第二個(gè)串在第一個(gè)串中首次出現(xiàn)時(shí)的位置。 （ 7）串替換 格式： RΦ〈串標(biāo)識(shí) 1〉Φ〈串標(biāo)識(shí) 2〉Φ〈串標(biāo)識(shí) 2〉Φ〈回車〉 將第一個(gè)串中出現(xiàn)所有出 現(xiàn)的第二個(gè)串用第三個(gè)串替換，顯示結(jié)果串的內(nèi)部名和串值，原串不變。 （ 8）顯示格式： PΦ〈回車〉 顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對(duì)照表。 （ 9）刪除格式： DΦ〈內(nèi)部名〉Φ〈回車〉 刪除該內(nèi)部名對(duì)應(yīng)的的串，即賦值的逆操作。 （ 10）退出 格式： QΦ〈回車〉 結(jié)束程序的運(yùn)行。 在上述命令中，如果一個(gè)自變量是串，則應(yīng)首先建立它。基本操作函數(shù)的結(jié)果（即函數(shù)值）如果是一個(gè)串，則應(yīng)在尚未分配的區(qū)域內(nèi)新辟空間存放。 測試數(shù)據(jù)： 自定。但要包括以下幾組： （ 1） E″ ″〈回 車〉，應(yīng)顯示“ EQUAL”。 （ 2） E′ abc′ ′ abcd′〈回車〉，應(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′ aaaaaaaa′ ′ aaaa′ ′ ab′〈回車〉，應(yīng)顯示′ abab′。 實(shí)現(xiàn)提示： （ 1）演示系統(tǒng)的主結(jié)構(gòu)是一個(gè)串表頭，可定義為： struct { HString StrHead[100]； int CurNum }StrHeadList； 將各串的頭指針依次存于串頭數(shù)組 StrHead 中（設(shè)串的數(shù)目不超過 100）。 CurNum 為系統(tǒng)中現(xiàn)有的串的數(shù)目， CurNum+1 是可為下一個(gè)新串頭指針分配的位置?？梢匀?StrHead 的元素下標(biāo)作為所對(duì)應(yīng)串的內(nèi)部名。 （ 2）應(yīng)設(shè)置一個(gè)命令為分析函數(shù)，把命令分析結(jié)果通過一下類型的一個(gè)變量參數(shù)返回： typedef struct { int CmdNo； //或 char 類型，為命令號(hào)或命令符 int s[3]； //命令串參數(shù)的內(nèi)部名（最多 3 個(gè)） int num[2]； // 命令的數(shù)值參數(shù)（最多 2 個(gè)） }ResultType； 此函數(shù)還在存儲(chǔ)結(jié)構(gòu)中建立命令參數(shù)中的〈串〉?？赡茉僭O(shè)置一個(gè)“取下一個(gè)命令參數(shù)串”的操作是有益的。注意不要把這里的命令與所有機(jī)器的操作系統(tǒng)的命令相混。為了處理簡單化，可以不對(duì)命令的 格式作嚴(yán)格的語法檢查。 選做內(nèi)容 ： （ 1）串頭表改用單鏈表實(shí)現(xiàn)。 （ 2）對(duì)命令的格式（即語法）作嚴(yán)格檢查， 是系統(tǒng)既能處理正確的命令，也能處理錯(cuò)誤的命令。贅言，語義檢查（如某內(nèi)部名對(duì)于能夠的串已被刪除而無定義等）和基本操作參數(shù)合法性檢查仍留給基本操作去做。 （ 3） 支持串名。 將串名（可設(shè)不超過 6 個(gè)字符）存于串表頭中。命令（ 1）（ 3）（ 5）要增加命令參數(shù)〈結(jié)果串名〉；命令（ 7）中的〈串標(biāo)識(shí) 1〉改為〈串名〉，并用此名作為結(jié)果串名，刪除原被替串標(biāo)識(shí)，用〈串名〉代替〈串標(biāo)識(shí)〉定義和命令解釋 中的內(nèi)部名。每個(gè)命令執(zhí)行完畢時(shí)立即自動(dòng)刪除無名串。 問題描述：（需求分析和背景意義） 在教科書中，各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受。 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） （ 1）對(duì)以下 6 中常用的內(nèi)部算法進(jìn)行比較：起泡排序、直接插入排序、簡單選擇排序、快速查找排序、希爾排序、堆排序。 （ 2）待排序表的表長不小于 100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn) 生程序產(chǎn)生；至少要用 5 組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為 3 次移動(dòng)）。 （ 3）最后要對(duì)結(jié)果作出簡單分析，包括對(duì)各數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋。 測試數(shù)據(jù)： 由隨機(jī)數(shù)產(chǎn)生器產(chǎn)生。 實(shí)現(xiàn)提示： 主要工作是設(shè)法在已知算法中的適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)操作。程序還可以考慮幾組數(shù)據(jù)的典型性，如，正序、逆序和不同程度的亂序。注意采用分塊調(diào)試的方法。 選做內(nèi)容 ： （ 1）增加折半插入排序、二路插入排序、歸并 排序、基數(shù)排序等。 （ 2）對(duì)不同的輸入表長作實(shí)驗(yàn)，觀察檢查的兩個(gè)指標(biāo)相對(duì)于表長的變化關(guān)系。還可以對(duì)穩(wěn)定性作驗(yàn)證。 問題描述：假設(shè)停在鐵路調(diào)度站入口處的車廂序列