1、安徽師范大學(xué)數(shù)學(xué)計算機科學(xué)學(xué)院實驗報告專業(yè)名稱 計算機科學(xué)與技術(shù)實 驗 室 6號實驗樓401室實驗課程 數(shù)據(jù)結(jié)構(gòu)實驗名稱哈弗曼樹編碼和譯碼姓 名 陳陽學(xué) 號130704069同組人員 無實驗日期 2014-12-51、 實驗?zāi)康氖煜ち藢蚵鼧涞氖褂梅椒?，了解編碼和譯碼得過程并加以使用.2、 實驗原理1.首先構(gòu)建哈弗曼樹，再對哈弗曼樹進行初始化，再利用對各結(jié)點得遍歷處理進行尋找雙親，修改結(jié)點信息。接著利用函數(shù)對其生產(chǎn)得哈弗曼樹進行編碼，最后再進行譯碼。2.定義一個結(jié)構(gòu)體，用于存放哈弗曼樹得結(jié)點信息。3.定義一個結(jié)構(gòu)體，用于存放權(quán)重信息 4.構(gòu)建哈弗曼樹，利用上述存儲結(jié)構(gòu)實現(xiàn) 4.1初始化:將h

2、t0m-1中2n-1個結(jié)點里的指針均置為空，權(quán)值置為0。 4.2傳值：讀入n個葉子的權(quán)值存于向量的前n個分量中。它們是初始森林中n個孤立的根結(jié)點上的權(quán)值。 4.3合并：對森林中的樹共進行n-1次合并，所產(chǎn)生的新結(jié)點依次放入向量ht的第i個分量中。每次合并分兩步： 當(dāng)前森林ht0i-1的所有結(jié)點中，選取權(quán)最小和次小的兩個根點s1和 s2作為合并對象，這里0s1，s2i-1。  將根為hts1和hts2的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結(jié)點hti。具體操作：將hts1和hts2的parent置為i，將hti的lchild和rchild分別置為s1和s2

3、 .新結(jié)點hti的權(quán)值置為hts1和hts2的權(quán)值之和。5. 哈夫曼的編碼：約定左子為0，右子為1，則可以從根結(jié)點到葉子結(jié)點的路徑上的字符組成的字符串作為該葉子結(jié)點的編碼。 3.需求分析對輸入的一串電文字符實現(xiàn)哈夫曼編碼，再對哈夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。求得編碼就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。設(shè)計實現(xiàn)的功能： (1) 哈夫曼樹的建立； (2) 哈夫曼編碼的生成； (3) 編碼文件的譯碼。4.概要設(shè)計哈夫曼編碼主要是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進行譯碼 。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的

4、左分之代表0，右分支代表1，則從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點對應(yīng)字符的編碼為哈夫曼編碼。主流程圖： 哈夫曼樹的建立過程哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然要進行n1次合并，所以共產(chǎn)生n1個新結(jié)點，它們都是具有兩個孩子的分支結(jié)點。由此可知，最終求得的哈夫曼樹中一共有2n1個結(jié)點，其中n個結(jié)點是初始森林的n個孤立結(jié)點。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點。我們可以利用一個大小為2n-1的一維

5、數(shù)組來存儲哈夫曼樹中的結(jié)點。哈夫曼編碼得譯碼 譯碼的基本思想是：讀文件中編碼，并與原先生成的哈夫曼編碼表比較，遇到相等時，即取出其對應(yīng)的字符存入一個新串中。5.詳細設(shè)計結(jié)構(gòu)定義：typedef structint weight;/權(quán)值int parent;/父節(jié)節(jié)點int lchild;/左子節(jié)點int rchild;/右子節(jié)點HTNode,HuffmanM+1;/huffman樹typedef struct Nodeint weight; /葉子結(jié)點的權(quán)值char c; /葉子結(jié)點int num; /葉子結(jié)點的二進制碼的長度WNode,WeightNodeN;哈弗曼樹得算法：/*創(chuàng)建Huff

6、manTree*/void CreateHuffmanTree(Huffman ht,WeightNode w,int n)int i,j;int s1,s2;/初始化哈夫曼樹for(i=1;i<=n;i+)hti.weight =wi.weight;hti.parent=0;hti.lchild=0;hti.rchild=0;for(i=n+1;i<=2*n-1;i+)hti.weight=0;hti.parent=0;hti.lchild=0;hti.rchild=0;for(i=n+1;i<=2*n-1;i+)for(j=1;j<=i-1;j+)if(!htj.p

7、arent)break;s1=j; /找到第一個雙親為零的結(jié)點for(;j<=i-1;j+)if(!htj.parent)s1=hts1.weight>htj.weight?j:s1;hts1.parent=i;hti.lchild=s1;for(j=1;j<=i-1;j+)if(!htj.parent)break;s2=j; /找到第二個雙親為零的結(jié)點for(;j<=i-1;j+)if(!htj.parent)s2=hts2.weight>htj.weight?j:s2;hts2.parent=i;hti.rchild=s2;hti.weight=hts1.we

8、ight+hts2.weight;/權(quán)值累加字符串得解碼：/*解碼*/void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)int i=0,j,p;printf("*字符串編碼解碼后的信息*n");while(i<m)p=2*n-1;/從父親節(jié)點向下遍歷直到葉子節(jié)點for(j=0;hcij!='0'j+)if(hcij='0')p=htp.lchild;elsep=htp.rchild;printf("%c",wp.c); /*打

9、印原信息*/i+;主函數(shù)：void main()int i,n=0; /n為葉子結(jié)點的個數(shù)int m=0; /m為字符串ch的長度char chN; /chN存放輸入的字符串Huffman ht; /Huffman二叉樹HuffmanCode h,hc; /h存放葉子結(jié)點的編碼,hc存放所有結(jié)點的編碼WeightNode weight; /存放葉子結(jié)點的信息printf("*哈夫曼編碼*n");printf("請輸入待轉(zhuǎn)換字符串 :");gets(ch); CreateWeight(ch,&m,weight,&n); /創(chuàng)建葉子結(jié)點信息p

10、rintf("*節(jié)點權(quán)值信息*n");printf("t");for(i=1;i<=n;i+) /輸出葉子結(jié)點的字符與權(quán)值printf("%c ",weighti.c);printf("n權(quán)重 ");for(i=1;i<=n;i+)printf("%d ",weighti.weight);CreateHuffmanTree(ht,weight,n); /創(chuàng)建哈弗曼樹printf("n*哈弗曼樹信息表*n");printf("tit權(quán)重t雙親t左結(jié)點t右結(jié)

11、點n");for(i=1;i<=2*n-1;i+) /輸出哈弗曼樹內(nèi)容printf("t%dt%dt%dt%dt%dn",i,hti.weight,hti.parent,hti.lchild,hti.rchild);CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /對葉子結(jié)點編碼printf("-結(jié)點編碼-n"); /輸出葉子結(jié)點編碼for(i=1;i<=n;i+)printf("t%c:",weighti.c);printf("%sn",hi);CrtHuffmanCode(ch,h,hc,weight,n,m); /對所有字符編碼printf("-字符串編碼-n"); /輸出字符串的編碼for(i=0;i<m;i+)printf("%s",hci);printf("n");system("pause");TrsHuffmanTree(ht,weight,hc,n,m); /對哈弗曼樹編碼進行解碼printf("n");Fre