数据结构实验2(设计哈弗曼编码和译码系统)
最后更新于：2022-04-01 20:51:35
设计一个哈弗曼编码和译码系统, 要求如下:
B——建树：读入字符集和各字符频度，建立哈夫曼树。
T——遍历：先序和中序遍历二叉树。
E——生成编码：根据已建成的哈夫曼树，产生各个字符的哈夫曼编码。
C——编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。
D——译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt。
P——打印：屏幕显示文件textfile.txt，codefile.txt，result.txt。
X——退出。
提示: 修改教材中二叉树结点类BTNode, 增加一个指向双亲的parent域, 修改二叉树类的函数MakeTree设置该域的值. 通过遍历哈夫曼树, 产生每个叶子结点的哈夫曼编码. 当遍历访问某个叶节点时, 从该叶结点到根的路径可以确定该叶结点所代表的字符的编码.
忘记初始化debug了一晚上, 顺便复习文件操作. 代码用到了优先队列类以及二叉树类.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "cassert"
#include "fstream"
using namespace std;
template
class PrioQueue
{
public:
PrioQueue(int mSize = 0);
~PrioQueue() { delete []q; }
bool IsEmpty() const { return n == 0; } // 优先队列为空返回true
bool IsFull() const { return n == maxSize; } // 优先队列为满返回true
void Append(const T& x); // 优先队列中添加值为x的元素
void Serve(T& x); // 优先队列中弹出队列中优先权最高的元素, 并赋值给x
private:
void AdjustDown(int r, int j); // 向下调整
void AdjustUp(int j); // 向上调整
void Print();
T* q;
int n, maxSize;
/* data */
};
template
void PrioQueue::Print()
{
for(int i = 0; i < n; ++i)
cout << q[i] << "\t";
cout << endl;
}
template
PrioQueue::PrioQueue(int mSize)
{
maxSize = mSize;
n = 0;
q = new T[maxSize];
}
template
void PrioQueue::AdjustUp(int j)
{
int i = j;
T tmp = q[i];
while(i > 0 && tmp < q[(i - 1) / 2]) {
q[i] = q[(i - 1) / 2];
i = (i - 1) / 2;
}
q[i] = tmp;
}
template
void PrioQueue::Append(const T& x)
{
assert(!IsFull());
q[n++] = x;
AdjustUp(n - 1);
}
template
void PrioQueue::Serve(T& x)
{
x = q[0];
q[0] = q[--n];
AdjustDown(0, n - 1);
}
template
void PrioQueue::AdjustDown(int r, int j)
{
int child = 2 * r + 1;
T tmp = q[r];
while(child <= j) {
if(child < j && q[child] > q[child + 1]) child++;
if(tmp <= q[child]) break;
q[(child - 1) / 2] = q[child];
child = 2 * child + 1;
}
q[(child - 1) / 2] = tmp;
}
template
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T &x, const char &y) {
element = x;
ch = y;
lChild = rChild = parent = NULL;
memset(z, -1, sizeof(z));
}
BTNode(const T& x, const char &y, BTNode* l, BTNode* r) {
element = x;
ch = y;
lChild = l;
rChild = r;
parent = NULL;
memset(z, -1, sizeof(z));
}
T element;
BTNode* lChild, *rChild, *parent;
char ch;
int val, z[100];
};
template
class BinaryTree
{
public:
BinaryTree() { root = NULL; i = -1; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, const char &y, BinaryTree& left, BinaryTree& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree& left, BinaryTree& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
void Create_code(); // 生成编码
void Create_code_out(); // 输出编码
void Code(); // 编码
void Compile(); // 译码
void Print();
BTNode* root;
/* data */
private:
int i;
void Clear(BTNode* t);
int Size(BTNode *t); // 返回二叉树结点个数
int Count(BTNode *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode *t);
void InOrder(void (*Visit)(T &x), BTNode *t);
void PostOrder(void (*Visit)(T &x), BTNode *t);
void Create_code(BTNode *t);
void Create_code_out(BTNode *t);
void Code(BTNode *t);
void Compile(BTNode *t);
void Make(BTNode *t, char a);
};
template
void Visit(T &x)
{
cout << x << '\t';
}
template
BTNode* BinaryTree::Root()
{
return root;
}
template
bool BinaryTree::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template
void BinaryTree::Clear(BTNode* t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template
void BinaryTree::MakeTree(const T& x, const char &y, BinaryTree &left, BinaryTree &right)
{
if(root || &left == &right) return;
root = new BTNode(x, y, left.root, right.root);
if(left.root != right.root) {
left.root -> parent = root;
right.root -> parent = root;
left.root -> val = 0;
right.root -> val = 1;
}
left.root = right.root = NULL;
}
template
void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right)
{
if(!root || &left == &right || left.root || right.root) return;
x = root -> element;
left.root = root -> lChild;
right.root = root -> rChild;
delete root;
root = NULL;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x))
{
cout << "先序遍历为:" << endl;
PreOrder(Visit, root);
cout << endl;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::InOrder(void (*Visit)(T& x))
{
cout << "中序遍历为:" << endl;
InOrder(Visit, root);
cout << endl;
}
template
void BinaryTree::InOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x))
{
cout << "后序遍历为:" << endl;
PostOrder(Visit, root);
cout << endl;
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template
int BinaryTree::Size()
{
return Size(root);
}
template
int BinaryTree::Size(BTNode *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template
int BinaryTree::Count(BTNode *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
template
class HfmTree: public BinaryTree
{
public:
operator T() const{ return weight; }
T getW() { return weight; }
void putW(const T &x) { weight = x; }
void SetNull() { BinaryTree::root = NULL; }
private:
T weight;
};
template
HfmTree CreatHfmTree(T w[], char q[], int n)
{
PrioQueue > pq(n);
HfmTree x, y, z, zero;
for(int i = 0; i < n; ++i) {
z.MakeTree(w[i], q[i], x, y);
z.putW(w[i]);
pq.Append(z);
z.SetNull();
}
for(int i = 1; i < n; ++i) {
pq.Serve(x);
pq.Serve(y);
z.MakeTree(x.getW() + y.getW(), 'e', x, y);
z.putW(x.getW() + y.getW());
pq.Append(z);
z.SetNull();
}
pq.Serve(z);
return z;
}
HfmTree HfmT;
int num;
void Make_HfmT()
{
char s[100];
int w[100];
cout << "请输入字符个数:" << endl;
cin >> num;
cout << "请输入权值:" << endl;
for(int i = 0; i < num; ++i)
cin >> w[i];
cout << "请输入相应字符集:" << endl;
cin >> s;
HfmT = CreatHfmTree(w, s, num);
}
void Traversal_HfmT()
{
HfmT.PreOrder(Visit);
HfmT.InOrder(Visit);
HfmT.PostOrder(Visit);
}
template
void BinaryTree::Create_code()
{
Create_code(root);
}
template
void BinaryTree::Create_code(BTNode *t)
{
if(t) {
if(t -> parent) {
for(int j = 0; j <= i; ++j)
t -> z[j] = t -> parent -> z[j]; // 复制双亲编码域
i++;
t -> z[i] = t -> val; // 编码中加入自己编码
}
Create_code(t -> lChild);
Create_code(t -> rChild);
i--;
}
}
template
void BinaryTree::Create_code_out()
{
Create_code_out(root);
}
template
void BinaryTree::Create_code_out(BTNode *t)
{
if(t) {
if(t -> lChild == t -> rChild) {
cout << t -> ch << ':';
int i = 0;
while(t -> z[i] != -1) {
cout << t -> z[i];
i++;
}
cout << endl;
}
Create_code_out(t -> lChild);
Create_code_out(t -> rChild);
}
}
template
void BinaryTree::Code()
{
Code(root);
}
template
void BinaryTree::Code(BTNode *t)
{
ofstream outt("textfile.txt");
if(!outt) {
cout << "Open textfile.txt failed." << endl;
return ;
}
ofstream outc("codefile.txt", ios::trunc);
if(!outc) {
cout << "Open codefile.txt failed." << endl;
return ;
}
outc.close();
char s[100];
cout << "请输入由字符集组成的任意字符串:" << endl;
cin >> s;
outt << s;
outt.close();
int len = strlen(s);
cout << "编码为:" << endl;
for(int i = 0; i < len; ++i)
Make(root, s[i]);
cout << endl;
}
template
void BinaryTree::Make(BTNode *t, char a)
{
int i = 0;
if(t) {
if(t -> ch == a) {
ofstream outc("codefile.txt", ios::app);
while(t -> z[i] != -1) {
cout << t -> z[i];
outc << t -> z[i];
i++;
}
outc.close();
return ;
}
Make(t -> lChild, a);
Make(t -> rChild, a);
}
}
template
void BinaryTree::Compile()
{
Compile(root);
}
template
void BinaryTree::Compile(BTNode *t)
{
ifstream inf("codefile.txt");
if(!inf) {
cout << "Open codefile.txt failed." << endl;
return;
}
ofstream outs("result.txt",ios::trunc);
if(!outs) {
cout << "Open result.txt failed." << endl;
return;
}
outs.close();
char *re;
char tmp;
int n = 0;
while(inf.get(tmp) != '\0') n++;
inf.close();
re = new char[n+1];
int n2 = 0;
ifstream in("codefile.txt");
if(!in) {
cout<<"Open codefile.txt failed." << endl;
return;
}
while(in.get(tmp) != '\0') re[n2++] = tmp;
BTNode *c;
cout << "译码为 :";
int n3 = 0;
while(n3 < n) {
while(t) {
c = t;
if(re[n3] == '0') // 左0右1根据0或1向左走向右走直到叶子结点
t = t -> lChild;
else
t = t -> rChild;
n3++;
}
ofstream outs("result.txt", ios::app);
if(!outs) {
cout << "Open result.txt failed." << endl;
return;
}
cout << c -> ch;
outs << c -> ch;
outs.close();
t = root;
n3--;
}
cout << endl;
}
void Print()
{
char ch;
ifstream a("textfile.txt");
ifstream b("codefile.txt");
ifstream c("result.txt");
if(!a) {
cout << "Open textfile.txt failed." << endl;
return ;
}
if(!b) {
cout << "Open codefile.txt failed." << endl;
return ;
}
if(!c) {
cout << "Open result.txt failed." << endl;
return ;
}
cout << "textfile.txt内容为:" << endl;
while(a.get(ch) != '\0') cout << ch;
cout << endl;
cout << "codefile.txt内容为:" << endl;
while(b.get(ch) != '\0') cout << ch;
cout << endl;
cout << "result.txt内容为:" << endl;
while(c.get(ch) != '\0') cout << ch;
cout << endl;
a.close();
b.close();
c.close();
}
void Menu()
{
cout << "欢迎使用哈夫曼编码和译码系统" << endl;
cout << "**************" << endl;
cout << "******菜单******" << endl;
cout << "*******B-建树*******" << endl;
cout << "*******T-遍历*******" << endl;
cout << "*****E-生成编码*****" << endl;
cout << "*******C-编码*******" << endl;
cout << "*******D-译码*******" << endl;
cout << "*******P-打印*******" << endl;
cout << "*******X-退出*******" << endl;
cout << "**************" << endl;
}
int main(int argc, char const *argv[])
{
char ch;
Menu();
while(cin >> ch && ch != 'X') {
switch(ch) {
case 'B': {
Make_HfmT();
HfmT.Create_code();
break;
}
case 'T': {
Traversal_HfmT();
break;
}
case 'E': {
cout << "编码为:" << endl;
HfmT.Create_code_out();
break;
}
case 'C': {
HfmT.Code();
break;
}
case 'D': {
HfmT.Compile();
break;
}
case 'P': {
Print();
break;
}
default: {
cout << "输入有误, 请重新输入." << endl;
break;
}
}
Menu();
}
return 0;
}
~~~
';