用哈夫曼编码实现文件压缩实验报告 (2).pdf

《用哈夫曼编码实现文件压缩》

实 验 报 告

课程名称 数据结构 B

实验学期 2013 至 2014 学年 第 一 学期

学生所在系部 计算机学院

年级 2013 专业班级

学生姓名 学号

任课教师

实验成绩

4、掌握二叉树的存储结构及遍历算法。

5、利用 Huffman 树及 Huffman 编码，掌握实现文件压缩的一般原理。

三、实验设备与环境：

四、实验内容：

根据输入小写英文字母和输入的对应权值创建哈夫曼树，可以求出每个小写英文字母的哈夫

曼编码，将文本中的字母对应的哈夫曼编码写入文本中，实现对文本的编码。

五、概要设计：

（1）构造 Hufffman 树的 Hufffman 算法

构造 Huffman 树步骤：

1. 根据给定的 n 个权值{w1,w2,……wn}，构造 n 棵只有根结点的二叉树，起权

（2）Huffman 编码：数据通信用的二进制编码

编码：根据字符出现频率构造 Huffman 树，然后将树中结点引向其左孩子的

分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每

文本中。

六、详细设计：

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

//树结点定义

typedef struct

{

int weight;

int parent;

//封装最小权结点和次小权结点

typedef struct

{

int s1;

int s2;

}MinCode;

//函数声明

void Error();

HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n);

MinCode Select(HuffmanTree HT,int n);

//构造赫夫曼 HT，编码存放在 HC 中,w 为权值,n 为结点个数

HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n)

{

int i,s1=0,s2=0;

HuffmanTree p;

char *cd;

int f,c,start,m;

MinCode min;

if(n<=1)

{

Error();//只有一个结点不进行编码，直接 exit(1)退出

}

m=2*n-1;//赫夫曼码需要开辟的结点大小为 2n-1

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟赫夫曼树结点空间 m+1

{

p->parent=0;

//将 n-1 个非叶子结点的初始化

for(;i<=m;i++,p++)

{

p->weight=0;

p->parent=0;

p->rchild=0;

}

//构造赫夫曼树