建立Huffman树进行编码和译码的设计
郝萌 1100300423 哈尔滨工业大学计算机科学与技术学院 1003104班
摘要：建立一个简易的系统，对于给定的一篇英文文章，统计字符出
现的概率，并根据概率建立Huffman树，利用Huffman编码
对文章进行编码和译码。掌握Huffman树的建立与应用，并进
一步熟练掌握程序的设计流程。
关键词：Huffman树 Huffman编码 文章译码 文件压缩 解压缩
引言：
给定一篇文章，统计字符出现的概率，根据概率建立哈夫曼树，并进行哈夫曼编码，进而可以利用哈夫曼编码对文章进行编码与译码和文件压缩、解压缩等操作。
程序设计流程
(1)文字
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
述
开始进入功能选择界面，包含五种操作：1.读取文章并对字符编码，2.哈夫曼编码信息，3.文章编码，4.文章译码，5.文件压缩，6.文件解压缩，7.退出程序。操作1：给定一篇文章，统计字符出现的概率，并根据概率建立Huffman树，并利用Huffman树对字符进行Huffman编码。操作2：显示Huffman编码信息，包括字符，字符出现的概率，Huffman编码。操作3：对文章进行译码，显示译码信息，并保存。操作4：对文章进行译码，显示并保存。操作5：对文件进行压缩，每7位二进制序列对应一个ASCII码。操作6：对文件进行解压缩。
流程图
破产流程图 免费下载数据库流程图下载数据库流程图下载研究框架流程图下载流程图下载word
程序数据要求及功能实现
主界面
1.读取文件并对字符进行编码
2.哈夫曼编码信息
3.文件编码
显示文件编码
保存文件编码
4.文件译码
显示文章编码的译码
保存文章编码的译码
文件压缩
文件解压缩
附：程序源代码
/*
* File: HUFFMANFUNCTION.h
* Author: Administrator
*
* Created on 2011年12月19日, 下午6:19
*/
#ifndef HUFFMANFUNCTION_H
#define
HUFFMANFUNCTION_H
#include
#include
#include
#include
#define max1 150
#define max2 50
#define max3 256
using namespace std;
class Htnote {
public:
char name; //字符名
double weight; //权重
int lchild; //左孩子
int rchild; //右孩子
int parent; //父亲
Htnote() {
weight = 0;
lchild = -1;
parent = -1;
rchild = -1;
}
};
class Name {
public:
int num; //字符出现的次数
char pname; //字符名
double lweight; //权值
Name() {
num = 0;
lweight = 0;
}
};
class GetName {
public:
char namef[max2];
int n; //字符的种类
int sum; //字符的总数
Name letter[max1]; //存储字符信息的类的数组
GetName() {
sum = 0;
n = 0;
}
void GetWeight()//得到字符的权值
{
for (int i = 0; i < n; i++) {
letter[i].lweight = (double) letter[i].num / sum; //出现的次数除总数得到权值
}
}
int ReadLetter() {
ifstream input;
cout << "请输入文件名： " << endl;
cin >> namef;
input.open(namef); //打开文件
if (input.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
char ch;
ch = input.get();
letter[0].pname = ch;
letter[0].num++;
sum++;
while (!input.eof()) {//读取文件中的所有字符
int tag = 0;
ch = input.get();
for (int i = 0; i < n + 1; i++) {
if (letter[i].pname == ch) {
letter[i].num++;
sum++;
tag = 1;
}
}
if (tag == 0) {
n++;
letter[n].pname = ch;
letter[n].num++;
sum++;
}
}
sum--;
input.close();
GetWeight(); //得到字符权值
}
};
class CodeNode//编码类
{
public:
char ch; //存储字符
char bits[max1]; //存储编码
};
class Function {
public:
GetName L;
int fn; //定义哈夫曼数组大小
Htnote HuffmanT[max3]; //哈夫曼数组
CodeNode Code[max1]; //字符编码数组
Function() {
fn = 0;
}
void CharHuffmanTCoding()//编码功能实现
{
int i, f, c;
char cd[L.n + 1]; //暂时存储编码的数组
int start; //编码读取起始位置
cd[L.n] = '\0';
for (i = 0; i < L.n; i++) {
Code[i].ch = HuffmanT[i].name; //字符信息
start = L.n; //起始位置
c = i;
while ((f = HuffmanT[c].parent) >= 0) {
if (HuffmanT[f].lchild == c)//如果为左孩子，为‘0’
{
cd[--start] = '0';
} else//如果为右孩子，为‘1’
{
cd[--start] = '1';
}
c = f;
}
strcpy(Code[i].bits, &cd[start]); //将结果存入对应的编码数组中
}
}
void OutputHuffmanTCode() {
cout << "哈夫曼编码：" << endl;
cout << "——————————————————————" << endl;
cout << "字符\t权值\t\t哈夫曼编码 " << endl;
for (int i = 0; i < L.n; i++)//输出字符，权值，哈夫曼编码
{
cout << "——————————————————————" << endl;
cout << HuffmanT[i].name << "\t" << HuffmanT[i].weight << "\t";
cout << Code[i].bits;
cout << endl;
}
cout << "——————————————————————" << endl;
}
void InitHT()//哈夫曼初始化
{
L.ReadLetter();
fn = (L.n)*2 - 1;
for (int i = 0; i < fn; i++) {
if (i < L.n) {
HuffmanT[i].name = L.letter[i].pname;
HuffmanT[i].weight = L.letter[i].lweight;
}
}
}
void SelectMin(int m, int &p1, int &p2)//选择最小的两个节点
{
int i, j;
double m1, m2;
m1 = m2 = 1;
p1 = p2 = -1;
for (i = 0; i < m; i++) {
if (HuffmanT[i].parent == -1 && HuffmanT[i].weight < m1)//找出为访问过的最小权值节点
{
m2 = m1;
p2 = p1;
m1 = HuffmanT[i].weight;
p1 = i;
} else if (HuffmanT[i].parent == -1 && HuffmanT[i].weight < m2)//找出为访问的权值第二小结点
{
m2 = HuffmanT[i].weight;
p2 = i;
}
}
}
void CreatHT()//建立哈夫曼树
{
int i, p1, p2;
InitHT();
for (i = L.n; i < fn; i++) {
SelectMin(i, p1, p2);
HuffmanT[p1].parent = HuffmanT[p2].parent = i;
HuffmanT[i].lchild = p1;
HuffmanT[i].rchild = p2;
HuffmanT[i].weight = HuffmanT[p1].weight + HuffmanT[p2].weight;
}
}
int OutArticleCode()//显示文章编码
{//文章编码操作
ifstream input;
input.open(L.namef);
if (input.fail()) {
cout << "文件不存在！" << endl;
return 0;
}
char ch;
cout << "文章编码如下：" << endl;
while (!input.eof()) {
ch = input.get();
for (int i = 0; i < L.n; i++) {
if (Code[i].ch == ch)
cout << Code[i].bits;
}
}
cout << endl;
input.close();
}
int SaveArticleCode()//保存文章编码
{
ofstream output;
ifstream input;
char namef1[max2];
input.open(L.namef);
if (input.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
cout << "请输入保存文章编码的文件名：" << endl;
cin >> namef1;
output.open(namef1);
char ch;
while (!input.eof()) {
ch = input.get();
for (int i = 0; i < L.n; i++) {
if (Code[i].ch == ch) {
for (int j = 0; j < strlen(Code[i].bits); j++) {
output.put(Code[i].bits[j]);
}
}
}
}
input.close();
output.close();
cout << "保存完毕！" << endl;
}
int OutTransCode() {//文章译码操作
ifstream input;
char namef[max2];
cout << "请输入保存文章编码的文件名：" << endl;
cin >> namef;
input.open(namef);
if (input.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
char ch;
ch = input.get();
int c = 2 * L.n - 2;
while (!input.eof()) {
if (ch == '0')//遇0搜索左子树
{
if (HuffmanT[c].lchild >= 0) {
c = HuffmanT[c].lchild;
}
if (HuffmanT[c].lchild == -1)//判断是否到叶子
{
cout << HuffmanT[c].name; //输出字符
c = 2 * L.n - 2; //返回根节点
}
}
if (ch == '1')//遇1搜索右子树
{
if (HuffmanT[c].rchild >= 0) {
c = HuffmanT[c].rchild;
}
if (HuffmanT[c].rchild == -1)//判断是否到叶子
{
cout << HuffmanT[c].name; //输出字符
c = 2 * L.n - 2; //返回根节点
}
}
ch = input.get();
}
cout << endl;
input.close();
}
int SaveTransCode() {//保存文章译码
ofstream output;
ifstream input;
char namef[max2];
char namef1[max2];
cout << "请输入文章编码所在的文件名：" << endl;
cin >> namef;
input.open(namef);
if (input.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
cout << "请输入保存文章译码的文件名：" << endl;
cin >> namef1;
output.open(namef1);
char ch;
ch = input.get();
int c = 2 * L.n - 2;
while (!input.eof()) {
if (ch == '0') {
if (HuffmanT[c].lchild >= 0) {
c = HuffmanT[c].lchild;
}
if (HuffmanT[c].lchild == -1) {
output.put(HuffmanT[c].name);
c = 2 * L.n - 2;
}
}
if (ch == '1') {
if (HuffmanT[c].rchild >= 0) {
c = HuffmanT[c].rchild;
}
if (HuffmanT[c].rchild == -1) {
output.put(HuffmanT[c].name);
c = 2 * L.n - 2;
}
}
ch = input.get();
}
input.close();
output.close();
cout << "保存完毕！" << endl;
}
int FileCompression() {//文件压缩功能
CreatHT();
CharHuffmanTCoding();
//保存编码
ofstream output;
ifstream input;
char namef1[] = {"temp.txt"};
input.open(L.namef);
if (input.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
output.open(namef1);
char ch;
while (!input.eof()) {
ch = input.get();
for (int i = 0; i < L.n; i++) {
if (Code[i].ch == ch) {
for (int j = 0; j < strlen(Code[i].bits); j++) {
output.put(Code[i].bits[j]);
}
}
}
}
input.close();
output.close();
//压缩文件
ofstream File1;
ifstream File2;
char namef2[max2];
cout << "请输入压缩后的文件名：" << endl;
cin >> namef2;
File1.open(namef2);
File2.open(namef1);
if (File2.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
char sh;
char th;
int i = 0;
char j = '0';
int count = 0;
while (!File2.eof()) {
sh = File2.get();
if (i < 7 && sh != EOF) {
count = count + (sh - '0') * pow(2, i);
if (sh == '0') {
j++;
} else {
j = '0';
}
i++;
}
if (i == 7) {
th = count;
File1.put(th);
i = 0;
count = 0;
}
if (sh == EOF) {
th = count;
File1.put(th);
File1.put(j);
i = 0;
count = 0;
}
}
File1.close();
File2.close();
remove(namef1);
cout << "文件压缩完毕！" << endl;
}
int FileDecompression() {//文件解压缩
//保存编码
fstream output;
fstream input;
char namef2[max2];
char namef1[] = {"temp.txt"};
cout << "请输入待解压缩的文件名：" << endl;
cin >> namef2;
input.open(namef2, ios::in | ios::binary);
output.open(namef1, ios::out | ios::binary);
if (input.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
char ch;
input.read(reinterpret_cast (&ch), sizeof (ch));
char sh;
char th = ch;
input.read(reinterpret_cast (&ch), sizeof (ch));
int count;
char num;
char t = '0';
char p = '1';
while (!input.eof()) {
sh = th;
th = ch;
input.read(reinterpret_cast (&ch), sizeof (ch));
count = sh;
if (ch != EOF) {
for (int i = 0; i < 7; i++) {
num = count % 2 + '0';
output.write(reinterpret_cast (&num), sizeof (num));
count = count / 2;
}
}
if (ch == EOF) {
for (int i = 0; i < 7; i++) {
num = count % 2 + '0';
output.write(reinterpret_cast (&num), sizeof (num));
count = count / 2;
if (count == 0) {
break;
}
}
for (int i = 0; i < th - '0'; i++) {
output.write(reinterpret_cast (&t), sizeof (t));
}
}
}
output.close();
input.close();
//解压文件
fstream File1;
fstream File2;
char namef3[max2];
cout << "请输入解压后的文件名：" << endl;
cin >> namef3;
File2.open(namef1, ios::in | ios::binary);
File1.open(namef3);
if (File2.fail()) {
cout << "该文件不存在！" << endl;
return 0;
}
cout << "解压后的文件内容为：" << endl;
File2.read(reinterpret_cast (&ch), sizeof (ch));
int c = 2 * L.n - 2;
while (!File2.eof()) {
if (ch == '0') {
if (HuffmanT[c].lchild >= 0) {
c = HuffmanT[c].lchild;
}
if (HuffmanT[c].lchild == -1) {
cout << HuffmanT[c].name;
File1.write(reinterpret_cast (&HuffmanT[c].name), sizeof (HuffmanT[c].name));
c = 2 * L.n - 2;
}
}
if (ch == '1') {
if (HuffmanT[c].rchild >= 0) {
c = HuffmanT[c].rchild;
}
if (HuffmanT[c].rchild == -1) {
cout << HuffmanT[c].name;
File1.write(reinterpret_cast (&HuffmanT[c].name), sizeof (HuffmanT[c].name));
c = 2 * L.n - 2;
}
}
File2.read(reinterpret_cast (&ch), sizeof (ch));
}
cout << endl;
File2.close();
File1.close();
remove(namef1);
cout << "解压完毕！" << endl;
}
};
#endif
/* HUFFMANFUNCTION_H */
======================================================================
/*
* File: main.cpp
* Author: Administrator
*
* Created on 2011年12月13日, 上午9:09
*/
#include
#include "HUFFMANFUNCTION.h"
using namespace std;
/*
*
*/
int main(int argc, char** argv)
{
Function *a = new Function;
while (1)
{//主界面显示
cout << endl << endl << endl;
cout << "<<==================功 能 选 择===============>>" << endl;
cout << " 【1】读取文章并对字符编码 " << endl;
cout << " 【2】哈夫曼编码信息 " << endl;
cout << " 【3】文章编码 " << endl;
cout << " 【4】文章译码 " << endl;
cout << " 【5】压缩文件 " << endl;
cout << " 【6】解压缩文件 " << endl;
cout << " 【7】退出程序 " << endl;
cout << "=========================================================" << endl << endl;
char ch;
cout << "====>>请选择功能： ";
cin >> ch;
switch (ch)
{
case '1'://读取文章并对字符编码
{
delete a;
a = new Function;
system("cls");
a->CreatHT();
a->CharHuffmanTCoding();
cout << "操作完毕！" << endl;
system("pause");
system("cls");
break;
}
case '2'://哈夫曼编码信息
{
system("cls");
a->OutputHuffmanTCode();
system("pause");
system("cls");
break;
}
case '3'://文章编码
{
system("cls");
while (1)
{
cout << endl;
cout << "========>>1.显示文章编码" << endl;
cout << "========>>2.保存文章编码" << endl;
cout << "========>>3.返回上一界面" << endl;
char ch1;
cout << endl << "===>>请选择功能：";
cin >> ch1;
switch (ch1)
{
case '1'://显示文章编码
{
system("cls");
a->OutArticleCode();
system("pause");
system("cls");
continue;
}
case '2'://保存文章编码
{
system("cls");
a->SaveArticleCode();
system("pause");
system("cls");
continue;
}
case '3'://返回上一界面
{
break;
}
default:
{
system("cls");
cout << "输入错误，请重新输入！" << endl;
continue;
}
}
system("cls");
break;
}
break;
}
case '4'://文章译码
{
system("cls");
while (1)
{
cout << endl;
cout << "========>>1.显示文章编码的译码" << endl;
cout << "========>>2.保存文章编码的译码" << endl;
cout << "========>>3.返回上一界面" << endl;
char ch1;
cout << endl << "===>>请选择功能：";
cin >> ch1;
switch (ch1)
{
case '1'://显示文章编码的译码
{
system("cls");
a->OutTransCode();
system("pause");
system("cls");
continue;
}
case '2'://保存文章编码的译码
{
system("cls");
a->SaveTransCode();
system("pause");
system("cls");
continue;
}
case '3'://返回上一界面
{
break;
}
default:
{
system("cls");
cout << "输入错误，请重新输入！" << endl;
continue;
}
}
system("cls");
break;
}
break;
}
case '5':
{
delete a;
a = new Function;
system("cls");
a->FileCompression();
system("pause");
system("cls");
continue;
}
case '6':
{
system("cls");
a->FileDecompression();
system("pause");
system("cls");
continue;
}
case '7':
{
return 0;
}
default:
{
system("cls");
cout << "功能选择错误，请重新输入！" << endl;
break;
}
}
}
return 0;
}
浙公网安备 33021202002483