哈夫曼编解码完整c程序代码

1、1）内容： 利用 Huffman 编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。 2）要求： 一个完整的huffman编解码系统应该具有以下功能： 初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。 编码（Encoding）。利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree中读取），对文件ToBeTran中

2、的正文进行编码，然后将结果存入文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 解码（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。 打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件CodePrint中。 打印Huffman树（Tree Printing）。将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件Tre

3、ePrint中。3) 测试数据: 用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 10321 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 完整代码如下：#include<stdio.h>#include<iostream>#include<str

4、ing>#define N 100int *w;char *c,stackN,codeNN;int s1,s2;typedef struct HuffmanTreeint weight;int parent;int lchild;int rchild;HuffmanTree,*Huff;void menu(void); void Select(struct HuffmanTree HT,int i); void HuffmanTree(Huff &HT,int *w,int n);void visite(Huff HT,int i,int flag,int rear);void

5、translatef(char *scource,char *save,int n);bool uncodef(FILE *fp1,FILE *fp2,Huff HT,int n);int inputHuff();void screanio(int n);void fileio(int n);int initHuff();void Print_tree(int n,Huff HT);void Convert_tree(Huff HT,unsigned char T100100,int tt100100,int s,int *i,int j);void decoding(int n);void

6、coding(int n);void main()int n=0;menu();Huff HT;char state; dostd:cout<<"input:n"std:cin>>state;fflush(stdin); /读取状态switch(state) case'I':n=inputHuff();HuffmanTree(HT,w,n);std:cout<<"nHuffmanTree 初始化完毕n"break; case'C':coding(n);break; case'D&

7、#39;:decoding(n);break; case'P':Print_tree(n,HT);break; case'Q':break;while(state!='Q');void menu() /显示菜单函数std:cout<<"=HuffmanCoding=n" std:cout<<"input tt don"std:cout<<"I ttInit_HUffTreen" /初始化huffmantreestd:cout<<"

8、C ttCodingn" /对ToBeTran.txt文件中的字符进行编码到CodeFile.txt中std:cout<<"D ttUnCodingn" /对CodeFile.txt中的01序列进行解码到TextFile.txtstd:cout<<"P ttPrintTreen" /打印哈夫曼树std:cout<<"Q ttquitn"std:cout<<"请初始化哈夫曼树再执行后面的操作n"int inputHuff() /输入各个字母及其权值int i=

9、1,n=0;int ww28;char cc28;while(1)std:cout<<"input the letter(input '#' to stop):"cci=std:cin.get();fflush(stdin);if(cci='#')break;std:cout<<"input the weight:"std:cin>>wwi;fflush(stdin);n+;i+;w=(int *)malloc(sizeof(int)*(n+1);c=(char *)malloc(siz

10、eof(char)*(n+1);for(i=0;i<n+1;i+)wi=wwi;ci=cci;return n;void HuffmanTree(Huff &HT,int *w,int n) /初始化哈夫曼树int m,i;m=n*2-1;HT=(struct HuffmanTree *)malloc(sizeof(struct HuffmanTree)*(m+1);HT0.lchild=0;HT0.parent=0;HT0.rchild=0;HT0.weight=0;for(i=1;i<m;i+)HTi.weight=i<=n?wi:0;HTi.lchild=HTi

11、.rchild=HTi.parent=0;for(i=n+1;i<=m;i+) Select(HT,i);HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=HTs2.parent=i;void Select(struct HuffmanTree HT,int i) /在HT1.i-1中选择parent为0且weight为最小的两个结点 int j;for(j=1;j<i;j+)if(HTj.parent =0)s1=j;s2=j;goto flag;flag: for(j=s1+1;

12、j<i;j+)if(HTj.parent=0)if(HTs1.weight >=HTj.weight)s2=s1;s1=j;if(HTs2.weight>HTj.weight&&j!=s1)s2=j;if(s1=s2)s2=j;void Print_tree(int n,Huff HT) /以凹入法的形式打印树 unsigned char T100100; int tt100100; int i,j,m=0; FILE *fp; Convert_tree(HT,T,tt,0,&m,2*n-1); /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中

13、if(fp=fopen("treeprint.txt","wb+")=NULL) printf("Open file treeprint.txt error!n"); printf("n以凹凸表形式打印已建好的赫夫曼树：n"); for(i=1;i<=2*n-1;i+) for (j=0;Tij!=0;j+) if(Tij=' ') printf(" ");fputc(Tij,fp); else printf("%d",ttij);fprintf(fp,

14、"%dnnn",ttij); printf("n"); fclose(fp); printf("n此字符形式的哈夫曼树已写入文件treeprint.txt中.nn"); printf("n文件treeprint.txt的打开方式要为写字板，若打开方式为记事本，则无法显示凹凸表的形式n"); void Convert_tree(Huff HT,unsigned char T100100,int tt100100,int s,int *i,int j) /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中 int k

15、,l; l=+(*i); for(k=0;k<s;k+) Tlk=' ' Tlk='#' ttlk=HTj.weight; if(HTj.lchild) Convert_tree(HT,T,tt,s+1,i,HTj.lchild); if(HTj.rchild) Convert_tree(HT,T,tt,s+1,i,HTj.rchild); Tl+k='0' void coding(int n) /对文件ToBeTran.txt编码到CodeFile.txt FILE *fp1;Huff HT;HuffmanTree(HT,w,n);vis

16、ite(HT,2*n-1,2,0);fflush(stdin);translatef("ToBeTran.txt","CodeFile.txt",n);fp1=fopen("CodeFile.txt","r");printf("n编码已写入文件treeprint.txt中.n");fclose(fp1);void decoding(int n) /对CodeFile.txt中的01序列进行解码到TextFile.txtFILE *fp1,*fp2;Huff HT;HuffmanTree(HT,w

17、,n);fp1=fopen("CodeFile.txt","r");fp2=fopen("TextFile.txt","w");while(uncodef(fp1,fp2,HT,2*n-1);printf("n");printf("n解码已写入文件TextFile.txt中.n");fclose(fp1);fclose(fp2);void visite(Huff HT,int i,int flag,int rear)/通过递归调用visite()函数，得到各个字母的编码，存储

18、于全局变量code中int j=0,k=0;if(flag=0) stackrear='0'rear+;else if(flag=1)stackrear='1'rear+;if(HTi.lchild=0)for(j=0;j<rear;j+)codeij=stackj;codeij='#'rear-;return;visite(HT,HTi.lchild,0,rear);visite(HT,HTi.rchild,1,rear);k=rear;for(j=0;j<k;j+)codeij=stackj;codeij='#'r

19、ear-;return;void translatef(char *scource,char *save,int n)/读取文件中的字母序列，并根据code将其转换成01序列输出FILE *fp1,*fp2;char p=' 'int i=0,j=0,k=0;fp1=fopen(scource,"r");fp2=fopen(save,"w");p=fgetc(fp1);printf("n得到的编码为:n");while(p!=EOF)for(i=0;i<=n;i+)if(ci=p)for(j=0;j<N&&