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

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>
  13. #define MAXBIT      100
  14. #define MAXVALUE  10000
  15. #define MAXLEAF     30
  16. #define MAXNODE    MAXLEAF*2 -1
  18. typedef struct
  19. {
  20.     int bit[MAXBIT];
  21.     int start;
  22. } HCodeType;        /* 编码结构体 */
  23. typedef struct
  24. {
  25.     int weight;
  26.     int parent;
  27.     int lchild;
  28.     int rchild;
  29. } HNodeType;        /* 结点结构体 */
  31.                     /* 构造一颗哈夫曼树 */
  32. void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
  33. {
  34.     /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
  35.     x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
  36.     int i, j, m1, m2, x1, x2;
  37.     /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
  38.     for (i = 0; i<2 * n - 1; i++)
  39.     {
  40.         HuffNode[i].weight = 0;
  41.         HuffNode[i].parent = -1;
  42.         HuffNode[i].lchild = -1;
  43.         HuffNode[i].lchild = -1;
  44.     } /* end for */
  46.       /* 输入 n 个叶子结点的权值 */
  47.     for (i = 0; i<n; i++)
  48.     {
  49.         printf("Please input weight of leaf node %d: \n", i);
  50.         scanf("%d", &HuffNode[i].weight);
  51.     } /* end for */
  53.       /* 循环构造 Huffman 树 */
  54.     for (i = 0; i<n - 1; i++)
  55.     {
  56.         m1 = m2 = MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
  57.         x1 = x2 = 0;
  58.         /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
  59.         for (j = 0; j<n + i; j++)
  60.         {
  61.             if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)
  62.             {
  63.                 m2 = m1;
  64.                 x2 = x1;
  65.                 m1 = HuffNode[j].weight;
  66.                 x1 = j;
  67.             }
  68.             else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
  69.             {
  70.                 m2 = HuffNode[j].weight;
  71.                 x2 = j;
  72.             }
  73.         } /* end for */
  74.           /* 设置找到的两个子结点 x1、x2 的父结点信息 */
  75.         HuffNode[x1].parent = n + i;
  76.         HuffNode[x2].parent = n + i;
  77.         HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
  78.         HuffNode[n + i].lchild = x1;
  79.         HuffNode[n + i].rchild = x2;
  81.         printf("x1.weight and x2.weight in round %d: %d, %d\n", i + 1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
  82.         printf("\n");
  83.     } /* end for */
  84. } /* end HuffmanTree */
  86. int main(void)
  87. {
  88.     HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
  89.     HCodeType HuffCode[MAXLEAF], cd;       /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
  90.     int i, j, c, p, n;
  91.     printf("Please input n:\n");
  92.     scanf("%d", &n);
  93.     HuffmanTree(HuffNode, n);
  95.     for (i = 0; i < n; i++)
  96.     {
  97.         cd.start = n - 1;
  98.         c = i;
  99.         p = HuffNode[c].parent;
  100.         while (p != -1)   /* 父结点存在 */
  101.         {
  102.             if (HuffNode[p].lchild == c)
  103.                 cd.bit[cd.start] = 0;
  104.             else
  105.                 cd.bit[cd.start] = 1;
  106.             cd.start--;        /* 求编码的低一位 */
  107.             c = p;
  108.             p = HuffNode[c].parent;    /* 设置下一循环条件 */
  109.         } /* end while */
  111.           /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
  112.         for (j = cd.start + 1; j<n; j++)
  113.         {
  114.             HuffCode[i].bit[j] = cd.bit[j];
  115.         }
  116.         HuffCode[i].start = cd.start;
  117.     } /* end for */
  119.       /* 输出已保存好的所有存在编码的哈夫曼编码 */
  120.     for (i = 0; i<n; i++)
  121.     {
  122.         printf("%d 's Huffman code is: ", i);
  123.         for (j = HuffCode[i].start + 1; j < n; j++)
  124.         {
  125.             printf("%d", HuffCode[i].bit[j]);
  126.         }
  127.         printf("\n");
  128.     }
  129.     _getch();
  130.     return 0;
  131. }

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

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

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

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