南邮哈夫曼编码和译码系统

1、实验题二：哈夫曼编码和译码系统（1）所设计的系统重复显示以下菜单项：B建树：读入字符集和各字符频度，建立哈夫曼树。T遍历：先序和中序遍历二叉树。E生成编码：根据已建成的哈夫曼树，产生各字符的哈夫曼编码。C编码：输入由字符集中字符组成的任意字符串，利用已生成的哈夫曼编码进行编码，显示编码结果，并将输入的字符串及其编码结果分别保存在磁盘文件textfile.txt和codefile.txt中。D译码：读入codefile.txt，利用已建成的哈夫曼树进行译码，并将译码结果存入磁盘文件result.txt中。P打印：屏幕显示文件textfile.txt、codefile.txt和result.txt

2、。X退出。源代码#include #include #include #include #include using namespace std;int *weightArray;string s;string *codeArray;template struct BTNode T element;BTNode *lChild, *rChild; BTNode( lChild = rChild = NULL; BTNode(const T& x element = x;lChild = rChild = NULL; BTNode(const T& x, BTNode * l,

3、BTNode * r element = x;lChild = l;rChild = r;实 验 报 告template class BinaryTree public:BinaryTree( root = NULL;BinaryTree( bool isEmpty( const return root = NULL;void clear( postClear(root;bool retRoot(T& x const;void makeTree(const& x, BinaryTree & left, BinaryTree & right; void break

4、Tree(T& x, BinaryTree & left, BinaryTree & right; void preOrder( preOrder(root;void inOrder( inOrder(root;void postOrder( postOrder(root;BTNode * copy(BTNode *t; int size( return size(root;void change( change(root;void breathFirst( breathFirst(root;int height( return height(root;void lea

5、f( prePrint(root;实 验 报 告protected:BTNode * root; private:void clear(BTNode * t; void change(BTNode * t; void postClear(BTNode * t; void prePrint(BTNode * t; int size(BTNode * t; int height(BTNode * t; void preOrder(BTNode * t; void inOrder(BTNode * t; void postOrder(BTNode * t; void breathFirst(BTNo

6、de * t; void visit(T& x cout << x << " "template bool BinaryTree :retRoot(T& x const if (root x = root -> element;return true;else return false;template void BinaryTree :makeTree(const& x, BinaryTree & left, BinaryTree & right if (root | &left = &

7、right return;root = new BTNode (x, left.root, right.root; 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;

8、right.root = root -> rChild;delete root;root = NULL;实 验 报 告template void BinaryTree :preOrder(BTNode * t if (t visit(t -> element;preOrder(t -> lChild;preOrder(t -> rChild;template void BinaryTree :inOrder(BTNode * t if (t inOrder(t -> lChild;visit(t -> element;inOrder(t -> rChi

9、ld;template void BinaryTree :postOrder(BTNode * t if (t postOrder(t -> lChild;postOrder(t -> rChild;visit(t -> element;template void BinaryTree :clear(BTNode * t delete t;t = NULL;template void BinaryTree :postClear(BTNode * t if (t postClear(t -> lChild;postClear(t -> rChild;delete t

10、;实 验 报 告template BTNode * BinaryTree :copy(BTNode *t if (!t return NULL;BTNode * q = new BTNode (t ->element; q -> lChild = copy(t -> lChild;q -> rChild = copy(t -> rChild;return q;template int BinaryTree :size(BTNode * t if (!t return 0;else return size(t -> lChild + size(t ->

11、rChild;template void BinaryTree :change(BTNode * t if (!t return;BTNode *q = copy(t -> rChild; clear(t -> rChild;t -> rChild = t -> lChild;t -> lChild = q;change(t -> lChild;change(t -> rChild;template void BinaryTree :breathFirst(BTNode * t if (!t return;queue *> q1; q1.push

12、(t;BTNode *node; while (!q1.empty( node = q1.front(;visit(node -> element;q1.pop(;if (node -> lChild q1.push(node -> lChild;if (node-> rChild q1.push(node -> rChild;template int BinaryTree :height(BTNode * t 实 验 报 告 if(t = NULL return 0; else int m = height( t -> lChild ; int n = h

13、eight(t -> rChild; return (m > n ? (m + 1 : (n + 1; template void BinaryTree :prePrint(BTNode * t if (t if (t -> lChild = NULL && (t -> rChild = NULL visit(t -> element;return;prePrint(t -> lChild;prePrint(t -> rChild;template class PrioQueue public:PrioQueue(int mSize=2

14、0;PrioQueue(delete q;bool IsEmpty( constreturn n=0;bool IsFull( constreturn n=maxSize;void Append(const T &x;void Serve(T& x;private:void AdjustDown (int r, int j;void AdjustUp (int j;T* q;int n,maxSize;template PrioQueue :PrioQueue(int mSize maxSize=mSize;n=0;实 验 报 告q=new TmaxSize;template

15、void PrioQueue :AdjustUp (int j int i=j;T temp=qi;while (i>0 && temp qi=q(i-1/2; i=(i-1/2;qi=temp;template void PrioQueue :Append(const T &x if(IsFull( cout<< "Overflow"return;qn+=x;AdjustUp(n-1;template void PrioQueue :Serve(T& x if(IsEmpty(cout<< "Unde

16、rflow"return;x=q0;q0=q-n;AdjustDown (0, n-1;template void PrioQueue :AdjustDown (int r, int j int child = 2 * r + 1;T temp = qr;while (child <= j if (child < j && (qchild > qchild + 1 child+;if (temp <= qchild break;q(child - 1 / 2 = qchild;child = 2 * child + 1;实 验 报 告q(chi

17、ld - 1 / 2 = temp;template class HfmTree: public BinaryTree public:operator T(const return weight;T getW(return weight;void putW(const T& x weight=x; void SetNull(root=NULL; void code(string& c code(root, c;void decode(string s;private:T weight;void code(BTNode * t, string& c; ;template

18、void HfmTree :decode(string decodeString if (codeArray = NULL cout << "尚未编码！" << endl;return;BTNode * searchNode = root; for (int i = 0; i < decodeString.length(; i+ if (decodeStringi != '0' && decodeStringi != '1' cout << "所给码格式不正确！"

19、<< endl;return;if (searchNode -> lChild = NULL && searchNode -> rChild = NULL T value = searchNode -> element;for (int j = 0; j < s.length(; j+ if (value = weightArrayj cout << sj;break;实 验 报 告searchNode = root;if (decodeStringi = '0' searchNode = searchNode -

20、> lChild;if (decodeStringi = '1' searchNode = searchNode -> rChild;if (searchNode -> lChild = NULL && searchNode -> rChild = NULL T value = searchNode -> element;for (int j = 0; j < s.length(; j+ if (value = weightArrayj cout << sj;break; cout << endl;te

21、mplate void HfmTree :code(BTNode * t, string& c if (t if (t -> lChild = NULL && t -> rChild = NULL for (int i = 0; i < s.length(; i+ if (t -> element = weightArrayi codeArrayi = c;/cout << "NO" << i << " "cout << "字符" <

22、< si << "的权重是" << weightArrayi << ", 哈弗曼编码是" << codeArrayi << endl; break;if (t -> lChild != NULL string ls;ls.assign(c;ls.append("0"code(t -> lChild, ls;if (t -> rChild != NULL 实 验 报 告string rs;rs.assign(c;rs.append("1&quo

23、t;code(t -> rChild, rs;template HfmTree CreateHfmTree (T *w,int n PrioQueue > pq(n; / 空优先权队列HfmTree x,y,z; / 空哈夫曼树for (int i=0;i 构造 n 棵只有一个结点的哈夫曼树 z.makeTree(wi,x,y; z.putW(wi; pq.Append(z; z.SetNull(; for (i=1;i pq.Serve(x; /取出最小权值的哈夫曼树对象xpq.Serve(y; /取出最小权值的哈夫曼树对象y z.makeTree(x.getW(+y.getW(

24、,x,y; z.putW(x.getW(+y.getW(;pq.Append(z; z.SetNull(; pq.Serve(z; return z; void input(HfmTree & p cout << "请输入需要编码的字符组成的字符串: "cin >> s;weightArray = new ints.length(;codeArray = new strings.length(;for (int i = 0; i < s.length(; i+ cout << "请输入第" <<

25、; (i + 1 << "个字符的权值：" << endl;cin >> weightArrayi;p = CreateHfmTree(weightArray, s.length(;/p.postOrder(; 实 验 报 告void createCode(HfmTree & p if (codeArray = NULL cout << "树为空！" << endl;return;string c;p.code(c;void encode( if (codeArray = NULL co

26、ut << "尚未编码！" << endl;return;string encodeString;cout << "请输入需要编码的字符串: "cin >> encodeString;cout << "n经过编码的码值为："for (int i = 0; i < encodeString.length(; i+ for (int j = 0; j < s.length(; j+ if (sj = encodeStringj cout << codeAr

27、rayj;break;cout << endl;void main( bool flag = true;HfmTree p; string decodeString;while (flag cout << "B建树" << " T遍历" << " E生成编码" << endl;cout << "C编码" << " D译码" << " X退出" << endl;cout << "请输入指令："char c;cin >> c;cout << endl;switch (c case 'B':实 验 报 告input(p;break;case 'T'