文章

如何利用Python和C语言分别实现哈夫曼编码

这篇文章主要介绍“如何利用Python和C语言分别实现哈夫曼编码”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“如何利用Python和C语言分别实现哈夫曼编码”文章能帮助大家解决问

这篇文章主要介绍“如何利用Python和C语言分别实现哈夫曼编码”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“如何利用Python和C语言分别实现哈夫曼编码”文章能帮助大家解决问题。

1.C语言实现

1.1代码说明

a  创建双向链表：

在创建哈夫曼树的过程中，需要不断对结点进行更改和删除，所以选用双向链表的结构更容易

  1. '''C
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <windows.h>
  5.  
  6.  
  7. //哈夫曼树结构体，数据域存储字符及其权重
  8. typedef struct node
  9. {
  10.     char c;
  11.     int weight;
  12.     struct node *lchild, *rchild;
  13. }Huffman, *Tree;
  14.  
  15.  
  16. //双向链表结构体，数据域存储哈夫曼树结点
  17. typedef struct list
  18. {
  19.     Tree root;
  20.     struct list *pre;
  21.     struct list *next;
  22. }List, *pList;
  23.  
  24.  
  25. //创建双向链表，返回头结点指针
  26. pList creatList()
  27. {
  28.     pList head = (pList)malloc(sizeof(List));
  29.  
  30.     pList temp1 = head;
  31.     pList temp2 = (pList)malloc(sizeof(List));
  32.     temp1->pre = NULL;
  33.     temp1->next = temp2;
  34.     temp1->root = (Tree)malloc(sizeof(Huffman));
  35.     temp1->root->c = 'a';
  36.     temp1->root->weight = 22;
  37.     temp1->root->lchild = NULL;
  38.     temp1->root->rchild = NULL;
  39.     
  40.  
  41.     temp2->pre = temp1;
  42.     temp1 = temp2;
  43.     temp2 = (pList)malloc(sizeof(List));
  44.     temp1->next = temp2;
  45.     temp1->root = (Tree)malloc(sizeof(Huffman));
  46.     temp1->root->c = 'b';
  47.     temp1->root->weight = 5;
  48.     temp1->root->lchild = NULL;
  49.     temp1->root->rchild = NULL;
  50.     
  51.  
  52.     temp2->pre = temp1;
  53.     temp1 = temp2;
  54.     temp2 = (pList)malloc(sizeof(List));
  55.     temp1->next = temp2;
  56.     temp1->root = (Tree)malloc(sizeof(Huffman));
  57.     temp1->root->c = 'c';
  58.     temp1->root->weight = 38;
  59.     temp1->root->lchild = NULL;
  60.     temp1->root->rchild = NULL;
  61.  
  62.     temp2->pre = temp1;
  63.     temp1 = temp2;
  64.     temp2 = (pList)malloc(sizeof(List));
  65.     temp1->next = temp2;
  66.     temp1->root = (Tree)malloc(sizeof(Huffman));
  67.     temp1->root->c = 'd';
  68.     temp1->root->weight = 9;
  69.     temp1->root->lchild = NULL;
  70.     temp1->root->rchild = NULL;
  71.  
  72.     temp2->pre = temp1;
  73.     temp1 = temp2;
  74.     temp2 = (pList)malloc(sizeof(List));
  75.     temp1->next = temp2;
  76.     temp1->root = (Tree)malloc(sizeof(Huffman));
  77.     temp1->root->c = 'e';
  78.     temp1->root->weight = 44;
  79.     temp1->root->lchild = NULL;
  80.     temp1->root->rchild = NULL;
  81.  
  82.     temp2->pre = temp1;
  83.     temp1 = temp2;
  84.     temp2 = (pList)malloc(sizeof(List));
  85.     temp1->next = temp2;
  86.     temp1->root = (Tree)malloc(sizeof(Huffman));
  87.     temp1->root->c = 'f';
  88.     temp1->root->weight = 12;
  89.     temp1->root->lchild = NULL;
  90.     temp1->root->rchild = NULL;
  91.  
  92.     temp2->pre = temp1;
  93.     temp1 = temp2;
  94.     temp1->next = NULL;
  95.     temp1->root = (Tree)malloc(sizeof(Huffman));
  96.     temp1->root->c = 'g';
  97.     temp1->root->weight = 65;
  98.     temp1->root->lchild = NULL;
  99.     temp1->root->rchild = NULL;
  100.  
  101.     return head;                          
  102. }

b创建栈结构：

解码过程需要用到两个栈，一个用来存放树结点，一个用来存放码0和1

  1. '''C
  2. #define STACK_INIT_SIZE 100   //栈初始开辟空间大小
  3. #define STACK_INCREMENT 10    //栈追加空间大小
  4.  
  5. //字符栈结构体，存放编码'0'和'1'
  6. typedef struct {
  7.     char *base;
  8.     char *top;
  9.     int size;
  10. }charStack;
  11.  
  12.  
  13. //栈初始化
  14. charStack charStackInit()
  15. {
  16.     charStack s;
  17.     s.base = (char *)malloc(sizeof(char)*STACK_INIT_SIZE);
  18.     s.top = s.base;
  19.     s.size = STACK_INIT_SIZE;
  20.     return s;
  21. }
  22.  
  23. //入栈
  24. void charPush(charStack *s, char e)
  25. {
  26.     if(s->top - s->base >= s->size)
  27.     {
  28.         s->size += STACK_INCREMENT;
  29.         s->base = realloc(s->base, sizeof(char)*s->size);
  30.     }
  31.     *s->top = e;
  32.     s->top++;
  33. }
  34.  
  35. //出栈
  36. char charPop(charStack *s)
  37. {
  38.     if(s->top != s->base)
  39.     {
  40.         s->top--;
  41.         return *s->top;
  42.     }
  43.     return -1;
  44. }
  45.  
  46. //得到栈顶元素，但不出栈
  47. char charGetTop(charStack *s)
  48. {
  49.     s->top--;
  50.     char temp = *s->top;
  51.     s->top++;
  52.     return temp;
  53. }
  54.  
  55. //栈结构体，存放哈夫曼树结点
  56. typedef struct 
  57. {
  58.     Huffman *base;
  59.     Huffman *top;
  60.     int size;
  61. }BiStack;
  62.  
  63. //栈初始化
  64. BiStack stackInit()
  65. {
  66.     BiStack s;
  67.     s.base = (Huffman *)malloc(sizeof(Huffman)*STACK_INIT_SIZE);
  68.     s.top = s.base;
  69.     s.size =STACK_INIT_SIZE;
  70.     return s;
  71. }
  72.  
  73. //入栈
  74. void push(BiStack *s, Huffman e)
  75. {
  76.     if(s->top - s->base >= s->size)
  77.     {
  78.         s->size += STACK_INCREMENT;
  79.         s->base = (Huffman *)realloc(s->base, sizeof(Huffman)*s->size);
  80.     }
  81.     *s->top = e;
  82.     s->top++;
  83. }
  84.  
  85. //出栈
  86. Huffman pop(BiStack *s)
  87. {
  88.     Huffman temp;
  89.     s->top--;
  90.     temp = *s->top;
  91.     return temp;
  92. }
  93.  
  94. //得到栈顶元素，但不出栈
  95. Huffman getTop(BiStack s)
  96. {
  97.     Huffman temp;
  98.     s.top--;
  99.     temp = *s.top;
  100.     return temp;
  101. }
  102.  
  103. char stack[7][10];             //记录a~g的编码
  104. //遍历栈，得到字符c的编码
  105. void traverseStack(charStack s, char c)
  106. {
  107.     int index = c - 'a'; 
  108.     int i = 0;
  109.     while(s.base != s.top)
  110.     {
  111.         stack[index][i] = *s.base;
  112.         i++;
  113.         s.base++;
  114.     }
  115. }

