哈夫曼編譯碼器課程設(shè)計(jì)報(bào)告

1、<p><b>　　哈夫曼編碼/譯碼器</b></p><p><b>　　一 目的</b></p><p>　　通過(guò)本次課程設(shè)計(jì)：復(fù)習(xí)學(xué)過(guò)的數(shù)據(jù)結(jié)構(gòu)的內(nèi)容；鞏固和加深對(duì)線性表、棧、隊(duì)列、字符串、樹(shù)、圖、查找、排序等理論知識(shí)的理解，這里主要用到二叉樹(shù)和棧；掌握現(xiàn)實(shí)復(fù)雜問(wèn)題的分析建模和解決方法；提高利用計(jì)算機(jī)分析解決綜合性實(shí)際問(wèn)題的基本

2、能力。</p><p><b>　　二 需求分析</b></p><p>　　目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段是電報(bào)，即將需傳送的文字轉(zhuǎn)化成由二進(jìn)制的字符組成的字符串。在傳送電文時(shí)，希望總長(zhǎng)度盡可能地短。如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長(zhǎng)度便可減少。如果要設(shè)計(jì)長(zhǎng)短不等的編碼，則必須是任一個(gè)字符的編碼都

3、不是另外一個(gè)字符的編碼的前綴，這種編碼叫前綴編碼。設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，要以n種字符出現(xiàn)的頻率做權(quán)，設(shè)計(jì)一棵哈夫曼樹(shù)，由此得到的二進(jìn)制前綴編碼就叫做哈夫曼編碼。</p><p>　　編碼時(shí)，從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)（出現(xiàn)次數(shù)即為此字符的權(quán)值）；或從終端獲取各個(gè)字符及其權(quán)值據(jù)此建立哈夫曼樹(shù)。建好的哈夫曼樹(shù)以凹凸表的形式存到文件TreePrint.txt中。利用建

4、好的哈夫曼樹(shù)對(duì)各個(gè)字符進(jìn)行編碼，編得的哈夫曼碼存到文件HuffmanCodes.txt中。利用已建好的各字符的哈夫曼碼對(duì)ToBeTran.txt進(jìn)行逐字編碼，編好的二進(jìn)制字符串存到文件CodeFile.txt中。</p><p>　　在編碼期間，用戶可以選擇是否觀看：建好的哈夫曼樹(shù)；建好的各字符的哈夫曼碼；ToBeTran.txt中的原文；原文經(jīng)編譯產(chǎn)生的二進(jìn)制字符串。</p><p>　

5、　譯碼時(shí)，從HuffmanCodes.txt中獲取各字符的哈夫曼碼，據(jù)此建好哈夫曼樹(shù)，然后利用建好的哈夫曼樹(shù)對(duì)文件CodeFile.txt中的二進(jìn)制字符串進(jìn)行譯碼，將二進(jìn)制字符串譯成對(duì)應(yīng)字符集，并把它們存到文件TextFile.txt中。</p><p>　　在譯碼期間，用戶可以選擇是否觀看：CodeFile.txt中的哈夫曼碼集；建好的各字符的哈夫曼碼；哈夫曼碼集經(jīng)譯碼產(chǎn)生的字符集。</p>&l

6、t;p><b>　　三 概要設(shè)計(jì)</b></p><p>　　1、程序抽象數(shù)據(jù)類型的定義</p><p><b>　?。?）</b></p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　c

7、har character;//字符</p><p>　　unsigned int weight;//權(quán)值</p><p>　　unsigned int parent;//父母節(jié)點(diǎn)</p><p>　　unsigned int lchild;//左孩子</p><p>　　unsigned int rchild;//右孩子</p>

8、<p>　　}HTNode,*PHTNode,*HuffmanTree; </p><p>　　HuffmanTree：哈夫曼樹(shù)；HTNode：哈夫曼樹(shù)的節(jié)點(diǎn)；PHTNode：指向哈夫曼樹(shù)節(jié)點(diǎn)類型數(shù)據(jù)的指針類型。</p><p><b>　　（2）</b></p><p>　　typedef HTNode StackElement

9、Type;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　StackElementType *base;//棧底指針，在棧構(gòu)造前和銷毀后，base的值為0 。</p><p>　　StackElementType *top;//棧頂指針。</p>

