實(shí)驗(yàn)四 哈夫曼樹與哈夫曼編碼

《實(shí)驗(yàn)四 哈夫曼樹與哈夫曼編碼》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、ancode(HuffmanTree&HT,HuffmanCode&HC,intn)outputHuffman(HuffmanTreeHT,intm)select(HuffmanTree*ht,intn,int*s1,int*s2)模塊：在分析了實(shí)驗(yàn)要求和算法分析之后，將程序分為四個(gè)功能函數(shù)，分別如下：首先建立一個(gè)哈夫曼樹和哈夫曼編碼的存儲表示：typedefstruct{intweight;intparent,lchild,rchild;charelem;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲赫夫曼樹typedefchar**Huffm

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

5、nt=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)值最小的兩個(gè)值。inti,min;for(i=1;i<=n;i++){if(HT[i].parent==0){min=i;i=n+1;}}for(i=1;i<=n;i++){if(HT[i].parent==0){if(HT[i].weight

6、s1=min;在選擇s2的時(shí)候和s1相似，只有在判斷是否為最小的時(shí)候就，要加上一個(gè)條件：if(HT[i].parent==0&&i!=*s1)，就可以了，否則，選出來的最小權(quán)值和s1就相等了，失去了選擇的意義了。CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)：從葉子到根逆向求編碼：左孩子為0，右孩子為1，這樣一直循環(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

7、].parent)//從葉子到根結(jié)點(diǎn)求編碼if(HT[f].lchild==c)cd[--star]='0';//左分支標(biāo)0elsecd[--star]='1';//右分支標(biāo)1HC[i]=newchar[n-star];//為第i個(gè)編碼分配空間strcpy(HC[i],&cd[star]);//從cd復(fù)制編碼串到HC}否是是開始從葉子到根結(jié)點(diǎn)求編碼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)值相

8、應(yīng)的編碼結(jié)束output