Community Learn Tools Library Leisure
search
English
Home > Backend Development > Python Tutorial > body text

How to implement Huffman coding using Python and C language respectively

PHPz
Release： 2023-05-22 13:46:06
forward
1110 people have browsed it

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 = &#39;a&#39;;
    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 = &#39;b&#39;;
    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 = &#39;c&#39;;
    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 = &#39;d&#39;;
    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 = &#39;e&#39;;
    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 = &#39;f&#39;;
    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 = &#39;g&#39;;
    temp1->root->weight = 65;
    temp1->root->lchild = NULL;
    temp1->root->rchild = NULL;
 
    return head;                          
}
Copy after login

b创建栈结构：

解码过程需要用到两个栈，一个用来存放树结点，一个用来存放码0和1

&#39;&#39;&#39;C
#define STACK_INIT_SIZE 100   //栈初始开辟空间大小
#define STACK_INCREMENT 10    //栈追加空间大小
 
//字符栈结构体，存放编码&#39;0&#39;和&#39;1&#39;
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 - &#39;a&#39;; 
    int i = 0;
    while(s.base != s.top)
    {
        stack[index][i] = *s.base;
        i++;
        s.base++;
    }
}
Copy after login

c 创建哈夫曼树：

&#39;&#39;&#39;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 = &#39; &#39;;
        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;
}
Copy after login

d编码：

&#39;&#39;&#39;C
char stack[7][10];             //记录a~g的编码
//遍历栈，得到字符c的编码
void traverseStack(charStack s, char c)
{
    int index = c - &#39;a&#39;; 
    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);
            //&#39;0&#39;入字符栈
            charPush(&cs, &#39;0&#39;);
        }
        temp = root.rchild;     //后访问右孩子     
        while(temp == NULL)     //右孩子为空，代表左右孩子均已访问，结点可以出栈 
        {
            //结点出栈
            root = pop(&bs);
            //寻到叶子结点，可以得到结点中字符的编码
            if(root.c != &#39; &#39;)
                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);
            //&#39;1&#39;入字符栈
            charPush(&cs, &#39;1&#39;);
        }    
    }
}
Copy after login

e解码：

&#39;&#39;&#39;C
char decode[100];   //记录解码得到的字符串
//通过哈夫曼树解码
void decodeHuffman(Tree T, char *code)
{
    int cnt = 0;
    Tree root;
    while(*code != &#39;\0&#39;)                  //01编码字符串读完，解码结束
    {
        root = T;
        while(root->lchild != NULL)       //找到叶子结点
        {
            if(*code != &#39;\0&#39;)
            {
                if(*code == &#39;0&#39;)
                    root = root->lchild;
                else
                    root = root->rchild;
                code++;
            }
            else break;
        }
        decode[cnt] = root->c;             //叶子结点存放的字符即为解码得到的字符
        cnt++;
    }
}
Copy after login

f主函数：

&#39;&#39;&#39;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+&#39;a&#39;, 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); 
}
Copy after login

1.2运行结果

How to implement Huffman coding using Python and C language respectively

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(&#39;a&#39;, 22))
    list.append(Huffman(&#39;b&#39;, 5))
    list.append(Huffman(&#39;c&#39;, 38))
    list.append(Huffman(&#39;d&#39;, 9))
    list.append(Huffman(&#39;e&#39;, 44))
    list.append(Huffman(&#39;f&#39;, 12))
    list.append(Huffman(&#39;g&#39;, 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(&#39; &#39;, 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]
Copy after login

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 != &#39; &#39;:
                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
Copy after login

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] == &#39;0&#39;:
                    root = root.lchild
                else:
                    root = root.rchild
                index += 1
            else:
                break
        decode.append(root.c)           #叶子结点存放的字符即为解码得到的字符
    return decode
Copy after login

d主函数：

if __name__ == &#39;__main__&#39;:
    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=&#39; : &#39;)
        for j in range(len(code[i])):
            print(code[i][j], end=&#39;&#39;)
        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=&#39;&#39;)
    print("\n\n")
    datetime = datetime.datetime.now()
    print(datetime.strftime("%Y-%m-%d\n%H:%M:%S"))
    input("Press Enter to exit…")
Copy after login

2.2运行结果

How to implement Huffman coding using Python and C language respectively

The above is the detailed content of How to implement Huffman coding using Python and C language respectively. For more information, please follow other related articles on the PHP Chinese website!

Related labels：
python c language
source：yisu.com
Previous article：How python function returns multiple values Next article：How does Python memory manager implement pooling technology?
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
Python/MySQL cannot persist integer data correctly No code is required here. I want to save a very long number because I'm making a game and ...
From 2024-04-04 19:09:44
0
1
367
Using selenium want to click and define URL in class I need another tip today. I'm trying to build Python/Selenium code and the idea is to clic...
From 2024-04-04 14:14:44
0
1
3492
Selenium + Python - inspect image via execute_script I need to verify that an image is displayed on the page using selenium in python. For exam...
From 2024-04-03 09:32:15
0
1
375
How to keep the first X rows and delete table rows I have a big table with millions of records in MySQLincident_archive, I want to sort the r...
From 2024-04-01 18:32:54
0
1
347
How to scrape specific Google Weather text using BeautifulSoup? How to find the course text "New York City, USA" in Python using BeautifulSoup? ...
From 2024-04-01 14:06:14
0
1
308
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template