请选择 进入手机版 | 继续访问电脑版
查看: 147|回复: 0

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

[复制链接]

2198

主题

0

回帖

7027

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
7027
发表于 2022-10-9 01:06:01 | 显示全部楼层 |阅读模式
1.C语言实现


1.1代码说明

a  创建双向链表:
在创建哈夫曼树的过程中,需要不停对结点进行更改和删除,所以选用双向链表的结构更容易
  1. '''C
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <windows.h>


  5. //哈夫曼树结构体,数据域存储字符及其权重
  6. typedef struct node
  7. {
  8.     char c;
  9.     int weight;
  10.     struct node *lchild, *rchild;
  11. }Huffman, *Tree;


  12. //双向链表结构体,数据域存储哈夫曼树结点
  13. typedef struct list
  14. {
  15.     Tree root;
  16.     struct list *pre;
  17.     struct list *next;
  18. }List, *pList;


  19. //创建双向链表,返回头结点指针
  20. pList creatList()
  21. {
  22.     pList head = (pList)malloc(sizeof(List));

  23.     pList temp1 = head;
  24.     pList temp2 = (pList)malloc(sizeof(List));
  25.     temp1->pre = NULL;
  26.     temp1->next = temp2;
  27.     temp1->root = (Tree)malloc(sizeof(Huffman));
  28.     temp1->root->c = 'a';
  29.     temp1->root->weight = 22;
  30.     temp1->root->lchild = NULL;
  31.     temp1->root->rchild = NULL;
  32.    

  33.     temp2->pre = temp1;
  34.     temp1 = temp2;
  35.     temp2 = (pList)malloc(sizeof(List));
  36.     temp1->next = temp2;
  37.     temp1->root = (Tree)malloc(sizeof(Huffman));
  38.     temp1->root->c = 'b';
  39.     temp1->root->weight = 5;
  40.     temp1->root->lchild = NULL;
  41.     temp1->root->rchild = NULL;
  42.    

  43.     temp2->pre = temp1;
  44.     temp1 = temp2;
  45.     temp2 = (pList)malloc(sizeof(List));
  46.     temp1->next = temp2;
  47.     temp1->root = (Tree)malloc(sizeof(Huffman));
  48.     temp1->root->c = 'c';
  49.     temp1->root->weight = 38;
  50.     temp1->root->lchild = NULL;
  51.     temp1->root->rchild = NULL;

  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 = 'd';
  58.     temp1->root->weight = 9;
  59.     temp1->root->lchild = NULL;
  60.     temp1->root->rchild = NULL;

  61.     temp2->pre = temp1;
  62.     temp1 = temp2;
  63.     temp2 = (pList)malloc(sizeof(List));
  64.     temp1->next = temp2;
  65.     temp1->root = (Tree)malloc(sizeof(Huffman));
  66.     temp1->root->c = 'e';
  67.     temp1->root->weight = 44;
  68.     temp1->root->lchild = NULL;
  69.     temp1->root->rchild = NULL;

  70.     temp2->pre = temp1;
  71.     temp1 = temp2;
  72.     temp2 = (pList)malloc(sizeof(List));
  73.     temp1->next = temp2;
  74.     temp1->root = (Tree)malloc(sizeof(Huffman));
  75.     temp1->root->c = 'f';
  76.     temp1->root->weight = 12;
  77.     temp1->root->lchild = NULL;
  78.     temp1->root->rchild = NULL;

  79.     temp2->pre = temp1;
  80.     temp1 = temp2;
  81.     temp1->next = NULL;
  82.     temp1->root = (Tree)malloc(sizeof(Huffman));
  83.     temp1->root->c = 'g';
  84.     temp1->root->weight = 65;
  85.     temp1->root->lchild = NULL;
  86.     temp1->root->rchild = NULL;

  87.     return head;                          
  88. }
复制代码
b创建栈结构:
解码过程需要用到两个栈,一个用来存放树结点,一个用来存放码0和1
  1. '''C
  2. #define STACK_INIT_SIZE 100   //栈初始开辟空间大小
  3. #define STACK_INCREMENT 10    //栈追加空间大小

  4. //字符栈结构体,存放编码'0'和'1'
  5. typedef struct {
  6.     char *base;
  7.     char *top;
  8.     int size;
  9. }charStack;


  10. //栈初始化
  11. charStack charStackInit()
  12. {
  13.     charStack s;
  14.     s.base = (char *)malloc(sizeof(char)*STACK_INIT_SIZE);
  15.     s.top = s.base;
  16.     s.size = STACK_INIT_SIZE;
  17.     return s;
  18. }

  19. //入栈
  20. void charPush(charStack *s, char e)
  21. {
  22.     if(s->top - s->base >= s->size)
  23.     {
  24.         s->size += STACK_INCREMENT;
  25.         s->base = realloc(s->base, sizeof(char)*s->size);
  26.     }
  27.     *s->top = e;
  28.     s->top++;
  29. }

  30. //出栈
  31. char charPop(charStack *s)
  32. {
  33.     if(s->top != s->base)
  34.     {
  35.         s->top--;
  36.         return *s->top;
  37.     }
  38.     return -1;
  39. }

  40. //得到栈顶元素,但不出栈
  41. char charGetTop(charStack *s)
  42. {
  43.     s->top--;
  44.     char temp = *s->top;
  45.     s->top++;
  46.     return temp;
  47. }

  48. //栈结构体,存放哈夫曼树结点
  49. typedef struct
  50. {
  51.     Huffman *base;
  52.     Huffman *top;
  53.     int size;
  54. }BiStack;

  55. //栈初始化
  56. BiStack stackInit()
  57. {
  58.     BiStack s;
  59.     s.base = (Huffman *)malloc(sizeof(Huffman)*STACK_INIT_SIZE);
  60.     s.top = s.base;
  61.     s.size =STACK_INIT_SIZE;
  62.     return s;
  63. }

  64. //入栈
  65. void push(BiStack *s, Huffman e)
  66. {
  67.     if(s->top - s->base >= s->size)
  68.     {
  69.         s->size += STACK_INCREMENT;
  70.         s->base = (Huffman *)realloc(s->base, sizeof(Huffman)*s->size);
  71.     }
  72.     *s->top = e;
  73.     s->top++;
  74. }

  75. //出栈
  76. Huffman pop(BiStack *s)
  77. {
  78.     Huffman temp;
  79.     s->top--;
  80.     temp = *s->top;
  81.     return temp;
  82. }

  83. //得到栈顶元素,但不出栈
  84. Huffman getTop(BiStack s)
  85. {
  86.     Huffman temp;
  87.     s.top--;
  88.     temp = *s.top;
  89.     return temp;
  90. }

  91. char stack[7][10];             //记录a~g的编码
  92. //遍历栈,得到字符c的编码
  93. void traverseStack(charStack s, char c)
  94. {
  95.     int index = c - 'a';
  96.     int i = 0;
  97.     while(s.base != s.top)
  98.     {
  99.         stack[index][i] = *s.base;
  100.         i++;
  101.         s.base++;
  102.     }
  103. }
