哈夫曼编码算法实现完整版

1、实验三 树的应用一.实验题目：树的应用哈夫曼编码二.实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。三、程序源代码:#include #include #include #include typedef struct char data; int weight; int parent,lchild,rchild;HTNo

2、de,*HuffmanTree;typedef char * * HuffmanCode;void Select(HuffmanTree &HT,int n,int m) HuffmanTree p=HT; int tmp; for(int j=n+1;j=m;j+) int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x=j-1;x+) if(px.parent=0&px.weighttag1) tag1=px.weight;s1=x; for(int y=1;y=j-1;y+) if(py.parent=0&y!=s1&py.weights2

3、) /将选出的两个节点中的序号较小的始终赋给s1 tmp=s1; s1=s2; s2=tmp;ps1.parent=j;ps2.parent=j;pj.lchild=s1;pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) int m=2*n-1; if(n=1) return; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); HuffmanTree p=HT; for(int i=1;i=n;i+)

4、 pi.data=w1i-1; pi.weight=w2i; pi.parent=pi.lchild=pi.rchild=0; for(;i=m;i+) pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(HT,n,m); ofstream outfile; /生成hfmTree文件 outfile.open(hfmTree.txt,ios:out); for (i=1;i=m;i+)outfileHTi.weighttHTi.parenttHTi.lchild tHTi.rchildtendl; outfile.close(); cout初始化

5、结果已保存在hfmTree文件中n;void ToBeTree() /将正文写入文件ToBeTree中ofstream outfile;outfile.open(ToBeTree.txt,ios:out);outfileTHIS PROGRAM IS MYFAVORITE;outfile.close();void Encoding(HuffmanTree &HT,int n) /编码 HuffmanCode HC; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); char *cd; cd=(char *)malloc(n*sizeof(char); cd

6、n-1=0; for(int k=1;k=n;k+) int start=n-1; for(int c=k,f=HTk.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCk=(char *)malloc(n-start)*sizeof(char); strcpy(HCk,&cdstart); cout输出哈夫曼编码:endl; for(int h=1;h=n;h+) /输出编码 coutHTh.data:; coutHCh; cout ; if (h%8=0) coutendl; cout

7、endl输出正文编码:endl; ToBeTree(); /读取TOBETREE文件里的正文，并进行编码 fstream infile; infile.open(ToBeTree.txt,ios:in); char s80; while(!infile.eof() infile.getline(s,sizeof(s); infile.close(); fstream outfile; outfile.open(CodeFile.txt,ios:out); int count=0; for (h=0;sh!=0;h+) for(k=1;k=n;k+) if (sh=HTk.data) coutH

8、Ck; cout ; count+; outfileHCk; break; if (count%9=0) coutendl; /每输出7个换行 outfile.close(); coutn编码结果已保存在文件CodeFile中.; coutendl;void Decoding(HuffmanTree &HT,int n) /译码 int f=2*n-1; fstream infile; infile.open(CodeFile.txt,ios:in); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); infile.clos

9、e(); int i=0; int j=0; fstream outfile; outfile.open(TextFile.txt,ios:out); while(si!=0) f=2*n-1;while(HTf.lchild!=0)/以f对应的节点的左孩子的值=0作为结束 if (sj=0) f=HTf.lchild;else f=HTf.rchild;j+; i=j; coutHTf.data; outfileHTf.data; outfile.close();coutn译码结果已保存在文件TextFile中.;coutendl;void Print() /印代码文件 int count=

10、0; fstream infile; infile.open(CodeFile.txt,ios:in); char s1000; while(!infile.eof() infile.getline(s,sizeof(s); for(int i=0;si!=0;i+) coutsi;count+;if (count%50=0) coutendl; /在终端上每行显示50个代码 infile.close();coutendl;char menu() /菜单函数 cout功能菜单如下:endl; cout* * * * * * * * * * * * * * * * * * * * *endl;

11、cout I:初始化(Initialization) endl; cout E:编码(Encoding) endl; cout D:译码(Decoding) endl; cout P:印代码文件(Print) endl; cout Q:退出(Exit) endl; cout* * * * * * * * * * * * * * * * * * * * *endl; coutch;return ch;void main() int n; int Array100; char cArray100; HuffmanTree HT; cout输入n个字符:; cin.getline(cArray,10

12、0); n=strlen(cArray); cout一共n个字符.n; cout依次输入各个字符的权值:endl; for (int i=1;iArrayi; int tag; char x=menu(); while(1) switch (x) case I:HuffmanCoding(HT,n,cArray,Array);break; case E:Encoding(HT,n);break; case D:Decoding(HT,n);break; case P:Print();break; case Q:tag=0;cout结束endl;break; default:cout你输入错误!

13、endl; if(tag=0) break; couty(继续) or n(退出)ch; if (ch=y) coutc; x=c; else exit(1); 测试数据： 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的译码和编码:THIS PROGRAM IS MY FAVORITE. 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 四.测试结果：如图一所示五.实验体会 通过本次实验，尤其在自己对程序的调试过程中，感觉对树的存储结构，终结状态，还有编码，译码的过程都有了比较清