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

wwuc

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运行结果

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哈夫曼编码的资料请关注趣UU其它相关文章！

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