c 创建哈夫曼树：

  1. '''C
  2. //通过双向链表创建哈夫曼树，返回根结点指针
  3. Tree creatHuffman(pList head)
  4. {
  5.     pList list1 = NULL;
  6.     pList list2 = NULL;
  7.     pList index = NULL;
  8.     Tree root = NULL;
  9.     while(head->next != NULL)   //链表只剩一个结点时循环结束，此结点数据域即为哈夫曼树的根结点
  10.     {
  11.         list1 = head;
  12.         list2 = head->next;
  13.         index = list2->next;
  14.         root = (Tree)malloc(sizeof(Huffman));
  15.         while(index != NULL)    //找到链表中权重最小的两个结点list1,list2
  16.         {
  17.             if(list1->root->weight > index->root->weight || list2->root->weight > index->root->weight)
  18.             {
  19.                 if(list1->root->weight > list2->root->weight) list1 = index;
  20.                 else list2 = index;
  21.             }
  22.             index = index->next;
  23.         }
  24.         //list1和list2设为新结点的左右孩子
  25.         if(list2->root->weight > list1->root->weight)
  26.         {
  27.             root->lchild = list1->root;
  28.             root->rchild = list2->root;
  29.         }
  30.         else
  31.         {
  32.             root->lchild = list2->root;
  33.             root->rchild = list1->root;
  34.         }
  35.         //新结点字符统一设为空格，权重设为list1与list2权重之和
  36.         root->c = ' ';
  37.         root->weight = list1->root->weight + list2->root->weight;
  38.         //list1数据域替换成新结点，并删除list2
  39.         list1->root = root;
  40.         list2->pre->next = list2->next;
  41.         if(list2->next != NULL)
  42.             list2->next->pre = list2->pre;    
  43.     }
  44.     return head->root;
  45. }

d编码：

  1. '''C
  2. char stack[7][10];             //记录a~g的编码
  3. //遍历栈，得到字符c的编码
  4. void traverseStack(charStack s, char c)
  5. {
  6.     int index = c - 'a'; 
  7.     int i = 0;
  8.     while(s.base != s.top)
  9.     {
  10.         stack[index][i] = *s.base;
  11.         i++;
  12.         s.base++;
  13.     }
  14. }
  15.  
  16.  
  17. //通过哈夫曼树编码
  18. void encodeHuffman(Tree T)
  19. {  
  20.     BiStack bs = stackInit();
  21.     charStack cs = charStackInit();
  22.     Huffman root = *T;  
  23.     Tree temp = NULL;
  24.     push(&bs, root);      //根结点入栈
  25.     while(bs.top != bs.base)      //栈空表示遍历结束
  26.     {
  27.         root = getTop(bs);
  28.         temp = root.lchild;       //先访问左孩子
  29.         while(temp != NULL)       //左孩子不为空
  30.         {
  31.             //将结点左孩子设为空，代表已访问其左孩子
  32.             root.lchild = NULL;
  33.             pop(&bs);            
  34.             push(&bs, root);
  35.             //左孩子入栈
  36.             root = *temp;
  37.             temp = root.lchild;
  38.             push(&bs, root);
  39.             //'0'入字符栈
  40.             charPush(&cs, '0');
  41.         }
  42.         temp = root.rchild;     //后访问右孩子     
  43.         while(temp == NULL)     //右孩子为空，代表左右孩子均已访问，结点可以出栈 
  44.         {
  45.             //结点出栈
  46.             root = pop(&bs);
  47.             //寻到叶子结点，可以得到结点中字符的编码
  48.             if(root.c != ' ')
  49.                 traverseStack(cs, root.c);
  50.             charPop(&cs);       //字符栈出栈
  51.             if(bs.top == bs.base) break;    //根结点出栈，遍历结束
  52.             //查看上一级结点是否访问完左右孩子  
  53.             root = getTop(bs);
  54.             temp = root.rchild;           
  55.         }
  56.         if(bs.top != bs.base)
  57.         {
  58.             //将结点右孩子设为空，代表已访问其右孩子
  59.             root.rchild = NULL;       
  60.             pop(&bs);
  61.             push(&bs, root);
  62.             //右孩子入栈
  63.             root = *temp;      
  64.             push(&bs, root);
  65.             //'1'入字符栈
  66.             charPush(&cs, '1');
  67.         }    
  68.     }
  69. }

