设计一个哈弗曼编码和译码系统, 要求如下:
B——建树：读入字符集和各字符频度，建立哈夫曼树。
T——遍历：先序和中序遍历二叉树。
E——生成编码：根据已建成的哈夫曼树，产生各个字符的哈夫曼编码。
C——编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。
D——译码：读入codefile.txt，，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt。
P——打印：屏幕显示文件textfile.txt，codefile.txt，result.txt。
X——退出。
子结点的哈夫曼编码. 当遍历访问某个叶节点时, 从该叶结点到根的路径可以确定该叶结点所代表的字符的编码.
忘记初始化debug了一晚上, 顺便复习文件操作. 代码用到了优先队列类以及二叉树类.
实现代码:
#include "iostream"#include "cstdio"#include "cstring"#include "algorithm"#include "cassert"#include "fstream"using namespace std;template <class T>class PrioQueue{public:PrioQueue(int mSize = 0);~PrioQueue() { delete []q; }bool IsEmpty() const { return n == 0; } // 优先队列为空返回truebool IsFull() const { return n == maxSize; } // 优先队列为满返回truevoid Append(const T& x); // 优先队列中添加值为x的元素void Serve(T& x); // 优先队列中弹出队列中优先权最高的元素, 并赋值给xprivate:void AdjustDown(int r, int j); // 向下调整void AdjustUp(int j); // 向上调整void Print();T* q;int n, maxSize;/* data */};template <class T>void PrioQueue<T>::Print(){for(int i = 0; i < n; ++i)cout << q[i] << "\t";cout << endl;}template <class T>PrioQueue<T>::PrioQueue(int mSize){maxSize = mSize;n = 0;q = new T[maxSize];}template <class T>void PrioQueue<T>::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 <class T>void PrioQueue<T>::Append(const T& x){assert(!IsFull());q[n++] = x;AdjustUp(n – 1);}template <class T>void PrioQueue<T>::Serve(T& x){x = q[0];q[0] = q[–n];AdjustDown(0, n – 1);}template <class T>void PrioQueue<T>::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 <class T>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<T>* l, BTNode<T>* r) {element = x;ch = y;lChild = l;rChild = r;parent = NULL;memset(z, -1, sizeof(z));}T element;BTNode<T>* lChild, *rChild, *parent;char ch;int val, z[100];};template <class T>class BinaryTree{public:BinaryTree() { root = NULL; i = -1; }bool IsEmpty() const; // 判断是否为空, 是返回truevoid Clear(); // 移去所有结点, 成为空二叉树bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回trueBTNode<T>* Root();int Size();int Count() { return Count(root); }void MakeTree(const T& x, const char &y, BinaryTree<T>& left, BinaryTree<T>& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树void BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& 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<T>* root;/* data */private:int i;void Clear(BTNode<T>* t);int Size(BTNode<T> *t); // 返回二叉树结点个数int Count(BTNode<T> *t); // 返回二叉树只有一个孩子的结点个数void PreOrder(void (*Visit)(T &x), BTNode<T> *t);void InOrder(void (*Visit)(T &x), BTNode<T> *t);void PostOrder(void (*Visit)(T &x), BTNode<T> *t);void Create_code(BTNode<T> *t);void Create_code_out(BTNode<T> *t);void Code(BTNode<T> *t);void Compile(BTNode<T> *t);void Make(BTNode<T> *t, char a);};template <class T>void Visit(T &x){cout << x << '\t';}template <class T>BTNode<T>* BinaryTree<T>::Root(){return root;}template <class T>bool BinaryTree<T>::Root(T &x) const{if(root) {x = root -> element;return true;}return false;}template <class T>void BinaryTree<T>::Clear(BTNode<T>* t){if(t) {Clear(t -> lChild);Clear(t -> rChild);cout << "delete" << t -> element << "…" << endl;delete t;}}template <class T>void BinaryTree<T>::MakeTree(const T& x, const char &y, BinaryTree<T> &left, BinaryTree<T> &right){if(root || &left == &right) return;root = new BTNode<T>(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 <class T>void BinaryTree<T>::BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& 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 <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x)){cout << "先序遍历为:" << endl;PreOrder(Visit, root);cout << endl;}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x), BTNode<T>* t){if(t) {Visit(t -> element);PreOrder(Visit, t -> lChild);PreOrder(Visit, t -> rChild);}}template <class T>void BinaryTree<T>::InOrder(void (*Visit)(T& x)){cout << "中序遍历为:" << endl;InOrder(Visit, root);cout << endl;}template <class T>void BinaryTree<T>::InOrder(void (*Visit)(T& x), BTNode<T>* t){if(t) {InOrder(Visit, t -> lChild);Visit(t -> element);InOrder(Visit, t -> rChild);}}template <class T>void BinaryTree<T>::PostOrder(void (*Visit)(T& x)){cout << "后序遍历为:" << endl;PostOrder(Visit, root);cout << endl;}template <class T>void BinaryTree<T>::PostOrder(void (*Visit)(T& x), BTNode<T>* t){if(t) {PostOrder(Visit, t -> lChild);PostOrder(Visit, t -> rChild);Visit(t -> element);}}template <class T>int BinaryTree<T>::Size(){return Size(root);}template <class T>int BinaryTree<T>::Size(BTNode<T> *t){if(!t) return 0;return Size(t -> lChild) + Size(t -> rChild) + 1;}template <class T>int BinaryTree<T>::Count(BTNode<T> *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 T>class HfmTree: public BinaryTree<T>{public:operator T() const{ return weight; }T getW() { return weight; }void putW(const T &x) { weight = x; }void SetNull() { BinaryTree<T>::root = NULL; }private:T weight;};template <class T>HfmTree<T> CreatHfmTree(T w[], char q[], int n){PrioQueue<HfmTree<T> > pq(n);HfmTree<T> 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<int> 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 <class T>void BinaryTree<T>::Create_code(){Create_code(root);}template <class T>void BinaryTree<T>::Create_code(BTNode<T> *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 <class T>void BinaryTree<T>::Create_code_out(){Create_code_out(root);}template <class T>void BinaryTree<T>::Create_code_out(BTNode<T> *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 <class T>void BinaryTree<T>::Code(){Code(root);}template <class T>void BinaryTree<T>::Code(BTNode<T> *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 <class T>void BinaryTree<T>::Make(BTNode<T> *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 <class T>void BinaryTree<T>::Compile(){Compile(root);}template<class T>void BinaryTree<T>::Compile(BTNode<T> *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<T> *c;cout << "译码为 :";int n3 = 0;while(n3 < n) {while(t) {c = t;if(re[n3] == '0') // 左0右1根据0或1向左走向右走直到叶子结点t = t -> lChild;elset = 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;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
世界上那些最容易的事情中，拖延时间最不费力。
