【文章內(nèi)容簡介】 } else { if (huffTree[i].weight huffTree[s1].weight) { s2 = s1。 s1 = i。 } 9 else if (huffTree[i].weight huffTree[s2].weight) s2 = i。 } } } (5) 建立哈夫曼樹函數(shù) void Huffman::MakeCharMap() { if (n = 1) return。 int m = 2 * n 1。 //哈弗曼樹所需節(jié)點(diǎn)數(shù) huffTree = new HuffTreeNode[m+1]。 //0 號單元未使用 //初始化 int i。 for (i = 1。 i = n。 ++i) { huffTree[i].weight = chars[i].weight。 huffTree[i].cc = chars[i].c。 huffTree[i].parent = 0。 huffTree[i].lchild = 0。 huffTree[i].rchild = 0。 } for (i = n + 1。 i = m。 ++i) { huffTree[i].weight = 0。 huffTree[i].parent = 0。 huffTree[i].lchild = 0。 huffTree[i].rchild = 0。 huffTree[i].cc = 39。39。 } //建哈弗曼樹 for (i = n + 1。 i = m。 ++i) { int s1,s2。 select(i 1, s1, s2)。 //在 huffTree[1n]中選取 parent 和 weight 值最小的兩個節(jié)點(diǎn) huffTree[s1].parent = huffTree[s2].parent = i。 huffTree[i].lchild = s1。 huffTree[i].rchild = s2。 //從葉子到根節(jié)點(diǎn)逆向求每個字符的哈弗曼編碼 huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight。 } char *cd = new char[n]。 //分配求編碼的工作空間（每個字符編碼結(jié)果最長 n1 再加上 39。/039。） cd[n1] = 39。/039。 //編碼結(jié)束符 for(i = 1。 i = n。 ++i) //逐個字符求哈弗曼編碼 10 { int start = n 。 //原來是 n1，不正確，編碼結(jié)果總是多了個 0 int c,f。 //從葉子到根逆向求編碼 for (c = i, f = huffTree[i].parent。 f != 0。 c = f, f = huffTree[f].parent) { if (huffTree[f].lchild == c) //左孩子編碼為 1 cd[start] = 39。139。 else //右孩子編碼為 0 cd[start] = 39。039。 } chars[i].code = new char[n start]。 //為第 i 個字符編碼分配空間 strcpy(chars[i].code,amp。cd[start])。 } delete [] cd。 } (6) 統(tǒng)計哈夫曼編碼長度函數(shù) float Huffman::CountLength() { length = 0。 for(int i = 1。i = n。i ++ ) { length = length + chars[i].weight/() * (strlen((chars[i].code))4)。 } return length。 } (7) 譯碼函數(shù) void Huffman::Decode() { char s[1000]={39。\039。}。 char d[1000]={39。\039。}。 coutendl。 cout 提示：譯碼功能是在之前編碼的數(shù)據(jù)上來對二進(jìn)制代碼進(jìn)行的 !endl。 coutendl。 cout請輸入 二進(jìn)制代碼 :。 scanf(%s,s)。 char *ps = s。 char *pd = d。 cout譯碼結(jié)果為： 。 while(*ps!=39。\039。) { 11 int parent=2*n1。 while(huffTree[parent].lchild!=0) { if(*ps==39。139。) parent=huffTree[parent].lchild。 else parent=huffTree[parent].rchild。 ps++。 } *pd=chars[parent].c。 cout*pd。 pd++。 } coutendl。 coutendl。 coutendl。 system(pause)。 } (8) 編碼函數(shù) void Huffman::Encode() { //cout ()amp。*amp。*amp。*endl。 text 文件里字符的總個數(shù) code = 。 for (string::size_type i = 0。 i != ()。 ++i) { for (int j = 1。 j = n。 ++j) if (chars[j].c == text[i]) code += chars[j].code。 } (9) 打印哈夫曼碼函數(shù) void Huffman::PrintCharCode() { for (int i = 1。 i = n。 ++i) { switch (chars[i].c) { case 39。/t39。: cout //t。 break。 case 39。/n39。: cout //n。 break。 default: cout chars[i].c。 12 break。 } cout —— chars[i].code endl。 } } (10) 打印哈夫曼樹函數(shù) int Huffman::print_at_level(int h,int level) { if(!h || level 0) return 0。 if(0==level) { couthuffTree[h].cc 。 return 1。 } // coutendl。 return print_at_level(huffTree[h].lchild,level 1)+print_at_level(huffTree[h].rchild,level1)。 } void Huffman::print_by_level(int h) { int i=0。 for(i=0。i++) { if(!print_at_level(h,i)) { //coutendl。 break。 } coutendl。 } coutendl。 } void Huffman::printHuffTree() { print_by_level(2*n1)。 system(pause)。 } 13 四、 調(diào)試分析 本程序采用的數(shù)據(jù)結(jié)構(gòu)有數(shù)和鏈表，其中樹的部分有簡化，這有弊有利。在實現(xiàn)建立哈夫曼樹，編碼譯碼時，這些操作都十分簡單易懂。但也有不好的地方。由于在設(shè)計之初對左右孩子采用的是數(shù)字標(biāo)識的方法，而不是用一個指針，導(dǎo)致在最后編寫打印哈夫曼樹的代碼時，遇到了很大問題，使得按照樹的實際結(jié)構(gòu)打印十分困難，最終也只能達(dá)到層次打印的效果。這說明一個好的數(shù)據(jù)結(jié)構(gòu)十分重要，對于功能的實現(xiàn)有著非常重要的意義。 本程序的模塊劃分比較合理，一共分為了初始化，編碼，譯碼，打印哈夫曼樹四個主要部分。 思路清晰， 每次寫完一個部分的代碼 后，及時進(jìn)行測試，這樣使得完成進(jìn)度大大加快，一旦出現(xiàn)錯誤也能夠及時準(zhǔn)確地發(fā)現(xiàn)。值得改進(jìn)的地方是，在每個部分中，為了完成一個功能，有多個函數(shù)，這中間存在著設(shè)計缺陷，使得算法效率較低。這也反映了代碼量的不足，只有多練習(xí)才能盡量減少多余的代碼。 五、 用戶手冊 本程序的演示環(huán)境是 。 編譯鏈接成功后即可進(jìn)入程序執(zhí)行界面，如下所示。 初始化一共有兩種方法，分別是從文件讀入和手動輸入。如果采取從文件讀入，則需要在 文件中輸入字符集，然后將此 txt 文件放在程序所在路徑下。 14 手動輸入比較簡單，輸入字符和對應(yīng)權(quán)值，權(quán)值是字符出現(xiàn)次數(shù)。 在初始化完成后，就進(jìn)入菜單界面。 選擇 14，即可完成不同的功能。 六、 測試結(jié)果 在 文件中寫入測試數(shù)據(jù) “THIS PROGRAM IS MY FAVORITE”后，選擇編碼功能。 統(tǒng)計得字符對應(yīng)權(quán)值為： 15 哈夫曼編碼為： 16 求得編碼長度為： 17 實驗二 飛機(jī)訂票系統(tǒng) 一、 需求分析 問題分析 一機(jī)場每天有 n 個航班，每個班次都有一班次號（ 1， 2， 3……n ），固定的起飛時間，固定的路線（起始站，終點(diǎn)站），大致的飛行時間，固定的額定載客量。如： 班次 起飛時間 起始站 終點(diǎn)站 飛行時間 額定載量 定票人數(shù) 1 8： 00 天津 廣漢 2 145 130 2 6： 30 天津 成都 140 140 3 7： 00 天津 成都 140 120 4 10： 00 天津 成都 140 120 試設(shè)計一個機(jī)票管理系統(tǒng)，對機(jī)場的售票情況進(jìn)行管理。 基本要求 功能要求： (1) 錄入班次信息（信息用文件保存），可不時地增加班次數(shù)據(jù)； (2) 瀏覽班次信息，可顯示所有班次當(dāng)前狀況（如果系統(tǒng)時間超過了某班次的起飛時間，則顯示 “此班已發(fā)出 ”的提示信息）； (3) 查詢路線，可按班次號查詢，可按終點(diǎn)站查詢； (4) 售票和退票功能； A：根據(jù)客戶提出的要求（航班號，訂票數(shù)額）查詢該航班情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號。若已滿員或余票少于訂票額，則需重新詢問客戶要求。若需要，可預(yù)約等級排隊等候。 選做：當(dāng)客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達(dá)同一目的地的其他航線情況。 B：根據(jù)客戶提供的情況（日期，航班），為客戶辦理退票手續(xù)，然后查詢該航班是否有人預(yù)約登記。首先詢問排在第一的客戶