复制代码
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. void encodeHuffman(Tree T)
  17. {  
  18.     BiStack bs = stackInit();
  19.     charStack cs = charStackInit();
  20.     Huffman root = *T;  
  21.     Tree temp = NULL;
  22.     push(&bs, root);      //根结点入栈
  23.     while(bs.top != bs.base)      //栈空表示遍历结束
  24.     {
  25.         root = getTop(bs);
  26.         temp = root.lchild;       //先访问左孩子
  27.         while(temp != NULL)       //左孩子不为空
  28.         {
  29.             //将结点左孩子设为空,代表已访问其左孩子
  30.             root.lchild = NULL;
  31.             pop(&bs);            
  32.             push(&bs, root);
  33.             //左孩子入栈
  34.             root = *temp;
  35.             temp = root.lchild;
  36.             push(&bs, root);
  37.             //'0'入字符栈
  38.             charPush(&cs, '0');
  39.         }
  40.         temp = root.rchild;     //后访问右孩子     
  41.         while(temp == NULL)     //右孩子为空,代表左右孩子均已访问,结点可以出栈
  42.         {
  43.             //结点出栈
  44.             root = pop(&bs);
  45.             //寻到叶子结点,可以得到结点中字符的编码
  46.             if(root.c != ' ')
  47.                 traverseStack(cs, root.c);
  48.             charPop(&cs);       //字符栈出栈
  49.             if(bs.top == bs.base) break;    //根结点出栈,遍历结束
  50.             //查看上一级结点是否访问完左右孩子  
  51.             root = getTop(bs);
  52.             temp = root.rchild;           
  53.         }
  54.         if(bs.top != bs.base)
  55.         {
  56.             //将结点右孩子设为空,代表已访问其右孩子
  57.             root.rchild = NULL;      
  58.             pop(&bs);
  59.             push(&bs, root);
  60.             //右孩子入栈
  61.             root = *temp;      
  62.             push(&bs, root);
  63.             //'1'入字符栈
  64.             charPush(&cs, '1');
  65.         }   
  66.     }
  67. }
复制代码
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运行结果



2.Python实现


2.1代码说明

a创建哈夫曼树:
  1. #coding=gbk

  2. import datetime
  3. import time
  4. from pip._vendor.distlib.compat import raw_input

  5. #哈夫曼树结点类
  6. class Huffman:
  7.     def __init__(self, c, weight):
  8.         self.c = c
  9.         self.weight = weight
  10.         self.lchild = None
  11.         self.rchild = None
  12.    
  13.     #创建结点左右孩子   
  14.     def creat(self, lchild, rchild):
  15.         self.lchild = lchild
  16.         self.rchild = rchild

  17. #创建列表        
  18. def creatList():
  19.     list = []
  20.     list.append(Huffman('a', 22))
  21.     list.append(Huffman('b', 5))
  22.     list.append(Huffman('c', 38))
  23.     list.append(Huffman('d', 9))
  24.     list.append(Huffman('e', 44))
  25.     list.append(Huffman('f', 12))
  26.     list.append(Huffman('g', 65))
  27.     return list

  28. #通过列表创建哈夫曼树,返回树的根结点
  29. def creatHuffman(list):
  30.     while len(list) > 1:               #列表只剩一个结点时循环结束,此结点即为哈夫曼树的根结点
  31.         i = 0
  32.         j = 1
  33.         k = 2
  34.         while k < len(list):           #找到列表中权重最小的两个结点list1,list2         
  35.             if list[i].weight > list[k].weight or list[j].weight > list[k].weight:
  36.                 if list[i].weight > list[j].weight:
  37.                     i = k
  38.                 else:
  39.                     j = k
  40.             k += 1      
  41.         root = Huffman(' ', list[i].weight + list[j].weight) #新结点字符统一设为空格,权重设为list1与list2权重之和   
  42.         if list[i].weight < list[j].weight:                  #list1和list2设为新结点的左右孩子
  43.             root.creat(list[i], list[j])
  44.         else:
  45.             root.creat(list[j], list[i])
  46.         #list1数据域替换成新结点,并删除list2
  47.         list[i] = root
  48.         list.remove(list[j])
  49.     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哈夫曼编码的资料请关注趣UU其它相关文章!

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
打赏作者
  • 0
  • 0
  • 0
  • 0
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表