利用Python和C语言分别实现哈夫曼编码
作者：观察者555 发布时间：2021-08-12 09:59:49
标签：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;
}
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 创建哈夫曼树：
'''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编码：
'''C
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++;
}
}
//通过哈夫曼树编码
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解码：
'''C
char decode[100]; //记录解码得到的字符串
//通过哈夫曼树解码
void decodeHuffman(Tree T, char *code)
{
int cnt = 0;
Tree root;
while(*code != '\0') //01编码字符串读完，解码结束
{
root = T;
while(root->lchild != NULL) //找到叶子结点
{
if(*code != '\0')
{
if(*code == '0')
root = root->lchild;
else
root = root->rchild;
code++;
}
else break;
}
decode[cnt] = root->c; //叶子结点存放的字符即为解码得到的字符
cnt++;
}
}
f主函数：
'''C
void main()
{
pList pl = creatList();
printf("字符的权重如下\n");
for(pList l = pl; l->next != NULL; l = l->next)
printf("字符％c的权重是 ％d\n", l->root->c, l->root->weight);
Tree T = creatHuffman(pl);
encodeHuffman(T);
printf("\n\n字符编码结果如下\n");
for(int i = 0; i < 7; i++)
printf("％c : ％s\n", i+'a', stack[i]);
char code[100];
printf("\n\n请输入编码：\n");
scanf("％s", code);
printf("解码结果如下：\n");
decodeHuffman(T, code);
printf("％s\n", decode);
printf("\n\n");
system("date /T");
system("TIME /T");
system("pause");
exit(0);
}
1.2运行结果
2.Python实现
2.1代码说明
a创建哈夫曼树：
#coding=gbk
import datetime
import time
from 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 < len(list): #找到列表中权重最小的两个结点list1,list2
if list[i].weight > 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 < list[j].weight: #list1和list2设为新结点的左右孩子
root.creat(list[i], list[j])
else:
root.creat(list[j], list[i])
#list1数据域替换成新结点，并删除list2
list[i] = root
list.remove(list[j])
return list[0]
b编码：
#通过哈夫曼树编码
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 code
c解码：
#通过哈夫曼树解码
def decodeHuffman(T, strCode):
decode = []
index = 0
while index < len(strCode): #01编码字符串读完，解码结束
root = T
while root.lchild != None: #找到叶子结点
if index < len(strCode):
if strCode[index] == '0':
root = root.lchild
else:
root = root.rchild
index += 1
else:
break
decode.append(root.c) #叶子结点存放的字符即为解码得到的字符
return decode
d主函数：
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("\n字符编码结果如下")
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("\n请输入编码：\n")
#哈夫曼树在编码时被破坏，必须重建哈夫曼树
list = creatList()
T = creatHuffman(list)
decode = decodeHuffman(T, strCode)
print("解码结果如下：")
for i in range(len(decode)):
print(decode[i], end='')
print("\n\n")
datetime = datetime.datetime.now()
print(datetime.strftime("％Y-％m-％d\n％H:％M:％S"))
input("Press Enter to exit…")
2.2运行结果
来源：https://blog.csdn.net/guanchazhe55/article/details/125766584
0
投稿猜你喜欢
1、什么是水仙花数？水仙花数（Narcissistic number）也被称为超完全数字不变数（pluperfect digit- 目录元组简单介绍声明元组元组与列表的区别特殊的元组元组的简写元组常见运算操作索引 [ ] 取值切片 [ : : ] 取值运算符 +运算符 *
- 提示：本文多图，请手机端注意流量。前言利用python做图片识别，识别提取图片中的文字会有很多方法，但是想要简单一点怎么办，那就可以使用te
- 背景目前项目在移动端上，首推使用微信小程序。各项目的小程序访问数据有必要进行采集入库，方便后续做统计分析。虽然阿拉丁后台也提供了趋势分析等功
- 实际项目中会涉及到需要对有些函数的响应时间做一些限制，如果超时就退出函数的执行，停止等待。可以利用python中的装饰器实现对函数执行时间的
- QSpinBox 是一个计数器控件，允许用户选择一个整数值，通过单击向上/向下按钮或按键盘上的上/下箭头来增加/减少当前显示的值，当然用户也
- 什么是F型浏览？2006年4月，美国长期研究网站可用性的著名网站设计师杰柯柏·尼尔森（Jakob Nielsen）发表了一项《眼球轨迹的研究
- 摘要django框架本身自带有登录注册，也可以自己写登录注册，下面将介绍这这2种方式实登录注册一、自己写登录注册登出1.注册regist注册
- 1. 准备工作有朋友可能没用过folium，它其实就是python的一个专业绘制地图的第三方库，所以在使用之前需要先安装它。pip
- 在windows 2003下,在运行web应用程序的时候出现一下错误: 服务器无法处理请求，－－＞对路径“C:/temp/mytest.tx
- 1.问题复现：有时候我们去点击.py文件 文件里明明有打印信息，却一闪而过，没有任何显示比如以下内容#!/usr/local/bin/pyt
- 在定义类的过程中，无论是显式创建类的构造方法，还是向类中添加实例方法，都要求将 self 参数作为方法的第一个参数。例如，定义一个 Pers
- 在Oracle 8i中，往往会出现要在存储过程中运行操作系统命令的情况。一般来说，利用Oracle Enterprise Manager设定
- 需求有一个表，里面数据量比较大，每天一更新，其字段可以通过xml配置文件进行配置，即，可能每次建表的字段不一样。上游跑时会根据配置从源文件中
- 第一招、mysql服务的启动和停止net stop mysqlnet start mysql第二招、登陆mysql语法如下： mysql -
- 软件版本Python 2.7.13; Win 10场景描述1、使用python读取指定长度的文本；2、使用python读取某一范围内的文本。
- 认识pip众所周知，pip可以对python的第三方库进行安装、更新、卸载等操作，十分方便。pip的全称：package installer
- 当获取FileField数据时会出现编码问题在数据库里显示的是D:\python项目\wxmkczpy\uploadfile\QQ截图201
- 在pycharm中创建django项目的方法步骤，分享给大家，具体如下：创建完成后，我们可以看看django项目是否可以启动在Termina
- 前段时间用C语言做了个字符版的推箱子，着实是比较简陋。正好最近用到了Python，然后想着用Python做一个图形界面的推箱子。这回可没有C
