课 程 论 文
题目： 哈夫曼树及其应用课程设计报告
学 号： 201230210115
姓 名： 黄文宣
班 级： 1232101
专 业： 信息安全
课程名称： 数据结构
课程老师： 王晓燕
二零一肆年一月
目录
1、课程设计的题目及简介………………………………………………3
2、实验目的………………………………………………………………3
3、设计说明………………………………………………………………4
4、总体流图………………………………………………………………4
5、详细设计………………………………………………………………5
6、实现部分………………………………………………………………6
7、测试程序………………………………………………………………9
8、心得与体会……………………………………………………………10
一、课程设计题目
哈夫曼树及其应用
数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理
建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。
哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。
二、实验目的
1 熟悉树的各种存储结构及其特点。
2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。
三、设计说明
建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。
四、总体流图
五、详细设计
1.数据结构设计
#include<iostream.h> //包含的库函数
#include<string.h>
#include<iomanip.h> const int n=6; //叶子数目
const int m=2*n-1; //森林中树的棵树
const int c=4;
class tree { public: char data;
int weight; //权值
int parent; //双亲
int lch,rch; //左右孩子
void creathafumantree(); //建立哈夫曼树
void editcode();//编码函数
void trancode(char b[],int max);//译码函数
哈夫曼树译码算法：
译码：弹出译码界面→利用建立好的哈弗曼树进行译码→将译码输出→保存译码文件
void tree::trancode(char b[],int max){ //译码
int i=0;
int j=m;
cout<<"
该段代码编译为
:"<<endl;
while(b[i]!='\0'){
if(b[i]=='0')
j=hftree[j].lch;
else
j=hftree[j].rch;
if(hftree[j].lch==0 && hftree[j].rch==0)
{
cout<<hftree[j].weight;
j=m;
}
i++;
}
}
六、实现部分
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define n 6
#define m 2*n-1
typedef struct
{ float weight;
int lchild,rchild,parent;
}codenode;
typedef codenode huffmantree[m];
typedef struct
{ char ch;
char bits[n+1];
}code;
typedef code huffmancode[n];
void inithf(huffmantree T) //－哈夫曼树的初始化
{ int i;
for(i=0;i<m;i++)
{ T[i].weight=0;
T[i].parent=-1;
T[i].lchild=-1;
T[i].rchild=-1;
}
}
void inputhf(huffmantree T) //－输入哈夫曼树的树据
{ int i;float k;
for(i=0;i<n;i++)
{ scanf("%f",&k);
T[i].weight=k;
}
}
void selectmin(huffmantree T,int k,int *p1,int *p2)
{ int i;float small1=10000,small2=10000;
for(i=0;i<=k;i++)
{ if(T[i].parent==-1)
if(T[i].weight<small1)
{ small2=small1;
small1=T[i].weight;
*p2=*p1;
*p1=i;
}
else
if(T[i].weight<small2)
{ small2=T[i].weight;
*p2=i;
}
}
}
void creathftree(huffmantree T) //－建哈夫曼树
{ int i,p1,p2;
inithf(T);
inputhf(T);
for(i=n;i<m;i++)
{ selectmin(T,i-1,&p1,&p2);
T[p1].parent=T[p2].parent=i;
T[i].lchild=p1;
T[i].rchild=p2;
T[i].weight=T[p1].weight+T[p2].weight;
}
}
void creathfcode(huffmantree T, huffmancode H) //－哈夫曼编码表
{ int i,c,p,start;char cd[n+1];
cd[n]='\0';
for(i=0;i<n;i++)
{ H[i].ch=getchar();
start=n;
c=i;
while((p=T[c].parent)>=0)
{
cd[--start]=(T[p].lchild==c)?'0':'1';
c=p;
}
strcpy(H[i].bits,&cd[start]);
}
}
void zip(huffmancode H,char *ch,char *s) //－编码
{ int j=0;char *p[n]; unsigned int i;
for(i=0;i<strlen(ch);i++)
{ while(ch[i]!=H[j].ch) j++;
p[i]=H[j].bits;
}
strcpy(s,p[0]);
for(i=1;i<n;i++)
strcat(s,p[i]);
puts(s);
}
void uzip(huffmancode H,char *s,huffmantree T) //－解码
{ int j=0,p;
unsigned int i;
char ch[n+1];
while(i<strlen(s))
{ p=m-1;
while(T[p].lchild!=-1)
{ if(s[ i]=='0')
{ p=T[p].lchild;i++;}
else
{ p=T[p].rchild;i++;}
}
ch[j]=H[p].ch;
j++;
}
ch[j]='\0';
puts(ch);
}
main()
{ char ch[]="abcdef", s[36];
huffmantree T;
huffmancode H;
creathftree(T);
creathfcode(T,H);
zip(H,ch,s);
uzip(H,s,T);
}
七、测试程序
七、心得体会
这次实验，感觉到相对难度较大，用了比较长的时间来做，从这也反映了对 树的知识不够熟练。但在这次实验的练习中，不仅对树的知识进行了综合运用，还有了较深一步的了解，掌握了运用树的基本知识。总之，对树和二叉树这方面的知识了解和运用都还有待加强。
在实验中也出现了很多的问题，最大的问题就是对程序设计框架结构的不了解，在实现代码与功能的连接时经常会出现各种不同的错误，在实现一些功能时系统常常会报错。许多错误不知从哪修改，让程序运行不出来。
课程设计中，既回顾了很多以前的东西，也发现了很多的问题，以前都没遇见过的，收获很大。通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识， 此次哈夫曼树的应用系统的设计让自己对数据结构的了解更深入。
通过老师和同学的细心的帮助，终于做出了这个系统，感觉很棒！
第二篇：哈夫曼树课程设计
计算机学院信息管理与信息系统专业
数据结构课程设计
题 目： 哈夫曼树的应用 班 级：信管09101班 姓 名：赵林芬 学 号： 200917020114 同组人姓名： 陈立芳 王红 起 迄 日 期： 2011.03.01-03.04 课程设计地点:系办公楼E3-A513指导教师：孙叶枫
完成日期：20xx年3月4日 1
目录
1、设计目的 ....................................................................................................................................... 3
2、需求分析 ....................................................................................................................................... 4
2.1选题的意义及背景 ............................................. 4
2.2 输入/输出形式和输出值的范围 .................................. 4
3、概要设计 ....................................................................................................................................... 4
3.1设计思想 ..................................................... 4
3.2函数间的关系 ................................................. 4
4、详细设计 ....................................................................................................................................... 5
4.1哈夫曼的主要结构 ............................................. 5
4.1.1结构定义 ................................................. 5
4.1.2主要函数声明及功能描述 .................................... 6
4.2源程序 ....................................................... 7
4.2.1头文件 ................................................... 7
4.2.2源文件 ................................................... 8
5、程序测试结果及问题分析 ......................................................................................................... 17
6、总结 ............................................................................................................................................. 18
7、参考文献 ..................................................................................................................................... 18
2
1.设计目的
数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。
在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。
数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：
一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
3
2．需求分析
2.1选题的意义及背景
锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。
在信息传递时，希望长度能尽可能短，即采用最短码。赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。
2.2 输入/输出形式和输出值的范围
输入信息以加载存档的reading.txt文件为方式，加载不成功，提示出错信息，加载成功后，系统对其编码，并按照选择对各种相关信息存档
3．概要设计
3.1设计思想
哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。
利用多重结构体的形式设计出所需的变量类型，还有基本的文件读写知识，同时借助九大子函数结合一个主函数设计了此课程内容，第一部分为信息的读写及统计；第二部分为哈夫曼树及其编码的建立，再将编码信息写进文件；第三部分为给信息加密在写进文件，再在对其翻译。最后的主函数是整个程序的组织者，利用switch选择循环将九大子函数联系起来，画龙点睛。这样整个程序的基本流出就出来了，再根据此流出设计出源程序。 3.2函数间的关系
哈夫曼系统，函数间的关系如图所示：
界面运行图如下：
4
4、详细设计
4.1哈夫曼的主要结构
4.1.1结构定义：
#define MAXVALUE 1000//定义最大权值
#define MAXBIT 100//定义哈夫曼树中叶子结点个数 typedef struct {
char data;//字符值
int num;//某个值的字符出现的次数
}TotalNode; //统计结点，包括字符种类和出现次数 typedef struct {
TotalNode tot[300];//统计结点数组 int num;//统计数组中含有的字符个数
}Total; //统计结构体，包括统计数组和字符种类数 typedef struct {
char mes[300];//字符数组 int num;//总字符数
}Message; //信息结构体，包括字符数组和总字符数 typedef struct{
int locked[500];//密码数组 int num;//密码总数
5
}Locking; //哈夫曼编码后的密文信息
typedef struct
{
char data;//字符 int weight;//权值 int parent;//双亲结点在数组HuffNode[]中的序号 int lchild;//左孩子结点在数组HuffNode[]中的序号 int rchild;//右孩子结点在数组HuffNode[]中的序号
}HNodetype; //哈夫曼树结点类型，包括左右孩子，权值和信息 typedef struct
{
int bit[MAXBIT]; int start;
}HCodetype; //哈夫曼编码结构体，包括编码数组和起始位
4.1.2主要函数声明及功能描述如下：
void reading_file(Message *message);
从文件中读取信息
void writing_file(Message *message);
将信息写进文件
void total_message(Message *message,Total *total);
统计信息中各字符的出现次数
void HaffmanTree(Total *total,HNodetype HuffNode[]);
构建哈夫曼树
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);
建立哈夫曼编码
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);
将编码规则写进文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);
给文件信息加密编码
void writing_lock(Locking *locking);
将已编码信息写进文件
void writing_translate(Locking *locking,HCodetype
6
HuffCode[],HNodetype HuffNode[],Total *total);
将已编码信息翻译过来并写进文件
4.2源程序
4.2.1头文件head.h
#define MAXVALUE 1000//定义最大权值
#define MAXBIT 100//定义哈夫曼树中叶子结点个数
typedef struct
{
char data;//字符值
int num;//某个值的字符出现的次数
}TotalNode; //统计结点，包括字符种类和出现次数
typedef struct
{
TotalNode tot[300];//统计结点数组
int num;//统计数组中含有的字符个数
}Total; //统计结构体，包括统计数组和字符种类数
typedef struct
{
char mes[300];//字符数组
int num;//总字符数
}Message; //信息结构体，包括字符数组和总字符数
typedef struct{
int locked[500];//密码数组
int num;//密码总数
}Locking; //哈夫曼编码后的密文信息
typedef struct
{
char data;//字符
int weight;//权值
int parent;//双亲结点在数组HuffNode[]中的序号
int lchild;//左孩子结点在数组HuffNode[]中的序号
int rchild;//右孩子结点在数组HuffNode[]中的序号
}HNodetype; //哈夫曼树结点类型，包括左右孩子，权值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype; //哈夫曼编码结构体，包括编码数组和起始位
void reading_file(Message *message);//从文件中读取信息
void writing_file(Message *message);//将信息写进文件
void total_message(Message *message,Total *total);//统计信息中各字符的次数
void HaffmanTree(Total *total,HNodetype HuffNode[]);//构建哈夫曼树 7
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼编码
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//将编码规则写进文件
void lock(Message *message,HNodetype HuffNode[],HCodetype
HuffCode[],Total *total,Locking *locking);//给文件信息加密编码 void writing_lock(Locking *locking);//将已编码信息写进文件
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//将已编码信息翻译过来并写进文件
4.2.2源文件source.cpp
#include<iostream>
#include<fstream>
#include"head.h"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark标记文件信息是否读入到内存中 HNodetype HuffNode[500];//保存哈夫曼树中各结点信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0; //初始化变量
while(1)
{
cout<<"********************************************************************************";
cout<<"*1:从文件读取信息 2:显示编码规则 3:将原文件信息写进文件 *";
cout<<"*4:将编码规则写进文件 5:将编码后的信息写进文件 6:将译码后的信息写进文件 7:退出 *";
cout<<"********************************************************************************";
cout<<endl;
cout<<"请输入操作代码：";
8
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//从文件中读取信息
mark=1;
break;
case 2://显示编码规则
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
total_message(message,total);
HaffmanTree(total,HuffNode);
HaffmanCode(HuffNode,HuffCode,total);
for(i=0;i<total->num;i++)//显示编码规则
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://将原文件信息写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
writing_file(message);//将信息写进文件
break;
case 4://将编码规则写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
total_message(message,total);
HaffmanTree(total,HuffNode);
HaffmanCode(HuffNode,HuffCode,total);
writing_HCode(HuffNode,HuffCode,total);
}
break;
case 5://将编码后的信息写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
9
total_message(message,total);
HaffmanTree(total,HuffNode);
HaffmanCode(HuffNode,HuffCode,total);
lock(message,HuffNode,HuffCode,total,locking);
writing_lock(locking);
}
break;
case 6://将译码后的信息写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
total_message(message,total);
HaffmanTree(total,HuffNode);
HaffmanCode(HuffNode,HuffCode,total);
writing_translate(locking,HuffCode,HuffNode,total);
}
break;
case 7:
exit(1);
default:
cout<<"输入错误，请重新选择"<<endl;
}
}
for(i=0;i<locking->num;i++)
if(locking->locked[i]==-1)cout<<" ";
else
cout<<locking->locked[i];
cout<<endl;
for(i=0;i<total->num;i++)
cout<<total->tot[i].data<<"
"<<total->tot[i].num<<endl;
for(i=0;i<2*(total->num)-1;i++)
cout<<HuffNode[i].parent<<" ";
cout<<endl;
return 0;
}
void reading_file(Message *message)
{
int i=0;
char ch;
ifstream infile("c:\\reading.txt",ios::in|ios::out);
if(!infile)//打开失败则结束
{
cout<<"打开c:\\reading.txt文件失败"<<endl;
10
exit(1);
}
else
cout<<"读取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//读取字符直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//记录总字符数
infile.close();//关闭文件
}//从文件中读取信息
void writing_file(Message *message)//将信息写进文件
{
int i;
ofstream outfile("c:\\writing.txt",ios::in|ios::out);//打开文件 if(!outfile)//打开失败则结束
{
cout<<"打开c:\\writing.txt文件失败"<<endl;
exit(1);
}
for(i=0;i<message->num;i++)//写文件
outfile.put(message->mes[i]);
cout<<"信息写进文件成功"<<endl;
outfile.close();//关闭文件
}//将原信息写入文件
void total_message(Message *message,Total *total)
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍历message中的所有字符信息 {
if(message->mes[i]!=' ')//字符不为空格时
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索当前字符 if(total->tot[j].data==message->mes[i]) //搜索到，则此字符次数加1，mark标志为1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)
//未搜索到，新建字符种类，保存进total中，字符类加1
11
{
total->tot[total->num].data=message->mes[i]; total->tot[total->num].num=1;
total->num++;
}
}
}
}//统计信息中各字符的出现次数
通过各权值的一一比较选取最小和次小两权值建立二叉树，记录节点的左右孩子及双亲的位置关系最终构建成哈夫曼树，且记录的左孩子权值比右孩子小 void HaffmanTree(Total *total,HNodetype HuffNode[])
{
int i,j,min1,min2,x1,x2;
首先初始化哈夫曼树并存入叶子结点权值和信息
for(i=0;i<2*(total->num)-1;i++)
{
if(i<=total->num-1)HuffNode[i].data=total->tot[i].data; HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
接着选取最小x1和次小x2的两权值
for(j=0;j<total->num+i;j++)
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
12
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2) min2=HuffNode[j].weight;
x2=j;
}
HuffNode[x1].parent=total->num+i;//修改亲人结点位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weigh
t; 最后选出的左孩子比右孩子权值小
HuffNode[total->num+i].lchild=x1;
HuffNode[total->num+i].rchild=x2;
}
}
哈夫曼树构建成功
在建立的哈夫曼树基础上，利用数组使左分支为0，右分支为1，从叶结点向上
直到根结点建立哈夫曼编码，并保存每个叶结点起始位。该函数利用了while
的循环并多次利用for循环以完成目标
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total
*total)
{
int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立叶子结点个数的编码
{
cd.start=total->num-1;//起始位的初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//从叶结点向上爬直到到达根结点
{
if(HuffNode[p].lchild==c)//左分支都为0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支都为1
cd.start--;//起始位向前移动
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)
//保存求出的每个叶结点编码和起始位
HuffCode[i].bit[j]=cd.bit[j];
13
HuffCode[i].start=cd.start;
}
}
哈夫曼编码的建立成功
利用文件的输入输出规则打开HCode文件，打开失败则结束操作，否则将信息利用数组及for循环写进文件
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
{
int i,j;
ofstream outfile("c:\\HCode.txt",ios::in|ios::out); if(!outfile)//打开失败则结束并输出
{
cout<<"打开c:\\HCode.txt文件失败"<<endl;
exit(1);
}
for(i=0;i<total->num;i++)//写文件
{
outfile.put(HuffNode[i].data);
outfile<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++) outfile<<HuffCode[i].bit[j];
outfile<<endl;
}
cout<<"编码规则写进文件成功"<<endl;
outfile.close();//关闭文件
}
void lock(Message *message,HNodetype HuffNode[],HCodetype
HuffCode[],Total *total,Locking *locking)
{
int i,j,m;
for(i=0;i<message->num;i++)//遍历信息
{
if(message->mes[i]==' ')
//碰到空格则以-1形式保存进locked数组中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
14
for(j=0;j<total->num;j++)//搜索信息对应的编码 {
if(HuffNode[j].data==message->mes[i])
for(m=HuffCode[j].start+1;m<total->num;m++)
{
locking->locked[locking->num]=HuffCode[j].bit[m];
locking->num++;//locked数组总数加1
}
}
}
}//给文件信息加密编码
void writing_lock(Locking *locking)
{
int i;
ofstream outfile("c:\\locking.txt",ios::in|ios::out); if(!outfile)//打开失败则结束
{
cout<<"打开c:\\locking.txt文件失败"<<endl;
exit(1);
}
for(i=0;i<locking->num;i++)//写文件
if(locking->locked[i]==-1)
outfile.put(' ');
else
outfile<<locking->locked[i];
cout<<"已编码信息写进文件成功"<<endl;
outfile.close();//关闭文件
}//将哈夫曼编码后的密文信息写进文件
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
{
int i,j,mark[100],start[100],min,max;
ofstream outfile("c:\\translate.txt",ios::in|ios::out);//打开文件 if(!outfile)//打开失败则结束
{
cout<<"打开c:\\translate.txt文件失败"<<endl;
exit(1);
}
for(i=0;i<total->num;i++)//start数组初始化
start[i]=HuffCode[i].start+1;
for(i=0;i<total->num;i++)//mark数组初始化
mark[i]=1;
15
min=0;
for(max=0;max<locking->num;max++)//写文件
{
if(locking->locked[max]==-1)//碰到空格信息则直接输出空格 {
outfile.put(' ');
min++;
}
else
{
for(i=min;i<=max;i++)//查找从min开始到max的编码对应的信息 {
for(j=0;j<total->num;j++) {
if(start[j]==total->num+1)
mark[j]=0;//对应编码比所给编码短则不在比较
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到对应信息，则写进文件 {
if(mark[i]==1&&start[i]==total->num)
{
outfile.put(HuffNode[i].data);
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start数组初始化
start[i]=HuffCode[i].start+1; for(i=0;i<total->num;i++)//mark数组初始化
mark[i]=1;
}
}
cout<<"翻译信息写进文件成功"<<endl;
outfile.close();//关闭文件
｝
16
5.程序测试结果及问题分析
5.1 程序测试结果
在C盘中输入一个reading的文本文档
运行后有如下界面再选择操作代码1：
再选择2，即出现如下哈夫曼编码界面：
选择代码3，使程序运行，信息写进文件：
5.2 问题分析
程序的设计过程中，我们遇到不少问题，比如对文件的读写不能精确的掌握，所以这部分的设计过程中总免不了要翻书，有的时侯会打开文件之后忘记outfile.close();在哈夫曼编码的时候，在reading的文件中的拼写错误使我们运行过多次，但最终还是发现了，语法的错误导致浪费了很多时间，针对不同的电脑程序运行有的会出现不同的结果，比如：有的电脑只需要输入一个reading文件就可以，但有的电脑运行就需要把writing等的都写出来，才能运行，这可能是电脑的系统问题，但最终还是克服了。最主要的是编写程序是的细节错误， 17
但那是对算法的一种真正的考察，如果哈夫曼的算法不能熟悉的写出，说明其思想没有渗透这才是问题的关键，但是我们还是齐心协力把它给写出来了。
6.总结
通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。
这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存保存数据，在不断分析后明确并改正了错误和疏漏，使我的程序有了更高的质量。这不仅是程序设计,更是锻炼我们处理问题的能力,同时也使我们了解到团队合作的可贵.编写程序是件细心活,稍不留神就会出错,这就必须要求我们对待事情要认真!在编写程序的过程中,错误不断出现,不同的类型(如少写了一个符号,写错了字母,用错了函数等等)层出不穷,这考验我们待事细心,耐心,能不能坚持到底,不能半途而废。
三人行必有我师,遇到问题我们一起讨论,研究,错了再写,写了在改.经过多次的修改,调试,运行,添加,终于最后在大家的欢呼声中,完成了我们的任务.虽说是累了点，但我们也从中找到了自己的快乐，每当完成一个新的函数时，那心情是激动啊,这毕竟是自己弄出来的,同时也使我感受到了学习的快乐！
7.参考文献
[1]严蔚敏，吴伟民．《数据结构：C语言版》．北京：清华大学出版社．
[2]陈维兴，林小茶.《C++面向对象程序设计教程（第三版）》北京：清华大学出版社．
18