河南师范大学哈夫曼编译码系统的设计与实现.doc

哈夫曼编/译码系统的设计与实现 2014年12月 23日学 号姓 名时 间专 业计算机科学与技术班 级实验题目：哈夫曼编/译码系统的设计与实现一、 实验目的（1） 了解哈夫曼树的特点及构造方法；（2） 了解最优哈夫曼树的特点；二、 实验分析：#includestdio.h#includemalloc.h#includestring.h#define char_num 8 typedef struct char ch ; int w; DFileNode ;/ 定义数据文件的元素类型void creatDataFile( )/创建数据文件 FILE *f; char c; DFileNode s; int i,a9; /数组a用来存放从A-H每个字符出现的次数;0号单元不用 for(i=1;i=8;i+) ai=0; printf(创建数据文件DataFile.datn); printf(请输入一段仅包含大写字母A-H的一段文字以#结束n); c=getchar(); while(c!=#) ac-64+; /使字符c出现的次数+1;c=getchar(); f=fopen(DataFile.dat,wb);/写文件 for(i=1;i=8;i+) s.ch=i+64; s.w=ai; fwrite(&s,1,sizeof(DFileNode),f); fclose(f); f=fopen(DataFile.dat,rb); printf(字符及每个字符出现的次数(字符，出现次数)n); while(fread(&s,1,sizeof(DFileNode),f) printf(%c ,%d) , ,s.ch,s.w); fclose(f);void creatToBeTran( )/创建原文文件 FILE *f; char s; printf(创建原文文件,请输入一段仅包含大写字母A-H的一段文字作为原文以#结束n); f=fopen(ToBeTran.dat,w); s= getchar(); while(s!=#) fwrite(&s,1,sizeof(char),f); s=getchar(); fclose(f); void creatCodeFile( )/创建报文文件 FILE *f; int s; printf(创建报文文件,请输入一段仅包含0和1的一段文字作为原文以2作为结束标志.n); f=fopen(CodeFile.dat,wb); printf(输入报文0或1(输入的数字间用空格隔开)n); scanf(%d,&s); while(s2) fwrite(&s,1,sizeof(int),f); scanf(%d,&s); fclose(f); f=fopen(CodeFile.dat,r); while(fread(&s,1,sizeof(int),f) printf(%d ,s); fclose(f);typedef struct /赫夫曼树和赫夫曼编码的存储表示 char ch; int weight; int parent,lchild,rchild; char *next; / 指向该字符的编码 HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼树HuffmanTree HT;int min(HuffmanTree t,int i) / 函数void select()调用 int j,flag; int k=10000; / 字符出现的总次数不超过10000次 for(j=1;j=i;j+) if(tj.parent=0&tj.weights2) j=s1; s1=s2; s2=j; void print_huff_tree(HuffmanTree HT ,int n)/输出哈夫曼树，在必要时调用以验证算法的正确性 HuffmanTree p; int i; printf(字符 权 值 双 亲 左孩子 右孩子 指向编码的指针n); for(p=HT+1,i=1;i%sn,p-ch,p-weight,p-parent,p-lchild,p-rchild,p-next); void creatHuffmanTree( HuffmanTree &HT, int n) /创建含n个叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中,即初始化Initialzation FILE *f1; int m,i,s1,s2; HuffmanTree p; DFileNode s; /从文件中读数据时用； m=2*n-1; f1=fopen(DataFile.dat,rb); HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单元未用 for(p=HT+1,i=1;i=n;+i,+p) fread(&s,1,sizeof(DFileNode),f1); /从文件中读一个数给s,构造叶子 (*p).ch=s.ch; (*p).weight=s.w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; (*p).next=NULL; fclose(f1); printf(n); for(;i=m;+i,+p) (*p).ch= ;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;(*p).next=NULL; for(i=n+1;i=m;+i)/建n-1个分支结点 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; void HuffmanCoding(HuffmanTree &HT,int n) /对有n个叶子结点的哈夫曼树上的叶子结点进行编码 char *cd; int i,start,c,f; cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1=0; / 编码结束符 for(i=1;i=n;i+) / 逐个字符求赫夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0; else cd-start=1; HTi.next=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HTi.next,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间 void EnCoding()/编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中 FILE *f1, *f2; char s; int i; f2=fopen(Code.txt,w);/打开文件Code.txt为了写 f1=fopen(ToBeTran.dat,r);/打开文件ToBeTran.dat为了读 fgetc(f1); while(fread(&s,1,sizeof(char),f1) i=1; while(HTi.ch!=s) i+; fputs(HTi.next,f2); fclose(f1); fclose(f2);void Decoding( )/译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中 FILE *f1, *f2; char c; int s,p; f1=fopen(CodeFile.dat,rb); f2=fopen(Textfile.txt,w); p=2*char_num-1; /P指向哈夫曼树的根 while(fread(&s,1,sizeof(int),f1) / printf(%d,s);if(s=0) p=HTp.lchild; else p=HTp.rchild; if(HTp.lchild=0) c=HTp.ch; fputc(c,f2); p=2*char_num-1; /让P重新指向哈夫曼树的根 fclose(f1); fclose(f2);void output_1( )/输出原文和对应的译文； FILE *f1, *f2; char c; int s; f1=fopen(ToBeTran.dat,r);/打开文件ToBeTran.dat为了读 printf(原文：); while(fread(&c,1,sizeof(char),f1) printf(%c,c); fclose(f1); f2=fopen(Code.txt,r); printf(n译文：); while(fread(&c,1,sizeof(char),f2) putchar(c); printf(n); fclose(f2); void output_2( )/输出报文和对应的原文； FILE *f1, *f2; char c; int s; f1=fopen(CodeFile.dat,rb); printf(报文:); while(fread(&s,1,sizeof(int),f1) printf(%d,s); printf(n); fclose(f1); f2=fopen(Textfile.txt,r); printf(原文:); while(fread(&c,1,sizeof(char),f2) putchar(c); printf(n); fclose(f2);void main() int i , j; creatDataFile( );/创建数据文件 creatHuffmanTree(HT, char_num);/建哈夫曼树即初始化Initialzation printf(初始的哈夫曼树:n); print_huff_tree( HT, 2*char_num-1);/验证所建初始的哈夫曼树 HuffmanCoding(HT, char_num);/编码 printf(编码后的哈夫曼树:n); print_huff_tree( HT, 2*char_num-1);/验证编码后的哈夫曼树及编码 for(