博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
队列实现霍夫曼树
阅读量:4610 次
发布时间:2019-06-09

本文共 2896 字,大约阅读时间需要 9 分钟。

 
前面一节我们知道了,怎样去创建一个哈夫曼树,这一节我们来看看哈夫曼编码。
 
思想:得到哈夫曼树后,自顶向下按路径编号,指向左节点的边编号0,指向右节点的边编号1,从根到叶节点的所有边上的0和1连接起来,就是叶子节点中字符的哈夫曼编码。
 
下图体现了哈夫曼编码的过程:
 
 
  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.     
  13. }HuffMan;
  14. //队列设计
  15. typedef struct _node_
  16. {
  17.     HuffMan *data;
  18.     struct _node_ *next;
  19. }ListNode;
  20. typedef struct
  21. {
  22.     ListNode *front;
  23.     ListNode *rear;
  24. }Queue;
  25. //create empty queue
  26. Queue *create_empty_queue()
  27. {
  28.     ListNode *HList;
  29.     Queue *Hqueue;
  30.     HList = (ListNode *)malloc(sizeof(ListNode));
  31.     HList->next = NULL;
  32.     
  33.     Hqueue = (Queue *)malloc(sizeof(Queue));
  34.     Hqueue->front = Hqueue->rear = HList;
  35.     return Hqueue;
  36. }
  37. //入队
  38. int EnterQueue(Queue *head,HuffMan *data)
  39. {
  40.     ListNode *temp;
  41.     temp = (ListNode *)malloc(sizeof(ListNode));
  42.     temp->data = data;
  43.     temp->next = NULL;
  44.     head->rear->next = temp;
  45.     head->rear = temp;
  46.     return 0;
  47. }
  48. //有序插入结点
  49. int OrderEnterQueue(Queue *head,HuffMan *p)
  50. {
  51.     ListNode *m = head->front->next;
  52.     ListNode *n = head->front;
  53.     ListNode *temp;
  54.     while(m)
  55.     {
  56.         if(m->data->weight < p->weight)
  57.         {
  58.             m = m->next;
  59.             n = n->next;
  60.         }
  61.         else{
  62.             
  63.             break;
  64.         }
  65.     }
  66.     //插到最后一个结点
  67.     if(m == NULL)
  68.     {
  69.         temp = (ListNode *)malloc(sizeof(ListNode));
  70.         temp->data = p;
  71.         temp->next = NULL;
  72.         n->next = temp;
  73.         head->rear = temp;
  74.         return 0;
  75.     }
  76.     //插入中间结点
  77.     temp = (ListNode *)malloc(sizeof(ListNode));
  78.     temp->data = p;
  79.     n->next = temp;
  80.     temp->next = m;
  81.     return 0;
  82. }
  83. //判断队列是否为空(注意,我们认为队列含有一个结点为空,想想为什么
  84. //这样做?
  85. int _is_empty_queue(Queue *head)
  86. {
  87.     if(head->front->next->next == NULL)
  88.     {
  89.         printf("is_empty_queue\n");
  90.         return 1;
  91.     }
  92.     
  93.     return 0;
  94. }
  95. //判断队列是否为空
  96. int is_empty_queue(Queue *head)
  97. {
  98.     if(head->front == head->rear)
  99.         return 1;
  100.     else
  101.         return 0;
  102. }
  103. //出队
  104. HuffMan *DeleteQueue(Queue * head)
  105. {
  106.     ListNode *temp;
  107.     temp = head->front;
  108.     head->front = temp->next;
  109.     free(temp);
  110.     temp = NULL;
  111.     return head->front->data;
  112. }
  113. //创建哈夫曼树
  114. HuffMan *create_huffman_tree(Queue *head)
  115. {
  116.     HuffMan *right,*left,*current;
  117.     //循环结束时,队列只含有一个结点
  118.     while(!_is_empty_queue(head))
  119.     {
  120.         left = DeleteQueue(head);
  121.         right = DeleteQueue(head);
  122.         current = (HuffMan *)malloc(sizeof(HuffMan));
  123.         current->weight = left->weight + right->weight;
  124.         current->rchild = right;
  125.         current->lchild = left;
  126.         OrderEnterQueue(head,current);    
  127.     }
  128.     return head->front->next->data;
  129. }
  130. //哈夫曼编码
  131. int HuffmanCode(HuffMan *root)
  132. {
  133.     HuffMan *current = NULL;
  134.     Queue *queue = NULL;
  135.     queue = create_empty_queue();
  136.     EnterQueue(queue, root);
  137.     while(!is_empty_queue(queue))
  138.     {
  139.         current = DeleteQueue(queue);
  140.         if(current->rchild == NULL && current->lchild == NULL)
  141.         {
  142.             printf("%c:%d %s\n",current->ch,current->weight,current->code);
  143.         }
  144.         if(current->lchild)
  145.         {
  146.             strcpy(current->lchild->code,current->code);
  147.             strcat(current->lchild->code,"0");
  148.             EnterQueue(queue, current->lchild);
  149.         }
  150.         if(current->rchild)
  151.         {
  152.             strcpy(current->rchild->code,current->code);
  153.             strcat(current->rchild->code,"1");
  154.             EnterQueue(queue, current->rchild);
  155.         }
  156.     }
  157.     return 0;
  158. }
运行结果:
 
 

转载于:https://www.cnblogs.com/xuhj001/p/3409133.html

你可能感兴趣的文章
求两个集合的交集,并集,差集
查看>>
Kotlin的语法糖(一)基础篇
查看>>
OkHttp源码分析
查看>>
让你的app体验更丝滑的11种方法!冲击手机应用榜单Top3指日可待
查看>>
windows kernel exploitation基础教程
查看>>
NS_OPTIONS枚举的用法
查看>>
java9系列(九)Make G1 the Default Garbage Collector
查看>>
QAQ高精度模板笔记√
查看>>
Jmeter计数器的使用-转载
查看>>
【Android笔记】入门篇02:全屏设置和禁止横屏竖屏切换
查看>>
Kubernetes的本质
查看>>
PL/SQL developer 管理多套数据库
查看>>
黑马程序员-分类(category)
查看>>
vue-cli多页面
查看>>
进程和线程
查看>>
iOS Foundation框架简介 -1.常用结构体的用法和输出
查看>>
libevent reference Mannual I
查看>>
eclipse创建Maven父子结构Maven项目
查看>>
Python 太糟糕了?开发者总结了 8 大原因
查看>>
Spring中注入基本类型
查看>>