-树-哈夫曼编解码的实现-实验内容与要求.docx

数据结构实验报告
评分

满分——10分

学号：2015111840 姓名：陈周擎 专业：计算机科学与技术
知识范畴：树 完成日期：2017年05月12日
实验题目：Huffman编解码的实现
实验内容及要求：
从字符文件读取若干个大写英文字符(英文字符种类数m建议为6至8种，如:m=6，则英文字符可取A-F)，统计m种英文字符的出现频度，构造Huffman二叉树，对所有英文字符进行Huffman编码，将编码后的比特流用byte型（或char型）数组实现存储。在屏幕上输出该比特流的压缩率，然后利用该数组和Huffman二叉树进行译码，将译码后的字符序列输出到另一个字符文件。
提示：(1) 输入与输出字符文件每10个字符一行；
(2) 输入文件中的不可显示字符（如：回车、换行符）不进行统计和编码；
(3) 压缩率=平均编码长度/log2m。
实验目的：掌握Huffman二叉树及Huffman编、译码。
数据结构设计简要描述：
本实验采用数组以及静态链表方式存储。
码树结点的结构体：
typedef struct
{
int parent,； //双亲下标
int lchild； //左儿子下标
int rchild; //右儿子下标
double w; //结点权值
} HF_BTNode;
Huffman码树及码表：
typedef struct
{
int n; //实际符号数
char s[N]; //符号表
double weight[N]; //符号权重表
char code[N][N+1]; //编码表
HF_BTNode hf[2 * N - 1]; //码树
double rate; //压缩率
}HFT；
算法设计简要描述：
本实验中核心算法包括构造Huffman二叉树并编码算法、解码算法。
构造Huffman二叉树并编码：hf[0..n-1]为码树的叶子结点。构造Huffman树的过程共需要进行n-1趟两个子树的合并，每趟合并后，生成的新的子树的根结点按照下标增量次序加入。
解码算法：设接收二进制序列用字符串表示，从根结点出发，‘1’表示向左，‘0’表示向右深入，直到到达某个叶子结点时，输出叶子结点对应的符号；重复此过程，直到接收序列全部译出。
输入/输出设计简要描述：
本实验中分别有一次输入和两次输出。
输入：英文字符种类数m。
输出：译码的字符序列输出到另一个文件中；在屏幕上输出Huffman编码的压缩率。
编程语言说明：
1.编程软件，Code Blocks 16.0；
2.代码均用C++语言实现；
3.输入输出采用C++语言的cout和cin函数；
4.程序注释采用C/C++规范；
5.动态存储分配采用C++的new和delete操作符实现
主要函数说明：
void insert(char ch) //插入字符
int found(char ch) //查找字符
void creat() //构造霍夫曼二叉树
void coding() //生成各种字符编码
void cal() //计算压缩率
void coding(char *sour, HFT &hft) //字符串进行霍夫曼编码
void decoding(char *dsou, HFT &hft) //字符串解码
程序测试简要报告：
（1） 测试实例1
输入：
请输入m：4
输出：
压缩率为 0.875
运行界面：

结论：程序输出结果与期望输出结果相符。
（2） 测试实例2
输入：
请输入m：10
输出：
压缩率为 0.872987
运行界面：

结论：程序输出结果与期望输出结果相符。

（3） 测试实例3
输入：
请输入m：6
输出：
压缩率为 0.976803
运行界面：

结论：程序输出结果与期望输出结果相符。

源程序代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include<stdio.h>
#include <cmath>
#define N 256 //最多字符种类
#define MAXL 10000 //最长文件长度
using namespace std;

typedef struct
{
int parent, lchild, rchild;
double w;
} HF_BTNode;

char rece[MAXL]; //编码结果
char s[MAXL]; //源字符串（编码源）
int byte_num; //编码总位数

