哈夫曼编译码器课程设计报告.doc

计算机学院 《数据结构》课程设计报告
学号
2015-2016学年 第1学期
1508

《数据结构》

课程设计报告

题目：
哈夫曼编/译码器
专业：
计算机科学与技术（对口）
班级：
13（3）
姓名：
陈霞
指导教师：
彭飞
成绩：

计算机学院
2015年11月12日

目录

1 设计内容及要求 3
1.1 内容 3
1.2 要求 3
2 概要设计 4
2.1 抽象数据类型定义 4
2.2 模块划分 4
3 设计过程及代码 5
3.1 设计过程 5
3.2 代码 7
4 设计结果与分析 10
5 参考文献 12

1 设计内容及要求
1.1 内容
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。
1.2 要求
一个完整的系统应具有以下功能： 
（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和 n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 
（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件 htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 
（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 
（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 
（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
 [测试数据]    
（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序 进行调试。 
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“ 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

2 概要设计
2.1 抽象数据类型定义
ADT Stack 
数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0} 
数据关系：若D为空集，则称为空树。           
若D仅为一个数据元素，则R为空集，否则R={H}，H是如下的二元关 系： 
（1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。 
（2）若D-{root}<>空集，则存在一个划分D1，D2，···，Dm（m>0）。 
（3）对应于D-{root}的划分，H-{<root，X1}，···，<root，Xm>}有唯一的一个划分H1，H2，···，Hm（m>0）。 

基本操作：
  InitTree(&T) 
操作结果：构造空树T。
DestroyTree(&T) 
初始条件：树T已存在。 
操作结果：树T被销毁。
 ClearTree(&T) 
初始条件：树T已存在。 
操作结果：将树T清为空栈。
  TreeEmpty(T) 
初始条件：树T已存在。 
操作结果：若树T为空，则返回TRUE，否则FALSE。
  TreeDepth(T)
  初始条件:树T已存在。 
操作结果：返回T的深度。
  Root（T）
  初始条件：树T已存在。
操作结果：返回树T的根。

2.2 模块划分
本程序包括三个模块： 
(1)主程序模块 
void main()
{ 
初始化； 
构造哈夫曼树； 
求哈夫曼编码；
  哈夫曼编码输出； 
} 
（2）哈夫曼模块——实现哈夫曼树的抽象数据类型 
（3）求哈夫曼编码模块——实现求哈夫曼编码算法的数据类型

3 设计过程及代码
3.1 设计过程
1、 数据类型的定义

（1） 哈夫曼树类型 
typedef struct{//构造树      
char  data;//结点权值      
int weight;//权重      
int parent;//双亲结点      
int lchild;//左孩子      
int rchild;//右孩子   
}HTNode;   
HTNode ht[30]; 
（2） 求哈夫曼编码类型 
typedef struct{       
char cd[30];//存放当前结点的哈弗曼编码     
int start;//cd[start]~cd[n]存放哈弗曼码 
}HCode; 
HCode hcd[30];

