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

1）内容： 利用 Huffman 编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。 2）要求： 一个完整的huffman编解码系统应该具有以下功能： 初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。 编码（Encoding）。利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 解码（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。 打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件CodePrint中。 打印Huffman树（Tree Printing）。将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。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#include#include#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 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 coding(int n);void main()int n=0;menu();Huff HT;char state; dostd:coutstate;fflush(stdin); /读取状态switch(state) caseI:n=inputHuff();HuffmanTree(HT,w,n);std:coutnHuffmanTree 初始化完毕n;break; caseC:coding(n);break; caseD:decoding(n);break; caseP:Print_tree(n,HT);break; caseQ:break;while(state!=Q);void menu() /显示菜单函数std:cout=HuffmanCoding=n; std:coutinput tt don;std:coutI ttInit_HUffTreen; /初始化huffmantreestd:coutC ttCodingn; /对ToBeTran.txt文件中的字符进行编码到CodeFile.txt中std:coutD ttUnCodingn; /对CodeFile.txt中的01序列进行解码到TextFile.txtstd:coutP ttPrintTreen; /打印哈夫曼树std:coutQ ttquitn;std:cout请初始化哈夫曼树再执行后面的操作n;int inputHuff() /输入各个字母及其权值int i=1,n=0;int ww28;char cc28;while(1)std:coutinput the letter(input # to stop):;cci=std:cin.get();fflush(stdin);if(cci=#)break;std:coutwwi;fflush(stdin);n+;i+;w=(int *)malloc(sizeof(int)*(n+1);c=(char *)malloc(sizeof(char)*(n+1);for(i=0;in+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;im;i+)HTi.weight=i=n?wi:0;HTi.lchild=HTi.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;ji;j+)if(HTj.parent =0)s1=j;s2=j;goto flag;flag: for(j=s1+1;j=HTj.weight)s2=s1;s1=j;if(HTs2.weightHTj.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中 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,%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,l; l=+(*i); for(k=0;ks;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);visite(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,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()函数，得到各个字母的编码，存储于全局变量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;jrear;j+)codeij=stackj;codeij=#;rear-;return;visite(HT,HTi.lchild,0,rear);visite(HT,HTi.rchild,1,rear);k=rear;for(j=0;jk;j+)codeij=stackj;codeij=#;rear-;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=50)k=0;putchar(n);p=fgetc(fp1);fclose(fp1);fclose(fp2);bool uncodef(FILE *fp1,FILE *fp2,Huff HT,int n)/通过对树的访问，把文件中01序列转换成一个字母输出。本函数需循环调用，当读到n时返回falsechar p= ;if(!fp1|!fp2)printf(error);exit(0);if(HTn.lchild=0)fputc(cn,fp2);return true;else