検索
ホームページバックエンド開発Python チュートリアルPythonとC言語をそれぞれ使用してハフマンコーディングを実装する方法

PythonとC言語をそれぞれ使用してハフマンコーディングを実装する方法

PHPz
PHPz
May 22, 2023 pm 01:46 PM
pythonC言語

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;                          
}

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++;
    }
}

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;
}

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;);
        }    
    }
}

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++;
    }
}

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); 
}

1.2运行结果

PythonとC言語をそれぞれ使用してハフマンコーディングを実装する方法

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]

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

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

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…")

2.2运行结果

PythonとC言語をそれぞれ使用してハフマンコーディングを実装する方法

以上がPythonとC言語をそれぞれ使用してハフマンコーディングを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事は亿速云で複製されています。侵害がある場合は、admin@php.cn までご連絡ください。
関連記事
Python：自動化、スクリプト、およびタスク管理Python：自動化、スクリプト、およびタスク管理Apr 16, 2025 am 12:14 AM

Pythonは、自動化、スクリプト、およびタスク管理に優れています。 1）自動化：OSやShutilなどの標準ライブラリを介してファイルバックアップが実現されます。 2）スクリプトの書き込み：Psutilライブラリを使用してシステムリソースを監視します。 3）タスク管理：スケジュールライブラリを使用してタスクをスケジュールします。 Pythonの使いやすさと豊富なライブラリサポートにより、これらの分野で優先ツールになります。

Pythonと時間：勉強時間を最大限に活用するPythonと時間：勉強時間を最大限に活用するApr 14, 2025 am 12:02 AM

限られた時間でPythonの学習効率を最大化するには、PythonのDateTime、時間、およびスケジュールモジュールを使用できます。 1. DateTimeモジュールは、学習時間を記録および計画するために使用されます。 2。時間モジュールは、勉強と休息の時間を設定するのに役立ちます。 3.スケジュールモジュールは、毎週の学習タスクを自動的に配置します。

Python：ゲーム、GUIなどPython：ゲーム、GUIなどApr 13, 2025 am 12:14 AM

PythonはゲームとGUI開発に優れています。 1）ゲーム開発は、2Dゲームの作成に適した図面、オーディオ、その他の機能を提供し、Pygameを使用します。 2）GUI開発は、TKINTERまたはPYQTを選択できます。 TKINTERはシンプルで使いやすく、PYQTは豊富な機能を備えており、専門能力開発に適しています。

Python vs. C：比較されたアプリケーションとユースケースPython vs. C：比較されたアプリケーションとユースケースApr 12, 2025 am 12:01 AM

Pythonは、データサイエンス、Web開発、自動化タスクに適していますが、Cはシステムプログラミング、ゲーム開発、組み込みシステムに適しています。 Pythonは、そのシンプルさと強力なエコシステムで知られていますが、Cは高性能および基礎となる制御機能で知られています。

2時間のPython計画：現実的なアプローチ2時間のPython計画：現実的なアプローチApr 11, 2025 am 12:04 AM

2時間以内にPythonの基本的なプログラミングの概念とスキルを学ぶことができます。 1.変数とデータ型、2。マスターコントロールフロー（条件付きステートメントとループ）、3。機能の定義と使用を理解する4。

Python：主要なアプリケーションの調査Python：主要なアプリケーションの調査Apr 10, 2025 am 09:41 AM

Pythonは、Web開発、データサイエンス、機械学習、自動化、スクリプトの分野で広く使用されています。 1）Web開発では、DjangoおよびFlask Frameworksが開発プロセスを簡素化します。 2）データサイエンスと機械学習の分野では、Numpy、Pandas、Scikit-Learn、Tensorflowライブラリが強力なサポートを提供します。 3）自動化とスクリプトの観点から、Pythonは自動テストやシステム管理などのタスクに適しています。

2時間でどのくらいのPythonを学ぶことができますか？2時間でどのくらいのPythonを学ぶことができますか？Apr 09, 2025 pm 04:33 PM

2時間以内にPythonの基本を学ぶことができます。 1。変数とデータ型を学習します。2。ステートメントやループの場合などのマスター制御構造、3。関数の定義と使用を理解します。これらは、簡単なPythonプログラムの作成を開始するのに役立ちます。

プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は？プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は？Apr 02, 2025 am 07:18 AM

10時間以内にコンピューター初心者プログラミングの基本を教える方法は？コンピューター初心者にプログラミングの知識を教えるのに10時間しかない場合、何を教えることを選びますか...

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

もっと見る

人気の記事

R.E.P.O.説明されたエネルギー結晶と彼らが何をするか（黄色のクリスタル）
4週間前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最高のグラフィック設定
4週間前By尊渡假赌尊渡假赌尊渡假赌
アサシンのクリードシャドウズ：シーシェルリドルソリューション
2週間前ByDDD
R.E.P.O.誰も聞こえない場合はオーディオを修正する方法
1 か月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.チャットコマンドとそれらの使用方法
1 か月前By尊渡假赌尊渡假赌尊渡假赌
もっと見る

ホットツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

SublimeText3 英語版

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

もっと見る

ホットトピック

Gmailメールのログイン入り口はどこですか？
7529
15
CakePHP チュートリアル
1378
52
Steamのアカウント名の形式は何ですか
81
11
Win11 Activation Key Permanent
54
19
NYTの接続はヒントと回答です
21
76
もっと見る