2022年C语言哈夫曼编码、译码器 .pdf

《2022年C语言哈夫曼编码、译码器 .pdf》由会员分享，可在线阅读，更多相关《2022年C语言哈夫曼编码、译码器 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include#include#include#include#include /typedef int TElemType;const int UINT_MAX=1000;typedef struct int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char*HuffmanCode;/-全局变量-HuffmanTree HT;HuffmanCode HC;int*w,i,j,n;char*z;int flag=0;int numb=0;/-求赫夫曼编码-int min(HuffmanTree t,int i)/

2、函数 void select()调用int j,flag;int k=UINT_MAX;/取 k 为不小于可能的值for(j=1;j=i;j+)if(tj.weight s2)j=s1;s1=s2;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 14 页 -s2=j;/-算法 6.12-void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)/w 存放 n 个字符的权值(均0),构造赫夫曼树HT,并求出 n 个字符的赫夫曼编码HC int m,i,s1,s2,start;/unsigned c,f;int c,f;

3、HuffmanTree p;char*cd;if(n=1)return;/检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用for(p=HT+1,i=1;i weight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;i parent=0;for(i=n+1;i=m;+i)/建赫夫曼树/在 HT1i-1 中选择 parent 为 0 且 weight 最小的两个结点,其序号分别为s1 和 s2 select(HT,i-1,s1,s2);HTs1.parent=HTs2.

4、parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配 n 个字符编码的头指针向量(0不用)cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/编码结束符for(i=1;i=n;i+)/逐个字符求赫夫曼编码名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 14 页 -start=n-1;/编码结束符位置for(c=i

5、,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/为第 i 个字符编码分配空间strcpy(HCi,&cdstart);/从 cd 复制编码(串)到 HC free(cd);/释放工作空间/-初始化赫夫曼链表-void Initialization()flag=1;int num;int num2;cout 下面初始化赫夫曼链表 endl num;n=num;w=(int*)mallo

6、c(n*sizeof(int);z=(char*)malloc(n*sizeof(char);cout n 请依次输入 n 个字符(字符型)n 注意:必须以回车结束：endl;char base2;for(i=0;i n;i+)cout 第 i+1 个字符:endl;gets(base);*(z+i)=*base;for(i=0;i=n-1;i+)cout setw(6)*(z+i);cout n 请依次输入 n 个权值(n 注意:必须以回车结束)：endl;for(i=0;i=n-1;i+)cout endl 第 i+1 num2;*(w+i)=num2;名师资料总结-精品资料欢迎下载-名师

7、精心整理-第 3 页，共 14 页 -HuffmanCoding(HT,HC,w,n);/-打印编码-cout 字符对应的编码为:endl;for(i=1;i=n;i+)/cout 字符*(z+i-1)的编码;puts(HCi);/-将赫夫曼编码写入文件-cout 下面将赫夫曼编码写入文件 endl .endl;FILE*htmTree;char r=,0;if(htmTree=fopen(htmTree.txt,w)=NULL)cout can not open file endl;return;fputs(z,htmTree);for(i=0;i n+1;i+)fprintf(htmTre

8、e,%6d,*(w+i);fputs(r,htmTree);for(i=1;i=n;i+)fputs(HCi,htmTree);fputs(r,htmTree);fclose(htmTree);cout 已将字符与对应编码写入根目录下文件htmTree.txt 中 endl endl;/-获取报文并写入文件-void InputCode()/cout 请输入你想要编码的字符endl;FILE*tobetran;char str100;if(tobetran=fopen(tobetran.txt,w)=NULL)cout 不能打开文件 endl;名师资料总结-精品资料欢迎下载-名师精心整理-第

9、4 页，共 14 页 -return;cout 请输入你想要编码的字符 endl;gets(str);fputs(str,tobetran);cout 获取报文成功 endl;fclose(tobetran);/-编码函数-void Encoding()cout 下面对目录下文件tobetran.txt 中的字符进行编码 endl;FILE*tobetran,*codefile;if(tobetran=fopen(tobetran.txt,rb)=NULL)cout 不能打开文件 endl;if(codefile=fopen(codefile.txt,wb)=NULL)cout 不能打开文件

10、endl;char*tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99)if(fgets(tran,100,tobetran)=NULL)cout 不能打开文件 endl;break;for(i=0;*(tran+i)!=0;i+)for(j=0;j n)cout 字符错误，无法编码!endl;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 14 页 -cout 编码工作完成 endl 编码写入目录下的codefile.txt 中 endl endl;fclose(tobetran);fclose(code

11、file);free(tran);/-译码函数-void Decoding()cout 下面对根目录下文件codefile.txt 中的字符进行译码 endl;FILE*codef,*txtfile;if(txtfile=fopen(Textfile.txt,w)=NULL)cout 不能打开文件 endl;/txtfile=fopen(Textfile.txt,w);if(codef=fopen(codefile.txt,r)=NULL)cout 不能打开文件 endl;/codef=fopen(codefile.txt,r);char*work,*work2,i2;int i4=0,i,i

12、3;unsigned long length=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!=0;i+)i2=*(work+i);if(HTi3.lchild=0)*(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-;else if(i2=0)i3=HTi3.lchild;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 14 页

13、-else if(i2=1)i3=HTi3.rchild;*(work2+i4)=0;fputs(work2,txtfile);cout 译码完成 endl 内容写入根目录下的文件txtfile.txt 中 endl endl;cout work2;free(work);free(work2);fclose(txtfile);fclose(codef);/-打印赫夫曼树的函数-void coprint(HuffmanTree start,HuffmanTree HT)if(start!=HT)FILE*TreePrint;if(TreePrint=fopen(TreePrint.txt,a)=

14、NULL)cout 创建文件失败 rchild,HT);cout setw(5*numb)weight weight);coprint(HT+start-lchild,HT);numb-;fclose(TreePrint);void Tree_printing(HuffmanTree HT,int w)HuffmanTree p;p=HT+w;cout 下面打印赫夫曼树 endl;coprint(p,HT);cout 打印工作结束 endl;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 14 页 -/-主函数-void main()char choice;while(choic

15、e!=q)cout 赫夫曼编码解码系统 endl;cout 1.要初始化赫夫曼链表请输入i endl;cout 2.要编码请输入e endl;cout 3.要译码请输入d endl;cout 4.要打印编码请输入p endl;cout 5.要打印赫夫曼树请输入t endl;cout 6.要离开请输入q endl;/if(flag=0)coutn请先初始化赫夫曼链表,输入 i choice;switch(choice)case i:Initialization();break;case w:InputCode();break;case e:Encoding();break;case d:Deco

16、ding();break;case t:Tree_printing(HT,2*n-1);break;case q:default:cout input error endl;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 14 页 -free(z);free(w);free(HT);运行结果：赫夫曼编码解码系统1.要初始化赫夫曼链表请输入i 2.要编码请输入e 3.要译码请输入d 4.要打印编码请输入p 5.要打印赫夫曼树请输入t 6.要离开请输入q i 下面初始化赫夫曼链表数请输入结点的个n：8 请依次输入8 个字符(字符型)注意:必须以回车结束：第 1 个字符:a 第 2 个

17、字符:b 第 3 个字符:c 第 4 个字符:d 第 5 个字符:e 第 6 个字符:f 第 7 个字符:g 第 8 个字符:h a b c d e f g h 请依次输入8 个权值(注意:必须以回车结束)：第 1 个字符的权值:5 第 2 个字符的权值:29 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 14 页 -第 3 个字符的权值:7 第 4 个字符的权值:8 第 5 个字符的权值:14 第 6 个字符的权值:23 第 7 个字符的权值:3 第 8 个字符的权值:11 字符对应的编码为:0110 10 1110 1111 110 00 0111 010 下面将赫夫曼编码

18、写入文件.已将字符与对应编码写入根目录下文件htmTree.txt 中赫夫曼编码解码系统1.要初始化赫夫曼链表请输入i 2.要编码请输入e 3.要译码请输入d 4.要打印编码请输入p 5.要打印赫夫曼树请输入t 6.要离开请输入q i 下面初始化赫夫曼链表数请输入结点的个n：27 请依次输入27 个字符(字符型)注意:必须以回车结束：第 1 个字符:第 2 个字符:a 第 3 个字符:b 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 14 页 -第 4 个字符:c 第 5 个字符:d 第 6 个字符:e 第 7 个字符:f 第 8 个字符:g 第 9 个字符:h 第 10 个

19、字符:i 第 11 个字符:j 第 12 个字符:k 第 13 个字符:l 第 14 个字符:m 第 15 个字符:n 第 16 个字符:o 第 17 个字符:p 第 18 个字符:q 第 19 个字符:r 第 20 个字符:s 第 21 个字符:t 第 22 个字符:u 第 23 个字符:v 第 24 个字符:w 第 25 个字符:x 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 14 页 -第 26 个字符:y 第 27 个字符:z a b c d e f g m n o p q r s t z 请依次输入27 个权值(注意:必须以回车结束)：第 1 个字符的权值:186

20、 第 2 个字符的权值:64 第 3 个字符的权值:13 第 4 个字符的权值:22 第 5 个字符的权值:32 第 6 个字符的权值:103 第 7 个字符的权值:21 第 8 个字符的权值:15 第 9 个字符的权值:47 第 10 个字符的权值:57 第 11 个字符的权值:1 第 12 个字符的权值:5 第 13 个字符的权值:32 第 14 个字符的权值:20 第 15 个字符的权值:57 第 16 个字符的权值:63 第 17 个字符的权值:15 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 14 页 -第 18 个字符的权值:1 第 19 个字符的权值:48 第

21、 20 个字符的权值:51 第 21 个字符的权值:80 第 22 个字符的权值:23 第 23 个字符的权值:8 第 24 个字符的权值:18 第 25 个字符的权值:1 第 26 个字符的权值:16 第 27 个字符的权值:1 字符对应的编码为:110 1010 100100 00010 10110 010 111110 100101 0000 0110 1111011100 11110110 10111 111111 0111 1000 100110 1111011101 0010 0011 1110 00011 1111010 111100 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 14 页 -1111011110 100111 1111011111 下面将赫夫曼编码写入文件.已将字符与对应编码写入根目录下文件htmTree.txt 中名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 14 页 -