10、<p>　　int stack_max_capacity;//棧的最大容量。</p><p>　　int stack_length;//棧當(dāng)前的長(zhǎng)度。</p><p><b>　　}SqStack;</b></p><p>　　SqStack：棧（在打印哈夫曼樹(shù)前建立凹凸表時(shí)用到，程序的核心部分沒(méi)有用到棧。）</p>

11、<p><b>　?。?）</b></p><p>　　typedef int Status;</p><p>　　Status：函數(shù)的返回類型，0代表成功，1代表不成功。</p><p><b>　　2、程序含三個(gè)模塊</b></p><p><b>　?。?）主程序模塊&l

12、t;/b></p><p><b>　　打印菜單；</b></p><p>　　讓用戶選擇是編碼還是譯碼；</p><p>　　讓用戶決定是否觀看一些信息。</p><p><b>　?。?）編碼模塊</b></p><p>　　Status Initializatio

13、n(HuffmanTree& HT);</p><p>　　初始化哈弗曼樹(shù)，統(tǒng)計(jì)待編碼文件ToBeTran.txt中各字符出現(xiàn)次數(shù)并記入哈弗曼樹(shù)中；</p><p>　　Status CreatHuffman(HuffmanTree& HT);</p><p>　　已知各字符出現(xiàn)次數(shù)，據(jù)此建立哈弗曼樹(shù)；</p><p>　　S

14、tatus HuffmanCoding(HuffmanTree& HT,HuffmanCode& HC);</p><p>　　已建好哈弗曼樹(shù)，據(jù)此對(duì)各字符進(jìn)行編碼，并將各字符的哈弗曼碼存到HuffmanCodes.txt中；</p><p>　　Status TextCoding(HuffmanTree& HT,HuffmanCode& HC);</

15、p><p>　　對(duì)ToBeTran.txt中的文字編碼，結(jié)果存入CodeFile.txt中。</p><p><b>　?。?）譯碼模塊</b></p><p>　　Status CreatHuffmanTree2(HuffmanTree& HT);</p><p>　　讀HuffmanCodes.txt，建立哈夫曼

16、樹(shù)；</p><p>　　Status TextDecoding(HuffmanTree& HT);</p><p>　　建好哈弗曼樹(shù)后，讀CodeFile.txt 把哈弗曼碼譯為字符并存到TextFile.txt中。</p><p>　　3、程序中用到的其它函數(shù)</p><p>　?。?）打印相應(yīng)東西到屏幕上的3個(gè)函數(shù)</p&

17、gt;<p>　　Status ShowText(char *filename);</p><p>　　讀文件，把里面的字符打到屏幕上。</p><p>　　Status ShowTree(HuffmanTree& HT);</p><p>　　哈夫曼樹(shù)已建好，把哈夫曼樹(shù)以凹凸表形式打印到屏幕上。</p><p>　　S

18、tatus ShowHuffmanCodes();</p><p>　　各個(gè)字符的哈夫曼碼已建好并已存于HuffmanCodes.txt中，把各字符的哈夫曼碼打印到屏幕上。</p><p><b>　?。?）棧的6個(gè)函數(shù)</b></p><p>　　Status InitStack(SqStack& S);</p><

19、;p>　　Status Push(SqStack& S,StackElementType E);</p><p>　　Status Pop(SqStack& S,StackElementType& E);</p><p>　　Status GetTop(SqStack& S,StackElementType& E);</p>&l

20、t;p>　　Status FindSame(SqStack& S,StackElementType& E);</p><p>　　Status DestoryStack(SqStack& S);</p><p><b>　　4、程序流程圖</b></p><p><b>　　（1）主函數(shù)流程圖</b

21、></p><p>　?。?）編碼模塊流程圖</p><p>　?。?）譯碼模塊流程圖</p><p><b>　　四 詳細(xì)設(shè)計(jì)</b></p><p>　　1、編碼時(shí)建立哈夫曼樹(shù)</p><p>　　前提：初始化哈弗曼樹(shù)， 統(tǒng)計(jì)待編碼文件ToBeTran.txt中各字符出現(xiàn)次數(shù)并記入哈弗

