哈夫曼编译码数据结构C语言版课程设计.docx
《哈夫曼编译码数据结构C语言版课程设计.docx》由会员分享，可在线阅读，更多相关《哈夫曼编译码数据结构C语言版课程设计.docx（30页珍藏版）》请在冰点文库上搜索。
哈夫曼编译码数据结构C语言版课程设计
只要站起来的次数比倒下去的次数多，那就是成功。
《数据结构》
课程设计报告
设计题目哈夫曼（Huffman）编/译码器
学院名称信息工程学院
专业班级12计本2
姓名张翠翠
学号1212210217______
题目：
哈夫曼（Huffman）编/译码器
一、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率
缩短信息传输时间
降低传输成本
但是
这要求在发送端通过一个编码系统对待传数据预先编码
在接收端将传来的数据进行译码（复原）
对于双工信道（即可以双向传输信息的信道）
每端都需要一个完整的编/译码系统
试为这样的信息收发站写一个哈夫曼码的编/译码系统
二、设计目标
帮助学生熟练掌握树的应用和基本操作
重点掌握二叉树的存储
这里以哈夫曼树为设计目标进一步提高学生的设计能力及对树的理解
三、任务要求
一个完整的系统应具有以下功能：
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中
四、需求分析
利用哈夫曼树（Huffman）编/译码
（一）、初始化哈夫曼树
（二）、建立哈夫曼树
（三）、对哈夫曼树进行编码
（四）、输出对应字符的编码
（五）、译码过程
五、概要设计
哈夫曼树的存储结构描述
typedefstruct
{
unsignedintweight;
unsignedintparent
lchild
rchild;
}HTNode
*HuffmanTree;
哈弗曼树的算法
voidCreateHT（HTNodeht[]
intn）//调用输入的数组ht[]
和节点数n
{
inti
k
lnode
rnode;
intmin1
min2;
for（i=0;i<2*n-1;i++）
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1
for（i=n;i<2*n-1;i++）//构造哈夫曼树
{
min1=min2=32767;//int的范围是-32768-32767
lnode=rnode=-1;//lnode和rnode记录最小权值的两个结点位置
for（k=0;k<=i-1;k++）
{
if（ht[k].parent==-1）//只在尚未构造二叉树的结点中查找
{
if（ht[k].weight{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
elseif（ht[k].weight{
min2=ht[k].weight;rnode=k;
}
}
}
ht[lnode].parent=i;ht[rnode].parent=i;//两个最小节点的父节点是i
ht[i].weight=ht[lnode].weight+ht[rnode].weight;//两个最小节点的父节点权值为两个最小节点权值之和
ht[i].lchild=lnode;ht[i].rchild=rnode;//父节点的左节点和右节点
}
}
哈弗曼编码
voidCreateHCode（HTNodeht[]
HCodehcd[]
intn）
{
inti
f
c;
HCodehc;
for（i=0;i{
hc.start=n;c=i;
f=ht[i].parent;
while（f!
=-1）//循序直到树根结点结束循环
{
if（ht[f].lchild==c）//处理左孩子结点
hc.cd[hc.start--]='0';
else//处理右孩子结点
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++;//start指向哈夫曼编码hc.cd[]中最开始字符
hcd[i]=hc;
}
}
voidDispHCode（HTNodeht[]
HCodehcd[]
intn）//输出哈夫曼编码的列表
{
inti
k;
printf（"输出哈夫曼编码:
\n"）;
for（i=0;i即A-Z
{
printf（"%c:
\t"
ht[i].data）;
for（k=hcd[i].start;k<=n;k++）//输出所有data中数据的编码
{
printf（"%c"
hcd[i].cd[k]）;
}
printf（"\n"）;
}
}
voideditHCode（HTNodeht[]
HCodehcd[]
intn）//编码函数
{
charstring[MAXSIZE];
inti
j
k;
scanf（"%s"
string）;//把要进行编码的字符串存入string数组中
printf（"\n输出编码结果:
\n"）;
for（i=0;string[i]!
='#';i++）//#为终止标志
{
for（j=0;j{
if（string[i]==ht[j].data）//循环查找与输入字符相同的编号
相同的就输出这个字符的编码
{
for（k=hcd[j].start;k<=n;k++）
{
printf（"%c"
hcd[j].cd[k]）;
}
break;//输出完成后跳出当前for循环
}
}
}
}
哈弗曼译码
voiddeHCode（HTNodeht[]
HCodehcd[]
intn）//译码函数
{
charcode[MAXSIZE];
inti
j
l
k
m
x;
scanf（"%s"
code）;//把要进行译码的字符串存入code数组中
while（code[0]!
='#'）
for（i=0;i{
m=0;//m为想同编码个数的计数器
for（k=hcd[i].start
j=0;k<=n;k++
j++）//j为记录所存储这个字符的编码个数
{
if（code[j]==hcd[i].cd[k]）//当有相同编码时m值加1
m++;
}
if（m==j）//当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据
{
printf（"%c"
ht[i].data）;
for（x=0;code[x-1]!
='#';x++）//把已经使用过的code数组里的字符串删除
{
code[x]=code[x+j];
}
}
}
}
主函数
voidmain（）
{
intn=26
i;
charorz
back
flag=1;
charstr[]={'A'
'B'
'C'
'D'
'E'
'F'
'G'
'H'
'I'
'J'
'K'
'L'
'M'
'N'
'O'
'P'
'Q'
'R'
'S'
'T'
'U'
'V'
'W'
'X'
'Y'
'Z'};//初始化
intfnum[]={186
64
13
22
32
103
21
15
47
57
1
2
32
20
57
63
15
1
48
51
80
23
8
18
1
16};//初始化
HTNodeht[M];//建立结构体
HCodehcd[N];//建立结构体
for（i=0;i{
ht[i].data=str[i];
ht[i].weight=fnum[i];
}
while（flag）//菜单函数
当flag为0时跳出循环
显示部分源程序：
{
printf（"\n"）;
printf（"********************************"）;
printf（"\n**1---------------显示编码**"）;
printf（"\n**2---------------进行编码**"）;
printf（"\n**3---------------进行译码**"）;
printf（"\n**4---------------退出**\n"）;
printf（"***********************************"）;
printf（"\n"）;
printf（"请输入选择的编号:
"）;
scanf（"%c"
&orz）;
switch（orz）
{
case'a':
case'A':
system（"cls"）;//清屏函数
CreateHT（ht
n）;
CreateHCode（ht
hcd
n）;
DispHCode（ht
hcd
n）;
printf（"\n按任意键返回..."）;
getch（）;
system（"cls"）;
break;
case'b':
case'B':
system（"cls"）;
printf（"请输入要进行编码的字符串（以#结束）:
\n"）;
editHCode（ht
hcd
n）;
printf（"\n按任意键返回..."）;
getch（）;
system（"cls"）;
break;
case'c':
case'C':
system（"cls"）;
DispHCode（ht
hcd
n）;
printf（"请输入编码（以#结束）:
\n"）;
deHCode（ht
hcd
n）;
printf（"\n按任意键返回..."）;
getch（）;
system（"cls"）;
break;
case'd':
case'D':
flag=0;
break;
default:
system（"cls"）;
}}}
六、详细设计
字符空格ABCDEFGHIJKLM频度186********10321154757153220
由上表画出哈夫曼树：
由哈夫曼树得出各字符的编码：
字符 编码字符 编码空格 10D 0001 A 010E 1111 B 011111 F 11001 C0000 G 01110
关系调用：
该程序的流程图：
七、测试分析
白盒：
查看代码完整性
白盒测试也称结构测试或逻辑驱动测试
它是按照程序内部的结构测试程序
通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行
检验程序中的每条通路是否都能按预定要求正确工作
这一方法是把测试对象看作一个打开的盒子
测试人员依据程序内部逻辑结构相关信息
设计或选择测试用例
对程序所有逻辑路径进行测试
通过在不同点检查程序的状态
确定实际的状态是否与预期的状态一致
黑盒：
测试是否可以正确的创建
删除
插入
打印
查找等操作
黑盒测试也称功能测试
它是通过测试来检测每个功能是否都能正常使用
在测试中
把程序看作一个不能打开的黑盒子
在完全不考虑程序内部结构和内部特性的情况下
在程序接口进行测试
它只检查程序功能是否按照需求规格说明书的规定正常使用
程序是否能适当地接收输入数据而产生正确的输出信息
黑盒测试着眼于程序外部结构
不考虑内部逻辑结构
主要针对软件界面和软件功能进行测试
八、使用说明
1）输入n个字符的权值
2）输入对应的字符
3）得出各字符的编码
九、测试数据
用下表给出的字符集和频度的实际统计数据建立哈夫曼树
并实现以下报文的编码和译码：
"THISPROGRAMISMYFAVORITE"
字符空格ABCDEFGHIJKLM
频度1866413223210321154757153220
字符NOPQRSTUVWXYZ
频度5763151485180238181161
注：
学生在测试数据时
需要写出测试用例和截图
十、该程序的源代码
#include
#include//要用system函数要调用的头文件
#include//用getch（）要调用的头文件
#include
#defineN50//义用N表示50叶节点数
#defineM2*N-1//用M表示节点总数当叶节点数位n时总节点数为2n-1
#defineMAXSIZE100
typedefstruct
{
chardata;//结点值
intweight;//权值
intparent;//双亲结点
intlchild;//左孩子结点
intrchild;//右孩子结点
}HTNode;
typedefstruct
{
charcd[N];//存放哈夫曼码
intstart;//从start开始读cd中的哈夫曼码
}HCode;
voidCreateHT（HTNodeht[]
intn）//调用输入的数组ht[]
和节点数n
{
inti
k
lnode
rnode;
intmin1
min2;
for（i=0;i<2*n-1;i++）
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1
for（i=n;i<2*n-1;i++）//构造哈夫曼树
{
min1=min2=32767;//int的范围是-32768-32767
lnode=rnode=-1;//lnode和rnode记录最小权值的两个结点位置
for（k=0;k<=i-1;k++）
{
if（ht[k].parent==-1）//只在尚未构造二叉树的结点中查找
{
if（ht[k].weight{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
elseif（ht[k].weight{
min2=ht[k].weight;rnode=k;
}
}
}
ht[lnode].parent=i;ht[rnode].parent=i;//两个最小节点的父节点是i
ht[i].weight=ht[lnode].weight+ht[rnode].weight;//两个最小节点的父节点权值为两个最小节点权值之和
ht[i].lchild=lnode;ht[i].rchild=rnode;//父节点的左节点和右节点
}
}
voidCreateHCode（HTNodeht[]
HCodehcd[]
intn）
{
inti
f
c;
HCodehc;
for（i=0;i{
hc.start=n;c=i;
f=ht[i].parent;
while（f!
=-1）//循序直到树根结点结束循环
{
if（ht[f].lchild==c）//处理左孩子结点
hc.cd[hc.start--]='0';
else//处理右孩子结点
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++;//start指向哈夫曼编码hc.cd[]中最开始字符
hcd[i]=hc;
}
}
voidDispHCode（HTNodeht[]
HCodehcd[]
intn）//输出哈夫曼编码的列表
{
inti
k;
printf（"输出哈夫曼编码:
\n"）;
for（i=0;i即A-Z
{
printf（"%c:
\t"
ht[i].data）;
for（k=hcd[i].start;k<=n;k++）//输出所有data中数据的编码
{
printf（"%c"
hcd[i].cd[k]）;
}
printf（"\n"）;
}
}
voideditHCode（HTNodeht[]
HCodehcd[]
intn）//编码函数
{
charstring[MAXSIZE];
inti
j
k;
scanf（"%s"
string）;//把要进行编码的字符串存入string数组中
printf（"\n输出编码结果:
\n"）;
for（i=0;string[i]!
='#';i++）//#为终止标志
{
for（j=0;j{
if（string[i]==ht[j].data）//循环查找与输入字符相同的编号
相同的就输出这个字符的编码
{
for（k=hcd[j].start;k<=n;k++）
{
printf（"%c"
hcd[j].cd[k]）;
}
break;//输出完成后跳出当前for循环
}
}
}
}
voiddeHCode（HTNodeht[]
HCodehcd[]
intn）//译码函数
{
charcode[MAXSIZE];
inti
j
l
k
m
x;
scanf（"%s"
code）;//把要进行译码的字符串存入code数组中
while（code[0]!
='#'）
for（i=0;i{
m=0;//m为想同编码个数的计数器
for（k=hcd[i].start
j=0;k<=n;k++
j++）//j为记录所存储这个字符的编码个数
{
if（code[j]==hcd[i].cd[k]）//当有相同编码时m值加1
m++;
}
if（m==j）//当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据
{
printf（"%c"
ht[i].data）;
for（x=0;code[x-1]!
='#';x++）//把已经使用过的code数组里的字符串删除
{
code[x]=code[x+j];
}
}
}
}
voidmain（）
{
intn=26
i;
charorz
back
flag=1;
charstr[]={'A'
'B'
'C'
'D'
'E'
'F'
'G'
'H'
'I'
'J'
'K'
'L'
'M'
'N'
'O'
'P'
'Q'
'R'
'S'
'T'
'U'
'V'
'W'
'X'
'Y'
'Z'};//初始化
intfnum[]={186
64
13
22
32
103
21
15
47
57
1
2
32
20
57
63
15
1
48
51
80
23
8
18
1
16};//初始化
HTNodeht[M];//建立结构体
HCodehcd[N];//建立结构体
for（i=0;i{
ht[i].data=str[i];
ht[i].weight=fnum[i];
}
while（flag）//菜单函数
当flag为0时跳出循环
{
printf（"\n"）;
printf（"**************************************"）;
printf（"\n**A---------------显示编码**"）;
printf（"\n**B---------------进行编码**"）;
printf（"\n**C---------------进行译码**"）;
printf（"\n**D---------------退出**\n"）;
printf（"****************************************"）;
printf（"\n"）;
printf（"请输入选择的编号:
"）;
scanf（"%c"
&orz）;
switch（orz）
{
case'a':
case'A':
system（"cls"）;//清屏函数
CreateHT（ht
n）;
CreateHCode（ht
hcd
n）;
DispHCode（ht
hcd
n）;
printf（"\n按任意键返回..."）;
getch（）;
升级会员 