哈夫曼编译码---数据结构C语言版课程设计.doc

《数据结构》
课程设计报告

设计题目 哈 夫 曼 (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：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

四、需求分析
利用哈夫曼树(Huffman)编/译码
（一）、初始化哈夫曼树
（二）、建立哈夫曼树
（三）、对哈夫曼树进行编码
（四）、输出对应字符的编码
（五）、译码过程
五、概要设计
哈夫曼树的存储结构描述
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;
哈弗曼树的算法
void CreateHT(HTNode ht[],int n) //调用输入的数组ht[],和节点数n
{
int i,k,lnode,rnode;
int min1,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<min1) //若权值小于最小的左节点的权值
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
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; //父节点的左节点和右节点
}
}
哈弗曼编码
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++; //start指向哈夫曼编码hc.cd[]中最开始字符
hcd[i]=hc;
}
}

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码的列表
{
int i,k;
printf(" 输出哈夫曼编码:\n");
for (i=0;i<n;i++) //输出data中的所有数据，即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");
}
}

void editHCode(HTNode ht[],HCode hcd[],int n) //编码函数
{
char string[MAXSIZE];
int i,j,k;
scanf("%s",string); //把要进行编码的字符串存入string数组中
printf("\n输出编码结果:\n");
for (i=0;string[i]!='#';i++) //#为终止标志
{
for (j=0;j<n;j++)
{
if(string[i]==ht[j].data) //循环查找与输入字符相同的编号，相同的就输出这个字符的编码
{
for (k=hcd[j].start;k<=n;k++)
{
printf("%c",hcd[j].cd[k]);
}
break; //输出完成后跳出当前for循环
}
}
}
}
哈弗曼译码
void deHCode(HTNode ht[],HCode hcd[],int n) //译码函数
{
char code[MAXSIZE];
int i,j,l,k,m,x;
scanf("%s",code); //把要进行译码的字符串存入code数组中
while(code[0]!='#')
for (i=0;i<n;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];
}
}
}
}
主函数
void main()
{
int n=26,i;
char orz,back,flag=1;
char str[]={'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'}; //初始化
int fnum[]={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}; //初始化
HTNode ht[M]; //建立结构体
HCode hcd[N]; //建立结构体
for (i=0;i<n;i++) //把初始化的数据存入ht结构体中
{
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");
}}}
六、详细设计
字符
空格
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20

由上表画出哈夫曼树：

由哈夫曼树得出各字符的编码：

字符
编码
字符
编码
空格
10
D
0001
A
010
E
1111
B
011111
F
11001
C
0000
G
01110

关系调用：

该程序的流程图：

开始
结点数是否大于1
将data和权值赋给ht
输出根结点和权值
调用selectmin函数
计算根结点函数
父结点为两子结点之和
输出两子结点和已构造的结点 点
是否为根结点？
左子是否为空？
此时编码为0
i<=2*n
i++
编码为1
结束
否
否
否
右子是否为空
是
是
否
否
是
是
是

七、测试分析

白盒：
查看代码完整性
白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都能按预定要求正确工作。 这一方法是把测试对象看作一个打开的盒子，测试人员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。
黑盒：
测试是否可以正确的创建，删除，插入，打印，查找等操作
黑盒测试也称功能测试，它是通过测试来检测每个功能是否都能正常使用。在测试中，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能进行测试。

八、使用说明

1) 输入n个字符的权值
2) 输入对应的字符
3) 得出各字符的编码

九、测试数据
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 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
注：学生在测试数据时，需要写出测试用例和截图

十、该程序的源代码
#include <stdio.h>
#include <stdlib.h> //要用system函数要调用的头文件
#include<conio.h> //用getch()要调用的头文件
#include <string.h>
#define N 50 //义用N表示50叶节点数
#define M 2*N-1 //用M表示节点总数 当叶节点数位n时总节点数为2n-1
#define MAXSIZE 100

typedef struct
{
char data; //结点值
int weight; //权值
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}HTNode;

typedef struct
{
char cd[N]; //存放哈夫曼码
int start; //从start开始读cd中的哈夫曼码
}HCode;

void CreateHT(HTNode ht[],int n) //调用输入的数组ht[],和节点数n
{
int i,k,lnode,rnode;
int min1,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<min1) //若权值小于最小的左节点的权值
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
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; //父节点的左节点和右节点
}
}

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++; //start指向哈夫曼编码hc.cd[]中最开始字符
hcd[i]=hc;
}
}

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码的列表
{
int i,k;
printf(" 输出哈夫曼编码:\n");
for (i=0;i<n;i++) //输出data中的所有数据，即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");
}
}

void editHCode(HTNode ht[],HCode hcd[],int n) //编码函数
{
char string[MAXSIZE];
int i,j,k;
scanf("%s",string); //把要进行编码的字符串存入string数组中
printf("\n输出编码结果:\n");
for (i=0;string[i]!='#';i++) //#为终止标志
{
for (j=0;j<n;j++)
{
if(string[i]==ht[j].data) //循环查找与输入字符相同的编号，相同的就输出这个字符的编码
{
for (k=hcd[j].start;k<=n;k++)
{
printf("%c",hcd[j].cd[k]);
}
break; //输出完成后跳出当前for循环
}
}
}
}

void deHCode(HTNode ht[],HCode hcd[],int n) //译码函数
{
char code[MAXSIZE];
int i,j,l,k,m,x;
scanf("%s",code); //把要进行译码的字符串存入code数组中
while(code[0]!='#')
for (i=0;i<n;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];
}
}
}
}

void main()
{
int n=26,i;
char orz,back,flag=1;
char str[]={'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'}; //初始化
int fnum[]={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}; //初始化
HTNode ht[M]; //建立结构体
HCode hcd[N]; //建立结构体
for (i=0;i<n;i++) //把初始化的数据存入ht结构体中
{
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();
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");
}
}
}
：
该程序的截图：
初始化界面截图如下

选A时的显示结果截图如下

选择B时的显示结果截图如下

选C时的显示结果截图如下

十一、使用说明（给出软件如何使用，使用时的注意事项）
VC++6.0编程环境使用
1、 VC++6.0程序启动 
2、新建工程Project
3、 设定工程Project名称、保存位置 
4、 设定工程Project的类型 
5、 工程Project的描述信息生成
6、 空工程Project建立完毕
7） 向工程Project中添加(新建)源代码文件的类型、名称、保存位置 
8、设定源代码文件的类型、名称
9、 源代码文件被添加到工程中 
10、在源代码文件中添加程序代码
11、程序代码编译完成后编译、链接过程
注意事项： 
（1） 一个工程project中可以有多个源文件(.cpp)、多个头文件（.h）；
但这些源代码文件中只能出现一个main函数，作为整个程序运
行的入口； 
（2）必须关闭前一次程序运行结果窗口，才能进行下一次程序运行； 
（3）书写标识符时，忽略了大小写字母的区别。 
（4 )  忘记加分号 
（5） 多加分号
十二、课程设计总结
本次课程设计的题目是：哈夫曼(Huffman)编/译码器。通过这次课程设计，我了解到自己在编写程序方面还有很多不足，在实践过程中老师给了我很大的帮助。在这次课程设计中，虽然不会成功的编写一个完整的程序，但是在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，解决问题和在老师的帮助下一步一步慢慢的正确运行程序，终于完成了这次课程设计，虽然这次课程设计结束了但是总觉得自已懂得的知识很是不足，学无止境，以后还会更加的努力深入的学习。
27