文档介绍：编写目的
利用哈弗曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道,每端都需要一个完整的编/译码系统。因此编写此系统的目的即为这样的信息收发站写一个哈弗曼码的编/译码系统。
需求概述
设计一个哈弗曼编/译码系统,使之提供以下功能:
哈弗曼树的创建过程
哈弗曼编码的实现
哈弗曼译码的实现
需求说明
哈弗曼树的内容包括待编码的字符及各字符的权值大小。
编码需从叶子结点出发走一条从叶子到根的路径(个人****惯)。
译码需从根出发走一条从根到叶子的路径。
第二部分系统分析
编写目的
用户在了解了编写此系统的目的后,可以进一步的了解我实现此系统的大致过程,从而更好的运行哈弗曼编/译码系统。
总体设计
功能划分
该系统可以按功能进行模块划分,如下图:
数据结构
本系统主要的数据结构就是哈弗曼树的信息内容,包含待编码的字符及各字符的权值大小,在处理过程中各项可以作为哈弗曼树的不同属性来进行处理。
第三部分程序流程图
系统的执行应从功能菜单开始,一句用户的选择来进行后续的处理,直到用户选择退出系统为止,系统的流程图如下:
主程序流程图
(2)建立哈弗曼树流程图
(3)编码流程图
译码流程图
第四部分代码
//
#ifndef __HUFFMAN__H
#define __HUFFMAN__H
typedef char HElemType;
typedef struct
{
HElemType data; //数据字符
unsigned int weight; //权重
unsigned int parent,lch,rch;
}HTNode,*HuffmanTree;
Typedef char **HuffmanCode; //存放哈夫曼编码
void CreateHuffmanTree(HuffmanTree *HT,unsigned int *w,int n,HElemType *num); //建哈夫曼树
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,unsigned int *w,int n); //哈夫曼编码
void HuffmanDeCoding(HuffmanTree *HT,HuffmanCode *HC,int n); //哈夫曼译码
void Display(HuffmanTree HT,HuffmanCode HC,unsigned int *w,int n); //查看编译码信息
void menu(); //菜单
#endif
//
#include<>
#include<>
#include<>
#include""
void Select(HuffmanTree *HT,int t,int &s1,int &s2) //在n个结点中选择两个权值最小的结点序号,其中s1最小,s2次小
{
int i;
unsigned int m,n;
m=n=10000;
for(i=1;i<=t;i++)
{
if((*HT)[i].parent==0 && ((*HT)[i].weight<m || (*HT)[i].weight<n))
{
if(m<n)
{
n = (*HT)[i].weight;
s2 = i;
}
else
{
m = (*HT)[i].weight;
s1 = i;
}
}
}
if(s1>s2)
{
i=s1;
s1=s2;
s2=i;
}
}
void CreateHuffmanTree(HuffmanTree *HT,unsigned int *w,int n,HElemType *num)
{
int i,m;
int s1,s2;
HuffmanTree p;
if(n<=1)
return;
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=*HT+1,i=1;i<=n;++i,++p,++w,++num) //进行初始化
{
(*p).weight=*w;
(*p).parent=0;
(*p).lch=0;
(*p).rch=0;
(*p).