数据结构实验报告记录文件压缩
————————————————————————————————作者：————————————————————————————————日期：
数据结构与程序设计实验
实验报告
课程名称数据结构与程序设计实验课程编号0906550 实验项目名称文件压缩
学号年级
姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静
实验室名称地点21B276
哈尔滨工程大学
实验报告四
实验课名称：数据结构与程序设计实验
实验名称：文件压缩
班级：学号：姓名：时间：2016.04.21
一、问题描述
哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。
统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，
并将该哈夫曼树保存到文件HufTree.dat 中。
根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并
将字符编码保存到HufCode.txt 文件中。
压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。
解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。
二、数据结构设计
由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。
1.使用结构体数组统计词频，并存储:
typedef struct Node{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}LeafNode[N];
2.使用结构体数组存储哈夫曼树:
typedef struct{
unsigned int weight;//权值
unsigned int parent, LChild, RChild;
}HTNode,Huffman[M+1]; //huffman树
3.使用字符指针数组存储哈夫曼编码表：
typedef char *HuffmanCode[2*M]; //haffman编码表
三、算法设计
1.读取文件，获得字符串
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';
}
2.统计叶子结点的字符和权值并存储
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; jif(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++;//权值累加
}
}
*ch_len=len;//字符串长度
}
3．创建HuffmanTree，并存储
创建：
void CreateHuffmanTree(Huffman ht,LeafNode w,int n){
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i<=n;i++){
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++){
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
