数据结构课程设计哈夫曼编码.doc

课 程 设 计 报 告

课程名称 数据结构
课题名称 哈夫曼编码与译码

专 业 通信工程
班 级 通信0902
学 号 200903020228
姓 名 肖俊
指导教师 田娟秀、李杰君、张鏖烽

2011年 07 月 01日

湖南工程学院
课 程 设 计 任 务 书

课程名称 数据结构
课 题 哈夫曼编码与译码

专业班级 通信0902
学生姓名 肖俊
学 号 200903020228
指导老师 田娟秀、李杰君、张鏖烽
审 批

任务书下达日期 2011 年 06 月 27 日
任务完成日期 2011 年 07 月 01 日

1设计内容与设计要求
1.1设计内容
课题五：对电文中的字符串编码和译码
Huffman编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景，是数据压缩中的一个重要理论依据。对输入的一串文字符号实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。
要求完成以下功能：
a) 针对给定的字符串，建立Huffman树。
b) 生成Huffman编码。
c) 对编码文件译码。

1.2 选题方案：
所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9，则所选题目号为：9%6+1＝（题目4）。注意，所有的课题都要求用图形方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。

1.3设计要求：
1.3.1 课程设计报告规范
（1）需求分析
a.程序的功能。
b.输入输出的要求。
（2）概要设计
a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。
b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。
（3）详细设计
a.采用C语言定义相关的数据类型。
b． 写出各模块的类C码算法。
c.画出各函数的调用关系图、主要函数的流程图。
（4）调试分析以及设计体会
a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。
b.程序调试中遇到的问题以及解决问题的方法。
c.课程设计过程经验教训、心得体会。
（5）使用说明
用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。
（6）书写格式
a.设计报告要求用A4纸打印成册：
b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。
（7）附录
源程序清单（带注释）

1.3.2 考核方式
指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：
（1）平时出勤 （占10%）
（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）
（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）
（4）设计报告（占30%）
注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。
（5）独立完成情况（占10%）。

1.3.3 课程验收要求
（1）运行所设计的系统。
（2）回答有关问题。
（3）提交课程设计报告。
（4）提交软盘（源程序、设计报告文档）。
（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。

2 进度安排
第 19 周：星期一 8：00——12：00 上课
星期一 14：30——18：30 上机
星期二 14：30——18：30 上机
星期四 8：00——12：00 上机

附：
课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。
正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。
正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。
正文总字数要求在4500字以上（不含程序原代码）。

目录

一.需求分析 1
1.程序的功能 1
2.输入输出的要求 1
二.概要设计 1
1.程序模块及其关系 1
2.课题涉及的数据结构 2
三.详细设计 3
1.相关数据类型 3
2.各函数的调用关系图、主要函数的流程图 3
3.各模块的类C码算法 7
四.调试分析以及设计体会 9
1.测试数据 9
2.程序调试中遇到的问题以及解决问题的方法 10
3.课程设计过程经验教训、心得体会 10
五.用户使用手册 11
六.附录 12

一. 需求分析
1.程序的功能
能对输入的字符串实现Huffman编码，且能利用生成的编码对Huffman代码串进行译码，输出相应字符串。
2.输入输出的要求
首先，输入一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的次数，然后输出通过Huffman编码得到的各种字符的Huffman编码。此时程序要求输入一串Huffman代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出译码结果。

二. 概要设计
1.程序模块及其关系
主函数模块
编码模块
译码模块
输入字符串
构造哈夫曼树
生成哈夫曼编码
输入代码串
译码并输出
程序由主函数模块，编码模块，译码模块组成，主函数模块可调用编码模块，译码模块，编码模块可对字符串进行编码，译码模块可对输入的代码串进行译码并输出。各模块之间的关系示意图如下：
图1.各功能模块关系
2. 课题涉及的数据结构
1. 哈夫曼树类型HTNode（树形结构）：
typedef struct //哈弗曼树结点
{
char data; //存储字符
double weight; //存储权值
int parent; //双亲结点位置
int lchild; //左右孩子结点位置
int rchild;
}HTNode;
HTNode ht[2n-1];

