數據結構實驗2(設計哈弗曼編碼和譯碼系統) · 數據結構學習之路

設計一個哈弗曼編碼和譯碼系統, 要求如下: 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 T> 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 <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; // 判斷是否為空, 是返回true void Clear(); // 移去所有結點, 成為空二叉樹 bool Root(T& x) const; // 若二叉樹為空, 則x為根的值, 返回true BTNode<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; 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; } ~~~