利用Python和C語言分別實現(xiàn)哈夫曼編碼
更新時間：2022年07月14日 11:33:38 作者：觀察者555
這篇文章主要為大家詳細介紹了如何利用Python和C語言分別實現(xiàn)哈夫曼編碼，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
1.C語言實現(xiàn)
1.1代碼說明
a 創(chuàng)建雙向鏈表：
在創(chuàng)建哈夫曼樹的過程中，需要不斷對結(jié)點進行更改和刪除，所以選用雙向鏈表的結(jié)構(gòu)更容易
'''C
#include <stdlib.h>
#include <stdio.h>
#include <windows.h>
//哈夫曼樹結(jié)構(gòu)體，數(shù)據(jù)域存儲字符及其權(quán)重
typedef struct node
{
char c;
int weight;
struct node *lchild, *rchild;
}Huffman, *Tree;
//雙向鏈表結(jié)構(gòu)體，數(shù)據(jù)域存儲哈夫曼樹結(jié)點
typedef struct list
{
Tree root;
struct list *pre;
struct list *next;
}List, *pList;
//創(chuàng)建雙向鏈表，返回頭結(jié)點指針
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創(chuàng)建棧結(jié)構(gòu)：
解碼過程需要用到兩個棧，一個用來存放樹結(jié)點，一個用來存放碼0和1
'''C
#define STACK_INIT_SIZE 100 //棧初始開辟空間大小
#define STACK_INCREMENT 10 //棧追加空間大小
//字符棧結(jié)構(gòu)體，存放編碼'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;
}
//棧結(jié)構(gòu)體，存放哈夫曼樹結(jié)點
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 創(chuàng)建哈夫曼樹：
'''C
//通過雙向鏈表創(chuàng)建哈夫曼樹，返回根結(jié)點指針
Tree creatHuffman(pList head)
{
pList list1 = NULL;
pList list2 = NULL;
pList index = NULL;
Tree root = NULL;
while(head->next != NULL) //鏈表只剩一個結(jié)點時循環(huán)結(jié)束，此結(jié)點數(shù)據(jù)域即為哈夫曼樹的根結(jié)點
{
list1 = head;
list2 = head->next;
index = list2->next;
root = (Tree)malloc(sizeof(Huffman));
while(index != NULL) //找到鏈表中權(quán)重最小的兩個結(jié)點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設(shè)為新結(jié)點的左右孩子
if(list2->root->weight > list1->root->weight)
{
root->lchild = list1->root;
root->rchild = list2->root;
}
else
{
root->lchild = list2->root;
root->rchild = list1->root;
}
//新結(jié)點字符統(tǒng)一設(shè)為空格，權(quán)重設(shè)為list1與list2權(quán)重之和
root->c = ' ';
root->weight = list1->root->weight + list2->root->weight;
//list1數(shù)據(jù)域替換成新結(jié)點，并刪除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); //根結(jié)點入棧
while(bs.top != bs.base) //?？毡硎颈闅v結(jié)束
{
root = getTop(bs);
temp = root.lchild; //先訪問左孩子
while(temp != NULL) //左孩子不為空
{
//將結(jié)點左孩子設(shè)為空，代表已訪問其左孩子
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) //右孩子為空，代表左右孩子均已訪問，結(jié)點可以出棧
{
//結(jié)點出棧
root = pop(&bs);
//尋到葉子結(jié)點，可以得到結(jié)點中字符的編碼
if(root.c != ' ')
traverseStack(cs, root.c);
charPop(&cs); //字符棧出棧
if(bs.top == bs.base) break; //根結(jié)點出棧，遍歷結(jié)束
//查看上一級結(jié)點是否訪問完左右孩子
root = getTop(bs);
temp = root.rchild;
}
if(bs.top != bs.base)
{
//將結(jié)點右孩子設(shè)為空，代表已訪問其右孩子
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編碼字符串讀完，解碼結(jié)束
{
root = T;
while(root->lchild != NULL) //找到葉子結(jié)點
{
if(*code != '\0')
{
if(*code == '0')
root = root->lchild;
else
root = root->rchild;
code++;
}
else break;
}
decode[cnt] = root->c; //葉子結(jié)點存放的字符即為解碼得到的字符
cnt++;
}
}
f主函數(shù)：
'''C
void main()
{
pList pl = creatList();
printf("字符的權(quán)重如下\n");
for(pList l = pl; l->next != NULL; l = l->next)
printf("字符%c的權(quán)重是 %d\n", l->root->c, l->root->weight);
Tree T = creatHuffman(pl);
encodeHuffman(T);
printf("\n\n字符編碼結(jié)果如下\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("解碼結(jié)果如下：\n");
decodeHuffman(T, code);
printf("%s\n", decode);
printf("\n\n");
system("date /T");
system("TIME /T");
system("pause");
exit(0);
}
1.2運行結(jié)果
2.Python實現(xiàn)
2.1代碼說明
a創(chuàng)建哈夫曼樹：
#coding=gbk
import datetime
import time
from pip._vendor.distlib.compat import raw_input
#哈夫曼樹結(jié)點類
class Huffman:
def __init__(self, c, weight):
self.c = c
self.weight = weight
self.lchild = None
self.rchild = None
#創(chuàng)建結(jié)點左右孩子
def creat(self, lchild, rchild):
self.lchild = lchild
self.rchild = rchild
#創(chuàng)建列表
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
#通過列表創(chuàng)建哈夫曼樹，返回樹的根結(jié)點
def creatHuffman(list):
while len(list) > 1: #列表只剩一個結(jié)點時循環(huán)結(jié)束，此結(jié)點即為哈夫曼樹的根結(jié)點
i = 0
j = 1
k = 2
while k < len(list): #找到列表中權(quán)重最小的兩個結(jié)點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) #新結(jié)點字符統(tǒng)一設(shè)為空格，權(quán)重設(shè)為list1與list2權(quán)重之和
if list[i].weight < list[j].weight: #list1和list2設(shè)為新結(jié)點的左右孩子
root.creat(list[i], list[j])
else:
root.creat(list[j], list[i])
#list1數(shù)據(jù)域替換成新結(jié)點，并刪除list2
list[i] = root
list.remove(list[j])
return list[0]
b編碼：
#通過哈夫曼樹編碼
def encodeHuffman(T):
code = [[], [], [], [], [], [], []]
#列表實現(xiàn)棧結(jié)構(gòu)
treeStack = []
codeStack = []
treeStack.append(T)
while treeStack != []: #棧空代表遍歷結(jié)束
root = treeStack[-1]
temp = root.lchild
while temp != None:
#將結(jié)點左孩子設(shè)為空，代表已訪問其左孩子
root.lchild = None
#左孩子入棧
treeStack.append(temp)
root = temp
temp = root.lchild
#0入編碼棧
codeStack.append(0)
temp = root.rchild #后訪問右孩子
while temp == None: #右孩子為空，代表左右孩子均已訪問，結(jié)點可以出棧
root = treeStack.pop() #結(jié)點出棧
#尋到葉子結(jié)點，可以得到結(jié)點中字符的編碼
if root.c != ' ':
codeTemp = codeStack.copy()
code[ord(root.c) - 97] = codeTemp
if treeStack == []: #根結(jié)點出棧，遍歷結(jié)束
break
codeStack.pop() #編碼棧出棧
#查看上一級結(jié)點是否訪問完左右孩子
root = treeStack[-1]
temp = root.rchild
if treeStack != []:
treeStack.append(temp) #右孩子入棧
root.rchild = None #將結(jié)點右孩子設(shè)為空，代表已訪問其右孩子
codeStack.append(1) #1入編碼棧
return code
c解碼：
#通過哈夫曼樹解碼
def decodeHuffman(T, strCode):
decode = []
index = 0
while index < len(strCode): #01編碼字符串讀完，解碼結(jié)束
root = T
while root.lchild != None: #找到葉子結(jié)點
if index < len(strCode):
if strCode[index] == '0':
root = root.lchild
else:
root = root.rchild
index += 1
else:
break
decode.append(root.c) #葉子結(jié)點存放的字符即為解碼得到的字符
return decode
d主函數(shù)：
if __name__ == '__main__':
list = creatList()
print("字符的權(quán)重如下")
for i in range(len(list)):
print("字符{}的權(quán)重為: {}".format(chr(i+97), list[i].weight))
T = creatHuffman(list)
code = encodeHuffman(T)
print("\n字符編碼結(jié)果如下")
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("解碼結(jié)果如下：")
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運行結(jié)果
以上就是利用Python和C語言分別實現(xiàn)哈夫曼編碼的詳細內(nèi)容，更多關(guān)于Python哈夫曼編碼的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Django使用AJAX調(diào)用自己寫的API接口的方法
這篇文章主要介紹了Django使用AJAX調(diào)用自己寫的API接口的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-03-03
python支持多繼承,如果子類沒有重寫方法,則默認會調(diào)用父類的方法,本文主要介紹了一文講解python中的繼承沖突及繼承順序,具有一定的參考價值,感興趣的可以了解一下2024-03-03
玩過電腦游戲的同學(xué)對于外掛肯定不陌生,但是你在用外掛的時候有沒有想過外掛怎么制作出來的呢？現(xiàn)在來看一下怎么制作一個外掛,首先說下,這里的游戲外掛的概念,和那些大型網(wǎng)游里的外掛可不同,不能自動打怪,主要為了提高一下編程技術(shù),需要的朋友可以參考下2021-06-06
這篇文章主要為大家詳細介紹了PyQt5實現(xiàn)五子棋游戲，人機對弈，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
Python隨機生成均勻分布在單位圓內(nèi)的點代碼示例
這篇文章主要介紹了Python隨機生成均勻分布在單位圓內(nèi)的點代碼示例，具有一定參考價值，需要的朋友可以了解下。2017-11-11
python小白練習(xí)題之條件控制與循環(huán)控制
Python 中的條件控制和循環(huán)語句都非常簡單,也非常容易理解,與其他編程語言類似,下面這篇文章主要給大家介紹了關(guān)于python小白練習(xí)題之條件控制與循環(huán)控制的相關(guān)資料,需要的朋友可以參考下2021-10-10
平時打開一個網(wǎng)頁，除了文章的正文內(nèi)容，通常會有一大堆的導(dǎo)航，廣告和其他方面的信息。本文的目的，在于說明如何從一個網(wǎng)頁中提取出文章的正文內(nèi)容，而過渡掉其他無關(guān)的的信息。2014-06-06
這篇文章主要為大家詳細介紹了Python自定義時鐘類、定時任務(wù)類，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07
python 如何利用argparse解析命令行參數(shù)
這篇文章主要介紹了python 利用argparse解析命令行參數(shù)的步驟，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-09-09
python簡單實現(xiàn)操作Mysql數(shù)據(jù)庫
本文給大家分享的是在python中使用webpy實現(xiàn)簡單的數(shù)據(jù)庫增刪改查操作的方法，非常的簡單，有需要的小伙伴可以參考下2018-01-01