優先キュー解Huffman符号化c++
14181 ワード
priority_queue ,T ,Container ,,Compare , Container , vector,deque, list.STL vector. operator< , , 。 , 。STL greater<Type>, 。 (DanielWang_).
Huffman , , . , , .
typedef struct HTNode{ char c; unsigned int freq; HTNode *lchild, *rchild; // HTNode(char key='\0', unsigned int fr=0, HTNode *l=NULL, HTNode *r=NULL): c(key),freq(fr),lchild(l),rchild(r){}; }HTNode,*pNode; // struct cmp{ bool operator()(pNode node1, pNode node2){ return node1->freq > node2->freq; } }; // priority_queue<pNode, vector<pNode>, cmp> pq;
2. 具体实现代码
Huffman , string ,erase, . end() string , .
str.erase(str.end()-1); //
************************************************************************* > File Name: Huffman_code_pg.cpp > Author: He Xingjie > Mail: gxmshxj@163.com > Created Time: 2014 06 06 08 57 01 > Description: ************************************************************************/ #include<iostream> #include<queue> #include<vector> #include<cstdio> #include<stack> using namespace std; typedef struct HTNode{ char c; unsigned int freq; HTNode *lchild, *rchild; // HTNode(char key='\0', unsigned int fr=0, HTNode *l=NULL, HTNode *r=NULL): c(key),freq(fr),lchild(l),rchild(r){}; }HTNode,*pNode; // struct cmp{ bool operator()(pNode node1, pNode node2){ return node1->freq > node2->freq; } }; // priority_queue<pNode, vector<pNode>, cmp> pq; void HuffmanCode(int n) { pNode l, r; // , , // while (pq.size() > 1) { pNode z = new HTNode; l = pq.top(); pq.pop(); r = pq.top(); pq.pop(); z->lchild = l; z->rchild = r; z->freq = l->freq + r->freq; pq.push(z); } } void PrintCode(pNode t, string str) { // HuffmanTree HuffmanCode if (t == NULL) return; if (t->lchild) { str += '0'; PrintCode(t->lchild, str); } // if (t->lchild == NULL && t->rchild == NULL) { cout<<t->c<<"'s code: "<<str<<endl; } str.erase(str.end()-1); // if (t->rchild) { str += '1'; PrintCode(t->rchild, str); } } void DFS(HTNode *t) { HTNode *node; stack<pNode, vector<pNode> > pstack; pstack.push(t); node = pstack.top(); pstack.pop(); while (pstack.size() > 0) { if (node->lchild) { pstack.push(node->lchild); node = node->lchild; } else if(node->rchild) { pstack.push(node->rchild); node = node->rchild; } else { printf("%d ", node->freq); node = pstack.top(); pstack.pop(); } } } int main() { int n, i; FILE *fp; char tmp; string str; fp = fopen("in.txt", "r"); if (fp ==NULL) { printf("fopen error!
"); return -1; } // fscanf(fp, "%d", &n); fscanf(fp, "%c", &tmp); // for (i=0; i<n; i++) { char c; int freq; pNode p = new HTNode; fscanf(fp, "%c%d", &c, &freq); p->c = c; p->freq = freq; fscanf(fp, "%c", &tmp); pq.push(p); } HuffmanCode(n); PrintCode(pq.top(), str); return 0; }
参照先:
http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
http://blog.csdn.net/liuzhanchen1987/article/details/7856893
http://blog.csdn.net/daniel_ustc/article/details/17613359