2.哈夫曼编码类型HCode（顺序结构）
typedef struct //各叶子结点的哈弗曼编码
{
char cd[30]; //cd[start]~cd[n]存储哈夫曼编码
int start; //字符数组中哈夫曼编码的起始位置
}HCode;
HCode hcd[n];

3.CNode类型(顺序结构)
typedef struct CNode //用于保存字符频度的类型
{
char c; //存储出现字符种类
int num; //字符出现次数
int flag; //存储字符是否出现的标记
};
CNode CharNode[MAXV];

三. 详细设计
1.相关数据类型（采用C语言定义）
int cd[n]; //储存哈夫曼编码
char str[n]; //储存需要编码的字符串
double weight; //储存字符出现频度（权值）
int lchild,rchild,parent; //储存哈夫曼树中各结点位置

2.各函数的调用关系图、主要函数的流程图

main()
insertstr()
countstr() ；
dispCNode()；
CreateHT()；
CreateHCode()；
DispHCode();
insertstr1();
DispHCode();
strcompare();
图2.各函数调用关系示意图
1.各函数调用关系

2. CreateHT函数
开始
ht[i].parent=ht[i].lchild=
ht[i].rchild=-1;i++;
min1=min2=32767;
lnode=rnode=-1;
min2=min1;rnode=lnode;
min1=ht[k].weight;
lnode=k
结束
图3.CreateHT函数流程图
i=0;
i<2n-1
Y
N
i=n
i<2n-1
k<i-1;
k=0;
ht[k].parent=-1
Y
ht[k].weight<min1
ht[k].weight<min2
Y
min2=ht[k].weight;rnode=k;
Y
N
Y
N
N
ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i]lchilde=lnode;ht[i]rchilde=rnode;ht[lnode].parent=i;ht[rnode].parent=i;
N
Y
N

3.main函数
开始
调用CreateHT函数，
构造haffman树
调用CreateHCode函数，
生成haffman编码
译码
输入str1[];
存在相应代码串
结束
N
Y
图4.main函数流程图
flag=0
Y
N

开始
结束
hc.start=n;c=i;
f=ht[i].parent;
ht[f].lchild=c
ht[f].cd[hc.start--]=’0’;
ht[f].cd[hc.start--]=’1’;
Y
N
f!=-1
Y
hc.start++;
hcd[i]=hc;
N
i<n
图5.CreateHcode函数流程图
4. CreateHCode函数

3.各模块的类C码算法
1）编码模块：
首先通过键盘输入需要键盘的字符串，调用countstr()函数统计并储存字符频度，再调用函数：
void CreateHT(HTNode ht[],int n) //构造哈弗曼树
{
int i,j,k,lnode,rnode;
double min1,min2; //分别存放lnode和rnode的两个结点位置
使所有结点的相关域置-1
for(i=n;i<2*n-1;i++)
{
先寻找权值最小结点，使其成为左右孩子结点；
再求出权值为左右孩子结点权值之和的h[i]结点；
使ht[i]作为双亲结点；
}
}

再调用：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
for(i=0;i<n;i++)
{
hc.start=n;
c=i;
f=ht[i].parent;
若ht[i]为ht[f]的左孩子结点，则
hc.cd[hc.start--]='0';
若ht[i]为ht[f]的右孩子结点，则
hc.cd[hc.start--]='1';
再对ht[f]进行同样的判断，直至f=-1
hc.start++;
hcd[i]=hc;
}
}