22、曼樹(shù)中，即已經(jīng)知道了各字符及其權(quán)值。</p><p>　　功能：建立哈夫曼樹(shù)。</p><p>　　char chars[N]={' ','e','t','a','o','i','n','r','s','h','d'

23、,'c',',','.','l','m','p','u','f','g','w','y','b','v','\'','\n','k','x','j

24、9;,'q','z'};</p><p>　　Status CreatHuffman(HuffmanTree& HT)</p><p><b>　　{</b></p><p>　　int i,smallest1,smallest2,m=2*N-1;</p><p>　　統(tǒng)計(jì)權(quán)值不為

25、零的字符;</p><p>　　m=權(quán)值不為零的字符的個(gè)數(shù);</p><p>　　for(i=N+1;i<=m;i++)//建立哈弗曼樹(shù)，每循環(huán)一次少一棵子樹(shù)</p><p><b>　　{</b></p><p>　　//選擇兩棵權(quán)值最小的子樹(shù)，smallest1是靠前的那棵</p><p&g

26、t;　　Select(HT,i-1,smallest1,smallest2);</p><p>　　利用儲(chǔ)存哈夫曼樹(shù)的數(shù)組的新的一個(gè)空間，把此空間的左子樹(shù)設(shè)為下標(biāo)為smallest1的節(jié)點(diǎn)，右子樹(shù)設(shè)為下標(biāo)為smallest2的節(jié)點(diǎn)；</p><p>　　把下標(biāo)為smallest1和smallest2的節(jié)點(diǎn)的父母節(jié)點(diǎn)都設(shè)為新利用空間；</p><p><b>

27、;　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p>　　2、對(duì)ToBeTran.txt中的原文進(jìn)行編碼</p><p>　　前提：HC中儲(chǔ)存著各個(gè)字符的哈夫曼碼。</p><p>　　功能：把原文中的各個(gè)字符翻譯為這個(gè)字符

28、對(duì)應(yīng)的哈夫曼碼存于文件中。</p><p>　　Status TextCoding(HuffmanTree& HT,HuffmanCode& HC)</p><p><b>　　{</b></p><p>　　FILE *fp,*fp2;</p><p>　　fp打開(kāi)待譯文件ToBeTran.txt；&l

29、t;/p><p>　　fp2打開(kāi)CodeFile.txt；//將把原文譯得的二進(jìn)制字符串寫到里面。</p><p>　　//逐個(gè)讀ToBeTran.txt中的字符 在HT對(duì)應(yīng)位置找到該字符的碼 把碼打到CodeFile.txt中</p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{&l

30、t;/b></p><p><b>　　int p=1;</b></p><p>　　//從待譯文件中讀到一個(gè)字符ch，尋找ch在HT中的位置</p><p>　　while(ch!=(*(HT+p)).character)</p><p><b>　　p++;</b></p>

31、<p>　　fputs(HC[p],fp2);//把該字符對(duì)應(yīng)的哈夫曼碼寫到CodeFile.txt中。</p><p><b>　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p>　　3、譯碼時(shí)建立哈夫曼樹(shù)</p>

32、<p>　　前提：CodeFile.txt存在且里面已存有譯好的二進(jìn)制字符串， HuffmanCodes.txt存在且里面存有編好的各字符的哈夫曼碼，并且這兩個(gè)文件里的內(nèi)容是同一個(gè)編碼實(shí)例產(chǎn)生的。</p><p>　　功能：利用HuffmanCodes.txt建立哈夫曼樹(shù)。</p><p>　　Status CreatHuffmanTree2(HuffmanTree&

33、 HT)</p><p><b>　　{</b></p><p>　　for(i=1,p=HT+1;i<=m;i++,p++)//對(duì)哈弗曼樹(shù)進(jìn)行初始化</p><p>　　{ (*p).character='#'; (*p).lchild=0; (*p).rchild=0;}</p><p>&l

34、t;b>　　FILE *fp;</b></p><p>　　fp打開(kāi)HuffmanCodes.txt；//這樣可獲取每個(gè)字符的哈夫曼碼。</p><p><b>　　char ch;</b></p><p>　　int s=0;//s代表chars中的位置</p><p>　　int q=1;//q是未

35、入哈弗曼樹(shù)的第一個(gè)節(jié)點(diǎn)的下標(biāo)</p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{</b></p><p>　　HuffmanCodes.txt中哈夫曼碼為1的字符不做處理，continue；</p><p>　　//其它的做以下處理：</p><p

36、><b>　　int z=1;</b></p><p>　　while(遍歷該字符的哈夫曼碼的每一位)</p><p><b>　　{</b></p><p>　　讀此字符的哈夫曼碼的每一位，為0的則利用儲(chǔ)存哈夫曼樹(shù)的數(shù)組的第一個(gè)未被利用的空間，把此空間設(shè)為已利用的空間的右孩子，為1的設(shè)為左孩子;</p>

37、<p>　　非葉子節(jié)點(diǎn)的character都設(shè)為‘#’;</p><p><b>　　}</b></p><p>　　葉子節(jié)點(diǎn)的character設(shè)為對(duì)應(yīng)字符;</p><p><b>　　}</b></p><p>　　return OK;</p><p>&

38、lt;b>　　}</b></p><p>　　4、對(duì)CodeFile.txt中的二進(jìn)制字符串進(jìn)行譯碼</p><p>　　前提：哈夫曼樹(shù)已建好，CodeFile.txt存在且里面存有滿足一定條件的二進(jìn)制字符串。</p><p>　　功能：對(duì)CodeFile.txt中的二進(jìn)制字符串進(jìn)行譯碼，譯得的原文存于TextFile.txt中。</p>

39、;<p>　　Status TextDecoding(HuffmanTree& HT)</p><p><b>　　{</b></p><p>　　FILE *fp,*fp2;</p><p>　　fp打開(kāi)CodeFile.txt；fp2打開(kāi)TextFile.txt；</p><p><b&g

40、t;　　char ch;</b></p><p>　　while((ch=fgetc(fp))!=EOF)</p><p><b>　　{</b></p><p>　　int s=1;//從數(shù)組1位置 即根節(jié)點(diǎn)開(kāi)始往下走 根節(jié)點(diǎn)作為父母節(jié)點(diǎn)</p><p>　　while((ch=fgetc(fp))!=EO

41、F)//又讀了一位 因?yàn)槊總€(gè)字符的碼的第一位都是0 故要忽略</p><p><b>　　{</b></p><p>　　if(ch=='0') s=HT[s].rchild;//從節(jié)點(diǎn)HT[s]往下走了一層 付給s新值 s為新的父母節(jié)點(diǎn)的下標(biāo)。</p><p>　　else s=HT[s].lchild;</p>

42、<p>　　if(HT[s].character=='#') continue;//如果新的這層的節(jié)點(diǎn)內(nèi)存有'#' 則應(yīng)continue 。</p><p>　　else {fputc(HT[s].character,fp2); break;}//直到讀到非'#'時(shí)break 說(shuō)明此時(shí)一段哈碼已被譯為一個(gè)字符 則可開(kāi)始一段新的哈碼。</p>

43、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p><b>　　五 調(diào)試分析</b></p><p>

44、;<b>　　1、調(diào)試內(nèi)容一</b></p><p>　　作用：測(cè)試編碼模塊建好的哈夫曼樹(shù)是否和預(yù)期的一致。</p><p>　　路徑：main()--->Initialization(HT)---> CreatHuffman(HT)。</p><p>　　發(fā)現(xiàn)的問(wèn)題及解決策略：對(duì)哈夫曼樹(shù)的初賦值應(yīng)該分成兩部分，前半部分儲(chǔ)存字符，后

45、半部分儲(chǔ)存非葉子節(jié)點(diǎn)；儲(chǔ)存哈夫曼樹(shù)的數(shù)組，出現(xiàn)頻率高的字符放在數(shù)組靠前的位置，這樣子在統(tǒng)計(jì)ToBeTran.txt中各字符出現(xiàn)次數(shù)時(shí)可減少尋找對(duì)應(yīng)字符的時(shí)間；CreatHuffman(HT)中，有一個(gè)while循環(huán)的循環(huán)次數(shù)，原來(lái)設(shè)為N+1<=i<=2*N-1，但運(yùn)行不出正確結(jié)果，經(jīng)調(diào)試發(fā)現(xiàn)，while循環(huán)的循環(huán)次數(shù)不是一個(gè)固定的值，而是需要編碼幾種字符就循環(huán)幾次，所以后來(lái)就設(shè)了個(gè)計(jì)數(shù)器來(lái)記錄有幾種字符需編碼，這個(gè)問(wèn)題就解決

46、了。</p><p><b>　　2、調(diào)試內(nèi)容二</b></p><p>　　作用：測(cè)試譯碼模塊建的哈夫曼樹(shù)是否和預(yù)期的一致。</p><p>　　路徑：main()--->CreatHuffmanTree2(HT)。</p><p>　　發(fā)現(xiàn)的問(wèn)題及解決策略：因?yàn)閏har chars[N]這個(gè)數(shù)組不涉及到對(duì)它的改

47、變且至少有三個(gè)函數(shù)用到它，所以適合設(shè)為全局變量；因?yàn)楦鱾€(gè)字符的哈夫曼碼都是以“0”開(kāi)頭的，所以可以忽略這個(gè)“0”，建哈夫曼樹(shù)時(shí)，可以減少使用一個(gè)節(jié)點(diǎn)，且在后來(lái)的譯碼中，每一個(gè)需翻譯的原文字符都少走了一步（解釋：譯碼時(shí)，要從根節(jié)點(diǎn)走到葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)里儲(chǔ)存的是該路徑下對(duì)應(yīng)的字符，而該路徑就代表一個(gè)哈夫曼碼）。</p><p><b>　　3、調(diào)試內(nèi)容三</b></p><

48、p>　　作用：測(cè)試以凹凸表打印哈夫曼樹(shù)的模塊是否正確。</p><p>　　路徑：main()--->Initialization(HT) CreatHuffman(HT) ShowTree(HT)。</p><p>　　發(fā)現(xiàn)的問(wèn)題1：不能正確打印出哈夫曼樹(shù)。</p><p>　　解決策略：修改路徑為main()--->Initialization

49、(HT) HuffmanCoding(HT,HC)-CreatHuffman(HT) ShowTree(HT)。</p><p>　　結(jié)果：可以正確打印哈夫曼樹(shù)了。</p><p><b>　　原因：未找到。</b></p><p>　　發(fā)現(xiàn)的問(wèn)題2：在Status ShowTree(HuffmanTree& HT)這個(gè)函數(shù)中，char

50、 *dir開(kāi)辟的空間在本函數(shù)快結(jié)束時(shí)只要釋放就會(huì)在運(yùn)行時(shí)產(chǎn)生錯(cuò)誤。</p><p>　　解決策略：把釋放空間的代碼注釋，讓這塊未釋放的空間在程序停止運(yùn)行后由系統(tǒng)自動(dòng)收回。</p><p>　　結(jié)果：可以正確運(yùn)行了，但是這個(gè)問(wèn)題只是被隱藏了，并沒(méi)有真正解決。</p><p><b>　　原因：未找到。</b></p><p&g

51、t;<b>　　4、調(diào)試用到的環(huán)境</b></p><p><b>　　VC++6.0。</b></p><p><b>　　六 測(cè)試結(jié)果</b></p><p><b>　　1、編碼</b></p><p>　　測(cè)試數(shù)據(jù)（存于ToBeTran.txt中

52、）</p><p>　　經(jīng)編譯后得到的各字符的哈夫曼碼（存于HuffmanCodes.txt中，并可以在屏幕上顯示）</p><p>　　經(jīng)編譯產(chǎn)生的二進(jìn)制字符串（存于ColdFile.txt中）</p><p><b>　　2、譯碼</b></p><p>　　測(cè)試數(shù)據(jù)：見(jiàn)“1，編碼”部分的第四個(gè)截圖</p>

53、;<p>　　測(cè)試結(jié)果（存于TextFile.txt中）</p><p><b>　　七 用戶使用說(shuō)明</b></p><p><b>　　1、主界面</b></p><p>　　在此界面下有三個(gè)選項(xiàng)（1：編碼；2：譯碼；3：退出。），用戶可以輸入對(duì)應(yīng)的數(shù)字再敲回車鍵執(zhí)行相應(yīng)功能。</p>&

54、lt;p>　　2、編碼（正確運(yùn)行情況下）</p><p>　　編碼前請(qǐng)確認(rèn)文件夾內(nèi)已有文件ToBeTran.txt（已存有待譯原文）、HuffmanCodes.txt（將存儲(chǔ)編譯得到的各字符的哈夫曼碼）、CodeFile.txt（將存儲(chǔ)編譯原文得到的哈夫曼碼集）、HuffmanTree.txt（將把哈夫曼樹(shù)存入此中）。</p><p>　　獲得字符及其權(quán)值有兩種方法：1，讀待譯文件統(tǒng)

55、計(jì)出現(xiàn)的字符及其權(quán)值；2，從鍵盤輸入各字符及其權(quán)值。這里用第1種方法。</p><p>　　在此期間，用戶可選擇查看：建好的哈夫曼樹(shù)（以凹凸表的形式）、各字符的哈夫曼碼、ToBeTran.txt中的原文、原文經(jīng)編譯產(chǎn)生的哈夫曼碼集。</p><p>　　3、編碼（錯(cuò)誤輸入情況下）</p><p>　　在此次實(shí)例中，ToBeTran.txt中擁有全部的小寫字母及英文空

56、格、英文逗號(hào)、英文句號(hào)、英文單引號(hào)，但是在從終端輸入字符及其權(quán)值時(shí)，只輸入了abcdef六種字符，結(jié)果，原文經(jīng)編碼得到二進(jìn)制字符串是不對(duì)的。這是因?yàn)?，程序把原文中除abcdef以外的字符都編碼為1，這樣，就得到了截屏中看到的CodeFile.txt中的二進(jìn)制字符串。</p><p>　　用戶最好是用“從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這種方法來(lái)建立哈夫曼樹(shù)，這樣可保證建好的電文二

57、進(jìn)制字符串最短。而若從終端輸入字符及其權(quán)值，則有三個(gè)弊端：1，需注意輸入的字符正是待譯文件中存在的字符（若待譯文件中沒(méi)有的字符卻從終端輸入了該字符，則程序可得到正確運(yùn)行結(jié)果；若待譯文件中有的字符而終端沒(méi)有輸入，程序雖然能夠運(yùn)行，但得到的結(jié)果是錯(cuò)誤的）；2，用戶輸入的字符的權(quán)值不一定和待譯文件中對(duì)應(yīng)字符的出現(xiàn)次數(shù)相符合（這樣譯得的二進(jìn)制字符串就可能不是最短的了）；3，浪費(fèi)時(shí)間。</p><p><b>　

58、　4、譯碼</b></p><p>　　譯碼前請(qǐng)確認(rèn)文件夾內(nèi)已有文件HuffmanCodes.txt（已存有每個(gè)字符的哈夫曼碼）、CodeFile.txt（已存有原文的哈夫曼碼集）和TextFile.txt（將存入譯得的原文）。</p><p>　　在譯碼期間，用戶可以選擇是否觀看：CodeFile.txt中的哈夫曼碼集；建好的各字符的哈夫曼碼；哈夫曼碼集經(jīng)譯碼產(chǎn)生的字符集。&

59、lt;/p><p><b>　　八 課程設(shè)計(jì)總結(jié)</b></p><p>　　做這個(gè)課程設(shè)計(jì)，最開(kāi)始想向要求的那樣，從終端輸入字符及其權(quán)值，但是逐漸考慮到剛剛在用戶手冊(cè)中提到的用這種方法的三個(gè)弊端，于是就開(kāi)始想另外一種獲得字符集及其權(quán)值的方法，就這樣，“從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這樣的方法誕生了。但是隨后還是把“從終端輸入字符及

60、其權(quán)值”這種建哈夫曼樹(shù)的方法也加到了程序里，供用戶二選一。</p><p>　　用“從待編譯文件ToBeTran.txt中獲得出現(xiàn)的字符及其出現(xiàn)的次數(shù)”這樣的方法去建哈夫曼樹(shù)，需事先羅列出待譯文件中所有的可能出現(xiàn)的字符，若待譯文件中恰好有這個(gè)字符，就建它的哈夫曼碼，若沒(méi)有這個(gè)字符，則這個(gè)字符的哈夫曼碼設(shè)為“1”，因?yàn)槠渌５淖址墓蚵a開(kāi)頭的一位都是“0”，這樣子就可以把兩種字符區(qū)分開(kāi)來(lái)。事后證明，在打印各字

