編程實現哈夫曼編碼

1. c或c++ 實現 哈夫曼編碼 最優字元串編碼

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
using namespace std;
class Node {
public:
char c; //表示字元
int frequency; //表示該字元出現的次數或頻率
Node *left;
Node *right;
Node(char _c, int f, Node *l = NULL, Node *r = NULL)
:c(_c), frequency(f), left(l), right(r) { }
bool operator<(const Node &node) const { //重載<運演算法以至於在加入優先隊列的時候決定如何處理結點位置
return frequency > node.frequency;
}
};
void initNode(priority_queue<Node> &q, int nodeNum) {
char c;
int frequency;
for (int i = 0; i < nodeNum; i++) {
cout << "輸入字元和結點出現的次數: ";
cin >> c >> frequency;
Node node(c, frequency);
q.push(node);
}
}
void showNode(priority_queue<Node> q) {
while (!q.empty()) {
Node node = q.top(); q.pop();
cout << node.c << ", " << node.frequency << endl;
}
}
//構造哈夫曼樹
void huffmanTree(priority_queue<Node> &q) {
while (q.size() != 1) {
Node *left = new Node(q.top()); q.pop();
Node *right = new Node(q.top()); q.pop();
Node node('R', left->frequency + right->frequency, left, right);
q.push(node);
}
}

// 列印哈夫曼編碼
void huffmanCode(Node *root, string &prefix, map<char, string> &result) {
string m_prefix = prefix;
if (root->left == NULL)
return;
//處理左子樹
prefix += "0";
//如果是葉子結點則輸出,否則遞歸列印左子樹
if (root->left->left == NULL)
result[root->left->c] = prefix;
//cout << root->left->c << ": " << prefix << endl;
else
huffmanCode(root->left, prefix, result);
//還原原來的路徑,回溯
prefix = m_prefix;
//處理右子樹
prefix += "1";
//如果是葉子結點，則輸出, 否則遞歸列印右子樹
if (root->right->right == NULL)
result[root->right->c] = prefix;
//cout << root->right->c << ": " << prefix << endl;
else
huffmanCode(root->right, prefix, result);
}
void testResult(map<char, string> result) {
//迭代map容器
map<char, string>::const_iterator it = result.begin();
while (it != result.end()) {
cout << it->first << ": " << it->second << endl;
++it;
}
}
int main() {
priority_queue<Node> q;
int nodeNum;
//初始化字元信息
cout << "請輸入結點個數: ";
cin >> nodeNum;
initNode(q, nodeNum);
//showNode(q);
//構造哈夫曼樹
huffmanTree(q);
//構造哈夫曼編碼
Node root = q.top();
string prefix = "";
map<char, string> result;
huffmanCode(&root, prefix, result);
//檢驗結果是否正確
testResult(result);
return 0;
}

