哈夫曼樹上機實驗報告

1、霍夫曼樹實驗目的：掌握結構體、指針及二叉樹的生成、遍歷等操作掌握霍夫曼編碼/譯碼的原理?；疽螅菏炀氄莆諛涞牟僮?。程序實現：程序第一遍統(tǒng)計原數據中各字符出現的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹，并把樹的信息保存起來，以便解壓時創(chuàng)建同樣的哈夫曼樹進行解壓；第二遍，根據第一遍掃描得到的哈夫曼樹進行編碼，并把編碼后的碼字存儲。要點分析:題目中涉及的主要知識點： 1、本程序參考霍夫曼算法（由給定的權值構造赫夫曼樹）： （1）由給定的n個權值w0, w1, w2, , wn-1，構造具有n棵二叉樹的集合F =T0, T1, T2, , Tn-1，其中每一棵二叉樹Ti只有一個帶有權值wi的根結點，其左、

2、右子樹均為空。 （2）重復以下步驟, 直到F中僅剩下一棵樹為止: 在F中選取兩棵根結點的權值最小的二叉樹, 做為左、右子樹構造一棵 新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。 在F中刪去這兩棵二叉樹。 把新的二叉樹加入F。 2、用構造赫夫曼樹以完成赫夫曼編碼:把d1,d2, dn 作為葉子結點，把w1,w2,wn作為葉子結點 的權，構造赫夫曼樹。在赫夫曼樹中結點的左分支賦0，右 分支賦1，從根結點到葉子結點的路徑上的數字拼接起來就 是這個葉子結點字符的編碼。 3、譯碼的過程是分解電文中的字符串，從根出發(fā)，按字符0或1確定找左孩子或右孩子，直至葉子節(jié)點，便求得該子串

3、相應的字符。心得體會：通過本次實驗，我熟練掌握了結構體、指針及二叉樹的生成、遍歷等操作，掌握了霍夫曼編碼和譯碼的原理，熟練掌握樹的操作，尤其是對霍夫曼樹有了更深刻的理解。同時，在編寫代碼的過程中方，對字符串的相關知識進行了回顧。代碼#include<stdio.h>#include<stdlib.h>#include<string.h>typedef structint weight;int parent,lchild,rchild;int sign;HTNode,*HuffmanTree;typedef char * *HuffmanCode;void H

4、uffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *s);void select(HuffmanTree &HT,int i,int &s1,int &s2);void creatHuffmanTree(int *w,char *s,char *r);void pr(HuffmanCode &HC,char r,char s,char a);void HuffmanYM(HuffmanCode &HC,char r,char a,int n,HuffmanTree

5、 &HT);void HuffmanPass(HuffmanCode &HC,char r,int n,HuffmanTree &HT);int main()char s100;char r100;char a100="a"int w100;int n,p;HuffmanTree HT;HuffmanCode HC;printf("請輸入進行編碼的字符串n");scanf("%s",s);p=strlen(s);if(p!=1)creatHuffmanTree(w,s,r);printf("進行編碼.

6、n"); if(p!=1) HuffmanCoding(HT,HC,w,strlen(r)-1,r);else printf("%c的霍夫曼編碼是: %cn",s0,'0');printf("霍夫曼碼序列為：n");if(p!=1) for(int i=0;i<strlen(s);i+) pr(HC,r,si,a);printf("n");n=strlen(r)-1;if(p=1)printf("0n");printf("霍夫曼編碼進行譯碼:n");if(p=1)

7、printf("%c",s0);else HuffmanYM(HC,r,a,n,HT);printf("n"); printf("先序遍歷輸出葉子節(jié)點n");if(p=1)printf("%cn",s0);else HuffmanPass(HC,r,n,HT);return 0;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w,int n,char s)int s1,s2,f,c;int m,i,l;int start;char cd1

8、01;if(n<1)return;l=strlen(s);m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HT0.weight=10000; for (i=1;i<=n;+i) HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; HTi.sign=0; for(;i<=m+1;+i) HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; HTi.sign=0; for(i=n+1;i<=m;i+

9、) select(HT,i-1,s1,s2);/選擇最小的兩個結點 HTs1.parent=i;HTs2.parent=i;/將它們的父節(jié)點賦值 HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n; c=i; for(f=HTi.parent;f!=0;f=HTf.parent) if(HTf.lchild=c) start-; cdsta

10、rt='0' else start-; cdstart='1' c=f; HCi=(char *)malloc(n-start)*sizeof(char); for(int a=0;a<n-start;a+) HCia=cdstart+a; HCia='0' printf("%c的霍夫曼編碼是: %sn",si,HCi);void select(HuffmanTree &HT,int i,int &s1,int &s2)s1=0;s2=0;for(int j=1;j<=i;j+)if(HTj

11、.parent=0)if(HTj.weight<=HTs1.weight)s1=j;else continue;else continue;for(j=1;j<=i;j+)if(j=s1)continue;else if(HTj.parent=0) if(HTj.weight<=HTs2.weight) s2=j; else continue; else continue;void creatHuffmanTree(int w,char s,char r)int g=1;int q=0;r0='0'r1=s0;w0=1;for(int e=1;e<str

12、len(s);e+)for(int k=1;k<=g;k+)if(rk=se)wk-1+;q=1;else continue;if(q=0)r+g=se;wg-1=1;q=0;r+g='0'void pr(HuffmanCode &HC,char r,char s,char a)for(int i=1;i<strlen(r);i+)if(ri=s)printf("%s",HCi);strcat(a,HCi);else continue;void HuffmanYM(HuffmanCode &HC,char r,char a,int

13、 n,HuffmanTree &HT)int e=strlen(a);int k=0;int f=2*n-1;char b10="1"for(int j=1;j<=e;j+)if(HTf.lchild!=0|HTf.rchild!=0)bk=aj;k+; if(aj='1') f=HTf.rchild;else if(aj='0')f=HTf.lchild;else for(int s=1;s<=n;s+)if(strcmp(HCs,b)=0)printf("%c",rs);break;else con

14、tinue;for(int u=0;u<10;u+)bu='0'k=0;f=2*n-1;j=j-1;void HuffmanPass(HuffmanCode &HC,char r,int n,HuffmanTree &HT)int f,k=0;char b10="a"f=2*n-1;HTf.sign=0;if(HTf.lchild=0&&HTf.rchild=0)return;doif(HTf.lchild=0&&HTf.rchild=0)for(int s=1;s<=n;s+)if(strcmp(HCs,b)=0)printf("%c",rs);break;else continue; bk-='0'HTf.s