2）译码模块：
先通过键盘输入哈夫曼编码代码串，再调用：
int ReadCode(char str1[],HCode hcd[],HTNode ht[],int MAX,int n) //译码函数
{
int i,j,m=0,k;
int flag=1; //flag为1则哈弗曼编码输入合法
char temp[30]="";
for(i=0;str1[i]!='\0';i++,m++) //进行译码
{
temp[m]=str1[i];
for(j=0;j<n;j++)
{
若找到对应编码
{
printf("%c",ht[j].data);
for(k=0;k<30;k++)
temp[k]='\0';
m=-1;
终止循环； }
}
}

四. 调试分析以及设计体会
1.测试数据：
准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果：
输入：
图6.编码输入演示图

输出：
图7.编码输出演示图

正确输入哈夫曼编码代号：
图8.正确译码输入演示图

输出：
图9.正确输入译码译码结果输出演示图
错误输入哈夫曼编码代号：
图10.错误输入哈夫曼编码代码串示意图

输出：
图11.错误输入哈夫曼编码代码串输出示意图

2.程序调试中遇到的问题以及解决问题的方法：
编写完译码函数ReadCode（）后进行调试，程序会在译码过程中进入死循环，且无法译出正确字符串。经过仔细观察，发现程序中有一个循环的终止条件本应为str[i]!=’\0’，却将其误写成了str[i]!=’\n’,因而无法正常终止循环并译码，改正后实现了译码功能。

3.课程设计过程经验教训、心得体会：
此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终实现课题任务的过程中，我学到了不少东西：
首先，在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题的时候，因为没有仔细理解这些要求，就采用了键盘输入字符进行编码和译码的方式，以致没有完全达到课题的要求。
另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实现的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找改进程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用体验。最终在答辩的时候，交给老师的是一个界面简陋，功能不全面的程序。
通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。

五. 用户使用手册
1.运行程序，程序首先会要求你输入需要编码的字符串，输入完毕按回车即可进行编码：
图12.程序启动画面

输出：
图13.编码输出画面

2.输出编码后，程序会提示输入需要译码的哈夫曼编码串，输入后按回车即可进行译码：
图14.译码输入界面
输出：
图15.译码输出界面
3.译码结束后，输入a可退出程序，输入b可继续进行译码。

六. 附录
源程序清单（带注释）：

typedef.h文件代码：
#define MAXV 30
typedef struct CNode //用来保存字符次数的结构体
{
char c;
int num;
int flag;
};

typedef struct //哈弗曼树结点
{
char data;
double weight;
int parent;
int lchild;
int rchild;
}HTNode;

typedef struct //各叶子结点的哈弗曼编码
{
char cd[30];
int start;
}HCode;

main.cpp文件代码：
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include"typedef.h"
#define N 100

extern void insertstr(char str[]);
extern int countstr(char str[],CNode *);
extern void dispCNode(CNode *,int);
extern void CreateHT(HTNode ht[],int);
extern void CreateHCode(HTNode ht[],HCode hcd[],int n);
extern int DispHCode(HTNode ht[],HCode hcd[],int n);
extern void insertstr1(char str[]);
extern int ReadCode(char str1[],HCode hcd[],HTNode ht[],int MAX,int n);
int n=0;
void main()
{
int i;
int MAX; //哈弗曼编码的最大长度
int flag=0; //标记哈弗曼编码输入是否合法
char choice;
char str[N],str1[N];
CNode CharNode[MAXV];
HTNode ht[100];
HCode hcd[50];
insertstr(str);
printf("\n");
n=countstr(str,CharNode);
printf("\n");
dispCNode(CharNode,n);
printf("\n");
for(i=0;i<n;i++) //初始化哈弗曼树的叶子结点
{
ht[i].data=CharNode[i].c;
ht[i].weight=CharNode[i].num;
}
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
MAX=DispHCode(ht,hcd,n);
printf("\n");
while(flag==0)
{
insertstr1(str1);
printf("\n");
printf("译码结果如下：\n");
flag=ReadCode(str1,hcd,ht,MAX,n);
printf("\n请选择：a（退出）/b（继续译码）\n");
getchar();
scanf("%c",&choice);
switch(choice)
{
case 'a':
exit(1);break;
case 'b':
flag=0;break;
}

}
}

function.cpp文件代码：
#include<stdio.h>
#include<string.h>
#include"typedef.h"

#define N 100

void insertstr(char str[]) //输入字符串
{
printf("请输入一个字符串：\n");
scanf("%s",str);
}

int countstr(char str[],CNode *CharNode) //记录字符出现次数，并保存在CNode中
{
int i,j,a=0;
for(i=0;i<MAXV;i++)
{
CharNode[i].flag=-1;
CharNode[i].num=0;
CharNode[i].c='|';
}
for(i=0;str[i]!='\0';i++)
{
for(j=0;j<MAXV;j++)
{
if(str[i]==CharNode[j].c)
{
CharNode[j].num++;
break;
}
else
if(CharNode[j].flag==-1)
{
a++;
CharNode[j].c=str[i];
CharNode[j].num++;
CharNode[j].flag=0;
break;
}
}
}
return a;
}

void dispCNode(CNode *CharNode,int n)
{
int i;
printf("输入的字符极其出现次数如下 ：\n");
for(i=0;i<MAXV;i++)
{
if(CharNode[i].flag!=-1)
{

printf("%c: ",CharNode[i].c);
printf("%d\n",CharNode[i].num);
}
}
}

void CreateHT(HTNode ht[],int n) //构造哈弗曼树
{
int i,j,k,lnode,rnode;
double min1,min2; //分别存放lnode和rnode的两个结点位置
for(i=0;i<2*n-1;i++) //所有结点的相关域置-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=n;i<2*n-1;i++)
{
min1=min2=32767;
lnode=rnode=-1;
for(k=0;k<=i-1;k++)
if(ht[k].parent==-1)
{
if(ht[k].weight<min1)
{
min2=min1;
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
else if(ht[k].weight<min2)
{
min2=ht[k].weight;
rnode=k;
}
}
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode; ht[i].rchild=rnode; //ht[i]作为双亲结点
ht[lnode].parent=i; ht[rnode].parent=i;

}

}

void CreateHCode(HTNode ht[],HCode hcd[],int n) //求哈弗曼编码
{
int i,f,c;
HCode hc;
for(i=0;i<n;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++;
hcd[i]=hc;

}
}

int DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈弗曼编码
{
int i,k;
int j;
int MAX=0;
printf("输出哈弗曼编码：\n");
for(i=0;i<n;i++)
{
j=0;
printf("%c: ",ht[i].data);
for(k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
if(j>=MAX)
MAX=j;
}
printf("\n");
}
return MAX;
}

void insertstr1(char str1[]) //输入哈弗曼编码
{
int i;
for(i=0;i<N;i++) //初始化str1[]
str1[i]='\0';
printf("请输入一串需要译码的哈弗曼编码：\n");
scanf("%s",str1);
}

int strcompare(HCode hcd[],char temp[],int a,int n) //字符串比较函数
{
int i,j=hcd[a].start;
char str[30]="";
for(i=0;j<=n;i++,j++)
{
str[i]=hcd[a].cd[j];
}
if(strcmp(str,temp)==0)
return 1;
else
return 0;
}

int ReadCode(char str1[],HCode hcd[],HTNode ht[],int MAX,int n) //译码函数
{
int strcompare(HCode hcd[],char temp[],int a,int n); //声明字符串比较函数
int i,j,m=0,k;
int flag=1; //flag为1则哈弗曼编码输入合法
char temp[30]="";
for(i=0;str1[i]!='\0';i++,m++) //进行译码
{
temp[m]=str1[i];
for(j=0;j<n;j++)
{
if(strcompare(hcd,temp,j,n)) //存在对应编码
{
printf("%c",ht[j].data);
for(k=0;k<30;k++)
temp[k]='\0';
m=-1;
break;
}
}
if(m>=MAX-1) //输入不合法
{
printf("无译码，你所输入的编码不正确！\n");
flag=0;
break;
}
}
return flag; //返回标记值
}

第21页
共21页

计算机与通信学院课程设计评分表

课程名称： 哈夫曼编码与译码

项 目
评 价
设计方案的合理性与创造性

设计与调试结果

设计说明书的质量

答辩陈述与回答问题情况

课程设计周表现情况

综合成绩

教师签名：
日 期：

（注：1．此页附在课程设计报告之后；2．综合成绩按优、良、中、及格和不及格五级评定。）