實驗四 哈夫曼樹與哈夫曼編碼.doc

《實驗四 哈夫曼樹與哈夫曼編碼.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、.實驗四哈夫曼樹與哈夫曼編碼一、實驗內(nèi)容[問題描述]　　已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。[基本要求]　　1.初始化：從鍵盤讀入n個字符，以及它們的權(quán)值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）　　2.編碼：根據(jù)建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進行編碼。二、概要設(shè)計算法設(shè)計：要是實現(xiàn)哈夫曼樹的操作，首先創(chuàng)建一個哈夫曼樹，在創(chuàng)建哈夫曼樹的時候，對哈夫曼樹的葉子和非葉子結(jié)點進行初始化，而在建立哈夫曼樹時，最難的該是選擇權(quán)值最小的兩個頂點，然后兩個

2、結(jié)點的權(quán)值和作為新的權(quán)值，再選擇兩個權(quán)值最小的作為新的兩個結(jié)點創(chuàng)建一個小的二叉樹的子樹；創(chuàng)建哈夫曼樹后，進行編碼，在編碼過程中，先找到根，然后遍歷，左孩子用0標記，右孩子用1標記，最后將編碼好的哈夫曼樹進行輸出，就可以知道哈夫曼樹的編碼了。流程圖：..開始輸入哈弗曼樹的帶權(quán)結(jié)點數(shù)目n輸入相應(yīng)的權(quán)值和對應(yīng)的字符建立哈夫曼樹Huffmantree(HT,w,n,e)顯示哈夫曼樹outputHuffman(HT,m)哈夫曼樹的編碼CHuffmancode(HT,HC,n)結(jié)束算法：主函數(shù)Huffmantree(HuffmanTree&H

3、T,int*w,intn,char*e)*hc,intn)CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)outputHuffman(HuffmanTreeHT,intm)select(HuffmanTree*ht,intn,int*s1,int*s2)..模塊：在分析了實驗要求和算法分析之后，將程序分為四個功能函數(shù)，分別如下：首先建立一個哈夫曼樹和哈夫曼編碼的存儲表示：typedefstruct{intweight;intparent,lchild,rchild;charelem;

4、}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲赫夫曼編碼表CrtHuffmanTree(HuffmanTree*ht,int*w,intn)：w存放n個字符的權(quán)值，構(gòu)造哈夫曼樹HT。先將葉子初始化，再將非葉子結(jié)點初始化，然后構(gòu)造哈夫曼樹。構(gòu)造哈夫曼樹：..開始葉子初始化非葉子初始化調(diào)用select函數(shù)選擇權(quán)值最小的兩個這兩個權(quán)值最小的兩個字符非別作為同一個結(jié)點的左右孩子，其父母的權(quán)值為兩個字符的權(quán)值之和結(jié)束for(i=n+1;i<=m;+

5、+i){//在HT[1……i]選擇parent為0且weight最小的兩個Select(HT,i-1,&s1,&s2);..HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT..[Select(HuffmanTree&HT,intn,int*s1,int*s2)：在所給的權(quán)值中，選擇出權(quán)值最小的兩個值。inti,min;for(i=1;i<=n;i++){if(HT[i].parent==0){m

6、in=i;i=n+1;}}for(i=1;i<=n;i++){if(HT[i].parent==0){if(HT[i].weight

7、，這樣一直循環(huán)下去，而最重要的是：for(inti=1;i<=n;++i){star=n-1;//從右向左逐位存放編碼，首先存放編碼結(jié)束符for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根結(jié)點求編碼if(HT[f].lchild==c)cd[--star]='0';//左分支標0elsecd[--star]='1';//右分支標1HC[i]=newchar[n-star];//為第i個編碼分配空間strcpy(HC[i],&cd[star]);//從cd復(fù)制編碼串到HC}.

8、.否是是開始從葉子到根結(jié)點求編碼c=if=HT[i].parentf!=0c=將0輸入到cd數(shù)組HT[f].lchild==c中將1輸入到cd數(shù)組HT[f].lchild==c從cd復(fù)制編碼串到HCc=f,f=HT[f].parent否輸出字符權(quán)值