霍夫曼演算法代碼_哈夫曼編碼的演算法代碼

① 哈夫曼編碼的演算法代碼是什麼

// 哈夫曼編碼(演算法)#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char *HuffmanCode; //動態分配數組，存儲哈夫曼編碼typedef struct
{
unsigned int weight; //用來存放各個結點的權值
unsigned int parent,LChild,RChild; //指向雙親、孩子結點的指針
} HTNode, *HuffmanTree; //動態分配數組，存儲哈夫曼樹//選擇兩個parent為0，且weight最小的結點s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s2=min;
}//構造哈夫曼樹ht。w存放已知的n個權值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n)
{
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1; i<=n; i++) //1--n號存放葉子結點，初始化
{
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非葉子結點初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //創建非葉子結點，建哈夫曼樹
{
//在(*ht)[1]~(*ht)[i-1]的范圍內選擇兩個parent為0
//且weight最小的結點，其序號分別賦值給s1、s2
Select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
} //哈夫曼樹建立完畢//從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n個編碼的頭指針
cd=(char *)malloc(n*sizeof(char)); //分配求當前編碼的工作空間
cd[n-1]='\0'; //從右向左逐位存放編碼，首先存放編碼結束符
for(i=1; i<=n; i++) //求n個葉子結點對應的哈夫曼編碼
{
start=n-1; //初始化編碼起始指針
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //從葉子到根結點求編碼
if( (*ht)[p].LChild==c)
cd[--start]='0'; //左分支標0
else
cd[--start]='1'; //右分支標1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個編碼分配空間
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]);
printf("\n");
}void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;
printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}

② 求高手寫個關於哈夫曼編碼的演算法

恩，樓主這個題目相當復雜啊
首先讀文件，按字元讀。一個一個讀，統計所有出現字元的頻數。
記錄到一個鏈表裡吧
第二步，建樹。霍夫曼樹……復雜程度可想而知。
Huffman 演算法
思想：權大的外結點靠近根，權小的遠離根。
演算法：從m個權值中找出兩個最小值W1，W2構成
w
w1 w2 W=W1+W2表通過該結點的頻度。
依次往上找……
估計你的100個字元的短文，出現的字元數量估計平均有20個左右，建的樹的高度就12就算低的。
3 按結點到跟的距離編碼，從左到右編碼為0 1 0 1依次進行……
生成霍夫曼編碼
把每個字幕的二進制編碼記錄，打出，這就是密碼表
然後對原來的文件進行列印，碰到相應的字母列印出相應的密碼（二進制啊，汗……）
估計只有拿到密碼才能看明白那一串的01！！
如果某一電文出現的字元為D={M，S，T，A，Q， K} ，每個字元出現的頻率為W={10，29，4，8，15，7}，
則用改演算法生成的密碼為：
S：0 A：100 M：101 Q：111
T：1100 K：1101
100 1100 101 0 111 0 1101 0 0 密文的含義是：
A T M S Q S K S S

③ 霍夫曼編碼演算法在何時效率最高何時效率最低

霍夫曼(Huffman)編碼是1952年為文本文件而建立，是一種統計編碼。屬於無損壓縮編碼。
霍夫曼編碼的碼長是變化的，對於出現頻率高的信息，編碼的長度較短;而對於出現頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小於實際信息的符號長度。
霍夫曼計演算法步驟進行：
l)將信號源的符號按照出現概率遞減的順序排列。
2)將兩個最小出現概率進行合並相加，得到的結果作為新符號的出現概率。
3)重復進行步驟1和2直到概率相加的結果等於1為止。
4)在合並運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。
5)記錄下概率為1處到當前信號源符號之間的0，l序列，從而得到每個符號的編碼。
霍夫曼計演算法舉例：

