数据结构实验报告c语言哈夫曼实验.docx
- 文档编号:16924896
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:17
- 大小:189.71KB
数据结构实验报告c语言哈夫曼实验.docx
《数据结构实验报告c语言哈夫曼实验.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告c语言哈夫曼实验.docx(17页珍藏版)》请在冰点文库上搜索。
数据结构实验报告c语言哈夫曼实验
暨南大学本科实验报告专用纸
课程名称数据结构成绩评定
实验项目名称哈夫曼编/译码器指导教师孙世良
实验项目编号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:
印哈夫曼树(Treeprinting)。
将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
[测试数据]
(1)利用下面这道题中的数据调试程序。
某系统在通信联络中只可能出现八种字符,其概率分别为0.25,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计哈夫曼编码。
(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:
“THISPROGRAMISMYFAVORITE”。
字符空格 A B C D E F G H I J K L M
频度186 64 13 22 32103 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
(三)主要仪器设备
仪器:
计算机
实验环境:
Windows7+win-TC
(四)源程序
#include
#include
#include
#include
intn;
structnode{
intw;
intflag;
charc;
structnode*plink,*llink,*rlink;
charcode[50];
}*num[100],*root;
FILE*fp;
chartmpcode[50];
intt=0;
voidmain(void)
{
inti;
voidsettree(void);
voidcode(void);
voiddecode(void);
voiddisp(void);
root=(structnode*)malloc(sizeof(structnode));
while
(1){
start:
puts("1.Initialization""\n""2.Encoding""\n""3.Decoding""\n""4.Print""\n""5.Treeprinting");
while(scanf("%d",&i)!
=1)
{
while(getchar()!
='\n')
continue;
puts("inputerror");
puts("pleaserepeatagain");
puts("1.Initialization""\n""2.Encoding""\n""3.Decoding""\n""4.Print""\n""5.Treeprinting");
}
switch(i)
{
case1:
settree();
break;
case2:
code();
break;
case3:
decode();
break;
case4:
disp();
break;
case5:
exit(0);
default:
puts("inputerror");
puts("pleaserepeatagain");
gotostart;
}
}
getch();
}
voidsettree(void)
{
inti,j,k;
structnode*p1,*p2,*tmp,*p;
voidgo(structnode*);
voidsetcode(structnode*);
voidprinttree(structnode*);
puts("pleaseinputtheQuantityofCharacters");
scanf("%d",&n);
while(getchar()!
='\n')
continue;
for(i=0;i { p=(structnode*)malloc(sizeof(structnode)); puts("pleaseinputaCharacter"); scanf("%c",&p->c); while(getchar()! ='\n') continue; puts("pleaseinputtheweightoftheCharacter"); scanf("%d",&p->w); while(getchar()! ='\n') continue; p->plink=NULL; p->rlink=NULL; p->llink=NULL; num[i]=p; } for(i=0;i { for(j=i+1;j { if(num[i]->w>num[j]->w) { tmp=num[i]; num[i]=num[j]; num[j]=tmp; } } } num[n]=NULL; k=n; while(num[1]! =NULL) { p=(structnode*)malloc(sizeof(structnode)); p1=num[0]; p2=num[1]; p->llink=p1; p->rlink=p2; p->plink=NULL; p1->plink=p; p2->plink=p; p->w=p1->w+p2->w; for(i=1;i { num[i]=num[i+1]; } k--; num[0]=p; for(i=0;i { for(j=i+1;j { if(num[i]->w>num[j]->w) { tmp=num[i]; num[i]=num[j]; num[j]=tmp; } } } } root=num[0]; if((fp=fopen("f: \\text\text\hfmtree.wxl","wb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } setcode(root); go(root); fclose(fp); } voidsetcode(structnode*p) { if(p->llink==NULL&&p->rlink==NULL) { tmpcode[t]='\0'; strcpy(p->code,tmpcode); } else { tmpcode[t++]='0'; setcode(p->llink); t--; tmpcode[t++]='1'; setcode(p->rlink); t--; } } voidgo(structnode*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); } } voidcode(void) { FILE*fp1,*fp2,*fp3; charch1,ch2,c; if((fp1=fopen("f: \\text\text\hfmtree.wxl","rb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } if((fp2=fopen("f: \\text\text\tobetran.txt","rb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } if((fp3=fopen("f: \\text\text\codefile.wxl","wb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } while((ch1=fgetc(fp2))! =EOF) { t=0; while((ch2=fgetc(fp1))! =EOF) { if(ch1==ch2) { while((c=fgetc(fp1))! =')') { tmpcode[t++]=c; } tmpcode[t]='\0'; fputs(tmpcode,fp3); fputc('@',fp3); rewind(fp1); break; } } } fclose(fp1); fclose(fp2); fclose(fp3); } voiddecode(void) { FILE*fp1,*fp2,*fp3; charch1,ch2,ch3; chartemp_3[20]; chartemp_1[20]; intt1,t3; if((fp1=fopen("f: \\text\text\hfmtree.wxl","rb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } if((fp2=fopen("f: \\text\text\textfile.txt","wb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } if((fp3=fopen("f: \\text\text\codefile.wxl","rb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } while((ch3=fgetc(fp3))! =EOF) { t3=0; while(ch3! ='@') { temp_3[t3++]=ch3; ch3=fgetc(fp3); } temp_3[t3]='\0'; while((ch1=fgetc(fp1))! =EOF) { if(isalpha(ch1)) { ch2=ch1; t1=0; while((ch1=fgetc(fp1))! =')') { temp_1[t1++]=ch1; } temp_1[t1]='\0'; if(strcmp(temp_1,temp_3)==0) { fputc(ch2,fp2); rewind(fp1); break; } } } } fclose(fp1); fclose(fp2); fclose(fp3); getch(); } voiddisp(void) { FILE*fp1,*fp2; charch1,ch2; chartmp[20]; intt; if((fp1=fopen("f: \\text\text\hfmtree.wxl","rb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } if((fp2=fopen("f: \\text\text\hfmcode.txt","wb"))==NULL) { puts("FILEOPENERROR"); getchar(); exit(0); } while((ch1=fgetc(fp1))! =EOF) { if(ch1=='(') { t=0; ch1=fgetc(fp1); ch2=ch1; while((ch1=fgetc(fp1))! =')') { tmp[t++]=ch1; } tmp[t]='\0'; printf("%c-----%s\n",ch2,tmp); fputc(ch2,fp2); fputc('-',fp2); fputc('-',fp2); fputc('-',fp2); fputs(tmp,fp2); fputc('\n',fp2); } } fclose(fp1); fclose(fp2); } (五)数据调试 首先建立准备好调试环境,本次试验将文本的建立与存储都放置在F: /目录下 1.运行程序,选择1项,进行编码表的输入 输入完成后在目录下生成hfmtree.wxl文件 2.在目录下创建tobetran.txt文件,将“thisprogramismyfavorite”输入其中,在原程序中继续选择第二项编码操作,生成该句子的编码,并存储在codefile.wxl文件中。 3.运行程序第三项译码,翻译codefile中的编码,将所得语句存储在textfile.txt文件中 4.在原程序中显示哈夫曼数,并将其写入文件Treeprint.txt. (六)实验结果与分析 试验结果基本无误。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 语言 哈夫曼