Haffman算法(C++)
Huffman编码,C++实现,只是为了说明大致的思路,还有很多不完美之处,比如在输入数据超出限制等条件下会出现错误。
1 #include<iostream> 2 #include<string> 3 using namespace std; 4 #define MAX 20 5 6 /* 7 ** 用二叉树表示的Huffman节点 8 */ 9 typedef struct NodeTag { 10 char c; // 字母 11 int weight; // 频率 12 string code; // 编码后的字符串 13 struct NodeTag * lchild; // 左孩子 14 struct NodeTag * rchild; // 右孩子 15 } Node; 16 17 18 class Container { 19 20 private: 21 Node *nodes[MAX]; // 保存各节点指针的数组 22 int size; // 节点的个数 23 24 public: 25 Container () { 26 size = 0; 27 for ( int i = 0; i < MAX; i++ ) { 28 nodes[i] = NULL; 29 } 30 } 31 32 /* 33 ** 采用插入排序的方法,将节点node加入到数组nodes中,按照weight从小到大排列 34 */ 35 void push ( Node *node ) { 36 int weight = node->weight; 37 int i = size-1; 38 while ( i >= 0 && weight > nodes[i]->weight ) { 39 nodes[i+1] = nodes[i]; 40 i--; 41 } 42 nodes[i+1] = node; 43 size++; 44 } 45 46 /* 47 ** 返回weight值最小的一个节点 48 */ 49 Node * pop () { 50 Node *node = nodes[size-1]; 51 size--; 52 return node; 53 } 54 55 /* 56 ** 返回当前的节点数目 57 */ 58 int getSize() { 59 return size; 60 } 61 62 }; 63 64 /* 65 ** 对所有的叶子节点进行编码,得到各字母的码表 66 ** root:指向根节点的指针;code:本节点的编码 67 */ 68 int huffmanCode( Node *root, const string code ) { 69 70 root->code = code; 71 string temp; 72 73 if( root != NULL ){ 74 75 // 叶子节点,则输出编码方式 76 if( root->rchild == NULL && root->lchild == NULL ) { 77 cout<<root->c<<":"<<root->weight<<" "<<root->code<<endl; 78 } else { 79 temp = code; 80 huffmanCode ( root->lchild, temp.append("0") ); // 会增加上去,不用重新赋值 81 temp = code; 82 huffmanCode ( root->rchild, temp.append("1") ); 83 } 84 85 } 86 87 return 0; 88 89 } 90 91 /* 92 ** Huffman编码的函数 93 ** letter:字母表;weight:各字母的频率;length:字母的总个数 94 */ 95 void haffman ( char letter[], int weight[], int length ) { 96 97 Node *node = NULL; 98 Node *first = NULL; 99 Node *second = NULL; 100 Container *obj = NULL; 101 102 obj = new Container(); 103 104 for ( int i = 0; i < length; i++ ) { 105 /* 106 ** 创建一个新节点node,节点字符为c[i],频率为weight[i],左右孩子都为Null; 107 ** 将node按从小到大的顺序加入到容器obj中; 108 */ 109 node = new Node(); 110 node->c = letter[i]; 111 node->weight = weight[i]; 112 node->lchild = NULL; 113 node->rchild = NULL; 114 obj->push(node); 115 } 116 117 cout<<"All nodes are pushed into the queue:"<<obj->getSize()<<endl; 118 119 /* 120 ** 当容器中只有一个元素时,该元素即为指向Huffman编码二叉树的根节点的指针 121 */ 122 while ( obj->getSize() > 1 ) { 123 /* 124 ** 选出最小的两个元素,创建一个新的父节点,频率为两者之和,将父节点加入到队列中; 125 */ 126 first = obj->pop(); 127 second = obj->pop(); 128 node = new Node(); 129 node->weight = first->weight + second->weight; // 非根节点的字母不重要,故不用赋值 130 node->lchild = first; 131 node->rchild = second; 132 obj->push(node); 133 } 134 135 cout<<"After the Haffman code:"<<obj->getSize()<<endl; 136 137 /* 138 ** 采用中根次序遍历方法对二叉树进行遍历,得到每个叶子节点的编码 139 */ 140 node = obj->pop(); 141 cout<<node->weight<<endl; 142 huffmanCode( node, ""); 143 144 } 145 146 int main () { 147 char letter[] = {‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘, ‘f‘, ‘g‘, ‘h‘}; 148 int weight[] = {1, 1, 2, 3, 5, 8, 13, 21}; 149 int length = 8; 150 haffman( letter, weight, length ); 151 return 0; 152 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。