61、符的哈夫曼碼時(shí)，打印哈夫曼樹(shù)時(shí)，接收方建哈夫曼樹(shù)時(shí)（在下一段將詳細(xì)提到），這種區(qū)分是很有必要的。</p><p>　　本課程設(shè)計(jì)要求的是建好哈夫曼樹(shù)編譯了待譯文件，然后利用這棵已建好的哈夫曼樹(shù)，把二進(jìn)制字符串翻譯為原文。考慮到在實(shí)際應(yīng)用中，編譯待譯文件時(shí)建好的哈夫曼樹(shù)在發(fā)送文件方的電腦內(nèi)存中，而發(fā)送文件方只能把二進(jìn)制字符串發(fā)送給接受文件方，所以接受文件方的電腦內(nèi)存中肯定沒(méi)有現(xiàn)成的哈夫曼樹(shù)可以使用，他只能自己另建一

62、棵。這個(gè)是本程序的難點(diǎn)，就是接受文件方要依據(jù)些什么東西才能建一棵和發(fā)送文件方一樣的哈夫曼樹(shù)。于是我想到，發(fā)送方要把各字符的哈夫曼碼隨同譯好的二進(jìn)制電文一同發(fā)送給接收方，接收方要和發(fā)送方使用相同的字符順序，這樣接收方就可以知道各個(gè)字符的哈夫曼碼，他就依據(jù)這個(gè)可以再建一棵哈夫曼樹(shù)（接收方的哈夫曼樹(shù)形態(tài)上和發(fā)送方的大大不同，但實(shí)質(zhì)上一模一樣）。</p><p>　　寫這個(gè)程序遇到的另一個(gè)難點(diǎn)是怎樣把哈夫曼樹(shù)以凹凸表的形