霍夫曼優點：
霍夫曼碼的碼長雖然是可變的，但卻自帶同步代碼。例如，碼串中的第1位為0，那末肯定是符號A，因為表示其他符號的代碼沒有一個是以0開始的，因此下一位就表示下一個符號代碼的第1位。同樣，如果出現「110」，那麼它就代表符號D。如果事先編寫出一本解釋各種代碼意義的「詞典」，即碼簿，那麼就可以根據碼簿一個碼一個碼地依次進行解碼。
霍夫曼編碼方法的編碼效率比香農-范諾編碼效率高一些
霍夫曼缺點：
① 霍夫曼碼沒有錯誤保護功能，在解碼時，如果碼串中沒有錯誤，那麼就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪僅是1位出現錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現象稱為錯誤傳播(error propagation)。計算機對這種錯誤也無能為力，說不出錯在哪裡，更談不上去糾正它。
② 霍夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然後再解碼，這就需要在存儲代碼之前加以考慮。硬體實現有難度。
③ 由於"0"與"1"的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數據壓縮性能。
④ 壓縮與還原相當費時。
⑤ 對不同信號源的編碼效率不同

④ 哈夫曼編碼 C源代碼

#include <stdio.h>
#define MAXBIT 10 /*定義哈夫曼編碼的最大長度*/
#define MAXVALUE 10000 /*定義最大權值*/
#define MAXLEAF 30 /*定義哈夫曼樹中最多葉子節點個數*/
#define MAXNODE MAXLEAF*2-1 /*哈夫曼樹最多結點數*/
typedef struct { /*哈夫曼編碼信息的結構*/
int bit[MAXBIT];
int start;}Hcodetype;
typedef struct { /*哈夫曼樹結點的結構*/
int weight;
int parent;
int lchild;
int rchild;
}Hnodetype;
void huffmantree(Hnodetype huffnode[MAXNODE],int n) /*構造哈夫曼樹的函數*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) /*存放哈夫曼樹結點的數組huffnode[]初始化*/
{
huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i<n;i++) /*輸入入N個葉子節點的權值*/
{
printf("please input %d character's weight\n",i);
scanf("%d",&huffnode[i].weight);
}
for(i=0;i<n-1;i++) /*開始循環構造哈夫曼樹*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(huffnode[j].weight<m1&&huffnode[j].parent==-1)
{
m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;
}
else if(huffnode[j].weight<m2&&huffnode[j].parent==-1)
{
m2=huffnode[j].weight;x2=j;
}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
}
void main()
{
Hnodetype huffnode[MAXNODE];
Hcodetype huffcode[MAXLEAF],cd;
int i,j,c,p,n;
printf("please input n\n");
scanf("%d",&n); /*輸入葉子節點個數*/
huffmantree(huffnode,n); /*建立哈夫曼樹*/
for(i=0;i<n;i++) /*該循環求每個葉子節點對應字元的哈夫曼編碼*/
{
cd.start=n-1;c=i;
p=huffnode[c].parent;
while(p!=-1)
{
if(huffnode[p].lchild==c) cd.bit[cd.start]=0;
else cd.bit[cd.start]=1;
cd.start--;c=p;
p=huffnode[c].parent;
}
for(j=cd.start+1;j<n;j++) /*保存求出的每個葉節點的哈夫曼編碼和編碼的起始位*/
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
for(i=0;i<n;i++) /*輸出每個葉子節點的哈夫曼編碼*/
{
printf("%d character is:",i);
for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf("\n");
}
}

⑤ Huffman編碼的演算法