e解码：

  1. '''C
  2. char decode[100];   //记录解码得到的字符串
  3. //通过哈夫曼树解码
  4. void decodeHuffman(Tree T, char *code)
  5. {
  6.     int cnt = 0;
  7.     Tree root;
  8.     while(*code != '\\0')                  //01编码字符串读完，解码结束
  9.     {
  10.         root = T;
  11.         while(root->lchild != NULL)       //找到叶子结点
  12.         {
  13.             if(*code != '\\0')
  14.             {
  15.                 if(*code == '0')
  16.                     root = root->lchild;
  17.                 else
  18.                     root = root->rchild;
  19.                 code++;
  20.             }
  21.             else break;
  22.         }
  23.         decode[cnt] = root->c;             //叶子结点存放的字符即为解码得到的字符
  24.         cnt++;
  25.     }
  26. }

f主函数：

  1. '''C
  2. void main()
  3. {
  4.     pList pl = creatList();
  5.     printf("字符的权重如下\\n");
  6.     for(pList l = pl; l->next != NULL; l = l->next)
  7.         printf("字符%c的权重是 %d\\n", l->root->c, l->root->weight);
  8.     Tree T = creatHuffman(pl);
  9.     encodeHuffman(T);
  10.     printf("\\n\\n字符编码结果如下\\n");
  11.     for(int i = 0; i < 7; i++)
  12.         printf("%c : %s\\n", i+'a', stack[i]);
  13.     char code[100];
  14.     printf("\\n\\n请输入编码：\\n");
  15.     scanf("%s", code);
  16.     printf("解码结果如下：\\n");
  17.     decodeHuffman(T, code);
  18.     printf("%s\\n", decode);
  19.     printf("\\n\\n");
  20.     system("date /T");
  21.     system("TIME /T");
  22.     system("pause");
  23.     exit(0); 
  24. }

