[关闭]
@songpfei 2016-02-20T12:16:16.000000Z 字数 8752 阅读 948

16.3 霍夫曼编码

算法导论


Huffman 编码理论

1. Huffman code C语言实现

  1. /*-----------------------------------------------------------------
  2. * Name: 哈夫曼编码源代码。
  3. * Date: 2011.04.16
  4. * Author: Jeffrey Hill
  5. * 在 Win-TC 下测试通过
  6. * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
  7. * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
  8. * 父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
  9. *----------------------------------------------------------------*/
  10. #include <stdio.h>
  11. #include<conio.h>
  12. #define MAXBIT 100
  13. #define MAXVALUE 10000
  14. #define MAXLEAF 30
  15. #define MAXNODE MAXLEAF*2 -1
  16. typedef struct
  17. {
  18. int bit[MAXBIT];
  19. int start;
  20. } HCodeType; /* 编码结构体 */
  21. typedef struct
  22. {
  23. int weight;
  24. int parent;
  25. int lchild;
  26. int rchild;
  27. } HNodeType; /* 结点结构体 */
  28. /* 构造一颗哈夫曼树 */
  29. void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
  30. {
  31. /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
  32. x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
  33. int i, j, m1, m2, x1, x2;
  34. /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
  35. for (i = 0; i<2 * n - 1; i++)
  36. {
  37. HuffNode[i].weight = 0;
  38. HuffNode[i].parent = -1;
  39. HuffNode[i].lchild = -1;
  40. HuffNode[i].lchild = -1;
  41. } /* end for */
  42. /* 输入 n 个叶子结点的权值 */
  43. for (i = 0; i<n; i++)
  44. {
  45. printf("Please input weight of leaf node %d: \n", i);
  46. scanf("%d", &HuffNode[i].weight);
  47. } /* end for */
  48. /* 循环构造 Huffman 树 */
  49. for (i = 0; i<n - 1; i++)
  50. {
  51. m1 = m2 = MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
  52. x1 = x2 = 0;
  53. /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
  54. for (j = 0; j<n + i; j++)
  55. {
  56. if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)
  57. {
  58. m2 = m1;
  59. x2 = x1;
  60. m1 = HuffNode[j].weight;
  61. x1 = j;
  62. }
  63. else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
  64. {
  65. m2 = HuffNode[j].weight;
  66. x2 = j;
  67. }
  68. } /* end for */
  69. /* 设置找到的两个子结点 x1、x2 的父结点信息 */
  70. HuffNode[x1].parent = n + i;
  71. HuffNode[x2].parent = n + i;
  72. HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
  73. HuffNode[n + i].lchild = x1;
  74. HuffNode[n + i].rchild = x2;
  75. printf("x1.weight and x2.weight in round %d: %d, %d\n", i + 1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */
  76. printf("\n");
  77. } /* end for */
  78. } /* end HuffmanTree */
  79. int main(void)
  80. {
  81. HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
  82. HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
  83. int i, j, c, p, n;
  84. printf("Please input n:\n");
  85. scanf("%d", &n);
  86. HuffmanTree(HuffNode, n);
  87. for (i = 0; i < n; i++)
  88. {
  89. cd.start = n - 1;
  90. c = i;
  91. p = HuffNode[c].parent;
  92. while (p != -1) /* 父结点存在 */
  93. {
  94. if (HuffNode[p].lchild == c)
  95. cd.bit[cd.start] = 0;
  96. else
  97. cd.bit[cd.start] = 1;
  98. cd.start--; /* 求编码的低一位 */
  99. c = p;
  100. p = HuffNode[c].parent; /* 设置下一循环条件 */
  101. } /* end while */
  102. /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
  103. for (j = cd.start + 1; j<n; j++)
  104. {
  105. HuffCode[i].bit[j] = cd.bit[j];
  106. }
  107. HuffCode[i].start = cd.start;
  108. } /* end for */
  109. /* 输出已保存好的所有存在编码的哈夫曼编码 */
  110. for (i = 0; i<n; i++)
  111. {
  112. printf("%d 's Huffman code is: ", i);
  113. for (j = HuffCode[i].start + 1; j < n; j++)
  114. {
  115. printf("%d", HuffCode[i].bit[j]);
  116. }
  117. printf("\n");
  118. }
  119. _getch();
  120. return 0;
  121. }

