共享博客如何利用Python和C语言分别实现哈夫曼编码
1.C语言实现
1.1代码说明
a 创建双向链表：
在创建哈夫曼树的过程中，需要不断对结点进行更改和删除，所以选用双向链表的结构更容易
'''C#include <stdlib.h>#include <stdio.h>#include <windows.h> //哈夫曼树结构体，数据域存储字符及其权重typedef struct node{ char c; int weight; struct node *lchild, *rchild;}Huffman, *Tree; //双向链表结构体，数据域存储哈夫曼树结点typedef struct list{ Tree root; struct list *pre; struct list *next;}List, *pList; //创建双向链表，返回头结点指针pList creatList(){ pList head = (pList)malloc(sizeof(List)); pList temp1 = head; pList temp2 = (pList)malloc(sizeof(List)); temp1->pre = NULL; temp1->next = temp2; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'a'; temp1->root->weight = 22; temp1->root->lchild = NULL; temp1->root->rchild = NULL; temp2->pre = temp1; temp1 = temp2; temp2 = (pList)malloc(sizeof(List)); temp1->next = temp2; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'b'; temp1->root->weight = 5; temp1->root->lchild = NULL; temp1->root->rchild = NULL; temp2->pre = temp1; temp1 = temp2; temp2 = (pList)malloc(sizeof(List)); temp1->next = temp2; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'c'; temp1->root->weight = 38; temp1->root->lchild = NULL; temp1->root->rchild = NULL; temp2->pre = temp1; temp1 = temp2; temp2 = (pList)malloc(sizeof(List)); temp1->next = temp2; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'd'; temp1->root->weight = 9; temp1->root->lchild = NULL; temp1->root->rchild = NULL; temp2->pre = temp1; temp1 = temp2; temp2 = (pList)malloc(sizeof(List)); temp1->next = temp2; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'e'; temp1->root->weight = 44; temp1->root->lchild = NULL; temp1->root->rchild = NULL; temp2->pre = temp1; temp1 = temp2; temp2 = (pList)malloc(sizeof(List)); temp1->next = temp2; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'f'; temp1->root->weight = 12; temp1->root->lchild = NULL; temp1->root->rchild = NULL; temp2->pre = temp1; temp1 = temp2; temp1->next = NULL; temp1->root = (Tree)malloc(sizeof(Huffman)); temp1->root->c = 'g'; temp1->root->weight = 65; temp1->root->lchild = NULL; temp1->root->rchild = NULL; return head; }</windows.h></stdio.h></stdlib.h>b创建栈结构：
解码过程需要用到两个栈，一个用来存放树结点，一个用来存放码0和1
'''C#define STACK_INIT_SIZE 100 //栈初始开辟空间大小#define STACK_INCREMENT 10 //栈追加空间大小 //字符栈结构体，存放编码'0'和'1'typedef struct { char *base; char *top; int size;}charStack; //栈初始化charStack charStackInit(){ charStack s; s.base = (char *)malloc(sizeof(char)*STACK_INIT_SIZE); s.top = s.base; s.size = STACK_INIT_SIZE; return s;} //入栈void charPush(charStack *s, char e){ if(s->top - s->base >= s->size) { s->size += STACK_INCREMENT; s->base = realloc(s->base, sizeof(char)*s->size); } *s->top = e; s->top++;} //出栈char charPop(charStack *s){ if(s->top != s->base) { s->top--; return *s->top; } return -1;} //得到栈顶元素，但不出栈char charGetTop(charStack *s){ s->top--; char temp = *s->top; s->top++; return temp;} //栈结构体，存放哈夫曼树结点typedef struct { Huffman *base; Huffman *top; int size;}BiStack; //栈初始化BiStack stackInit(){ BiStack s; s.base = (Huffman *)malloc(sizeof(Huffman)*STACK_INIT_SIZE); s.top = s.base; s.size =STACK_INIT_SIZE; return s;} //入栈void push(BiStack *s, Huffman e){ if(s->top - s->base >= s->size) { s->size += STACK_INCREMENT; s->base = (Huffman *)realloc(s->base, sizeof(Huffman)*s->size); } *s->top = e; s->top++;} //出栈Huffman pop(BiStack *s){ Huffman temp; s->top--; temp = *s->top; return temp;} //得到栈顶元素，但不出栈Huffman getTop(BiStack s){ Huffman temp; s.top--; temp = *s.top; return temp;} char stack[7][10]; //记录a~g的编码//遍历栈，得到字符c的编码void traverseStack(charStack s, char c){ int index = c - 'a'; int i = 0; while(s.base != s.top) { stack[index][i] = *s.base; i++; s.base++; }}c 创建哈夫曼树：
立即学习“Python免费学习笔记（深入）”；
'''C//通过双向链表创建哈夫曼树，返回根结点指针Tree creatHuffman(pList head){ pList list1 = NULL; pList list2 = NULL; pList index = NULL; Tree root = NULL; while(head->next != NULL) //链表只剩一个结点时循环结束，此结点数据域即为哈夫曼树的根结点 { list1 = head; list2 = head->next; index = list2->next; root = (Tree)malloc(sizeof(Huffman)); while(index != NULL) //找到链表中权重最小的两个结点list1,list2 { if(list1->root->weight > index->root->weight || list2->root->weight > index->root->weight) { if(list1->root->weight > list2->root->weight) list1 = index; else list2 = index; } index = index->next; } //list1和list2设为新结点的左右孩子 if(list2->root->weight > list1->root->weight) { root->lchild = list1->root; root->rchild = list2->root; } else { root->lchild = list2->root; root->rchild = list1->root; } //新结点字符统一设为空格，权重设为list1与list2权重之和 root->c = ' '; root->weight = list1->root->weight + list2->root->weight; //list1数据域替换成新结点，并删除list2 list1->root = root; list2->pre->next = list2->next; if(list2->next != NULL) list2->next->pre = list2->pre; } return head->root;}d编码：
'''Cchar stack[7][10]; //记录a~g的编码//遍历栈，得到字符c的编码void traverseStack(charStack s, char c){ int index = c - 'a'; int i = 0; while(s.base != s.top) { stack[index][i] = *s.base; i++; s.base++; }} //通过哈夫曼树编码void encodeHuffman(Tree T){ BiStack bs = stackInit(); charStack cs = charStackInit(); Huffman root = *T; Tree temp = NULL; push(&bs, root); //根结点入栈 while(bs.top != bs.base) //栈空表示遍历结束 { root = getTop(bs); temp = root.lchild; //先访问左孩子 while(temp != NULL) //左孩子不为空 { //将结点左孩子设为空，代表已访问其左孩子 root.lchild = NULL; pop(&bs); push(&bs, root); //左孩子入栈 root = *temp; temp = root.lchild; push(&bs, root); //'0'入字符栈 charPush(&cs, '0'); } temp = root.rchild; //后访问右孩子 while(temp == NULL) //右孩子为空，代表左右孩子均已访问，结点可以出栈 { //结点出栈 root = pop(&bs); //寻到叶子结点，可以得到结点中字符的编码 if(root.c != ' ') traverseStack(cs, root.c); charPop(&cs); //字符栈出栈 if(bs.top == bs.base) break; //根结点出栈，遍历结束 //查看上一级结点是否访问完左右孩子 root = getTop(bs); temp = root.rchild; } if(bs.top != bs.base) { //将结点右孩子设为空，代表已访问其右孩子 root.rchild = NULL; pop(&bs); push(&bs, root); //右孩子入栈 root = *temp; push(&bs, root); //'1'入字符栈 charPush(&cs, '1'); } }}e解码：
'''Cchar decode[100]; //记录解码得到的字符串//通过哈夫曼树解码void decodeHuffman(Tree T, char *code){ int cnt = 0; Tree root; while(*code != '') //01编码字符串读完，解码结束 { root = T; while(root->lchild != NULL) //找到叶子结点 { if(*code != '') { if(*code == '0') root = root->lchild; else root = root->rchild; code++; } else break; } decode[cnt] = root->c; //叶子结点存放的字符即为解码得到的字符 cnt++; }}f主函数：
'''Cvoid main(){ pList pl = creatList(); printf("字符的权重如下"); for(pList l = pl; l->next != NULL; l = l->next) printf("字符%c的权重是 %d", l->root->c, l->root->weight); Tree T = creatHuffman(pl); encodeHuffman(T); printf("字符编码结果如下"); for(int i = 0; i <h4>1.2运行结果</h4><p><img src="https://img.php.cn/upload/article/000/000/164/168473436956762.png" alt="如何利用Python和C语言分别实现哈夫曼编码"></p><h3>2.Python实现</h3><h4>2.1代码说明</h4><p>a创建哈夫曼树：</p><pre class="brush:py;">#coding=gbk import datetimeimport timefrom pip._vendor.distlib.compat import raw_input #哈夫曼树结点类class Huffman: def __init__(self, c, weight): self.c = c self.weight = weight self.lchild = None self.rchild = None #创建结点左右孩子 def creat(self, lchild, rchild): self.lchild = lchild self.rchild = rchild #创建列表 def creatList(): list = [] list.append(Huffman('a', 22)) list.append(Huffman('b', 5)) list.append(Huffman('c', 38)) list.append(Huffman('d', 9)) list.append(Huffman('e', 44)) list.append(Huffman('f', 12)) list.append(Huffman('g', 65)) return list #通过列表创建哈夫曼树，返回树的根结点def creatHuffman(list): while len(list) > 1: #列表只剩一个结点时循环结束，此结点即为哈夫曼树的根结点 i = 0 j = 1 k = 2 while k list[k].weight or list[j].weight > list[k].weight: if list[i].weight > list[j].weight: i = k else: j = k k += 1 root = Huffman(' ', list[i].weight + list[j].weight) #新结点字符统一设为空格，权重设为list1与list2权重之和 if list[i].weight <p>b编码：</p><pre class="brush:py;">#通过哈夫曼树编码def encodeHuffman(T): code = [[], [], [], [], [], [], []] #列表实现栈结构 treeStack = [] codeStack = [] treeStack.append(T) while treeStack != []: #栈空代表遍历结束 root = treeStack[-1] temp = root.lchild while temp != None: #将结点左孩子设为空，代表已访问其左孩子 root.lchild = None #左孩子入栈 treeStack.append(temp) root = temp temp = root.lchild #0入编码栈 codeStack.append(0) temp = root.rchild #后访问右孩子 while temp == None: #右孩子为空，代表左右孩子均已访问，结点可以出栈 root = treeStack.pop() #结点出栈 #寻到叶子结点，可以得到结点中字符的编码 if root.c != ' ': codeTemp = codeStack.copy() code[ord(root.c) - 97] = codeTemp if treeStack == []: #根结点出栈，遍历结束 break codeStack.pop() #编码栈出栈 #查看上一级结点是否访问完左右孩子 root = treeStack[-1] temp = root.rchild if treeStack != []: treeStack.append(temp) #右孩子入栈 root.rchild = None #将结点右孩子设为空，代表已访问其右孩子 codeStack.append(1) #1入编码栈 return codec解码：
#通过哈夫曼树解码def decodeHuffman(T, strCode): decode = [] index = 0 while index <p>d主函数：</p><pre class="brush:py;">if __name__ == '__main__': list = creatList() print("字符的权重如下") for i in range(len(list)): print("字符{}的权重为: {}".format(chr(i+97), list[i].weight)) T = creatHuffman(list) code = encodeHuffman(T) print("字符编码结果如下") for i in range(len(code)): print(chr(i+97), end=' : ') for j in range(len(code[i])): print(code[i][j], end='') print("") strCode = input("请输入编码：") #哈夫曼树在编码时被破坏，必须重建哈夫曼树 list = creatList() T = creatHuffman(list) decode = decodeHuffman(T, strCode) print("解码结果如下：") for i in range(len(decode)): print(decode[i], end='') print("") datetime = datetime.datetime.now() print(datetime.strftime("%Y-%m-%d%H:%M:%S")) input("Press Enter to exit…")2.2运行结果
文章推荐
-
Python大神都知道的内置函数
python内置了一些非常巧妙而且强大的内置函数，对初学者来说，一般不怎么用到，我也是用了一段时间python之后才发现...
Python
11秒前 0 -
挑战Python的四个语言：Swift、Go、Julia、R
没什么是永恒的——包括编程语言。很多看起来可能是将来的佼佼者，到头来可能被人们遗忘。无论是因为不可抗拒的原因，还是因为自...
Python
56秒前 0 -
如何在 Visual Studio 上更好开发 Python 的六大功能！
Visual Studio 2013/2015 搭配 Python Tools for Visual Studio 扩充...
Python
2分钟前 0 -
Python开发的10个注意事项
下面是十个Python中很有用的贴士和技巧。其中一些是初学这门语言常常会犯的错误。注意：假设我们都用的是Python 3...
Python
2分钟前 0 -
理解 Python 中的线程
我们将会看到一些在Python中使用线程的实例和如何避免线程之间的竞争。你应当将下边的例子运行多次，以便可以注意到线程是...
Python
4分钟前 1