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

目录
  • 1.C语言实现
    • 1.1代码说明
    • 1.2运行结果
  • 2.Python实现
    • 2.1代码说明
    • 2.2运行结果

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

以上就是利用Python和C语言分别实现哈夫曼编码的详细内容,更多关于Python哈夫曼编码的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++实现哈夫曼树编码解码

    本文实例为大家分享了C++实现哈夫曼树的编码解码,供大家参考,具体内容如下 代码: #pragma once #include<iostream> #include<stack> using namespace std; #define m 20 stack<int> s; /*哈夫曼树结点类HuffmanNode声明*/ template<class T> class HuffmanNode { private: HuffmanNode<T>

  • C++实现哈夫曼编码

    本文实例为大家分享了C++实现哈夫曼编码的具体代码,供大家参考,具体内容如下 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int Max = 300; class tree{ public: char s; int num; tree *left; tree *right; tree(){ s= '!'; num =

  • C语言实现BMP图像处理(哈夫曼编码)

    哈夫曼(Huffman)编码是一种常用的压缩编码方法,是 Huffman 于 1952 年为压缩文本文件建立的.它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同.这些代码都是二进制码,且码的长度是可变的. 下面给出具体的 Huffman 编码算法: (1) 首先统计出每个符号出现的频率,上例 S0 到 S7 的出现频率分别为 4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14. (2) 从左到右把上述频率按从小到大的

  • 解析C++哈夫曼树编码和译码的实现

    一.背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化

  • Python完成哈夫曼树编码过程及原理详解

    哈夫曼树原理 秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧. https://www.jb51.net/article/97396.htm 其大概流程 哈夫曼编码代码 # 树节点类构建 class TreeNode(object): def __init__(self, data): self.val = data[0] self.priority = data[1] self.leftChild = None self.rightChild = None self.co

  • C语言实现哈夫曼编码

    本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下 代码来自于<小甲鱼C++快速入门> 主程序main.cpp #include "stdafx.h" #include <stdlib.h> #include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hl

  • 基于C++实现的哈夫曼编码解码操作示例

    本文实例讲述了基于C++实现的哈夫曼编码解码操作.分享给大家供大家参考,具体如下: 哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:'0'与'1'表示.编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加"0",如果为其右孩子,则在字符串后追加"1".结束条件为没有父节点.然后将字符串倒过来存入结点中. C++实现代码如下: #include<iostre

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

    目录 1.C语言实现 1.1代码说明 1.2运行结果 2.Python实现 2.1代码说明 2.2运行结果 1.C语言实现 1.1代码说明 a  创建双向链表: 在创建哈夫曼树的过程中,需要不断对结点进行更改和删除,所以选用双向链表的结构更容易 '''C #include <stdlib.h> #include <stdio.h> #include <windows.h> //哈夫曼树结构体,数据域存储字符及其权重 typedef struct node { char

  • 用R语言实现霍夫曼编码的示例代码

    可读性极低,而且其实也没必要用R语言写,图个乐罢了 p=c(0.4,0.2,0.2,0.1,0.1)###输入形如c(0.4,0.2,0.2,0.1,0.1)的概率向量,即每个待编码消息的发生概率 p1=p###将概率向量另存,最后计算编码效率要用 mazijuzhen=matrix(,nrow=length(p),ncol=length(p)-1)###码字矩阵:第i行对应向量p的第i个分量所对应的那个待编码消息的编码后的码字 group=matrix(c(1:length(p),rep(NA

  • Java利用哈夫曼编码实现字符串压缩

    赫夫曼编码基本介绍 1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一. 3) 赫夫曼编码广泛地用于数据文件压缩.其压缩率通常在 20%-90%之间 4) 赫夫曼码是可变字长编码(VLC)的一种.Huffman 于 1952 年提出一种编码方法,称之为最佳编码 在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you li

  • 使用C语言详解霍夫曼树数据结构

    1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,--,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径. 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1. b.结点的权和带权路径长度 在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权) 结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘

  • 基于C语言利用哈夫曼树实现文件压缩的问题

    一.哈夫曼树 具有n个权值的n个叶子结点,构造出一个二叉树,使得该树的带权路径长度(WPL)最小,则称此二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree). 注意:哈夫曼树是带权路径长度最短的树,且权值越大的叶子结点离根结点越近. 二.哈夫曼编码         哈夫曼编码是一种编码方式,又称"霍夫曼编码",其是可变字长的编码(VCL)的一种,是由霍夫曼于1952年提出的一种编码方式,有时被称为最佳编码,一般称为Huffman编码. 那么我们为什么要使用哈夫曼编码进行压缩?

  • Python描述数据结构学习之哈夫曼树篇

    前言 本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念.构造.代码实现以及哈夫曼编码,并用Python实现. 1. 基本概念 哈夫曼树(Huffman(Huffman(Huffman Tree)Tree)Tree),又称为最优二叉树,指的是带权路径长度最小的二叉树.树的带权路径常记作: 其中,nnn为树中叶子结点的数目,wkw_kwk​为第kkk个叶子结点的权值,lkl_klk​为第kkk个叶子结点与根结点的路径长度. 带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘

  • C语言实现哈夫曼树的方法

    本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下 准备工作: 1.定义一个结构体,表示一个节点.其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标 2.定义一个整形数组,用于存放各个节点的权值 3.定义一个整形数组,用于存放哈夫曼编码,当然也可以定义一个整形数组来存放哈夫曼编码 构建哈夫曼树: 1.给这个哈夫曼树创建一个结构体数组,其中分配的空间是2 * n - 1,因为我们都知道哈夫曼树的性质有一个是:给定n个叶子节点,那么由这n个叶子

  • 利用python/R语言绘制圣诞树实例代码

    目录 Python R语言 总结 圣诞节快到了,想着用python.r来画画圣诞树玩,就在网络上各种找方法,不喜勿喷哈~~ Python 1. import turtle screen = turtle.Screen() screen.setup(800,600) circle = turtle.Turtle() circle.shape('circle') circle.color('red') circle.speed('fastest') circle.up() square = turt

随机推荐