参考:http://www.cnblogs.com/syblogs/articles/2020145.html

2. huffman 编码实现(优先队列)(需要找时间好好研究)

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. //哈夫曼树结点
  5. typedef struct HuffNode
  6. {
  7. int weight;
  8. char ch;
  9. char code[20];
  10. struct HuffNode *rchild;
  11. struct HuffNode *lchild;
  12. }HuffMan;
  13. //队列设计
  14. typedef struct _node_
  15. {
  16. HuffMan *data;
  17. struct _node_ *next;
  18. }ListNode;
  19. typedef struct
  20. {
  21. ListNode *front;
  22. ListNode *rear;
  23. }Queue;
  24. //create empty queue
  25. Queue *create_empty_queue()
  26. {
  27. ListNode *HList;
  28. Queue *Hqueue;
  29. HList = (ListNode *)malloc(sizeof(ListNode));
  30. HList->next = NULL;
  31. Hqueue = (Queue *)malloc(sizeof(Queue));
  32. Hqueue->front = Hqueue->rear = HList;
  33. return Hqueue;
  34. }
  35. //入队
  36. int EnterQueue(Queue *head,HuffMan *data)
  37. {
  38. ListNode *temp;
  39. temp = (ListNode *)malloc(sizeof(ListNode));
  40. temp->data = data;
  41. temp->next = NULL;
  42. head->rear->next = temp;
  43. head->rear = temp;
  44. return 0;
  45. }
  46. //有序插入结点
  47. int OrderEnterQueue(Queue *head,HuffMan *p)
  48. {
  49. ListNode *m = head->front->next;
  50. ListNode *n = head->front;
  51. ListNode *temp;
  52. while(m)
  53. {
  54. if(m->data->weight < p->weight)
  55. {
  56. m = m->next;
  57. n = n->next;
  58. }
  59. else{
  60. break;
  61. }
  62. }
  63. //插到最后一个结点
  64. if(m == NULL)
  65. {
  66. temp = (ListNode *)malloc(sizeof(ListNode));
  67. temp->data = p;
  68. temp->next = NULL;
  69. n->next = temp;
  70. head->rear = temp;
  71. return 0;
  72. }
  73. //插入中间结点
  74. temp = (ListNode *)malloc(sizeof(ListNode));
  75. temp->data = p;
  76. n->next = temp;
  77. temp->next = m;
  78. return 0;
  79. }
  80. //判断队列是否为空(注意,我们认为队列含有一个结点为空,想想为什么
  81. //这样做?
  82. int _is_empty_queue(Queue *head)
  83. {
  84. if(head->front->next->next == NULL)
  85. {
  86. printf("is_empty_queue\n");
  87. return 1;
  88. }
  89. return 0;
  90. }
  91. //判断队列是否为空
  92. int is_empty_queue(Queue *head)
  93. {
  94. if(head->front == head->rear)
  95. return 1;
  96. else
  97. return 0;
  98. }
  99. //出队
  100. HuffMan *DeleteQueue(Queue * head)
  101. {
  102. ListNode *temp;
  103. temp = head->front;
  104. head->front = temp->next;
  105. free(temp);
  106. temp = NULL;
  107. return head->front->data;
  108. }
  109. //创建哈夫曼树
  110. HuffMan *create_huffman_tree(Queue *head)
  111. {
  112. HuffMan *right,*left,*current;
  113. //循环结束时,队列只含有一个结点
  114. while(!_is_empty_queue(head))
  115. {
  116. left = DeleteQueue(head);
  117. right = DeleteQueue(head);
  118. current = (HuffMan *)malloc(sizeof(HuffMan));
  119. current->weight = left->weight + right->weight;
  120. current->rchild = right;
  121. current->lchild = left;
  122. OrderEnterQueue(head,current);
  123. }
  124. return head->front->next->data;
  125. }
  126. //哈夫曼编码
  127. int HuffmanCode(HuffMan *root)
  128. {
  129. HuffMan *current = NULL;
  130. Queue *queue = NULL;
  131. queue = create_empty_queue();
  132. EnterQueue(queue, root);
  133. while(!is_empty_queue(queue))
  134. {
  135. current = DeleteQueue(queue);
  136. if(current->rchild == NULL && current->lchild == NULL)
  137. {
  138. printf("%c:%d %s\n",current->ch,current->weight,current->code);
  139. }
  140. if(current->lchild)
  141. {
  142. strcpy(current->lchild->code,current->code);
  143. strcat(current->lchild->code,"0");
  144. EnterQueue(queue, current->lchild);
  145. }
  146. if(current->rchild)
  147. {
  148. strcpy(current->rchild->code,current->code);
  149. strcat(current->rchild->code,"1");
  150. EnterQueue(queue, current->rchild);
  151. }
  152. }
  153. return 0;
  154. }