2、主要模块的算法描述
开始
Int I;
i<n
Scanf(“%d”,&ht[t].we
i++
结束
Int I,f,c;
I=0
I<n
Hc.start=n;c=i
F!=-1
multiplex
Hc.start++;
I++
主函数流程图
图3.1.1

哈弗曼编码算法流程图
图3.1.2

3.2 代码

#include<stdio.h> 
#define n 27  //叶子数目 
#define m (2*n-1)    //结点总数
#define maxval 10000.0 
#define maxsize 100   //哈夫曼编码的最大位数
 typedef struct 
{ 
  char ch; 
 float weight; 
  int lchild,rchild,parent;
 }hufmtree; 
typedef struct 
{ 
 char bits[n];   //位串 
 int start;      //编码在位串中的起始位置 
 char ch;        //字符
 }codetype;

void huffman(hufmtree tree[]);//建立哈夫曼树 
void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码 
void decode(hufmtree tree[]);//依次读入字符，根据哈夫曼树译码  
int  main()
 { 
  printf("  ——哈夫曼编码——\n");  
printf("总共有%d个字符\n",n); 
 hufmtree tree[m];
   codetype code[n];
   int i,j;//循环变量
   huffman(tree);//建立哈夫曼树
   huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
  printf("【输出每个字符的哈夫曼编码】\n"); 
  for(i=0;i<n;i++)
  { 
   printf("%c: ",code[i].ch);   for(j=code[i].start;j<n;j++) 
    printf("%c ",code[i].bits[j]);   printf("\n"); 
 } 
 printf("【读入字符，并进行译码】\n"); 
 decode(tree);//依次读入电文，根据哈夫曼树译码
 } 
  void huffman(hufmtree tree[])//建立哈夫曼树
 {
int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
   float small1,small2,f; 
 char c; 
 for(i=0;i<m;i++)    //初始化 
 { 
   tree[i].parent=0;
    tree[i].lchild=-1;  
 tree[i].rchild=-1;  
 tree[i].weight=0.0; 
 } 
 printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】\n",n); 
  for(i=0;i<n;i++)  //读入前n个结点的字符及权值 
 { 
   printf("输入第%d个字符为和权值",i+1); 
   scanf("%c %f",&c,&f); 
   getchar();
    tree[i].ch=c; 
   tree[i].weight=f; 
 } 
 for(i=n;i<m;i++)      //进行n-1次合并，产生n-1个新结点
  { 
   p1=0;
p2=0;
small1=maxval;
small2=maxval;   //maxval是float类型的最大值  
 for(j=0;j<i;j++)    //选出两个权值最小的根结点  
  if(tree[j].parent==0) 
    if(tree[j].weight<small1)
     { 
      small2=small1;  //改变最小权、次小权及对应的位置    
   small1=tree[j].weight;  
    p2=p1;  
    p1=j;   
  }  
   else 
     if(tree[j].weight<small2)    
  { 
      small2=tree[j].weight;  //改变次小权及位置   
     p2=j;    
  } 
  tree[p1].parent=i;  
 tree[p2].parent=i; 
  tree[i].lchild=p1;  //最小权根结点是新结点的左孩子 
  tree[i].rchild=p2;  //次小权根结点是新结点的右孩子 
  tree[i].weight=tree[p1].weight+tree[p2].weight; 
 } 
}//huffman  
void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码
 //codetype code[]为求出的哈夫曼编码 
//hufmtree tree[]为已知的哈夫曼树
 {
int i,c,p; 
  codetype cd;   //缓冲变量 
 for(i=0;i<n;i++) 
 { 
   cd.start=n; 
   cd.ch=tree[i].ch; 
   c=i;       //从叶结点出发向上回溯 
   p=tree[i].parent;   //tree[p]是tree[i]的双亲  
 while(p!=0)  
 { 
    cd.start--; 
   if(tree[p].lchild==c) 
     cd.bits[cd.start]='0';   //tree[i]是左子树，生成代码'0'
    else 
     cd.bits[cd.start]='1';   //tree[i]是右子树，生成代码'1'  
   c=p; 
    p=tree[p].parent;  
 } 
  code[i]=cd;    //第i+1个字符的编码存入code[i]  
} 
}//huffmancode  
void decode(hufmtree tree[])//依次读入字符，根据哈夫曼树译码 
{ 
 int i,j=0; 
char b[maxsize]; 
 char endflag='2';    //电文结束标志取2
   i=m-1;             //从根结点开始往下搜索
  printf("输入发送的编码(以'2'为结束标志)："); 
 gets(b); 
printf("译码后的字符为"); 
 while(b[j]!='2')  
{ 
   if(b[j]=='0') 
    i=tree[i].lchild;   //走向左孩子
   else 
    i=tree[i].rchild;   //走向右孩子 
  if(tree[i].lchild==-1)     //tree[i]是叶结点 
  { 
    printf("%c",tree[i].ch); 
    i=m-1;      //回到根结点
   } 
  j++;  
} 
 printf("\n");   
if(tree[i].lchild!=-1&&b[j]!='2')   //电文读完，但尚未到叶子结点  
  printf("\nERROR\n");  //输入电文有错 
}//decode

4 设计结果与分析

图4.1

图4.2

图4.3

图4.4

图4.5

5 参考文献

[1] 黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，2008 
[2] 董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出版社，2008
1