哈夫曼编译码器设计.docx
- 文档编号:15771380
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:37
- 大小:318.81KB
哈夫曼编译码器设计.docx
《哈夫曼编译码器设计.docx》由会员分享,可在线阅读,更多相关《哈夫曼编译码器设计.docx(37页珍藏版)》请在冰点文库上搜索。
哈夫曼编译码器设计
兰州商学院陇桥学院
工学系课程设计报告
设计题目:
哈夫曼编译码器
系别:
工学系
专业(方向):
计算机科学与技术
年级、班:
2012级(网络工程方向)班
学生姓名:
xxx
学生学号:
xxxx
指导教师:
xxxx
2013年12月20日
目录
一、系统开发的背景1
二、系统分析与设计1
(一)系统功能要求1
(二)系统模块结构设计2
(一)初始化哈夫曼树:
InitHuffman(HuffmanHfm)3
(二)编码:
Encoding(HuffmanHfm)6
(三)译码:
Decoding(HuffmanHfm)7
(四)印代码文件:
Print(HuffmanHfm)9
(五)印哈夫曼树:
TreePrint(HuffmanHfm)10
四、系统测试11
(一)测试main()函数11
(二)测试InitHuffman(HuffmanHfm)函数12
(三)测试Encoding(HuffmanHfm)函数12
(四)测试Decoding(HuffmanHfm)函数12
(五)测试Print(HuffmanHfm)函数13
(六)测试TreePrint(HuffmanHfm)函数13
五、总结14
六、附件(代码、部分图表)14
哈夫曼编译码器
一、系统开发的背景
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼码的编/译码系统。
二、系统分析与设计
(一)系统功能要求
一个完整的哈夫曼系统应具有以下功能:
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)利用教科书中的数据调试程序。
2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:
“THISPROGRAMISMYFAVORITE”。
字符
空格
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
(二)系统模块结构设计
通过对系统功能的分析,哈夫曼编译码系统功能如图1所示。
图1哈夫曼编译码器系统功能图
通过上图的功能分析,把整个系统划分为6个模块
1、初始化哈夫曼树(Initialization),该模块主要实现:
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
借助函数InitHuffman(HuffmanHfm)来实现;
2、编码(Encoding),该模块主要实现:
利用以建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
借助函数voidEncoding(HuffmanHfm)来实现;
3、译码(Decoding),该模块主要实现:
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
借助函数voidDecoding(HuffmanHfm)来实现;
4、印代码文件(Print),该模块主要实现:
将文件CodeFile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
借助函数Print(HuffmanHfm)来实现;
5、印哈夫曼树(TreePrinting),该模块主要实现:
将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
借助函数Print(HuffmanHfm)来实现;
三、系统的设计与实现
(一)初始化哈夫曼树:
InitHuffman(HuffmanHfm)
分析:
首先建立一个哈夫曼树,对其进行初始化后,然后依次输入字符和权值的基本信息,存入文件。
流程图如图2所示。
图2:
InitHuffman(HuffmanHfm)流程图
该模块的具体代码如下所示。
#include
#include
#include
#include
#include
#defineMaxbite1000
#defineMax100
typedefchar**HuffmanCode;//动态分配数组存储哈夫曼表码表
typedefstruct{
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedefstruct{
HuffmanTreeHT;
char*c;
intlength;
HuffmanCodeHC;
}Huffman;//全局结构体变量,来存储字符与代码
voidSelect(HuffmanTreeHT,intend,int*s1,int*s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点,其序号为s1,s2
{
inti;
intmin1=Maxbite;
intmin2;
for(i=1;i<=end;i++)//遍历查找权值最小的结点S1
{
if(HT[i].parent==0&&HT[i].weight { *s1=i; min1=HT[i].weight; } } min2=Maxbite; for(i=1;i<=end;i++)//遍历查找除S1外权值最小的结点S2 { if(HT[i].parent==0&&(*s1! =i)&&min2>HT[i].weight) { *s2=i; min2=HT[i].weight; } } } HuffmanHuffmanCoding(HuffmanHfm)//存放n个字符的权值(均〉0),构造哈夫曼树HT,并求出n个字符的构造哈夫曼编码HC { inti,n,m,s1,s2,start; intc,f; char*cd; n=Hfm.length; if(n<=1)returnHfm; m=2*n-1; for(i=n+1;i<=m;++i)//选择HT[1....i-1]中无双亲且权值最小的两个节点,其序号为s1,s2 { Select(Hfm.HT,i-1,&s1,&s2); Hfm.HT[s1].parent=i;//修改父亲位置 Hfm.HT[s2].parent=i; Hfm.HT[i].lchild=s1;//修改孩子位置 Hfm.HT[i].rchild=s2; Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;//父亲结点权值为左右孩子权值之和 } //从叶子结点到根逆向求每个字符的哈夫曼编码 Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间 cd[n-1]='\0';//编码结束符 for(i=1;i<=n;++i)//逐个字符求哈夫曼编码 { start=n-1;//编码结束符位置 for(c=i,f=Hfm.HT[i].parent;f! =0;c=f,f=Hfm.HT[f].parent)//从叶子到根逆向求编码 { if(c==Hfm.HT[f].lchild) cd[--start]='0'; elsecd[--start]='1'; } Hfm.HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(Hfm.HC[i],&cd[start]);//从cd复制编码到Hfm.HC } free(cd);//释放工作空间 returnHfm; } HuffmanInputHuffman(HuffmanHfm)//输入函数,控制用户输入字符和相应权值 { inti,n; printf("请输入字符个数: "); scanf("%d",&n); if(n<=1) { printf("只有一个字符! 不能需要编码! \n");//若只有一个数值则无需编码 printf("请输入字符个数: "); scanf("%d",&n); } Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); Hfm.c=(char*)malloc((n+1)*sizeof(char)); for(i=1;i<=n;i++) { printf("请输入字符: "); scanf("%s",&Hfm.c[i]); printf("请输入这个字符的权值: "); scanf("%d",&Hfm.HT[i].weight); Hfm.HT[i].parent=0; Hfm.HT[i].lchild=0; Hfm.HT[i].rchild=0; } for(;i<=2*n-1;++i) { Hfm.HT[i].weight=0; Hfm.HT[i].parent=0; Hfm.HT[i].lchild=0; Hfm.HT[i].rchild=0; } Hfm.length=n; returnHfm; } HuffmanInitHuffman(HuffmanHfm)//初始化哈夫曼数,要求用户输入字符和相应权值 { intn,i,x; FILE*fp; fp=fopen("hfmTree","rt");//对文件hfmTree以读文本的形式打开 if(fp==NULL) { Hfm=InputHuffman(Hfm);//调用InputHuffman函数,用户输入字符和相应权值存入哈夫曼数中 fp=fopen("hfmTree","wt"); fprintf(fp,"%d\n",Hfm.length); for(i=1;i<=Hfm.length;i++) fprintf(fp,"%c%d",Hfm.c[i],Hfm.HT[i].weight); rewind(fp); } else { printf("字符已存在! \n");//询问是否重新初始化 scanf("%s",&x); if(x=='Y') {Hfm=InputHuffman(Hfm);//调用InputHuffman函数,用户输入字符和相应权值存入哈弗曼数中 fp=fopen("hfmTree","w+"); fprintf(fp,"%d\n",Hfm.length); for(i=1;i<=Hfm.length;i++) fprintf(fp,"%c%d",Hfm.c[i],Hfm.HT[i].weight); rewind(fp); } else { fscanf(fp,"%d\n",&n); Hfm.c=(char*)malloc((n+1)*sizeof(char)); Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); for(i=1;i<=n;i++) fscanf(fp,"%s%d",&Hfm.c[i],&Hfm.HT[i].weight);//将已经在文件中的字符和其对应的权重输入到Hfm.c[i]和&Hfm.HT[i].weight中 for(i=1;i<=n;i++)//对每个节点初始化 { Hfm.HT[i].parent=0; Hfm.HT[i].lchild=0; Hfm.HT[i].rchild=0; } for(;i<=2*n-1;++i) { Hfm.HT[i].weight=0; Hfm.HT[i].parent=0; Hfm.HT[i].lchild=0; Hfm.HT[i].rchild=0; } Hfm.length=n; } } fclose(fp); Hfm=HuffmanCoding(Hfm); returnHfm; } (二)编码: Encoding(HuffmanHfm) 分析: 利用已建好的Huffman树(如不在内存,则从文件hfmTre 中读入),对文件中的正文进行编码,然后将结果存入文件CodeFile中。 流程图如图3所示。 图3: Encoding(HuffmanHfm)流程图 该模块的具体代码如下所示。 voidEncoding(HuffmanHfm)//利用已建好的Huffman树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 { inti=0,j=0,n; charch[Max]; FILE*fp,*fw; n=Hfm.length; if((fw=fopen("ToBeTran","r+"))==NULL)//尝试打开ToBeTran { printf("请输入字符串: \n"); scanf("%s",ch); printf("\n"); fp=fopen("CodeFile","wt+"); } else { fscanf(fw,"%s",ch); fclose(fw); } while(ch[j]) { for(i=1;i<=n;i++) if(ch[j]==Hfm.c[i]) { printf("%s",Hfm.HC[i]); fprintf(fp,"%s",Hfm.HC[i]); break; } j++; } printf("\n"); rewind(fp); fclose(fp); } (三)译码: Decoding(HuffmanHfm) 分析: 利用已建好的Huffman树将文件CodeFile中的代码 进行译码,结果存入文件TextFile中。 流程图如图4所示。 图4: Decoding(HuffmanHfm)流程图 该模块的具体代码如下所示。 voidDecoding(HuffmanHfm)//利用已建好的Huffman树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 { HuffmanTreep; inti,n; intj=0; chard[500]; FILE*fp; n=Hfm.length; if((fp=fopen("CodeFile","r+"))==NULL) { printf("请输入代码: "); scanf("%s",d); } else { fscanf(fp,"%s",d);//将文件中的字符输入到数组d中 fclose(fp); } printf("文件是: \n"); fp=fopen("TextFile","wt+");//以写入文件的形式打开TextFile while(d[j]) { p=&Hfm.HT[2*n-1]; while(p->lchild||p->rchild) { if(d[j]=='0') {i=p->lchild;p=&Hfm.HT[i]; } else {i=p->rchild;p=&Hfm.HT[i]; } j++; } printf("%c",Hfm.c[i]); fprintf(fp,"%c",Hfm.c[i]); } printf("\n"); fclose(fp); } (四)印代码文件: Print(HuffmanHfm) 分析: 将文件CodeFile以紧凑格式显示在终端上流程图。 如图5所示。 图5: Printf(HuffmanHfm)流程图 该模块的具体代码如下所示。 voidPrint(HuffmanHfm)//将文件CodeFile以紧凑格式显示在终端上,每行50个代码。 { inti,n; intm=1;//计数器 charch; FILE*fprint; n=Hfm.length; printf("输出字符的代码: \n"); for(i=1;i<=n;i++)//显示每一个字符对应的哈夫曼编码 { printf("\n"); printf("Char: %c\t",Hfm.c[i]); printf("Weight: %d\t",Hfm.HT[i].weight); printf("Code: "); puts(Hfm.HC[i]); } fprint=fopen("CodeFile","rb"); while(feof(fprint)==0) { ch=fgetc(fprint); printf("%c",ch); m++; if(m%50==0)//保证每一行输出50个字符 printf("\n"); } printf("\n"); fclose(fprint); } (五)印哈夫曼树: TreePrint(HuffmanHfm) 分析: 将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。 如图6所示。 图6: TreePrintf(HuffmanHfm)流程图 该模块的具体代码如下所示。 voidTreePrint(HuffmanHfm)//将文件CodeFile以紧凑格式显示在终端上,每行50个代码。 { inti,n; intm=1;//计数器 charch; FILE*fprint; n=Hfm.length; printf("输出字符的代码: \n"); for(i=1;i<=n;i++)//显示每一个字符对应的哈夫曼编码 { printf("\n"); printf("Char: %c\t",Hfm.c[i]); printf("Weight: %d\t",Hfm.HT[i].weight); printf("Code: "); puts(Hfm.HC[i]); } fprint=fopen("CodeFile","rb"); while(feof(fprint)==0) { ch=fgetc(fprint); printf("%c",ch); m++; if(m%50==0)//保证每一行输出50个字符 printf("\n"); } printf("\n"); fclose(fprint); } 四、哈夫曼编译码器源代码 #include #include #include #include #include #defineMaxbite1000 #defineMax100 typedefchar**HuffmanCode;//动态分配数组存储哈夫曼表码表 typedefstruct{ intweight; intparent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 typedefstruct{ HuffmanTreeHT; char*c; intlength; HuffmanCodeHC; }Huffman;//全局结构体变量,来存储字符与代码 voidSelect(HuffmanTreeHT,intend,int*s1,int*s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点,其序号为s1,s2 { inti; intmin1=Maxbite; intmin2; for(i=1;i<=end;i++)//遍历查找权值最小的结点S1 { if(HT[i].parent==0&&HT[i].weight { *s1=i; min1=HT[i].weight; } } min2=Maxbite; for(i=1;i<=end;i++)//遍历查找除S1外权值最小的结点S2 { if(HT[i].parent==0&&(*s1! =i)&&min2>HT[i].weight) { *s2=i; min2=HT[i].weight; } } } HuffmanHuffmanCoding(HuffmanHfm)//存放n个字符的权值(均〉0),构造哈夫曼树HT,并求出n个字符的构造哈夫曼编码HC { inti,n,m,s1,s2,start; intc,f; char*cd; n=Hfm.length; if(n<=1)re
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼编 译码器 设计