亚洲乱论无码在线,中文字幕在线观看,亚洲av午夜福利精品一区二区

1.C語(yǔ)言實(shí)現(xiàn)

1.1代碼說(shuō)明

a 創(chuàng)建雙向鏈表：

在創(chuàng)建哈夫曼樹(shù)的過(guò)程中，需要不斷對(duì)結(jié)點(diǎn)進(jìn)行更改和刪除，所以選用雙向鏈表的結(jié)構(gòu)更容易

'''C
#include <stdlib.h>
#include <stdio.h>
#include <windows.h>
 
 
//哈夫曼樹(shù)結(jié)構(gòu)體，數(shù)據(jù)域存儲(chǔ)字符及其權(quán)重
typedef struct node
{
 char c;
 int weight;
 struct node *lchild, *rchild;
}Huffman, *Tree;
 
 
//雙向鏈表結(jié)構(gòu)體，數(shù)據(jù)域存儲(chǔ)哈夫曼樹(shù)結(jié)點(diǎn)
typedef struct list
{
 Tree root;
 struct list *pre;
 struct list *next;
}List, *pList;
 
 
//創(chuàng)建雙向鏈表，返回頭結(jié)點(diǎn)指針
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)：

解碼過(guò)程需要用到兩個(gè)棧，一個(gè)用來(lái)存放樹(shù)結(jié)點(diǎn)，一個(gè)用來(lái)存放碼0和1

'''C
#define STACK_INIT_SIZE 100//棧初始開(kāi)辟空間大小
#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)體，存放哈夫曼樹(shù)結(jié)點(diǎn)
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)建哈夫曼樹(shù)：