2. 哈夫曼編碼的程序實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define M 100
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
//建立隊列
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
//生成新節點
NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode ));
if(NewNode!=NULL)
{
NewNode->start=s;
NewNode->end=e;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
else
{
printf(Error!);
exit(-1);
}
}
//按權分組
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i<=e;i++)
sum+=f[i].weight;//
*m=s;
sum1=0;
for(i=s;i<e;i++)
{
sum1+=f[i].weight;
*m=fabs(sum-2*sum1)>fabs(sum-2*sum1-2*f[i+1].weight)?(i+1):*m;
if(*m==i) break;
}
}
void main()
{
int i,j,n,max,m,h[M];
int sta,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//初始化隊Q
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf( ***FanoCoding*** );
printf(Please input the number of node:);
//輸入信息
scanf(%d,&n);
//超過定義M,退出
if(n>=M)
{
printf(>=%d,M);
exit(-1);
}
i=1; //從第二個元素開始錄入
while(i<=n)
{
printf(%d weight and node:,i);
scanf(%f %c,&FN[i].weight,&FN[i].ch);
for(j=1;j<i;j++)
{
if(FN[i].ch==FN[j].ch)//查找重復
{
printf(Same node!!! ); break;
}
}
if(i==j)
i++;
}
//排序(降序)
for(i=1;i<=n;i++)
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN[i].weight<FN[max].weight)
{
w=FN[i].weight;
FN[i].weight=FN[max].weight;
FN[max].weight=w;
c=FN[i].ch;
FN[i].ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) //初始化h
h[i]=0;
EnterQueue(Q,1,n); //1和n進隊
while(Q->front->next!=NULL)
{
p=Q->front->next; //出隊
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
sta=p->start;
end=p->end;
free(p);
Divide(FN,sta,&m,end); /*按權分組*/
for(i=sta;i<=m;i++)
{
fc[i][h[i]]='0';
++h[i];
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='';
for(i=m+1;i<=end;i++)
{
fc[i][h[i]]='1';
++h[i];
}
if(m==sta&&(m+1)==end)
//如果分組後首元素的下標與中間元素的相等，
//並且和最後元素的下標相差為1，則編碼碼字字元串結束
{
fc[m][h[m]]='';
fc[end][h[end]]='';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*列印編碼信息*/
{
printf(%c:,FN[i].ch);
printf(%s ,fc[i]);
}
system(pause);
} #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman編碼
typedef struct
{
int weight;//權值
int parent;//父節節點
int LChild;//左子節點
int RChild;//右子節點
}HTNode,Huffman[M+1];//huffman樹
typedef struct Node
{
int weight; //葉子結點的權值
char c; //葉子結點
int num; //葉子結點的二進制碼的長度
}WNode,WeightNode[N];
/***產生葉子結點的字元和權值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//葉子節點個數
//統計字元出現個數,放入CW
for(i=0;ch[i]!='';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch[i])
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//權值累加
}
}
*s=i;//字元串長度
}
/********創建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼樹
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j; //找到第一個雙親為零的結點
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二個雙親為零的結點
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//權值累加
}
}
/***********葉子結點的編碼***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次從末尾開始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父親方向遍歷,直到為0
{
start--;//依次向前置值
if(ht[p].LChild==c)//與左子相同,置0
cd[start]='0';
else //否則置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二進制碼的長度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//將二進制字元串拷貝到指針數組h中
}
free(cd);//釋放cd內存
system(pause);
}
/*********所有字元的編碼*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*從weight[k].c中查找與ch[i]相等的下標K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷貝二進制編碼
}
}
/*****解碼*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf(***StringInformation*** );
while(i<m)
{
p=2*n-1;//從父親節點向下遍歷直到葉子節點
for(j=0;hc[i][j]!='';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf(%c,w[p].c); /*列印原信息*/
i++;
}
}
/*****釋放huffman編碼內存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//釋放葉子結點的編碼
free(h[i]);
for(i=0;i<m;i++) //釋放所有結點的編碼
free(hc[i]);
}
void main()
{
int i,n=0; /*n為葉子結點的個數*/
int m=0; /*m為字元串ch[]的長度*/
char ch[N]; /*ch[N]存放輸入的字元串*/
Huffman ht; /*Huffman二叉數*/
HuffmanCode h,hc; /*h存放葉子結點的編碼，hc 存放所有結點的編碼*/
WeightNode weight; /*存放葉子結點的信息*/
printf( ***HuffmanCoding*** );
printf(please input information :);
gets(ch); /*輸入字元串*/
CreateWeight(ch,&m,weight,&n); /*產生葉子結點信息，m為字元串ch[]的長度*/
printf(***WeightInformation*** Node );
for(i=1;i<=n;i++) /*輸出葉子結點的字元與權值*/
printf(%c ,weight[i].c);
printf( Weight );
for(i=1;i<=n;i++)
printf(%d ,weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*產生Huffman樹*/
printf( ***HuffamnTreeInformation*** );
printf( i weight parent LChild RChild );
for(i=1;i<=2*n-1;i++) /*列印Huffman樹的信息*/
printf( %d %d %d %d %d ,i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*葉子結點的編碼*/
printf( ***NodeCode*** ); /*列印葉子結點的編碼*/
for(i=1;i<=n;i++)
{
printf( %c:,weight[i].c);
printf(%s ,h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字元的編碼*/
printf(***StringCode*** ); /*列印字元串的編碼*/
for(i=0;i<m;i++)
printf(%s,hc[i]);
system(pause);
TrsHuffmanTree(ht,weight,hc,n,m); /*解碼*/
FreeHuffmanCode(h,hc,n,m);
system(pause);
} Matlab 中簡易實現Huffman編譯碼：
n=input('Please input the total number: ');
hf=zeros(2*n-1,5);
hq=[];
for ki=1:n
hf(ki,1)=ki;
hf(ki,2)=input('Please input the frequency: ');
hq=[hq,hf(ki,2)];
end
for ki=n+1:2*n-1
hf(ki,1)=ki;
mhq1=min(hq);
m=size(hq);
m=m(:,2);
k=1;
while k<=m%del min1
if hq(:,k)==mhq1
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location
k=k+1;
end
hf(k,5)=1;
k1=k;
mhq2=min(hq);
k=1;
while k<=m%del min2
if hq(:,k)==mhq2
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location
k=k+1;
end
hf(k,5)=1;
k2=k;
hf(ki,2)=mhq1+mhq2;
hf(ki,3)=k1;
hf(ki,4)=k2;
hq=[hq hf(ki,2)];
end
clc
choose=input('Please choose what you want: 1: Encoding 2: Decoding 3:.Exit ');
while choose==1|choose==2
if choose==1
a=input('Please input the letter you want to Encoding: ');
k=1;
while hf(k,2)~=a
k=k+1;
if k>=n
display('Error! You did not input this number.');
break
end
end
if k>=n
break
end
r=[];
while hf(k,5)==1
kc=n+1;
while hf(kc,3)~=k&hf(kc,4)~=k
kc=kc+1;
end
if hf(kc,3)==k
r=[0 r];
else
r=[1 r];
end
k=kc;
end
r
else
a=input('Please input the metrix you want to Decoding: ');
sa=size(a);
sa=sa(:,2);
k=2*n-1;
while sa~=0
if a(:,1)==0
k=hf(k,3);
else
k=hf(k,4);
end
a=a(:,2:sa);
sa=sa-1;
if k==0
display('Error! The metrix you entered is a wrong one.');
break
end
end
if k==0
break
end
r=hf(k,2);
end
choose=input('Choose what you want: 1: Encoding 2: Decoding 3:.Exit ');
clc;
end
if choose~=1&choose~=2
clc;
end

3. 用C程序實現哈夫曼編碼

去年做的課程設計，有什麼不合要求的自己改改

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

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示：");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1);
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("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}

//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

4. 哈夫曼編碼/解碼器編程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000 //定義字元串最大長度
#define N 128 //定義葉子節點個數
typedef struct node //定義哈夫曼樹節點結構體
{
int weight;
struct node *LChild,*RChild,*Parent; //分別指向該節點的左孩子，右孩子，和雙親節點
struct node *next; //指向建立的哈夫曼樹的下一個節點
}HFMNode,*HFMTree;
typedef struct //定義哈夫曼編碼的結構體
{
char ch; //存儲對應的字元
char code[N+1]; //存儲對應字元的編碼
int start; //存儲編碼的起始位置
}CodeNode;int n; //存儲真正葉子節點個數
void clearscreen()
{
system("cls");
}
void Open(char s[]) //打開存放字元或編碼的文件，將其存入字元串數組中
{
char name[10];
FILE *fp;
int i=0;
printf("請輸入要打開的文件名：");
gets(name); //要打開的文件名
if((fp=fopen(name,"rt"))==NULL)
{
printf("打開失敗！\n"); //若打開失敗，則直接退出
exit(1);
}
s[i++]=fgetc(fp);
while(s[i-1]!=EOF)
s[i++]=fgetc(fp);
s[i]='\0'; //存取字元串結束
fclose(fp);
}
void Save(char s[]) //保存字元或編碼到文件中
{
char name[10];
FILE *fp;
printf("請輸入要保存的文件名：");
gets(name);
if((fp=fopen(name,"wt"))==NULL)
{
printf("存儲失敗！");
exit(1);
}
fputs(s,fp);
printf("\n保存成功，文件名為:%s。\n",name);
printf("\n按回車鍵繼續...");
getchar();
fclose(fp);} void SearchStr(char s[],char str[],int count[])
{
//查找字元串中字元的個數和每個字元出現的次數
int i,j,k=0;
for(i=0;i<N;i++) //初始化每個字元出現的次數
count[i]=0;
for(i=0;s[i];i++)
{
for(j=0;j<k;j++) //在str[]中查找是否有該字元
if(str[j]==s[i])
{
count[j]++;
break;
}
if(j==k) //在str[]中無該字元，將其存入最後一個單元
{
str[k]=s[i];
count[k++]++;
}
}
str[k]='\0'; //將字元串結尾置\0
n=k; //將實際的字元個數作為葉子節點個數存入n
}void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)
{
//查找哈夫曼鏈表中兩個權值最小的節點
int i,min;
HFMTree p;
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0)
{
min=p->weight;
*HT1=p;
}
min=32767;
for(i=0,p=HT;i<k;i++,p=p->next)
if(p->weight<min&&p->Parent==0&&p!=*HT1) //令第二個最小的節點不等於第一個節點
{
min=p->weight;
*HT2=p;
}}
void CreatHFMTree(HFMTree *HT,int count[])
{
//創建哈夫曼樹
int i;
HFMTree p,HT1,HT2; //HT1，HT2分別存放權值最小和次小的節點的位置
p=*HT=(HFMTree)malloc(sizeof(HFMNode));
p->next=p->LChild=p->RChild=p->Parent=NULL; //初始化哈夫曼鏈表且有2n-1個節點
for(i=1;i<2*n-1;i++)
{
p->next=(HFMTree)malloc(sizeof(HFMNode));
p=p->next;
p->next=p->LChild=p->RChild=p->Parent=NULL;
}for(i=0,p=*HT;i<n;i++) //將各個字元出現的次數作為權值
{ //存入哈夫曼鏈表的前n個單元中
p->weight=count[i];
p=p->next;
}for(i=n;i<2*n-1;i++) //將後n-1個節點賦權值，建樹
{
SelectMin(*HT,i,&HT1,&HT2); //每次從前i個節點中選取權值最小的兩個節點
HT1->Parent=HT2->Parent=p;
p->LChild=HT1;
p->RChild=HT2;
p->weight=HT1->weight+HT2->weight; //將兩個節點的權值相加存入最後一個節點中
p=p->next; //p指向下一個沒有存儲權值的節點
}}
void HFMCode(HFMTree HT,CodeNode HC[],char str[])
{
//從每個葉子節點開始，利用哈夫曼樹對每個字元進行編碼，最終建立一個哈夫曼表
int i;
HFMTree q,p=HT;
for(i=0;i<n;i++) //將字元存入哈夫曼編碼結構體數組的字元單元中
{
HC[i].ch=str[i];
HC[i].code[n-1]='\0'; //初始化編碼的最後一位
}
for(i=0;i<n;i++)
{
HC[i].start=n-1;
for(q=p;q->Parent;q=q->Parent) //判斷q所指向的節點，左孩子置0，右孩子置1
if(q==q->Parent->LChild)
HC[i].code[--HC[i].start]='0';
else HC[i].code[--HC[i].start]='1';
p=p->next; //判斷下一個葉子節點
}
}
void TotalCoding(char s[],CodeNode HC[],char code[])
{
//利用哈夫曼編碼表對整個字元串進行編碼
int i,j;
code[0]='\0'; //編碼數組初始化
for(i=0;s[i];i++) //將每個字元在哈夫曼編碼表中對應的編碼存入存放總編碼的數組中
for(j=0;j<n;j++)
if(s[i]==HC[j].ch)
strcpy(code+strlen(code),HC[j].code+HC[j].start);
}void DeCoding(char code[],HFMTree HT,char str[],char s[])
{
//對哈夫曼編碼進行解碼，放入字元串s中
int i,j,k=0;
HFMTree root,p,q;
for(root=HT;root->Parent;root=root->Parent); //用root指向哈夫曼樹的根結點
for(i=0,p=root;code[i];i++) //從根結點開始按編碼順序訪問樹
{
if(code[i]=='0')
p=p->LChild;
else p=p->RChild;
if(p->LChild==NULL&&p->RChild==NULL) //到根節點時將該節點對應的字元輸出
{
for(j=0,q=HT;q!=p;q=q->next,j++);
s[k++]=str[j];
p=root; //回溯到根結點
}
}
s[k]='\0'; //解碼完畢，在字元串最後一個單元存入'\0'
}
void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打開存放字元串的文件...\n\n");
Open(s); //打開源碼文件
SearchStr(s,str,count); //查找字元串中不同的字元及其出現的次數
CreatHFMTree(HT,count); //用每個字元出現的次數作為葉子節點的權值建立哈夫曼樹
HFMCode(*HT,HC,str); //利用哈夫曼樹對每個葉子節點進行編碼，存入編碼表中
TotalCoding(s,HC,code); //利用編碼表對字元串進行最終編碼
printf("\n讀入的字元串為:\n");
puts(s);
printf("\n最終的哈夫曼編碼是:\n");
puts(code);
printf("\n保存編碼,");
Save(code); //保存最終的哈夫曼編碼
}
void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[])
{
clearscreen();
printf("\n打開編碼的文件...\n\n");
Open(code); //打開編碼文件
DeCoding(code,*HT,str,ss); //將編碼進行解碼存入字元串數組ss[]中
printf("\n得到的最終字元串為:\n");
puts(ss);
printf("\n保存解碼，");
Save(ss); //保存解碼後的字元串
}void main()
{
//主函數
char s[M],ss[M]; //定義字元串數組，s[]存放將要編碼的字元串，ss[]存解碼後的字元串
char str[N]; //存放輸入的字元串中n個不同的字元
int count[N]; //存放n個不同字元對應的在原字元串中出現的次數
char code[M]; //存放最終編碼完成後的編碼
char choice;
HFMTree HT; //定義一個哈夫曼樹的鏈表
CodeNode HC[N]; //定義一個哈夫曼編碼表的數組，存放每個字元對應的哈夫曼編碼
do
{
clearscreen();
printf("\n\n");
printf(" ************哈夫曼樹************\n");
printf(" ** **\n");
printf(" ** 1.編碼。 **\n");
printf(" ** 2.解碼。 **\n");
printf(" ** 0.退出。 **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** **\n");
printf(" ** 請輸入相應操作的序號(0-2) **\n");
printf(" ********************************\n");
scanf("%c",&choice);
getchar();
switch(choice)
{
case '1': Coding(s,str,code,count,&HT,HC);break; //對字元串進行編碼
case '2': TransCode(code,str,ss,&HT,HC);break; //對編碼進行解碼
case '0': break;
default : printf(" 輸入錯誤！請重新輸入！\n");
}
}while(choice!='0');
}

