数据结构实验报告(c语言)哈夫曼实验.pdf

1暨暨南大学本科南大学本科实验报实验报告告专专用用纸纸课程名称 数据结构 成绩评定 实验项目名称 哈夫曼编/译码器 指导教师 孙世良 实验项目编号 5 实验项目类型 实验地点 学生姓名 谢显栩 学号 2009051718 学院 电气信息学院 系 专业 软件工程实验时间 2010 年 11 月 20 日 中 午 11 月 20 日 下午 （一）（一）实验目的实验目的通过实验，理解且熟悉树型数据结构的应用与相关具体程序操作（二）（二）实验内容和要求实验内容和要求问题描述问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。基本要求基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件 hfmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。（4）P：印代码文件（Print）。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。（5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。2测试数据测试数据（1）利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“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（三）（三）主要仪器设备主要仪器设备仪器：仪器：计算机实验环境：实验环境：Windows 7+win-TC（四）（四）源程序源程序#include#include#include#include int n;struct node int w;int flag;char c;struct node*plink,*llink,*rlink;char code50;*num100,*root;FILE*fp;char tmpcode50;int t=0;void main(void)int i;void settree(void);void code(void);void decode(void);3 void disp(void);root=(struct node*)malloc(sizeof(struct node);while(1)start:puts(1.Initializationn2.Encodingn3.Decodingn4.Printn5.Tree printing);while(scanf(%d,&i)!=1)while(getchar()!=n)continue;puts(input error);puts(please repeat again);puts(1.Initializationn2.Encodingn3.Decodingn4.Printn5.Tree printing);switch(i)case 1:settree();break;case 2:code();break;case 3:decode();break;case 4:disp();break;case 5:exit(0);default:puts(input error);puts(please repeat again);goto start;getch();void settree(void)int i,j,k;struct node*p1,*p2,*tmp,*p;void go(struct node*);4 void setcode(struct node*);void printtree(struct node*);puts(please input the Quantity of Characters);scanf(%d,&n);while(getchar()!=n)continue;for(i=0;ic);while(getchar()!=n)continue;puts(please input the weight of the Character);scanf(%d,&p-w);while(getchar()!=n)continue;p-plink=NULL;p-rlink=NULL;p-llink=NULL;numi=p;for(i=0;in-1;i+)for(j=i+1;jwnumj-w)tmp=numi;numi=numj;numj=tmp;numn=NULL;k=n;while(num1!=NULL)p=(struct node*)malloc(sizeof(struct node);p1=num0;5 p2=num1;p-llink=p1;p-rlink=p2;p-plink=NULL;p1-plink=p;p2-plink=p;p-w=p1-w+p2-w;for(i=1;ik;i+)numi=numi+1;k-;num0=p;for(i=0;ik-1;i+)for(j=i+1;jwnumj-w)tmp=numi;numi=numj;numj=tmp;root=num0;if(fp=fopen(f:texttexthfmtree.wxl,wb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);setcode(root);go(root);fclose(fp);void setcode(struct node*p)if(p-llink=NULL&p-rlink=NULL)6 tmpcodet=0;strcpy(p-code,tmpcode);else tmpcodet+=0;setcode(p-llink);t-;tmpcodet+=1;setcode(p-rlink);t-;void go(struct node*p)if(p-llink=NULL&p-rlink=NULL)fputc(,fp);fputc(p-c,fp);fputs(p-code,fp);fputc(),fp);else go(p-llink);go(p-rlink);void code(void)FILE*fp1,*fp2,*fp3;char ch1,ch2,c;if(fp1=fopen(f:texttexthfmtree.wxl,rb)=NULL)puts(FILE OPEN ERROR);getchar();7 exit(0);if(fp2=fopen(f:texttexttobetran.txt,rb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);if(fp3=fopen(f:texttextcodefile.wxl,wb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);while(ch1=fgetc(fp2)!=EOF)t=0;while(ch2=fgetc(fp1)!=EOF)if(ch1=ch2)while(c=fgetc(fp1)!=)tmpcodet+=c;tmpcodet=0;fputs(tmpcode,fp3);fputc(,fp3);rewind(fp1);break;fclose(fp1);fclose(fp2);fclose(fp3);void decode(void)8 FILE*fp1,*fp2,*fp3;char ch1,ch2,ch3;char temp_320;char temp_120;int t1,t3;if(fp1=fopen(f:texttexthfmtree.wxl,rb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);if(fp2=fopen(f:texttexttextfile.txt,wb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);if(fp3=fopen(f:texttextcodefile.wxl,rb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);while(ch3=fgetc(fp3)!=EOF)t3=0;while(ch3!=)temp_3t3+=ch3;ch3=fgetc(fp3);temp_3t3=0;while(ch1=fgetc(fp1)!=EOF)if(isalpha(ch1)ch2=ch1;t1=0;while(ch1=fgetc(fp1)!=)temp_1t1+=ch1;temp_1t1=0;9 if(strcmp(temp_1,temp_3)=0)fputc(ch2,fp2);rewind(fp1);break;fclose(fp1);fclose(fp2);fclose(fp3);getch();void disp(void)FILE*fp1,*fp2;char ch1,ch2;char tmp20;int t;if(fp1=fopen(f:texttexthfmtree.wxl,rb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);if(fp2=fopen(f:texttexthfmcode.txt,wb)=NULL)puts(FILE OPEN ERROR);getchar();exit(0);while(ch1=fgetc(fp1)!=EOF)if(ch1=()t=0;ch1=fgetc(fp1);ch2=ch1;while(ch1=fgetc(fp1)!=)10 tmpt+=ch1;tmpt=0;printf(%c-%sn,ch2,tmp);fputc(ch2,fp2);fputc(-,fp2);fputc(-,fp2);fputc(-,fp2);fputs(tmp,fp2);fputc(n,fp2);fclose(fp1);fclose(fp2);（五）（五）数据调试数据调试首先建立准备好调试环境，本次试验将文本的建立与存储都放置在 F:/目录下1.运行程序，选择 1 项，进行编码表的输入11输入完成后在目录下生成 hfmtree.wxl 文件2.在目录下创建 tobetran.txt 文件，将“this program is my favorite”输入其中，在原程序中继续选择第二项编码操作，生成该句子的编码，并存储在 codefile.wxl 文件中。3.运行程序第三项译码，翻译 codefile 中的编码，将所得语句存储在textfile.txt 文件中124.在原程序中显示哈夫曼数，并将其写入文件 Treeprint.txt.(六六)实验结果与分析实验结果与分析试验结果基本无误。