霍夫曼編/解碼器c/c++代碼#include<iostream.h>#include"stdio.h" #include"stdlib.h"#include"string.h"typedef char ElemType;typedef struct { ElemType elem; unsigned int m_weight; unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char** HuffmanCode;typedef int Status; typedef struct weight{ char elem; unsigned int m_weight;}Weight;void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);void Select(HuffmanTree,int,int *,int *); void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);Status main(void){ HuffmanTree HT; HuffmanCode HC; Weight *w; char c; int i,n; int wei; printf("請輸入要編碼的字元種類數:" ); scanf("%d",&n); w=(Weight *)malloc(n*sizeof(Weight)); for(i=0;i<n;i++) { printf("輸入元素和所佔比例:"); scanf("%1s%d",&c,&wei); w[i].elem=c; w[i].m_weight=wei;} HuffmanCoding(&HT,&HC,w,n); OutputHuffmanCode(HT,HC,n); return 1;} void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n){int i,m,s1,s2,start,c,f; char *cd; if(n<=1) return; m=2*n-1; (*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1;i<=n;++i){ (*HT)[i].elem=w[i-1].elem; (*HT)[i].m_weight=w[i-1].m_weight; (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; } for(;i<=m;++i) { (*HT)[i].elem='0'; (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;} for(i=n+1;i<=m;++i){ Select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=i;(*HT)[s2].parent=i; (*HT)[i].lchild=s1;(*HT)[i].rchild=s2; (*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;} (*HC)=(HuffmanCode)malloc(n*sizeof(char*)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) { start=n-1; for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) {if((*HT)[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } (*HC)[i]=(char *)malloc((n-start)*sizeof(char)); strcpy((*HC)[i],&cd[start]); } } void Select(HuffmanTree HT,int n,int *s1,int *s2){ int i; (*s1)=(*s2)=0; for(i=1;i<=n;i++) { if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0) { if(HT[i].m_weight<HT[(*s1)].m_weight) { (*s2)=(*s1); (*s1)=i; } else (*s2)=i; } if(((*s1)==0||(*s2)==0)&&HT[i].parent==0) { if((*s1)==0) (*s1)=i; else if((*s2)==0) { if(HT[i].m_weight<HT[(*s1)].m_weight) { (*s2)=(*s1); (*s1)=i; } else (*s2)=i; } } } if((*s1)>(*s2)) { i=(*s1); (*s1)=(*s2); (*s2)=i; } }void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) { char SCE[100],K; printf("\nnumber--element--weight--huffman code\n"); for(int i=1;i<=n;i++) printf(" %-5d %-5c %-7d %-8s\n",i,HT[i].elem,HT[i].m_weight,HC[i]); printf("input the scentence :\n"); for(int j=0;K!='q';j++){cin>>K;SCE[j]=K;} printf("output the code :\n"); for(int k=0;k<=j-2;k++) for(int m=1;m<=n;m++) if(SCE[k]==HT[m].elem)cout<<HC[m]<<" ";}

⑥ 3. 找到最優樹(霍夫曼樹)問題分別用C、C++進行演算法描述、流程圖以及可實現的具體程序

霍夫曼樹：帶權路徑長度達到最小的擴充二叉樹即為霍夫曼樹。
在霍夫曼樹中，權值大的結點離根最近。
霍夫曼演算法
(1) 由給定的n個權值{w0, w1, w2, …, wn-1}，構造具有n棵擴充二叉樹的森林F = {T0, T1, T2, …, Tn-1}，其中每一棵擴充二叉樹Ti只有一個帶有權值wi的根結點，其左、右子樹均為空。
(2) 重復以下步驟, 直到F中僅剩下一棵樹為止：
① 在F中選取兩棵根結點的權值最小的擴充二叉樹, 做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。
② 在F中刪去這兩棵二叉樹。
③ 把新的二叉樹加入F。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