5. 哈夫曼樹及哈夫曼編碼的C程序實現(數據結構題)

去年做的課程設計，有什麼不合要求的自己改改

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

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示：");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1);
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("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}

//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

6. 用C/C++或Java編程實現： 通過給定字元a,b,c,d,e,f,g,h,i,h的使用頻率，編程求出它們的赫夫曼編碼。

下面的截圖就是你給定的權重對應的haffman編碼，見圖：

下面的二進制數就是對應的編碼

7. 哈夫曼樹及哈夫曼編碼解碼的實現（根據程序畫流程圖及對每句程序注釋）

這是以前寫的，可是我不想加註釋了，Huffman編碼其實原理很簡單的，你自己好好學下吧，一句一句注釋也太誇張了啊。

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

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

void Select(HuffmanTree HT,int n)
{
int i,j;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j;
}
if(s1>s2)
{
int temp=s1;
s1=s2;
s2=temp;
}
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i<=n; i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}

//添加查看，便於調試
printf("構造過程顯示：\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");

for(i=n+1;i<=m;i++)
{
Select(HT,i-1);
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("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
*/
}
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
else if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}

}

int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("請輸入節點數：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("請輸入節點的權值：\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("輸出編碼：\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
return 0;
system("pause");
}

8. 用哈夫曼編碼 編程

手打的,你最好編譯一下以免我哪裡敲錯了
(網路不能顯示行首空格真是不爽)

//哈夫曼樹和~編碼的存儲表示
typedef struct{
unsigned int weight;//權值
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;//動態分配數組存儲哈夫曼樹
typedef char * *HuffmanCode;//動態分配數組存儲哈夫曼編碼表

void HoffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
//w存放n個字元的權值(均>0),構造哈夫曼樹HT,並求出n個字元的哈夫曼編碼HC
if (n<=1) return;
m=2*n-1;
HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));//0號單元未採用
for (p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0};
for (;i<=m;++i;++p) *p={0,0,0,0}
for (i=n+1;i<=m;++i){//建哈夫曼樹
//在HT[1..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;
}
//從葉子到根逆向求每個字元的哈夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n個字元編碼的頭指針向量
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));//為第i個字元編碼分配空間
strcpy(HC[i],&cd[start]);//從cd復制編碼(串)到HC
}
free(cd);//釋放工作空間
}//HuffmanCoding

9. 哈夫曼編碼碼長怎麼算

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼編碼是變長編碼，思路：對概率大的編的碼字短，概率小的編的碼字長，這樣一來所編的總碼長就小，這樣編碼效率就高。上面那樣求是不對的，除非你這6個碼字是等概率的，各佔1/6。應該用對應的概率*其對應得碼長，再求和。

實際應用中

除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。

按照CCITT標准，需要統計2×1728種遊程（長度），這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。