1.2运行结果

如何利用Python和C语言分别实现哈夫曼编码

2.Python实现

2.1代码说明

a创建哈夫曼树：

  1. #coding=gbk
  2.  
  3. import datetime
  4. import time
  5. from pip._vendor.distlib.compat import raw_input
  6.  
  7. #哈夫曼树结点类
  8. class Huffman:
  9.     def __init__(self, c, weight):
  10.         self.c = c
  11.         self.weight = weight
  12.         self.lchild = None
  13.         self.rchild = None
  14.     
  15.     #创建结点左右孩子    
  16.     def creat(self, lchild, rchild):
  17.         self.lchild = lchild
  18.         self.rchild = rchild
  19.  
  20. #创建列表        
  21. def creatList():
  22.     list = []
  23.     list.append(Huffman('a', 22))
  24.     list.append(Huffman('b', 5))
  25.     list.append(Huffman('c', 38))
  26.     list.append(Huffman('d', 9))
  27.     list.append(Huffman('e', 44))
  28.     list.append(Huffman('f', 12))
  29.     list.append(Huffman('g', 65))
  30.     return list
  31.  
  32. #通过列表创建哈夫曼树，返回树的根结点
  33. def creatHuffman(list):
  34.     while len(list) > 1:               #列表只剩一个结点时循环结束，此结点即为哈夫曼树的根结点
  35.         i = 0
  36.         j = 1
  37.         k = 2
  38.         while k < len(list):           #找到列表中权重最小的两个结点list1,list2          
  39.             if list[i].weight > list[k].weight or list[j].weight > list[k].weight:
  40.                 if list[i].weight > list[j].weight:
  41.                     i = k
  42.                 else:
  43.                     j = k
  44.             k += 1       
  45.         root = Huffman(' ', list[i].weight + list[j].weight) #新结点字符统一设为空格，权重设为list1与list2权重之和   
  46.         if list[i].weight < list[j].weight:                  #list1和list2设为新结点的左右孩子
  47.             root.creat(list[i], list[j])
  48.         else:
  49.             root.creat(list[j], list[i])
  50.         #list1数据域替换成新结点，并删除list2
  51.         list[i] = root
  52.         list.remove(list[j])
  53.     return list[0]

