哈夫曼编码和译码的设计与实现.docx
《哈夫曼编码和译码的设计与实现.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码和译码的设计与实现.docx（17页珍藏版）》请在冰点文库上搜索。
哈夫曼编码和译码的设计与实现
算法与数据结构课程设计
哈夫曼编码和译码的设计与实现
1。
问题描述
利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）.对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼码的编/译码系统。
2.基本要求
a。
编/译码系统应具有以下功能:
（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中。
b。
测试数据
（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
3．需求分析
3.1程序的基本功能
本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。
并可以在程序运行结束后的任意时间对它解码还原生成字符文件。
即：
先对一条电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码串进行译码,最后输出电文数字
3。
2输入/输出形式
当进行编码时输入为原字符文件文件名，当程序运行编码完成之后输入编码文件名（默认名为code。
dll）。
当进行译码时输入为编码文件名（默认名为code。
dll），从文件中读取Huffman编码树后输入字符文件的文件名.
3.3测试数据要求
本程序中测试数据主要为字符型文件。
4．概要设计
1。
系统结构图（功能模块图）
2．功能模块说明
（1）.编码：
提示要编码的文件文件名→读取文件→以字母出现次数为权值建立哈弗曼树→对文本进行哈弗曼编码并输出编码→提示将编码保存的文件名→保存编码文件;
（2）.译码：
提示输入要译码的文件名→利用建立好的哈弗曼树进行译码→将译码输出→提示保存译码文件的文件名→保存译码文件；
（3）.退出:
退出系统，程序运行结束.
5．详细设计
创建哈弗曼树
编码
译码
6．调试分析
1。
从叶子节点开始向上遍历二叉树，获得哈夫曼编码;
2.根据哈夫曼编码遍历哈夫曼树直到叶子节点,获得译码
3。
算法的时间复杂度分析:
程序部分用双循环嵌套结构，时间复杂度为O（n2）.
4．算法的空间复杂度分析：
算法的空间复杂度为O（n）
5。
程序需要反复调试,并且调试过程比较慢，需要有一个比较正确的调试方法，更需要我们有耐心
7．用户使用说明
1。
输入字符的个数n
2输入n个字符和n个权值
3选择（1—5）操作可对huffman树进行编码和译码以及huffman树表的打印
4退出系统
8．测试结果
9．附录
#include”stdio.h”
#include"stdlib.h”
＃include"string.h”
#defineMAX100
structHafNode
｛
intweight；
intparent;
charch;
intlchild；
intrchild；
}＊myHaffTree；
structCoding
｛
charbit［MAX];
charch；
intweight;
｝＊myHaffCode；
voidHaffman（intn）/＊构造哈弗曼树*/
{
inti,j,x1,x2,s1，s2;
for（i=n+1;i<=2*n—1；i++）
{
s1=s2=10000；
x1=x2=0；
for（j=1;j〈=i-1；j++）
{
if（myHaffTree［j].parent==0＆＆myHaffTree［j]。
weight｛
s2=s1；
x2=x1；
s1=myHaffTree[j]。
weight;
x1=j;
}
elseif（myHaffTree[j］。
parent==0＆&myHaffTree［j]。
weight{
s2=myHaffTree[j］.weight；
x2=j；
}
}
myHaffTree［x1]。
parent=i；
myHaffTree［x2］。
parent=i；
myHaffTree[i]。
weight=s1+s2；
myHaffTree[i］。
lchild=x1；
myHaffTree［i]。
rchild=x2;
｝
｝
voidHaffmanCode（intn）
｛
intstart，c，f,i,j，k；
char*cd；
cd=（char＊）malloc（n*sizeof（char））；
myHaffCode=（structCoding*）malloc（（n+1）*sizeof（structCoding））;
cd[n—1］=’\0';
for（i=1；i<=n；++i）
｛
start=n-1;
for（c=i,f=myHaffTree[i］。
parent;f!
=0；c=f，f=myHaffTree[f].parent）
if（myHaffTree［f］.lchild==c）cd[—-start]='0';
elsecd［——start]=’1'；
for（j=start，k=0；j{
myHaffCode[i]。
bit[k]=cd［j];
k++;
｝
myHaffCode[i］.ch=myHaffTree[i]。
ch；
myHaffCode［i]。
weight=myHaffTree[i］。
weight;
｝
free（cd）；
｝
voidprint（）
{
printf（"*＊＊＊*＊**＊*＊＊**＊＊**＊*＊＊*＊＊＊＊＊**＊＊**＊*＊＊＊＊＊＊***＊*＊*＊*＊＊＊＊＊***＊＊*＊*＊**＊＊***＊＊＊＊**＊\n”）；
printf（"＊***＊＊*＊＊＊\n"）；
printf（"＊****＊****\n”）；
printf（"****＊welcometohuffmancodingandcodeprinting＊**＊＊\n”）;
printf（"**＊＊＊＊＊***\n”）;
printf（”＊**＊*＊***＊\n"）；
printf（”＊****1.init2。
coding3。
codeprinting4。
printthehuffman5。
exit****＊\n"）;
printf（"＊***＊＊*＊＊*\n"）;
printf（”*＊＊＊＊＊＊**＊*＊*＊**＊*＊***＊＊＊***＊*＊*＊＊*＊**＊**＊**＊***＊**＊＊＊**＊****＊****＊＊*＊*＊*＊＊**＊*\n”）；
｝
Init（）
{
inti，n，m；
printf（”nowinit\n"）;
printf（”pleaseinputthenumberofwords：
\n"）；
scanf（"%d”，&n）;
m=2＊n—1；
myHaffTree=（structHafNode＊）malloc（sizeof（structHafNode）＊（m+1））;
for（i=1；i〈=n;i++）
｛
printf（"pleaseinputthewordandtheequal：
\n”）;
scanf（”％s％d"，&myHaffTree［i］.ch，&myHaffTree[i］.weight）；
myHaffTree[i]。
parent=0;
myHaffTree［i］.lchild=0；
myHaffTree［i］。
rchild=0;
}
for（i=n+1；i<=m;i++）
{
myHaffTree[i].ch=’#'；
myHaffTree[i].lchild=0；
myHaffTree［i］.parent=0;
myHaffTree[i］.rchild=0;
myHaffTree［i］。
weight=0;
}
Haffman（n）;
HaffmanCode（n）；
for（i=1；i<=n;i++）
｛
printf（"％c%d"，myHaffCode［i].ch，myHaffCode［i].weight）;
printf（”\n"）；
}
printf（"initsuccess!
\n"）;
returnn；
}
voidCaozuo_C（intm）/＊对字符进行编码＊/
{
intn，i，j；
charstring[50]，*p;
printf（"pleaseinputthewords:
\n”）;
scanf（"％s",string）;
n=strlen（string）；
for（i=1，p=string；i〈=n；i++，p++）
｛
for（j=1；j<=m;j++）
if（myHaffCode[j].ch==*p）
printf（”％s\n",myHaffCode[j]。
bit）;
｝
｝
voidCaozuo_D（intn）
{
inti,c；
charcode［1000]，*p；
printf（"pleaseinputthecoding：
\n"）；
scanf（"％s"，code）;
for（p=code,c=2*n—1；＊p！
='\0';p++）
｛
if（*p==’0'）
{
c=myHaffTree［c］.lchild;
if（myHaffTree［c]。
lchild==0）
｛
printf（”%c”，myHaffTree［c]。
ch）;
c=2*n-1；
continue；
}
｝
elseif（*p=='1'）
{
c=myHaffTree［c]。
rchild；
if（myHaffTree［c］。
lchild==0）
{
printf（"%c",myHaffTree［c]。
ch）;
c=2*n—1;
continue;
｝
｝
}
printf（"\n"）；
｝
voidCaozuo_T（intn）
｛
inti;
printf（"wordequalleftchildrightchildprents\n"）；
for（i=1；i〈=2＊n-1;i++）
printf（”％c%d％d％d%d\n"，myHaffTree[i］.ch，myHaffTree［i］.weight,myHaffTree［i].lchild，myHaffTree[i］。
rchild,myHaffTree[i］。
parent）；
}
main（）
｛
intn;
charchar1；
print（）;
n=Init（）；
while
（1）
{
printf（”A。
codingB.codeprintingC.printthehuffmanD。
exit\npleaseinputtheprocess：
\n"）;
scanf（"%s”,＆char1）；
if（char1=='D’）
break；
switch（char1）
{case’A’:
Caozuo_C（n）；break；/＊执行编码操作＊/
case’B'：
Caozuo_D（n）；break；/＊执行译码操作*/
case’C’:
Caozuo_T（n）；break；/*打印哈弗曼树＊/
｝
｝
}
升级会员 