'''C
//通過(guò)雙向鏈表創(chuàng)建哈夫曼樹(shù)，返回根結(jié)點(diǎn)指針
Tree creatHuffman(pList head)
{
 pList list1 = NULL;
 pList list2 = NULL;
 pList index = NULL;
 Tree root = NULL;
 while(head->next != NULL)//鏈表只剩一個(gè)結(jié)點(diǎn)時(shí)循環(huán)結(jié)束，此結(jié)點(diǎn)數(shù)據(jù)域即為哈夫曼樹(shù)的根結(jié)點(diǎn)
 {
  list1 = head;
  list2 = head->next;
  index = list2->next;
  root = (Tree)malloc(sizeof(Huffman));
  while(index != NULL) //找到鏈表中權(quán)重最小的兩個(gè)結(jié)點(diǎn)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é)點(diǎn)的左右孩子
  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é)點(diǎn)字符統(tǒng)一設(shè)為空格，權(quán)重設(shè)為list1與list2權(quán)重之和
  root->c = ' ';
  root->weight = list1->root->weight + list2->root->weight;
  //list1數(shù)據(jù)域替換成新結(jié)點(diǎn)，并刪除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++;
 }
}
 
 
//通過(guò)哈夫曼樹(shù)編碼
void encodeHuffman(Tree T)
{  
 BiStack bs = stackInit();
 charStack cs = charStackInit();
 Huffman root = *T;  
 Tree temp = NULL;
 push(&bs, root);//根結(jié)點(diǎn)入棧
 while(bs.top != bs.base)//棧空表示遍歷結(jié)束
 {
  root = getTop(bs);
  temp = root.lchild; //先訪問(wèn)左孩子
  while(temp != NULL) //左孩子不為空
  {
//將結(jié)點(diǎn)左孩子設(shè)為空，代表已訪問(wèn)其左孩子
root.lchild = NULL;
pop(&bs);
push(&bs, root);
//左孩子入棧
root = *temp;
temp = root.lchild;
push(&bs, root);
//'0'入字符棧
charPush(&cs, '0');
  }
  temp = root.rchild;  //后訪問(wèn)右孩子  
  while(temp == NULL)  //右孩子為空，代表左右孩子均已訪問(wèn)，結(jié)點(diǎn)可以出棧 
  {
//結(jié)點(diǎn)出棧
root = pop(&bs);
//尋到葉子結(jié)點(diǎn)，可以得到結(jié)點(diǎn)中字符的編碼
if(root.c != ' ')
 traverseStack(cs, root.c);
charPop(&cs); //字符棧出棧
if(bs.top == bs.base) break; //根結(jié)點(diǎn)出棧，遍歷結(jié)束
//查看上一級(jí)結(jié)點(diǎn)是否訪問(wèn)完左右孩子  
root = getTop(bs);
temp = root.rchild;  
  }
  if(bs.top != bs.base)
  {
//將結(jié)點(diǎn)右孩子設(shè)為空，代表已訪問(wèn)其右孩子
root.rchild = NULL; 
pop(&bs);
push(&bs, root);
//右孩子入棧
root = *temp;
push(&bs, root);
//'1'入字符棧
charPush(&cs, '1');
  } 
 }
}

e解碼：

'''C
char decode[100];//記錄解碼得到的字符串
//通過(guò)哈夫曼樹(shù)解碼
void decodeHuffman(Tree T, char *code)
{
 int cnt = 0;
 Tree root;
 while(*code != '\0')//01編碼字符串讀完，解碼結(jié)束
 {
  root = T;
  while(root->lchild != NULL) //找到葉子結(jié)點(diǎn)
  {
if(*code != '\0')
{
 if(*code == '0')
  root = root->lchild;
 else
  root = root->rchild;
 code++;
}
else break;
  }
  decode[cnt] = root->c; //葉子結(jié)點(diǎn)存放的字符即為解碼得到的字符
  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請(qǐng)輸入編碼：\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運(yùn)行結(jié)果

2.Python實(shí)現(xiàn)

2.1代碼說(shuō)明

a創(chuàng)建哈夫曼樹(shù)：

#coding=gbk
 
import datetime
import time
from pip._vendor.distlib.compat import raw_input
 
#哈夫曼樹(shù)結(jié)點(diǎn)類(lèi)
class Huffman:
 def __init__(self, c, weight):
  self.c = c
  self.weight = weight
  self.lchild = None
  self.rchild = None
 
 #創(chuàng)建結(jié)點(diǎn)左右孩子 
 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
 
#通過(guò)列表創(chuàng)建哈夫曼樹(shù)，返回樹(shù)的根結(jié)點(diǎn)
def creatHuffman(list):
 while len(list) > 1:#列表只剩一個(gè)結(jié)點(diǎn)時(shí)循環(huán)結(jié)束，此結(jié)點(diǎn)即為哈夫曼樹(shù)的根結(jié)點(diǎn)
  i = 0
  j = 1
  k = 2
  while k < len(list):  #找到列表中權(quán)重最小的兩個(gè)結(jié)點(diǎn)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é)點(diǎn)字符統(tǒng)一設(shè)為空格，權(quán)重設(shè)為list1與list2權(quán)重之和
  if list[i].weight < list[j].weight:#list1和list2設(shè)為新結(jié)點(diǎn)的左右孩子
root.creat(list[i], list[j])
  else:
root.creat(list[j], list[i])
  #list1數(shù)據(jù)域替換成新結(jié)點(diǎn)，并刪除list2
  list[i] = root
  list.remove(list[j])
 return list[0]

b編碼：

#通過(guò)哈夫曼樹(shù)編碼
def encodeHuffman(T):
 code = [[], [], [], [], [], [], []]
 #列表實(shí)現(xiàn)棧結(jié)構(gòu)
 treeStack = []
 codeStack = []
 treeStack.append(T)
 while treeStack != []:  #?？沾肀闅v結(jié)束
  root = treeStack[-1]
  temp = root.lchild
  while temp != None:
#將結(jié)點(diǎn)左孩子設(shè)為空，代表已訪問(wèn)其左孩子
root.lchild = None  
#左孩子入棧 
treeStack.append(temp)
root = temp
temp = root.lchild
#0入編碼棧
codeStack.append(0)
  temp = root.rchild#后訪問(wèn)右孩子
  while temp == None:  #右孩子為空，代表左右孩子均已訪問(wèn)，結(jié)點(diǎn)可以出棧
root = treeStack.pop()  #結(jié)點(diǎn)出棧
#尋到葉子結(jié)點(diǎn)，可以得到結(jié)點(diǎn)中字符的編碼
if root.c != ' ':
 codeTemp = codeStack.copy()
 code[ord(root.c) - 97] = codeTemp  
if treeStack == []: #根結(jié)點(diǎn)出棧，遍歷結(jié)束
 break
codeStack.pop()  #編碼棧出棧
#查看上一級(jí)結(jié)點(diǎn)是否訪問(wèn)完左右孩子
root = treeStack[-1]
temp = root.rchild
  if treeStack != []:
treeStack.append(temp)  #右孩子入棧
root.rchild = None#將結(jié)點(diǎn)右孩子設(shè)為空，代表已訪問(wèn)其右孩子
codeStack.append(1)  #1入編碼棧
 return code

c解碼：

#通過(guò)哈夫曼樹(shù)解碼
def decodeHuffman(T, strCode):
 decode = []
 index = 0
 while index < len(strCode):  #01編碼字符串讀完，解碼結(jié)束
  root = T
  while root.lchild != None:  #找到葉子結(jié)點(diǎn)
if index < len(strCode):
 if strCode[index] == '0':
  root = root.lchild
 else:
  root = root.rchild
 index += 1
else:
 break
  decode.append(root.c)  #葉子結(jié)點(diǎn)存放的字符即為解碼得到的字符
 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請(qǐng)輸入編碼：\n")
 #哈夫曼樹(shù)在編碼時(shí)被破壞，必須重建哈夫曼樹(shù)
 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運(yùn)行結(jié)果

以上就是利用Python和C語(yǔ)言分別實(shí)現(xiàn)哈夫曼編碼的詳細(xì)內(nèi)容，更多關(guān)于Python哈夫曼編碼的資料請(qǐng)關(guān)注本站其它相關(guān)文章！

香港服務(wù)器租用

版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。

排名優(yōu)化：網(wǎng)站排名優(yōu)化方法有什么，如何做有效果

老域名：怎樣才算老域名，老域名建站有什么影響

內(nèi)容優(yōu)化：關(guān)鍵字排名要做哪些方面的優(yōu)化，怎樣做

技巧：網(wǎng)站轉(zhuǎn)化率究竟是什么，有什么提升的技巧

一下吧：外貿(mào)站優(yōu)化有哪些基本的做法和注意事項(xiàng)

概要：競(jìng)價(jià)推廣費(fèi)用大概要多少呢，競(jìng)價(jià)推廣好不好

一下吧：SEO中site是什么意思，作用和應(yīng)用是怎樣的

郵箱：付費(fèi)郵箱有哪些優(yōu)勢(shì)，付費(fèi)郵箱挑選要考慮什么

集群是什么意思：集群是什么意思，都有哪些優(yōu)勢(shì)呢