赫夫曼编码器数据结构课程设计.docx
《赫夫曼编码器数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《赫夫曼编码器数据结构课程设计.docx（14页珍藏版）》请在冰点文库上搜索。
赫夫曼编码器数据结构课程设计
《数据结构》
课程设计报告
课程设计:
赫夫曼编码器
一、任务描述
（1）建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。
（2）“压缩文件”即：
读文件、统计文件中的字符个数、对文件进行哈夫曼编码和译码、并将编码译码后的字符存储在文件中。
要求：
根据以上任务说明，设计程序完成功能。
二、问题分析
1、功能分析
分析设计课题的要求，要求编程实现以下功能：
（1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。
（2）E：
编码（Encoding）。
利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：
译码（Decoding）。
利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。
三、数据结构设计
.哈夫曼树节点的数据类型定义为：
typedefstruct{//赫夫曼树的结构体
charch;
intweight;//权值
intparent,lchild,rchild;
}htnode,*hfmtree;
四、功能设计
（一）主控菜单设计
为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。
程序运行后，给出6个菜单项的内容和输入提示，如下：
1.一个功能函数对ASCII码的初始化并需要一个数组来保存它们；
2.定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程；
3.自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码；
4.从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；
5.使用文件读写操作哈夫曼编码和解码结果的写入；
（二）程序模块结构
由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：
（1）intmain（）
主函数：
利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）
对文件中的正文进行编码，然后将结果存入文件codefile.txt中。
如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。
读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。
（2）Encoding
编码功能：
对输入字符进行编码
（3）、Decoding
译码功能：
利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat中。
（三）函数调用关系
程序的主要结构（函数调用关系）如下图所示。
其中main（）是主函数，它进行菜单驱动，根据选择项0~5调用相应的函数。
main（）函数使用for循环实现重复选择。
其循环结构如下：
intmain（）{
charcode[100],h[100],hl[100];
intn,i,j,k,l;
ifstreaminput_file;//文件输入输出流
ofstreamoutput_file;
charchoice,str[100];
hfmtreeHT;
hfmcodeHC;
cout<<"\n";
cout<<""<<"计算机（3）班"<<""<<"Q07620307"<<""<<"XXX\n";
while（choice!
='Q'&&choice!
='q'）//当choice的值不为q且不为Q时循环
{
cout<<""<<"*************************赫夫曼编码/译码器*************************\n";
cout<<""<<"I.Init"<<""<<"E.Encoding"<<""<<"D.Decoding"<<""<<"Q.Exit\n";
cout<<"请输入您要操作的步骤：
";
cin>>choice;
if（choice=='I'||choice=='i'）//初始化赫夫曼树
{
cout<<"请输入字符个数：
";
cin>>n;
hfmcoding（HT,HC,n）;
for（i=1;i<=n;++i）
{
cout<"<}
output_file.open（"hfmTree.txt"）;
if（!
output_file）{
cout<<"can'toenfile!
"<return1;
}
for（i=1;i<=n;i++）
{
output_file<<"（"<}
output_file.close（）;
cout<<"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!
"<}
elseif（choice=='E'||choice=='e'）//进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中
{
printf（"请输入字符：
"）;
gets（str）;
output_file.open（"ToBeTran.txt"）;
if（!
output_file）
{
cout<<"can'toenfile!
"<return1;
}
output_file<output_file.close（）;
output_file.open（"CodeFile.txt"）;
if（!
output_file）{
cout<<"can'toenfile!
"<return1;
}
for（i=0;ifor（j=0;j<=n;++j）
{
if（HT[j].ch==str[i]）
{
output_file<break;
}
}
}
output_file.close（）;
cout<<"\n";
cout<<"编码完毕，并且已经存入CodeFile.txt文件！
\n";
input_file.open（"CodeFile.txt"）;//从CodeFile.txt中读入编码，输出在终端
if（!
input_file）
{
cout<<"can'toenfile!
"<return1;
}
input_file>>code;
cout<<"编码码值为：
"<input_file.close（）;
}
elseif（choice=='D'||choice=='d'）//读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中
{
input_file.open（"CodeFile.txt"）;
if（!
input_file）{
cout<<"can'toenfile!
"<return1;
}
input_file>>h;
input_file.close（）;
output_file.open（"Textfile.txt"）;
if（!
output_file）
{
cout<<"can'toenfile!
"<return1;
}
k=0;
while（h[k]!
='\0'）//先用编码中的前几个和字符的编码相比较，然后往后移
{
for（i=1;i<=n;i++）{
l=k;
for（j=0;jhl[j]=h[l];
}
hl[j]='\0';
if（strcmp（HC[i],hl）==0）
{
output_file<k=k+strlen（HC[i]）;
break;
}
}
}
output_file.close（）;
input_file.open（"Textfile.txt"）;
if（!
input_file）{
cout<<"can'toenfile!
"<return1;
}
input_file>>h;
cout<input_file.close（）;
cout<<"译码结束，字符已经存入Textfile.txt文件中！
"<}
elseif（choice=='Q'||choice=='q'）//退出程序
{
exit（0）;
}
else//如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤，请重新输入！
"<}
cout<}
return0;
}
（四）文件结构
1、linklist.h：
赫夫曼树相关的定义与声明
2、linklist.cpp：
单链表运算的实现
3、menu.h：
主菜单函数的声明
4、menu.cpp：
主菜单函数的实现
5、mn.cpp：
主函数
（五）各函数的算法设计
1selete、
算法原理：
选出HT树到a为止，权值最小且parent为0的2个节点
流程图：
代码描述：
voidSelect（hfmtree&HT,inta,int*p1,int*p2）//Select函数，选出HT树到a为止，权值最小且parent为0的2个节点
{
inti,j,x,y;
for（j=1;j<=a;++j）{
if（HT[j].parent==0）{
x=j;
break;
}
}
for（i=j+1;i<=a;++i）{
if（HT[i].weightx=i;//选出最小的节点
}
}
for（j=1;j<=a;++j）{
if（HT[j].parent==0&&x!
=j）
{
y=j;
break;
}
}
for（i=j+1;i<=a;++i）
{
if（HT[i].weight=i）
{
y=i;//选出次小的节点
}
}
if（x>y）{
*p1=y;
*p2=x;
}
else
{
*p1=x;
*p2=y;
}
}
算法的时间复杂度分析：
O（a）
2、hfmcoding
算法原理：
构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC
流程图：
代码描述：
voidhfmcoding（hfmtree&HT,hfmcode&HC,intn）//构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC
{
inti,start,c,f,m,w;
intp1,p2;
char*cd,z;
if（n<=1）{
return;
}
算法的时间复杂度分O（n）
五、测试数据和结果
1、测试数据
自定义一组如下的测试数据，包含三个人员：
字符权值
A1
B12
C3
D7
E8
F14
G31
H23
U41
J9
K18
2、测试结果
本程序在VC++环境下实现，下面是对以上测试数据的运行结果。
（1）主菜单显示如下：
（2）编码：
译码
退出
六、结束语
本设计完成了课题要求的任务，哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，设计了较便捷的操作界面。
进一步的改进设想：
当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来
升级会员 