文档介绍：. .
优选
数据构造与程序设计实验
实 验 报 告
课程名称
数据构造与程序设计实验
课程编号
0906550
实验工程名称
文件压缩
学号
年级
专业
计算机科学与技术
学生所在学院
计算机学院
指导教师
静
实验室名称地点
21B276
工程大学
实验报告四
实验课名称：数据构造与程序设计实验
实验名称：文件压缩
. .
优选
班级：
学号：
：
时间：
一、问题描述
哈夫曼编码是一种常用的数据压缩技术，对数据文件进展哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进展哈夫曼编码以到达压缩文件的目的，再用哈夫曼编码进展译码解压缩。
l统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，
中。
l根据哈夫曼树〔 中〕对每个字符进展哈夫曼编码，并
文件中。
l压缩：根据哈夫曼编码，。
l解压： 文件利用哈夫曼树译码解压，恢复为源文件。
二、数据构造设计
由于哈夫曼树中没有度为1的结点，那么一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据构造。
，并存储:
typedef struct Node{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}LeafNode[N];
. .
优选
:
typedef struct{
unsigned int weight;//权值
unsigned int parent, LChild, RChild;
}HTNode,Huffman[M+1];//huffman树
：
typedef char *HuffmanCode[2*M];//haffman编码表
三、算法设计
，获得字符串
void read_file(char const *file_name, char *ch){
FILE *in_file = Fopen(file_name, "r");
unsigned int flag = fread(ch, sizeof(char), N, in_file);
if(flag == 0){
printf("%s读取失败\n", file_name);
fflush(stdout);
}
printf("读入的字符串是: %s\n\n", ch);
Fclose(in_file);
int len = strlen(ch);
ch[len-1] = '\0';
}
. .
优选
void CreateLeaf(char ch[], int *ch_len, LeafNode leaves, int *leaf_num){
int len,j,k;
int tag;
*leaf_num=0;//叶子节点个数
//统计字符出现个数,放入CW
for(len=0; ch[len]!='\0'; len++){//遍历字符串ch[]
tag=1;
for(j=0; j<len; j++){
if(ch[j]==ch[len]){
tag=0;
break;
}
}
if(tag){// *leaf_num =0 不用
leaves[++*leaf_num].c=ch[len];
leaves[*leaf_num].weight=1;
for(k=len+1; ch[k]!='\0'; k++)//在之后的字符串中累计权值
if(ch[len]==ch[k])
leaves[*leaf_num].weight++