参考:http://blog.chinaunix.net/uid-26833883-id-3160434.html

3. huffman 编码实现(基于最小堆的优先队列)

  1. #include<stdlib.h>
  2. #include<stdio.h>
  3. #include<string.h>
  4. struct BinaryTree
  5. {
  6. int freq;//字符频率
  7. char c;//字符
  8. BinaryTree* lchild;
  9. BinaryTree* rchild;
  10. };
  11. typedef struct BinaryTree HuffumanTreeNode;
  12. HuffumanTreeNode* BuildTreeNode(int freq, char c, HuffumanTreeNode* lchild, HuffumanTreeNode* rchild)
  13. {
  14. HuffumanTreeNode* node = (HuffumanTreeNode*)malloc(sizeof(HuffumanTreeNode));
  15. if (node != NULL)
  16. {
  17. node->freq = freq;
  18. node->c = c;
  19. node->lchild = lchild;
  20. node->rchild = rchild;
  21. }
  22. return node;
  23. }
  24. void ClearTree(HuffumanTreeNode *root)
  25. {
  26. if (root == NULL)
  27. return;
  28. if (root->lchild == NULL&&root->rchild == NULL)
  29. return;
  30. if (root->lchild != NULL)
  31. {
  32. ClearTree(root->lchild);
  33. free(root->lchild);
  34. root->lchild = NULL;
  35. }
  36. if (root->rchild != NULL)
  37. {
  38. ClearTree(root->rchild);
  39. free(root->rchild);
  40. root->rchild = NULL;
  41. }
  42. }
  43. typedef struct tagQueen
  44. {
  45. int length;//队列容量
  46. int heapsize;//队列中当前所有元素的个数
  47. HuffumanTreeNode* heap;
  48. }PriorityQueen;//定义一个二叉堆实现的优先队列结构
  49. PriorityQueen* AllocHeap(int n)
  50. {
  51. PriorityQueen *q= (PriorityQueen*)malloc(sizeof(PriorityQueen));
  52. if (q == NULL)
  53. return NULL;
  54. q->length = n;
  55. q->heapsize = 0;
  56. q->heap = (HuffumanTreeNode*)malloc(n*sizeof(HuffumanTreeNode));
  57. if (q->heap == NULL)
  58. {
  59. free(q);
  60. q = NULL;
  61. }
  62. return q;
  63. }
  64. int parent(int i)//父节点下标
  65. {
  66. return (i - 1) / 2;
  67. }
  68. int left(int i)//左孩子下标
  69. {
  70. return 2 * i + 1;
  71. }
  72. int right(int i)//右孩子下标
  73. {
  74. return 2 * i + 2;
  75. }
  76. void swap(HuffumanTreeNode* x, HuffumanTreeNode* y)
  77. {
  78. HuffumanTreeNode temp = *y;
  79. *y = *x;
  80. *x = temp;
  81. }
  82. /*--------------------------------------------
  83. 最小堆性质维护
  84. i:待维护节点
  85. heapsize:堆元素个数
  86. ----------------------------------------------*/
  87. void heapify(HuffumanTreeNode* e,int i,int heapsize)
  88. {
  89. int l, r, most;
  90. l = left(i);
  91. r = right(i);
  92. if (l<heapsize && (e + l)->freq<(e + i)->freq)//left<i
  93. most = l;
  94. else
  95. most = i;
  96. if (r<heapsize && (e + r)->freq<(e + most)->freq)//right<most
  97. most = r;
  98. if (most != i)//i不是最小结点,交换元素位置,使其满足最小堆的性质
  99. {
  100. swap(e + i, e + most);
  101. heapify(e, most, heapsize);//递归检测
  102. }
  103. }
  104. /*----------------------------------------------------
  105. 入队操作,按最小堆实现
  106. ------------------------------------------------------*/
  107. void enQueen(PriorityQueen *q,HuffumanTreeNode* e)
  108. {
  109. if (q == NULL || e == NULL)
  110. return;
  111. if (q->length == q->heapsize)//队列已满
  112. return;
  113. int i = q->heapsize++;//堆扩大后最后元素的下标
  114. *(q->heap + i) = *e;//复制树节点到队列中
  115. while (i > 0 && (q->heap + i)->freq <(q->heap + parent(i))->freq)//heap[i]<parent(i),其小于父节点
  116. {
  117. swap((q->heap + i), (q->heap + parent(i)));//交换元素,维护堆的性质
  118. i = parent(i);
  119. }
  120. }
  121. /*----------------------------------------------------
  122. 出队操作
  123. ------------------------------------------------------*/
  124. HuffumanTreeNode* deQueen(PriorityQueen* q)
  125. {
  126. if (q == NULL || q->heapsize == 0)//队列不存在或为空
  127. return NULL;
  128. HuffumanTreeNode* top_node = (HuffumanTreeNode*)malloc(sizeof(HuffumanTreeNode));
  129. *top_node = *(q->heap);
  130. q->heapsize--;//删除堆中一个元素
  131. *(q->heap) = *(q->heap + q->heapsize);//heap[0]=heap[heapsize]
  132. heapify(q->heap,0,q->heapsize);//堆性质维护
  133. return top_node;
  134. }
  135. bool isQueenEmpty(PriorityQueen* q)
  136. {
  137. if (q == NULL)
  138. return 1;
  139. else
  140. return q->heapsize < 1;
  141. }
  142. void PriorityQueenClear(PriorityQueen* q)
  143. {
  144. if (q == NULL)
  145. return;
  146. free(q->heap);
  147. q->heap = NULL;
  148. q->length = q->heapsize = 0;
  149. }
  150. HuffumanTreeNode* huffuman(int*f, char*d, int n)
  151. {
  152. HuffumanTreeNode* min1, *min2, *e;
  153. PriorityQueen* q = AllocHeap(n);//创建队列
  154. for (int i = 0; i < n; i++)
  155. {
  156. e = BuildTreeNode(f[i], d[i], NULL, NULL);
  157. enQueen(q, e);
  158. }
  159. for (int i = 0; i < n - 1;i++)
  160. {
  161. min1 = deQueen(q);
  162. min2 = deQueen(q);
  163. e = BuildTreeNode(min1->freq + min2->freq, '*', min1, min2);
  164. enQueen(q, e);
  165. }
  166. e = deQueen(q);//返回huffumanTree根结点
  167. PriorityQueenClear(q);
  168. return e;
  169. }
  170. void PrintHuffumanCode(HuffumanTreeNode* root,char* c)
  171. {
  172. if (root == NULL || c == NULL)
  173. return;
  174. int l = strlen(c);
  175. char* c1 = (char*)malloc((l + 2)*sizeof(char));
  176. if (root->lchild != NULL)//向左搜索
  177. {
  178. strcpy_s(c1, sizeof(c1), c);
  179. strcat_s(c1, strlen(c1) + 2, "0");
  180. PrintHuffumanCode(root->lchild, c1);
  181. }
  182. if (root->rchild != NULL)
  183. {
  184. strcpy_s(c1, sizeof(c1), c);
  185. strcat_s(c1, strlen(c1) + 2, "1");
  186. PrintHuffumanCode(root->rchild, c1);
  187. }
  188. if (root->lchild == NULL&&root->rchild == NULL)//打印叶子节点
  189. printf("character:%c frequency: %d code: %s\n", root->c, root->freq, c);
  190. }
  191. int main(int argc, char** argv)
  192. {
  193. int f[] = { 45, 13, 12, 16, 9, 5 };
  194. char d[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
  195. BinaryTree* h = huffuman(f, d, 6);
  196. PrintHuffumanCode(h, "");
  197. ClearTree(h);
  198. h = NULL;
  199. system("pause");
  200. return (EXIT_SUCCESS);
  201. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注