63、式打印到屏幕上。一開(kāi)始想用遞歸，但是這樣不好確定哈夫曼各個(gè)節(jié)點(diǎn)在屏幕上相應(yīng)的位置。其實(shí)我們上學(xué)期也寫過(guò)以凹凸表形式打印二叉樹(shù)的一個(gè)程序，但那個(gè)程序里的二叉樹(shù)是以二叉鏈表的形式儲(chǔ)存的，而本程序的哈夫曼樹(shù)（二叉樹(shù)的一種）是以數(shù)組形式儲(chǔ)存的，一開(kāi)始我以為那個(gè)程序的方法在本程序中不適用。后來(lái)因?yàn)橄氩坏狡渌椒?，就考慮能否用那個(gè)程序的方法放在本程序中使用。結(jié)果發(fā)現(xiàn)，我只改動(dòng)了少許地方就可以了。從這一點(diǎn)上我認(rèn)識(shí)到，二叉樹(shù)是以什么方式儲(chǔ)存的不重要，最

64、重要的是對(duì)二叉樹(shù)的一些操作對(duì)于不同儲(chǔ)存類型的二叉樹(shù)是普遍通用的。</p><p>　　另外，因?yàn)槲磳W(xué)扎實(shí)，程序中還有至少兩個(gè)未解決的問(wèn)題。這在“調(diào)試分析”中提到過(guò)。這兩個(gè)問(wèn)題通過(guò)其它的一些措施可以避免錯(cuò)誤的運(yùn)行，但終究是沒(méi)有徹底解決，需在課程設(shè)計(jì)被檢查完以后，再花些時(shí)間搞懂?？傊ㄟ^(guò)此次的課程設(shè)計(jì)，我又復(fù)習(xí)了一遍二叉樹(shù)、棧等數(shù)據(jù)結(jié)構(gòu)里的知識(shí)點(diǎn)，加深了對(duì)它們的理解，對(duì)使用這些數(shù)據(jù)結(jié)構(gòu)更加熟練了；又重新略看了一遍《