文档介绍：《数据结构课程设计》
姓名:
刘欢
学号:
201001051118
班级:
信管10-1班
成绩:
信息科学与工程学院
2012年5月23日
哈弗曼编码问题
需求分析
利用哈弗曼编码进行通信可以大大提高通行利用率,缩短信息传输时间,降低传输成本,但是,要求在发送端通过一个编码系统对待传数据进行预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道,每段都需要一个完善的便/译码系统,试为这样的信息首发站写个哈弗曼码的编/译码系统
概要设计
:
ADT {
数据对象:D= {|int,i = 1,2,3...n,n0}
数据关系:R = {<,>|,D,<,i=2...n}
基本操作:void Inithialization()//初始化
操作结果: 初始化哈夫曼树,这个函数的实现实际是在HuffmanCoding中的直接初始化并编码
基本操作:void HuffmanCoding ()// 编码
操作结果: 利用已经建立好的哈夫曼树编码
基本操作:void Decoding ()// 译码
操作结果:利用已经建立好的哈夫曼树将文件codeFile中的代码进行译码
基本操作:void Print()// 打印代码文件
操作结果: 将文件CodeFIle以紧凑的格式显示在终端屏幕上
}ADT
主函数的设计
Int main (){
接受输入的数据
建立哈夫曼树
输出编码结果
}
详细设计
元素类型、节点类型、指针类型
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchile;
}HTNode,*HuffmanTree;// 动态分配数组存储哈夫曼树
typedef char* *HuffmanCode;// 动态分配数组存储哈夫曼表
void Inithialization(HuffmanTree &HT,HuffmanCode& HC,int *w,int n){//初始化函数
if(n <= 1)return ;
int m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));// 0号单元未用
HuffmanTree p;
int i,s1,s2;
for(p= HT +1,i=1;i<=n;++i,++p,++w)*p = {*w,0,0,0};
for(i=n+1;i<=m;++i){//建立哈弗曼树
//在HT[1..i-1]选择parent为0且weight最小的两个点。其序号分别是s1,s2
Select(HT,i-1,s1,s2);
HT[s1].parent = i;HT[s2].parent = i;
HT[i].lchild = s1; HT[i].lchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode& HC,int *