b编码：

  1. #通过哈夫曼树编码
  2. def encodeHuffman(T):
  3.     code = [[], [], [], [], [], [], []]
  4.     #列表实现栈结构
  5.     treeStack = []
  6.     codeStack = []
  7.     treeStack.append(T)
  8.     while treeStack != []:        #栈空代表遍历结束
  9.         root = treeStack[-1]
  10.         temp = root.lchild
  11.         while temp != None:
  12.             #将结点左孩子设为空，代表已访问其左孩子
  13.             root.lchild = None        
  14.             #左孩子入栈          
  15.             treeStack.append(temp)         
  16.             root = temp
  17.             temp = root.lchild
  18.             #0入编码栈
  19.             codeStack.append(0)
  20.         temp = root.rchild            #后访问右孩子
  21.         while temp == None:           #右孩子为空，代表左右孩子均已访问，结点可以出栈
  22.             root = treeStack.pop()           #结点出栈
  23.             #寻到叶子结点，可以得到结点中字符的编码
  24.             if root.c != ' ':
  25.                 codeTemp = codeStack.copy()
  26.                 code[ord(root.c) - 97] = codeTemp     
  27.             if treeStack == []:    #根结点出栈，遍历结束
  28.                 break
  29.             codeStack.pop()        #编码栈出栈
  30.             #查看上一级结点是否访问完左右孩子
  31.             root = treeStack[-1]
  32.             temp = root.rchild
  33.         if treeStack != []:
  34.             treeStack.append(temp)     #右孩子入栈
  35.             root.rchild = None         #将结点右孩子设为空，代表已访问其右孩子
  36.             codeStack.append(1)        #1入编码栈
  37.     return code

c解码：

  1. #通过哈夫曼树解码
  2. def decodeHuffman(T, strCode):
  3.     decode = []
  4.     index = 0
  5.     while index < len(strCode):        #01编码字符串读完，解码结束
  6.         root = T
  7.         while root.lchild != None:     #找到叶子结点
  8.             if index < len(strCode):
  9.                 if strCode[index] == '0':
  10.                     root = root.lchild
  11.                 else:
  12.                     root = root.rchild
  13.                 index += 1
  14.             else:
  15.                 break
  16.         decode.append(root.c)           #叶子结点存放的字符即为解码得到的字符
  17.     return decode

d主函数：

  1. if __name__ == '__main__':
  2.     list = creatList()
  3.     print("字符的权重如下")
  4.     for i in range(len(list)):
  5.         print("字符{}的权重为: {}".format(chr(i+97), list[i].weight))
  6.     T = creatHuffman(list)
  7.     code = encodeHuffman(T)
  8.     print("\\n字符编码结果如下")
  9.     for i in range(len(code)):
  10.         print(chr(i+97), end=' : ')
  11.         for j in range(len(code[i])):
  12.             print(code[i][j], end='')
  13.         print("")
  14.     strCode = input("\\n请输入编码：\\n")
  15.     #哈夫曼树在编码时被破坏，必须重建哈夫曼树
  16.     list = creatList()
  17.     T = creatHuffman(list)
  18.     decode = decodeHuffman(T, strCode)
  19.     print("解码结果如下：")
  20.     for i in range(len(decode)):
  21.         print(decode[i], end='')
  22.     print("\\n\\n")
  23.     datetime = datetime.datetime.now()
  24.     print(datetime.strftime("%Y-%m-%d\\n%H:%M:%S"))
  25.     input("Press Enter to exit…")

2.2运行结果

如何利用Python和C语言分别实现哈夫曼编码

关于“如何利用Python和C语言分别实现哈夫曼编码”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注恰卡网行业资讯频道，小编每天都会为大家更新不同的知识点。

本站部分文章来自网络或用户投稿，如无特殊说明或标注，均为本站原创发布。涉及资源下载的，本站旨在共享仅供大家学习与参考，如您想商用请获取官网版权，如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
c语言python
开发者

怎么使用Vite+React搭建一个开源组件库

2022-8-3 21:04:27

开发者

python怎么读取和存储dict()与.json格式文件

2022-8-3 21:04:32

请输入验证码

请输入图片中的验证码
点击发送按钮获取验证码

取消
×
×
￥undefined
请打开手机使用微信扫码支付
「」
×

....支付确认中....

「」
×
支付金额

￥

undefined
×
积分支付
您当前的积分为0

检测到您未绑定微信账户，请先绑定微信

立刻绑定
确定
×

举报

请选择举报类型*

政治有害
不友善
垃圾广告
违法违规
色情低俗
涉嫌侵权
网络暴力
涉未成年
自杀自残
不实信息
引人不适
抄袭
扰乱社区秩序
请输入举报内容 *

举报提交后，我们会以邮件的形式向您反馈处理结果。

×

打开微信扫一扫

扫码并「关注我们的公众号」安全快捷登录

×

下载海报：

搜索

  • 扫码打开当前页

返回顶部