哈夫曼编码的实现c语言,哈夫曼树算法c语言

2022-08-25 06:33:25 分类：python 阅读()

　　哈夫曼编码的实现c语言,哈夫曼树算法c语言

　　这篇文章主要为大家详细介绍了如何利用计算机编程语言和C语言分别实现哈夫曼编码，文中的示例代码讲解详细，感兴趣的小伙伴可以跟随小编一起学习一下

　　

目录
1.C语言实现1.1代码说明1.2运行结果2.计算机编程语言实现2.1代码说明2.2运行结果

　　

1.C语言实现

　　

1.1代码说明

　　a创建双向链表：

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

　　 C

　　#包含标准库

　　#包含标准视频

　　#包含windows.h

　　//哈夫曼树结构体，数据域存储字符及其权重

　　数据类型说明结构节点

　　{

　　char c；

　　（同Internationalorganizations）国际组织重量；

　　结构节点*lchild，* rchild

　　}霍夫曼，*树；

　　//双向链表结构体，数据域存储哈夫曼树结点

　　数据类型说明结构列表

　　{

　　树根；

　　结构列表*之前

　　结构列表*下一个

　　}列表，* pList

　　//创建双向链表，返回头结点指针

　　pList creatList()

　　{

　　pList head=(pList)malloc(sizeof(List))；

　　pList temp1=头

　　pList temp 2=(pList)malloc(sizeof(List))；

　　temp 1-pre=NULL；

　　temp 1-next=temp 2；

　　temp1-root=(树)malloc(sizeof(霍夫曼));

　　temp 1-root-c= a ；

　　温度1-根-重量=22；

　　temp 1-root-l child=NULL；

　　temp 1-root-rchild=NULL；

　　温度2-pre=温度1；

　　温度1=温度2

　　temp 2=(pList)malloc(sizeof(List))；

　　temp 1-next=temp 2；

　　temp1-root=(树)malloc(sizeof(霍夫曼));

　　temp 1-root-c= b ；

　　温度1-根-重量=5；

　　temp 1-root-l child=NULL；

　　temp 1-root-rchild=NULL；

　　温度2-pre=温度1；

　　温度1=温度2

　　temp 2=(pList)malloc(sizeof(List))；

　　temp 1-next=temp 2；

　　temp1-root=(Tree)malloc(sizeof(霍夫曼));

　　temp 1-root-c= c ；

　　温度1-根-重量=38；

　　temp 1-root-l child=NULL；

　　temp 1-root-rchild=NULL；

　　温度2-pre=温度1；

　　温度1=温度2

　　temp 2=(pList)malloc(sizeof(List))；

　　temp 1-next=temp 2；

　　temp1-root=(树)malloc(sizeof(霍夫曼));

　　temp 1-root-c= d ；

　　温度1-根-重量=9；

　　temp 1-root-l child=NULL；

　　temp 1-root-rchild=NULL；

　　温度2-p

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

　　

　　以上就是利用Python和C语言分别实现哈夫曼编码的详细内容，更多关于Python哈夫曼编码的资料请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

标签： python

相关文章阅读

  • c语言调用退出函数 c语言退出整个程序怎么写
  • c语言中怎么给函数初始化 c语言的初始化语句
  • c语言编写函数计算平均值 c语言求平均函数
  • 详解c语言中的字符串数组是什么,详解c语言中的字符串数组结构,详解C语言中的字符串数组
  • 表达式求值c++实现,c语言实现表达式求值
  • 看懂c语言基本语法,C语言详解,C语言的基本语法详解
  • 用c语言实现快速排序算法,排序算法设计与实现快速排序C语言,C语言实现快速排序算法实例
  • 深入解析c语言中函数指针的定义与使用方法,深入解析c语言中函数指针的定义与使用情况,深入解析C语言中函数指针的定义与使用
  • 描述E-R图,E-R图举例,关于C语言中E-R图的详解
  • 折半查找法C语言,折半查找算法(算法设计题)
  • 折半查找法C语言,c语言折半法查找数据,C语言实现折半查找法（二分法）
  • 扫雷小游戏c++代码设计,c语言扫雷游戏源代码,C语言实现扫雷小游戏详细代码
  • 怎样统计程序代码行数,C语言统计行数,C#程序员统计自己的代码行数
  • 基于c语言的贪吃蛇游戏程序设计,用c语言编写贪吃蛇游戏程序,C语言实现简单的贪吃蛇游戏
  • 图的两种遍历算法,图的遍历算法代码c语言,Python算法之图的遍历
    • 留言与评论（共有 条评论）
       
    验证码：