typedef struct
{
unsigned int Weight;
unsigned int Parent;
unsigned int lChild;
unsigned int rChild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

int LookFor(char *str,char letter,int count);
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count);
void HuffmanCoding(HuffmanTree *HT,
HuffmanCode *HC,
int *Weight,
int Count);
void Select(HuffmanTree HT,int Count,int *s1,int *s2);
int main()
{
HuffmanTree HT;
HuffmanCode HC;
char Data[100];
char *WhatLetter;
int *Weight;
int Count;
int i;

printf("Please input the line:");
/* Example: aaaaaaaaaaaaaabcccccc*/
scanf("%s",Data);
printf("\n");

OutputWeight(Data,strlen(Data),
&WhatLetter,
&Weight,
&Count);

HuffmanCoding(&HT,&HC,Weight,Count);

printf(" Letter Weight Code\n");
for(i=0;i<Count;i++)
{
printf(" %c ",WhatLetter[i]);
printf("%d ",Weight[i]);
printf("%s\n",HC[i+1]);
}
printf("\n");
getch();
return 0;
}

void HuffmanCoding(HuffmanTree *HT,
HuffmanCode *HC,
int *Weight,
int Count)
{
int i;
int s1,s2;
int TotalLength;
HuffmanTree p;
char* cd;
unsigned int c;
unsigned int f;
int start;

if(Count<=1) return;
TotalLength=Count*2-1;
(*HT)=(HuffmanTree)malloc((TotalLength+1)*sizeof(HTNode));

p=((*HT)++);
for(i=1;i<=Count;i++)
{
(*HT)[i].Parent=0;
(*HT)[i].rChild=0;
(*HT)[i].lChild=0;
(*HT)[i].Weight=(*Weight);
Weight++;
}
for(i=Count+1;i<=TotalLength;i++)
{
(*HT)[i].Weight=0;
(*HT)[i].Parent=0;
(*HT)[i].lChild=0;
(*HT)[i].rChild=0;
}
/*///////////////////Create HuffmanTree////////////////*/
for(i=Count+1;i<=TotalLength;++i)
{
Select((*HT),i-1,&s1,&s2);
(*HT)[s1].Parent=i;
(*HT)[s2].Parent=i;
(*HT)[i].lChild=s1;
(*HT)[i].rChild=s2;
(*HT)[i].Weight=(*HT)[s1].Weight+(*HT)[s2].Weight;
}
/*///////////////////Output Huffman Code///////////////*/
(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
cd=(char*)malloc(Count*sizeof(char));
cd[Count-1]='\0';
for(i=1;i<=Count;++i)
{
start=Count-1;
for(c=i,f=(*HT)[i].Parent;f!=0;c=f,f=(*HT)[f].Parent)
{
if((*HT)[f].lChild==c)
cd[--start]='0';
else
cd[--start]='1';
(*HC)[i]=(char*)malloc((Count-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}
}
void Select(HuffmanTree HT,int Count,int *s1,int *s2)
/*/(*s1) is smallest,(*s2) is smaller.*/
{
int i;
unsigned int temp1=0;
unsigned int temp2=0;
unsigned int temp3;
for(i=1;i<=Count;i++)
{
if(HT[i].Parent==0)
{
if(temp1==0)
{
temp1=HT[i].Weight;
(*s1)=i;
}
else
{
if(temp2==0)
{
temp2=HT[i].Weight;
(*s2)=i;
if(temp2<temp1)
{
temp3=temp2;
temp2=temp1;
temp1=temp3;

temp3=(*s2);
(*s2)=(*s1);
(*s1)=temp3;
}
}
else
{
if(HT[i].Weight<temp1)
{
temp2=temp1;
temp1=HT[i].Weight;

(*s2)=(*s1);
(*s1)=i;
}
if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
{
temp2=HT[i].Weight;
(*s2)=i;
}
}
}
}
}
}

int LookFor(char *str,char letter,int count)
{
int i;
for(i=0;i<count;i++)
{
if(str[i]==letter) return i;
}
return -1;
}
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count)
{
int i;
char* Letter=(char*)malloc(Length);
int* LetterCount=(int *)malloc(Length);
int AllCount=0;
int Index;
int Sum=0;
float Persent=0;

for(i=0;i<Length;i++)
{
if(i==0)
{
Letter[0]=Data[i];
LetterCount[0]=1;
AllCount++;
}
else
{
Index=LookFor(Letter,Data[i],AllCount);
if(Index==-1)
{
Letter[AllCount]=Data[i];
LetterCount[AllCount]=1;
AllCount++;
}
else
{
LetterCount[Index]++;
}
}
}
for(i=0;i<AllCount;i++)
{
Sum=Sum+LetterCount[i];
}
(*Weight)=(int*)malloc(AllCount);
(*WhatLetter)=(char*)malloc(AllCount);

for(i=0;i<AllCount;i++)
{
Persent=(float)LetterCount[i]/(float)Sum;
(*Weight)[i]=(int)(1000*Persent);
(*WhatLetter)[i]=Letter[i];
}
(*Count)=AllCount;
}

⑦ huffman演算法，解決文件壓縮，先讀入一個文件，再將文件變成huffman編碼，在解壓成原文件。

//這個是關於huffmantree構造的代碼
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
#include <queue>
using namespace std;

struct HuffNode
{
char chr;
int val_int;
vector<int> code;
HuffNode * left;
HuffNode * right;
bool leaf;
HuffNode(int val,HuffNode * l,HuffNode * r)
{
this->val_int=val;
this->left=l;
this->right=r;
}
};

class HuffTree
{
public:
HuffTree()
{
root=NULL;
}
HuffTree(multimap<int,char> &rhs)
{
root=creatTree(rhs);
}
map<char,vector<int>> gethuffcode()
{
return this->huffcode;
}
bool operator<(HuffNode* p)
{
return (this->root->val_int)<(p->val_int);
}
bool less(HuffNode * s,HuffNode * t)
{
return (s->val_int)<(t->val_int);
}
//用於檢查該huffman tree 是否構造成功。
void inorder_recursive(void (*visit)(int x))
{
inorder_recursive(root,visit);
}

//利用level_order() 得到每一個節點的huffmancode
void level_order()
{
queue<HuffNode*> temp;
if(root!=NULL)
{
temp.push(root);
}

while (!temp.empty())
{
(calculateCode)(temp.front());//調用函數，計算該節點的huffmancode

if(temp.front()->left)
{
temp.push(temp.front()->left);
}

if(temp.front()->right)
{
temp.push(temp.front()->right);
}

temp.pop();
}
}

private:
//calculate the huffman code of each HuffNode
void calculateCode(HuffNode* & t)
{
if(t->left )
{

t->left->code=t->code;
t->left->code.push_back(0);
}
if(t->right)
{
t->right->code=t->code;
t->right->code.push_back(1);
}
if(t->leaf)
{
this->huffcode.insert(make_pair(t->chr,t->code));
}
}

HuffNode * root;
map<char,vector<int> > huffcode;//store the huffcode of the huffnode
void inorder_recursive(HuffNode* t, void (*visit)(int x))
{
if(t==NULL)
{
return;
}
else
{
inorder_recursive(t->left,visit);
(visit)(t->val_int);
inorder_recursive(t->right,visit);
}
}
//構造HuffTree
HuffNode * creatTree(multimap<int,char> & rhs)
{
vector<HuffNode*> v_huffNode;
multimap<int,char>::iterator it=rhs.begin();
while (it!=rhs.end ())
{
HuffNode * p=new HuffNode ((*it).first,NULL,NULL);
p->chr=(*it).second;
p->leaf=true;
v_huffNode.push_back(p);
it++;
}

while(v_huffNode.size()>1)
{
sort(v_huffNode.begin(),v_huffNode.end());

HuffNode * ptrHuff1=*v_huffNode.begin();
int temp1=(*v_huffNode.begin())->val_int;
v_huffNode.erase(v_huffNode.begin());
HuffNode * ptrHuff2=*v_huffNode.begin();
int temp2=(*v_huffNode.begin())->val_int;
v_huffNode.erase(v_huffNode.begin());
HuffNode * ptrHuff=new HuffNode(temp1+temp2,ptrHuff1,ptrHuff2);
v_huffNode.push_back(ptrHuff);
}
return *v_huffNode.begin();
}

};
//用於遍歷檢查
void print(int x)
{
cout<<x<<" ";
}

map<char,vector<int> > huffcode_turnBinary(const multimap<int,char> & rhs)
{
multimap<int,char> another_map(rhs);
HuffTree huftree1(another_map);//構造huffTree
//檢查構造的hufftree 利用中序
/*
cout<<"已經構造完hufftree"<<endl;
cout<<"檢查構造的huffTree：use inorder"<<endl;
huftree1.inorder_recursive(print);
cout<<endl;
*/
huftree1.level_order();

map<char,vector<int> > result=huftree1.gethuffcode();

return result;

}
//關於將文件解壓會的代碼
//#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <map>
#include <iomanip>
#include "changemap.h"
#include "readwenjian.h"
using namespace std;

void huff_to_wenjian(char * f,const map<char, vector<int> > &rhs)
{

map<vector<int>,char> huff_code_new = changemap1(rhs);//huff_code_new 用於將huffcode轉為正常文件
map<vector<int>,char>::iterator huff_code_new_it=huff_code_new.begin();
cout<<"用於解碼的Huffcode如下"<<endl;
cout<<setw(8)<<"HuffCode"<<setw(8)<<"字元"<<endl;
while(huff_code_new_it!=huff_code_new.end())
{

( (*huff_code_new_it).first.begin(),(*huff_code_new_it).first.end(),ostream_iterator<int>(cout,""));
cout<<setw(4)<<(*huff_code_new_it).second<<endl;
huff_code_new_it++;

}
cout<<"下面開始進行解碼先讀取huffcode文件"<<endl;
system("pause");
system("cls");

cout<<"讀取huffcode 文件"<<endl;
vector<char> ch_huff_wenjian=readwenjian(f);
vector<int> v_hu_wenjian;//文件的huffcode全部將用它進行下一步的解碼
//由 char 0 1轉化為int 0 1
vector<char>::iterator it_ch=ch_huff_wenjian.begin();
while(it_ch!=ch_huff_wenjian.end())
{
v_hu_wenjian.push_back( (*it_ch)-'0' );
it_ch++;
}
ch_huff_wenjian.clear();

//檢查讀入huffcode的情況

(v_hu_wenjian.begin(),v_hu_wenjian.end(),ostream_iterator<int> (cout,""));
cout<<"讀入的是01文件，下面開始解碼！"<<endl;
system("pause");
system("cls");

cout<<"解碼正在進行中，可能你要等一下時間…………"<<endl;
vector<int>::iterator v_it=v_hu_wenjian.begin();
vector<int> temp_huff;
string wenjian;//用於存放轉化的文件
map<vector<int>,char>::iterator index=huff_code_new.begin();
while(v_it!=v_hu_wenjian.end())
{
temp_huff.push_back((*v_it) );
index=huff_code_new.find(temp_huff);
if(index!=huff_code_new.end())
{
wenjian.push_back((*index).second);
temp_huff.clear();
}
v_it++;
}
cout<<"huffcode 文件已經成功解碼！"<<endl;
cout<<"解碼文件如下"<<endl;
system("pause");
cout<<wenjian<<endl;

ofstream output;
output.open("newwenjian.txt");
output<<wenjian;
output.close();
wenjian.clear();
cout<<"已經成功將文件儲存在newwenjian.txt中！"<<endl;
cout<<"程序運行結束!"<<endl;
system("pause");

return;
}

⑧ 哈夫曼編碼的演算法代碼

//本程序根據26個英文字母出現的頻度，得到了它們的一種哈夫曼編碼方案 //by jirgal 2005.4.18 #include<iostream.h> #include<iomanip.h> #define NUM 26 //字母數 #define TNUM 51 // #define LTH 15 //編碼最大長度 class Node { public: char data; int weight; int parent; int lchild; int rchild; }; void main() { char ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l', 'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26個字母 int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42, 339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出現頻率 Node nodes[TNUM]; //用對象數組存儲哈夫曼樹 int i,j,one,two,a,b; int hc[NUM][LTH]; //用於存儲編碼 int m,n; //初始化數組 for(i=0;i<NUM;i++) { nodes[i].data=ch[i]; nodes[i].weight=weit[i]; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } for(i=NUM;i<TNUM;i++) { nodes[i].data='@'; nodes[i].weight=-1; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } //建立哈夫曼樹 for(i=NUM;i<TNUM;i++) { a=b=-1; one=two=10000; //最大權數 for(j=0;j<i;j++) { if(nodes[j].parent==-1) if(nodes[j].weight<=two) one=two; two=nodes[j].weight; a=b; b=j; } else if(nodes[j].weight>two&&nodes[j].weight<=one) { one=nodes[j].weight; a=j; } } }//for語句得到 parent=-1(即尚沒有父結點)且weight最小的兩個結點 nodes[a].parent=i; nodes[b].parent=i; nodes[i].lchild=a; nodes[i].rchild=b; nodes[i].weight=nodes[a].weight+nodes[b].weight; } //初始化hc for(i=0;i<LTH;i++) { for(j=0;j<NUM;j++) { hc[j][i]=7; } } //編碼 for(i=0;i<NUM;i++) { j=LTH-1; for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent) { if(nodes[n].lchild==m) { hc[i][j]=0; } else { hc[i][j]=1; } j--; } } //輸出 nodes cout<<"HuffmanTree:"<<endl; cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) <<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; for(i=0;i<TNUM;i++) { cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) <<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; } //輸出編碼 cout<<endl<<"Result:"<<endl; cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; for(i=0;i<NUM;i++) { cout<<setw(6)<<ch[i]<<setw(8)<<weit[i]; cout<<" "; for(j=0;j<LTH;j++) { if(hc[i][j]!=7) { cout<<hc[i][j]; } } cout<<endl; } cout<<"\nDone.\n"<<endl; }

⑨ 霍夫曼編程採用的是哪種編程原理

霍夫曼編碼的matlab實現一、實驗內容：用Matlab語言編程實現霍夫曼（Huffman）編碼。二、實驗原理及編碼步驟：霍夫曼（Huffman）編碼演算法是滿足前綴條件的平均二進制碼長最短的編-源輸出符號，而將較短的編碼碼字分配給較大概率的信源輸出。演算法是：在信源符號集合中，首先將兩個最小概率的信源輸出合並為新的輸出，其概率是兩個相應輸出符號概率之和。這一過程重復下去，直到只剩下一個合並輸出為止，這個最後的合並輸出符號的概率為1。這樣就得到了一張樹圖，從樹根開始，將編碼符號1和0分配在同一節點的任意兩分支上，這一分配過程重復直到樹葉。從樹根到樹葉途經支路上的編碼最後就構成了一組異前置碼，就是霍夫曼編碼輸出。

⑩ Huffman編碼

這個是一個簡單的，沒有文件導入，需要編碼的是自己輸入的數組，你將它換成文件讀取基本就可以實現對文章中的字元進行Huffman編碼，這是我自己曾經做的一個程序，是VC6.0的,沒有解碼部分，解碼部分你反過來推一下演算法然後編一下代碼就可以了。我還有一個是文件是用matlab作的huffman編碼，你要的話給我郵箱，我給你發過去。
#include<iostream.h>
#include<string.h>
#define N 100
typedef struct
{
int wei; //權值
int prt; //父節點
int lch; //左子節點
int rch; // 右子節點
int tmp; //中間變數，tmp=0 還未進行遍歷 tmp=1 已近進行過向左遍歷 tmp=2 已經進行過左右遍歷向上找到節點
char code[N];
}huffmantree;
void input();
void print(huffmantree );
void select(huffmantree *HT,int n,int &i,int &j)
{
int k;
i=1;
while(HT[i].prt!=0)
{
i++;

}
for(k=i+1;k<=n;k++)
{
if((HT[k].prt=0)&&(HT[k].wei <HT[i].wei))
i=k;
}
j=1;
while((j==i)||(HT[j].prt!=0))
{
j++;
}
for(k=j+1;k<=n;k++)
{
if((HT[k].prt=0)&&k!=i&&HT[k].wei<HT[j].wei)
j=k;
}
}

void huffman(int w[],huffmantree *HT,int n) //w存放n個字元的權值
{
int m=2*n-1;
int i,k,j;
huffmantree *p=0;
for(p=HT+1,i=1;i<=m;i++,p++)
{
HT[i].prt=0;
HT[i].lch=0;
HT[i].rch=0;
}
for(p=HT+1,i=1;i<=n;i++,p++)
{
HT[i].wei=w[i-1];
}
for(p=HT+n+1,i=n+1;i<=m;i++,p++)
{ HT[i].wei=0;}
for(k=n+1;k<=m;k++)
{
select(HT,k-1,i,j); // 找最小值和次小值的位置
HT[i].prt=k,HT[j].prt=k; // 找到i j 的父節點付給k
HT[k].lch=i,HT[k].rch=j; // 父節點的左右指針分別指向i, j
HT[k].wei=HT[i].wei+HT[j].wei;
}
}
void huffmancoding(huffmantree *HT,int n) //n個葉子結點的huffman編碼從根節點開始編碼
{
int BT=2*n-1;
int m=BT;
int l,r,p;
char s1[100]="0",s2[100]="1";
for(int i=0;i<=m;i++) //中間變數賦初值
{ HT[i].tmp=0; }
strcpy(HT[m].code," ");
while(1)
{
l=HT[BT].lch;
r=HT[BT].rch;
p=HT[BT].prt;
if(p==0&&HT[BT].tmp==2)
break;
if(l==0||r==0)
{
HT[BT].tmp=2; //如果是葉子結點則給中間變數賦值2向上返回一節結點

}
if(HT[BT].tmp==0) //未進行過遍歷，開始向左遍歷
{
HT[BT].tmp=1; //已經進行過向左遍歷
l=HT[BT].lch;
strcpy(HT[l].code,HT[BT].code);
strcat(HT[l].code,s1);
BT=l;
}
else
if(HT[BT].tmp==1)
{
HT[BT].tmp=2;
r=HT[BT].rch;
strcpy(HT[r].code,HT[BT].code);
strcat(HT[r].code,s2);
BT=r;
}
else if(HT[BT].tmp==2)
{
p=HT[BT].prt;
BT=p;
}
}
}

void print(huffmantree HT[],int n) //總共n個葉子節點
{
int i;
cout<<"源碼："<<endl;
for(i=1;i<=n;i++)
cout<<HT[i].wei<<endl;
cout<<"Huffman編碼："<<endl;
for(i=1;i<=n;i++)
{

cout<<HT[i].code<<endl;
}
}
void input(int w[],int n)
{
int t,*p;
int i=0;
cout<<"對應的輸入源碼出現權值：(以-1結束)"<<endl;
cin>>t;
while(t>=0)
{
p=new int;
*p=t;
w[i]=*p;
i++;
cin>>t;
}

}
void main()
{
int n,m;
cout<<"輸入源碼個數：";
cin>>n;
int *w;
w=new int[n+1];
input(w,n);
m=2*n-1;
huffmantree *HT;
HT=new huffmantree[m+1];
huffman(w,HT,n);
huffmancoding(HT,n);
print(HT,n);
delete w,HT;
}

導航:首頁 > 源碼編譯 > 霍夫曼演算法代碼

霍夫曼演算法代碼

與霍夫曼演算法代碼相關的資料