typedef struct
{
int n; //实际符号数
char s[N]; //符号表
double weight[N]; //符号权重表
char code[N][N+1]; //编码表
HF_BTNode hf[2 * N - 1]; //码树
double rate; //压缩率

void insert(char ch) //插入字符ch
{
for (int i = 0; i < n; i++)
if (s[i] == ch)
{
weight[i]++;
return;
}
s[n] = ch;
weight[n]++;
n++;
}

int found(char ch) //查找ch字符
{
for (int i = 0; i < n; i++)
if (ch == s[i])
return i;
return -1;
}

void creat() //构造霍夫曼二叉树
{
int m = 2 * n - 1;
for (int i = 0; i < m; i++)
hf[i].parent = hf[i].lchild = hf[i].rchild = -1;
for (int i = 0; i < n; i++)
hf[i].w = weight[i];
for (int i = n; i < m; i++)
{
int j1, j2;
for (j1 = 0; j1 < i; j1++)
if (hf[j1].parent == -1)
break;
for (int j = j1 + 1; j < i; j++)
if (hf[j].parent == -1 && hf[j].w < hf[j1].w)
j1 = j;
hf[j1].parent = i;
hf[i].lchild = j1;
for (j2 = 0; j2 < i; j2++)
if (hf[j2].parent == -1)
break;
for (int j = j2 + 1; j < i; j++)
if (hf[j].parent == -1 && hf[j].w < hf[j2].w)
j2 = j;
hf[j2].parent = i;
hf[i].rchild = j2;
hf[i].w = hf[j1].w + hf[j2].w;
}
}

void coding() //生成各种字符编码
{
for (int i = 0; i < n; i++)
{
int j = i;
char *p = code[i];
while (hf[j].parent != -1)
{
int child = j;
j = hf[j].parent;
if (hf[j].lchild == child) *p++ = '1';
else *p++ = '0';
}
*p = '\0';
char *q = code[i];
p--;
while (q < p)
{
char ch = *q;
*q = *p;
*p = ch;
q++;
p--;
}
}
}

void cal() //计算压缩率
{
double len = 0;
for (int i = 0; i < n; i++)
len += strlen(code[i])*weight[i];
rate = len / log(n) * log(2);
}
} HFT;

void coding(char *sour, HFT &hft) //对sour字符串进行霍夫曼编码
{
byte_num = 0;
int len = strlen(sour);
for (int i = 0; i < len; i++)
{
int ind = hft.found(sour[i]);
if (ind == -1)
continue;
char *p = hft.code[ind];
int l = strlen(p);
for (int j = 0; j < l; j++)
{
int x = byte_num / 8;
int y = byte_num % 8;
if (p[j] == '0') rece[x] &= ~(1 << y);
else rece[x] |= (1 << y);
byte_num++;
}
}
}
void decoding(char *dsou, HFT &hft) //对dsou字符串解码
{
int x, y, cnt = 0;
FILE *fp;
fp=fopen("file_result.txt","w");
for (int i = 0; i < byte_num;)
{
int k = 2 * hft.n - 2;
while (k >= hft.n && i < byte_num)
{
x = i / 8;
y = i % 8;
if (dsou[x] & (1 << y))
k = hft.hf[k].lchild;
else k = hft.hf[k].rchild;
i++;
}
if (k < hft.n)
{
cnt++;
fputc(hft.s[k], fp);
if (cnt % 10 == 0) fputc('\n', fp);
}
}
}HFT hufft;

int main()
{
FILE *fp;
int ch, slen = 0;
fp=fopen("file_data.txt", "r");
while ((ch = fgetc(fp)) != EOF && slen < MAXL)
if (ch != ' ' && ch != '\n')
{
hufft.insert(ch);
s[slen++] = ch;
}
s[slen] = '\0';
for (int i = 0; i < hufft.n; i++)
hufft.weight[i] /= slen;
hufft.creat();
hufft.coding();
hufft.cal();

cout << "压缩率为 " << hufft.rate << endl;
coding(s, hufft);
decoding(rece, hufft);
fclose(fp);
return 0;
}

9 / 9