哈弗曼编码C++程序.docx

#include #include #include #includeusing namespace std;int ii=0;char a1200;int n1=0;int nn200;int mm200; int n,nn1; /输入字符串的长度class Huffmanpublic: char elementChar;/节点元素 int weight;/权重 char s;/哈夫曼编码 Huffman* parent;/父节点 Huffman* leftChild;/左孩子 Huffman* rightChild;/右孩子void Display(); /显示压缩效果 Huffman(); Huffman(char a, int weight); bool operator (const Huffman &m)const return weight m.weight;hh;Huffman:Huffman()parent = leftChild = rightChild = NULL;void Huffman:Display()coutendl;double c;int num=0;for(int i=0;i200;i+)num=num+nni*mmi; c=100*(8*n-num)/(8*n); cout编码前字符串的长度是8*nendl; cout编码后字符串的长度是numendl; cout压缩比为c%endl;int huffmanCode(Huffman & h) /递归输出哈夫曼值 if(h.leftChild = NULL & h.rightChild = NULL) /如果是叶子节点，输出器哈夫曼编码 string ss; Huffman temp = h; while(temp.parent != NULL) nnn1=nnn1+1; ss = temp.s+ss; temp = *temp.parent; mmn1=h.weight; n1+; cout h.elementChar 的哈夫曼编码是： ss endl; return 0; /左孩子 huffmanCode(*h.leftChild); /右孩子 huffmanCode(*h.rightChild);void Decode(Huffman & h) /解码Huffman temp = h;int i;for(i=0;inn1+1;i+)if(temp.leftChild!= NULL)if(a1i=0)temp= *temp.leftChild;else if(a1i=1)temp = *temp.rightChild;elsecouttemp.elementChar;temp=hh;i-;void main()cout 请输入需要编码的字符串： endl;char a200;for(int z=0;z200;z+)az=NULL;cin.getline(a,200);coutendl;int xx=0;for(int yy=0;yy200;yy+)if(ayy!=NULL)xx+;string huffmanStr;char y;for(int x=0;xxx;x+)y=ax;huffmanStr=huffmanStr+y;n=huffmanStr.length(); Huffman huffmanTemp; vector huffmanQueue; /得到字符串信息 char cha100; /数组cha记录所有输入字符的种类 int i=0,j,m100,h,k=0; /数组m记录各种输入字符的频度，和cha对应 for(i=0; i n; i+) j = 0; h = 0; while(huffmanStri != huffmanStrj) j+; if(j = i) chak = huffmanStri; cout 字符 chak 出现; else /如果j !=i 则略过此次循环 continue; for(j = i; j n; j+) if(huffmanStri = huffmanStrj) h+; cout h 次 endl; mk = h; k+; /初始化队列 for(i = 0; i k; i+) huffmanTemp.elementChar = chai; huffmanTemp.weight = mi; huffmanQueue.push_back(huffmanTemp); /得到哈夫曼树所有结点 int huffmanQueue_index = 0; sort(huffmanQueue.begin(), huffmanQueue.end(); while(huffmanQueue.size() 2 * k - 1) /合成最小两个节点的父结点 huffmanTemp.weight = huffmanQueuehuffmanQueue_index.weight + huffmanQueuehuffmanQueue_index + 1.weight; huffmanQueuehuffmanQueue_index.s = 0; huffmanQueuehuffmanQueue_index + 1.s = 1; huffmanTemp.elementChar = *; /新生成的父结点的标志 huffmanQueue.push_back(huffmanTemp);/将父结点加入队列 sort(huffmanQueue.begin(), huffmanQueue.end(); huffmanQueue_index += 2; /构造哈夫曼树 int step = 0; while(step 2 * k-2) for(int j = step + 1; j = huffmanQueue.size(); j+) if(huffmanQueuej.elementChar = * & huffmanQueuej.leftChild = NULL & (huffmanQueuej.weight = huffmanQueuestep.weight + huffmanQueuestep+1.weight) huffmanQueuej.leftChild = &huffmanQueuestep; huffmanQueuej.rightChild = &huffmanQueuestep+1; huffmanQueuestep.parent = huffmanQueuestep+1.parent = &huffmanQueuej; break; step += 2; huffmanTemp = huffmanQueue.back(); /哈弗曼树的根 hh=huffmanTemp; coutendl; huffmanCode(huffmanTemp);/huffmanTemp.Display(); coutendl;for(z=0;z200;z+)a1z=NULL;cout 请输入需要解码的字符串： endl