C語言赫夫曼樹編碼解碼

1. huffman編碼解碼的c語言實現

留個腳印，晚上回去看看

#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>

//typedef int TElemType;
const int UINT_MAX=1000;
char str[50];

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

typedef char **HuffmanCode;

//-----------全局變數-----------------------
HuffmanTree HT;
HuffmanCode HC;
int w[50],i,j,n;
char z[50];
int flag=0;
int numb=0;

// -----------------求赫夫曼編碼-----------------------
struct cou{
char data;
int count;
}cou[50];

int min(HuffmanTree t,int i)
{ // 函數void select()調用
int j,flag;
int k=UINT_MAX; // 取k為不小於可能的值,即k為最大的權值1000
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

//--------------------slect函數----------------------
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1為最小的兩個值中序號小的那個
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
}
// --------------演算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ // w存放n個字元的權值(均>0),構造赫夫曼樹HT,並求出n個字元的赫夫曼編碼HC
int m,i,s1,s2,start;
//unsigned c,f;
int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;//檢測結點數是否可以構成樹
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
p->parent=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=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個字元編碼的頭指針向量([0]不用)
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); // 釋放工作空間
}
//---------------------獲取報文並寫入文件---------------------------------
int InputCode()
{
//cout<<"請輸入你想要編碼的字元"<<endl;
FILE *tobetran;

if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
return 0;
}
cout<<"請輸入你想要編碼的字元"<<endl;
gets(str);
fputs(str,tobetran);
cout<<"獲取報文成功"<<endl;
fclose(tobetran);
return strlen(str);
}

//--------------初始化赫夫曼鏈表---------------------------------
void Initialization()
{ int a,k,flag,len;
a=0;
len=InputCode();
for(i=0;i<len;i++)
{k=0;flag=1;
cou[i-a].data=str[i];
cou[i-a].count=1;
while(i>k)
{
if(str[i]==str[k])
{
a++;
flag=0;
}
k++;
if(flag==0)
break;

}

if(flag)
{
for(j=i+1;j<len;j++)
{if(str[i]==str[j])
++cou[i-a].count;}
}

}
n=len-a;
for(i=0;i<n;i++)
{ cout<<cou[i].data<<" ";
cout<<cou[i].count<<endl;
}
for(i=0;i<=n;i++)
{*(z+i)=cou[i].data;
*(w+i)=cou[i].count;
}

/* 原來未修改的初始化程序段:
flag=1;
int num;
int num2;
cout<<"下面初始化赫夫曼鏈表"<<endl<<"請輸入結點的個數n：";
cin>>num;
n=num;
w=(int*)malloc(n*sizeof(int));
z=(char*)malloc(n*sizeof(char));
cout<<"\n請依次輸入"<<n<<"個字元(字元型)："<<endl;
char base[2];
for(i=0;i<n;i++)
{
cout<<"第"<<i+1<<"個字元:"<<endl;
gets(base);
*(z+i)=*base;
}
for(i=0;i<=n-1;i++)
{
cout<<setw(6)<<*(z+i);
}
cout<<"\n請依次輸入"<<n<<"個權值："<<endl;
for(i=0;i<=n-1;i++)
{
cout<<endl<<"第"<<i+1<<"個字元的權值:";
cin>>num2;
*(w+i)=num2;
}*/
HuffmanCoding(HT,HC,w,n);
//------------------------列印編碼-------------------------------------------
cout<<"字元對應的編碼為:"<<endl;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
//--------------------------將赫夫曼編碼寫入文件------------------------
cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"...................."<<endl;
FILE *htmTree;
char r[]={' ','\0'};
if((htmTree=fopen("htmTree.txt","w"))==NULL)
{
cout<<"can not open file"<<endl;
return;
}

fputs(z,htmTree);
for(i=0;i<n+1;i++)
{
fprintf(htmTree,"%6d",*(w+i));
fputs(r,htmTree);
}
for(i=1;i<=n;i++)
{
fputs(HC[i],htmTree);
fputs(r,htmTree);
}
fclose(htmTree);
cout<<"已將字元與對應編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;
}
//---------------------編碼函數---------------------------------
void Encoding()
{
cout<<"下面對目錄下文件tobetran.txt中的字元進行編碼"<<endl;

FILE *tobetran,*codefile;

if((tobetran=fopen("tobetran.txt","rb"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
if((codefile=fopen("codefile.txt","wb"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
char *tran;
i=99;
tran=(char*)malloc(100*sizeof(char));
while(i==99)
{
if(fgets(tran,100,tobetran)==NULL)
{
cout<<"不能打開文件"<<endl;
break;
}
for(i=0;*(tran+i)!='\0';i++)
{
for(j=0;j<=n;j++)
{
if(*(z+j-1)==*(tran+i))
{
fputs(HC[j],codefile);
if(j>n)
{
cout<<"字元錯誤，無法編碼!"<<endl;
break;
}
}
}
}
}
cout<<"編碼工作完成"<<endl<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}
//-----------------解碼函數---------------------------------
void Decoding()
{
cout<<"下面對根目錄下文件codefile.txt中的字元進行解碼"<<endl;
FILE *codef,*txtfile;
if((txtfile=fopen("txtfile.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
if ((codef=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
char *work,*work2,i2;
int i4=0,i,i3;
unsigned long length=10000;
work=(char*)malloc(length*sizeof(char));
fgets(work,length,codef);
work2=(char*)malloc(length*sizeof(char));
i3=2*n-1;
for(i=0;*(work+i-1)!='\0';i++)
{
i2=*(work+i);
if(HT[i3].lchild==0)
{
*(work2+i4)=*(z+i3-1);
i4++;
i3=2*n-1;
i--;
}
else if(i2=='0') i3=HT[i3].lchild;
else if(i2=='1') i3=HT[i3].rchild;
}
*(work2+i4)='\0';
fputs(work2,txtfile);
cout<<"解碼完成"<<endl<<"內容寫入根目錄下的文件txtfile.txt中"<<endl<<endl;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);
}
//-----------------------列印編碼的函數----------------------
void Code_printing()
{
cout<<"下面列印根目錄下文件CodePrin.txt中編碼字元"<<endl;
FILE * CodePrin,* codefile;
if((CodePrin=fopen("CodePrin.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
if((codefile=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}

char *work3;
work3=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work3,51,codefile)==NULL)
{
cout<<"不能讀取文件"<<endl;
break;
}
fputs(work3,CodePrin);
puts(work3);
}while(strlen(work3)==50);
free(work3);
cout<<"列印工作結束"<<endl<<endl;
fclose(CodePrin);
fclose(codefile);
}
//-------------------------------列印解碼函數---------------------------------------------
void Code_printing1()
{
cout<<"下面列印根目錄下文件txtfile.txt中解碼字元"<<endl;
FILE * CodePrin1,* txtfile;
if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
if((txtfile=fopen("txtfile.txt","r"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
char *work5;
work5=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work5,51,txtfile)==NULL)
{
cout<<"不能讀取文件"<<endl;
break;
}
fputs(work5,CodePrin1);
puts(work5);
}while(strlen(work5)==50);
free(work5);
cout<<"列印工作結束"<<endl<<endl;
fclose(CodePrin1);
fclose(txtfile);
}
//------------------------列印赫夫曼樹的函數-----------------------
void coprint(HuffmanTree start,HuffmanTree HT)
{
if(start!=HT)
{
FILE * TreePrint;

if((TreePrint=fopen("TreePrint.txt","a"))==NULL)
{cout<<"創建文件失敗"<<endl;
return;
}
numb++;//該變數為已被聲明為全局變數
coprint(HT+start->rchild,HT);
cout<<setw(5*numb)<<start->weight<<endl;

fprintf(TreePrint,"%d\n",start->weight);
coprint(HT+start->lchild,HT);
numb--;
fclose(TreePrint);
}
}
void Tree_printing(HuffmanTree HT,int w)
{
HuffmanTree p;
p=HT+w;
cout<<"下面列印赫夫曼樹"<<endl;
coprint(p,HT);
cout<<"列印工作結束"<<endl;
}
//------------------------主函數------------------------------------
void main()
{
char choice;
while(choice!='q')
{ cout<<"\n******************************"<<endl;
cout<<" 歡迎使用赫夫曼編碼解碼系統"<<endl;
cout<<"******************************"<<endl;
cout<<"(1)要初始化赫夫曼鏈表請輸入'i'"<<endl;
cout<<"(2)要編碼請輸入'e'"<<endl;
cout<<"(3)要解碼請輸入'd'"<<endl;
cout<<"(4)要列印編碼請輸入'p'"<<endl;
cout<<"(5)要列印赫夫曼樹請輸入't'"<<endl;
cout<<"(6)要列印解碼請輸入'y'"<<endl;
if(flag==0)cout<<"\n請先初始化赫夫曼鏈表,輸入'i'"<<endl;
cin>>choice;
switch(choice)
{
case 'i':
Initialization();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT,2*n-1);
break;
case 'y':
Code_printing1();
break;
default:
cout<<"input error"<<endl;
}

}
free(z);
free(w);
free(HT);
}

2. C語言哈夫曼樹的編碼及其解碼問題，數據結構與演算法，求解

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct TreeNode *HuffmanTree;
typedef HuffmanTree ElemType;
typedef struct code Code;
struct TreeNode{
char c;
int Weight;
HuffmanTree Left,Right;
};
typedef struct Heap{
ElemType Data[MAXSIZE];
int Size;
int Capacity;
}*MinHeap;
struct code{
char c;
char code[10];
};
struct TNode{
int Data;
struct TNode* lchild;
struct TNode* rchild;
};
MinHeap BuildHeap()
{

MinHeap tmpH;
tmpH=(MinHeap)malloc(sizeof(struct Heap));
ElemType Min=(ElemType)malloc(sizeof(ElemType));
Min->Weight=-1,Min->Left=Min->Right=NULL;
tmpH->Size=0;
tmpH->Capacity=MAXSIZE;
tmpH->Data[0]=Min;
return tmpH;
}
int isFull(MinHeap H)
{
return H->Size>=H->Capacity;
}
int isEmpty(MinHeap H)
{
return H->Size==0;
}
void Insert(MinHeap H,ElemType T)
{
int i;
if(isFull(H)){
printf("MinHeap is Full");
return ;
}
i=++H->Size;
for(;H->Data[i/2]->Weight>T->Weight;i/=2)
H->Data[i]=H->Data[i/2];
H->Data[i]=T;
}
ElemType DeleteMin(MinHeap H){
int Parent,child;
ElemType min,tmp;
if(isEmpty(H)){
printf("The Heap is Empty");
return NULL;
}
min=H->Data[1];
tmp=H->Data[H->Size--];
for(Parent=1;Parent*2<H->Size;Parent=child)
{
child=Parent*2;
if(child!=H->Size-1&&H->Data[child]->Weight>H->Data[child+1]->Weight)
child++;
if(tmp->Weight>H->Data[child]->Weight)
{
H->Data[Parent]=H->Data[child];
}else break;
}
H->Data[Parent]=tmp;
return min;
}
void InitHeap(MinHeap H,int n)
{
ElemType tmp;
for(int i=0;i<n;i++)
{ getchar();
tmp=(ElemType)malloc(sizeof(ElemType));
scanf("%c,%d",&tmp->c,&tmp->Weight);
tmp->Left=tmp->Right=NULL;
Insert(H,tmp);
}
}
HuffmanTree Huffman(MinHeap H)
{
int i;
HuffmanTree T;
for(i=1;i<H->Size;i++)
{
T=(HuffmanTree)malloc(sizeof(HuffmanTree));
T->Left=DeleteMin(H);
T->Right=DeleteMin(H);
T->Weight=T->Left->Weight+T->Right->Weight;
Insert(H,T);
}
T=DeleteMin(H);
return T;
}
int main()
{
int n;
scanf("%d",&n);
Code ans[n];
MinHeap H=BuildHeap();
HuffmanTree T;
InitHeap(H,n);
T=Huffman(H);

return 0;
}
哈夫曼樹的構造，編碼有01左右子樹之分，稍微復雜

3. c語言版 哈弗曼編碼和解碼

哈弗曼編碼涵義是將一竄數字或者字母按哈弗曼數的形式編碼，並使得這竄字元中的每個數字或者字母都能被唯一的「0，1」序列來編碼，而且沒有相同的前綴，這是一種非等長的編碼方式。如果你覺得這樣解釋很難聽懂的話就舉個例子：如果用計算機發信息，只能用0和1，但是每個字母的使用頻度又不一樣，比如a ,i,o,e等這些字母使用的就多些，而z,v這樣的字母使用的就少一些，如果所有字母都用等長的0,1序列來編碼的話會造成浪費，那麼我們就把常用的字母用少點的0,1，進行編碼（比如用兩個或三個），不常用的再用多點0,1編碼，但是還不能造成油相同前綴的情況，這會使計算機無法識別，比如E用010，z用01001，計算機就只能識別出前面三個是E，而後面就拋棄或者識別出別的字母。哈弗曼編碼就是出於這樣的條件下產生的。也許這樣的形容還是很抽象，那麼再具體點。加入a,b,c,d,e使用的頻度分別是10,7,5,5,3那麼就可以構造哈弗曼數：從樹頂到樹根，假如左邊是0，右邊是1，那麼就能得到他們的哈弗曼編碼(就是從上到下，到達他們字母經過的路徑)，分別是：a:00;b:11;c:10;d:011;e:010;你可以發現他們全部沒有相同的前綴。具體的編碼方式我可以大致的跟你說下，因為我還在上班所以無法使用自己的電腦進行編譯，怕寫的有錯誤，你拿到一個待編碼的數據肯定有標識符（即上面的a,b,c），還有所帶的權值（即3,5,5等）你需要用哈弗曼演算法構造出哈弗曼編碼，即每次取最小的兩個數當作葉子，來生成樹根（樹根的值等於他們的和），整數據就少了一個，直到最後兩個數相加的值作為最終的樹根。然後從上往下，左邊為0右邊為1，到達每個樹葉（即是標識符的位置），那麼路徑的編碼就是他的哈弗曼編碼。以上是演算法，建議你可以用一個結構體（帶標識符，權值，哈弗曼編碼（編碼暫時為空）），用一個vector（C++裡面的數據類型）裝載他們並按照權值大小進行排序，然後通過哈弗曼演算法（另用一個函數來計算）創建一個哈弗曼數，並計算出它的哈弗曼編碼並寫到結構體中，這樣就把字元進行了哈弗曼壓縮。這就是整個過程

4. 求用c語言實現霍夫曼編碼的程序，最好能帶講解的程序。感謝！

//* * * * * * * * * * * * * * * * * * * * * * * *
//哈夫曼樹的構造哈夫曼樹,哈夫曼編碼 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{unsigned int weight; //結點權值
unsigned int parent,lchild,rchild; //結點的父指針，左右孩子指針
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char **HuffmanCode; //動態分配數組存儲哈夫曼編碼表
void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼樹
void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //對哈夫曼樹進行編碼
void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //顯示哈夫曼編碼
void Select(HuffmanTree,int,int&,int&); //在數組中尋找權值最小的兩個結點
void main()
{HuffmanTree HT; //哈夫曼樹HT
HuffmanCode HC; //哈夫曼編碼表HC
int n,i; //n是哈夫曼樹葉子結點數
unsigned int *w; //w存放葉子結點權值
char j='y';
textbackground(3); //設定屏幕顏色
textcolor(15);
clrscr();
//程序解說
printf("本程序將演示構造哈夫曼樹.\n");
printf("首先輸入葉子結點數目.\n例如:8\n");
printf("然後輸入每個葉子結點的權值.\n");
printf("例如:5 29 7 8 14 23 3 11\n");
printf("程序會構造一棵哈夫曼樹並顯示哈夫曼編碼.\n");
printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n");
printf(" 23---00\n 3---0111\n 11---010\n");
while(j!='N'&&j!='n')
{printf("請輸入葉子結點數目:");
scanf("%d",&n); //輸入葉子結點數
if(n<=1) {printf("該數不合理!\n");continue;}
w=(unsigned int*)malloc(n*sizeof(unsigned int)); //開辟空間存放權值
printf("請輸入各葉子結點的權值:\n");
for(i=0;i<n;i++) scanf("%d",&w[i]); //輸入各葉子結點權值
CreateHuffmanTree(HT,w,n); //生成哈夫曼樹
HuffmanCoding(HT,HC,n); //進行哈夫曼編碼
PrintHuffmanCode(HC,w,n); //顯示哈夫曼編碼
printf("哈夫曼樹構造完畢，還要繼續嗎?(Y/N)");
scanf(" %c",&j);
}
}

void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)
{//w存放n個結點的權值，將構造一棵哈夫曼樹HT
int i,m;
int s1,s2;
HuffmanTree p;
if(n<=1) return;
m=2*n-1; //n個葉子結點的哈夫曼樹，有2*n-1個結點
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //開辟2*n各結點空間，0號單元不用
for(p=HT+1,i=1;i<=n;++i,++p,++w) //進行初始化
{p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i) //建哈夫曼樹
{Select(HT,i-1,s1,s2);
//從HT[1...i-1]中選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2
HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2結點的父指針parent
HT[i].lchild=s1; HT[i].rchild=s2; //修改i結點的左右孩子指針
HT[i].weight=HT[s1].weight+HT[s2].weight; //修改權值
}
}
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{//將有n個葉子結點的哈夫曼樹HT進行編碼， 所編的碼存放在HC中
//方法是從葉子到根逆向求每個葉子結點的哈夫曼編碼
int i,c,f,start;
char *cd;
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'; //若是左孩子編為'0'
else cd[--start]='1'; //若是右孩子編為'1'
HC[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個編碼分配空間
strcpy(HC[i],&cd[start]); //將編碼從cd復制到HC中
}
free(cd); //釋放工作空間
}
void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)
{//顯示有n個葉子結點的哈夫曼樹的編碼表
int i;
printf("HuffmanCode is :\n");
for(i=1;i<=n;i++)
{printf(" %3d---",w[i-1]);
puts(HC[i]);
}
printf("\n");
}
void Select(HuffmanTree HT,int t,int&s1,int&s2)
{//在HT[1...t]中選擇parent不為0且權值最小的兩個結點，其序號分別為s1和s2
int i,m,n;
m=n=10000;
for(i=1;i<=t;i++)
{if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n))
if(m<n)
{n=HT[i].weight;s2=i;}
else {m=HT[i].weight;s1=i;}

}
if(s1>s2) //s1放較小的序號
{i=s1;s1=s2;s2=i;}
}

5. 怎麼樣用c語言程序編碼哈夫曼樹

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 動態分配數組存儲赫夫曼樹
typedef char **HuffmanCode; // 動態分配數組存儲赫夫曼編碼表
// algo6-1.cpp 求赫夫曼編碼。實現演算法6.12的程序

int min(HuffmanTree t,int i)
{
// 函數void select()調用
int j,flag;
unsigned int k=UINT_MAX; // 取k為不小於可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int &s1,int &s2)
{
// s1為最小的兩個值中序號小的那個

s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 演算法6.12
{
// w存放n個字元的權值(均>0),構造赫夫曼樹HT,並求出n個字元的赫夫曼編碼HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用
for(p=HT+1,i=1; i<=n; ++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p)
(*p).parent=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=HT[s2].parent=i;
HT[i].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 從葉子到根逆向求每個字元的赫夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n個字元編碼的頭指針向量([0]不用)
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]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 為第i個字元編碼分配空間
strcpy(HC[i],&cd[start]); // 從cd復制編碼(串)到HC
}
free(cd); // 釋放工作空間
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);

}
return 0;
}

6. 有人可以幫我注釋一段關於用c語言實現哈夫曼樹的代碼嗎

在一般的數據結構的書中，樹的那章後面，著者一般都會介紹一下哈夫曼(HUFFMAN)樹和哈夫曼編碼。哈夫曼編碼是哈夫曼樹的一個應用。哈夫曼編碼應用廣泛，如

JPEG中就應用了哈夫曼編碼。 首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點

的權值乘上其到根結點的 路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。

樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) ，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。 可以證明哈夫曼樹的WPL是最小的。

哈夫曼編碼步驟：

一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現算 法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。

簡易的理解就是，假如我有A,B,C,D,E五個字元，出現的頻率（即權值）分別為5,4,3,2,1,那麼我們第一步先取兩個最小權值作為左右子樹構造一個新樹，即取1，2構成新樹，其結點為1+2=3，如圖：

所以各字元對應的編碼為：A->11,B->10,C->00,D->011,E->010

霍夫曼編碼是一種無前綴編碼。解碼時不會混淆。其主要應用在數據壓縮，加密解密等場合。

C語言代碼實現：

/*-------------------------------------------------------------------------
* Name: 哈夫曼編碼源代碼。
* Date: 2011.04.16
* Author: Jeffrey Hill+Jezze(解碼部分)
* 在 Win-TC 下測試通過
* 實現過程：著先通過 HuffmanTree() 函數構造哈夫曼樹，然後在主函數 main()中
* 自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷，若在
* 父結點左側，則置碼為 0,若在右側,則置碼為 1。最後輸出生成的編碼。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>

#define MAXBIT 100
#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;
int value;
} HNodeType; /* 結點結構體 */

/* 構造一顆哈夫曼樹 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循環變數，m1、m2：構造哈夫曼樹不同過程中兩個最小權值結點的權值，
x1、x2：構造哈夫曼樹不同過程中兩個最小權值結點在數組中的序號。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼樹數組 HuffNode[] 中的結點 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//權值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //實際值，可根據情況替換為字母
} /* end for */

/* 輸入 n 個葉子結點的權值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d: ", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */

/* 循環構造 Huffman 樹 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE; /* m1、m2中存放兩個無父結點且結點權值最小的兩個結點 */
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;
}
} /* end for */
/* 設置找到的兩個子結點 x1、x2 的父結點信息 */
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;

printf ("x1.weight and x2.weight in round %d: %d, %d ", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用於測試 */
printf (" ");
} /* end for */
/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d ",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///測試
} /* end HuffmanTree */

//解碼
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild ;
}
else tmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


int main(void)
{

HNodeType HuffNode[MAXNODE]; /* 定義一個結點結構體數組 */
HCodeType HuffCode[MAXLEAF], cd; /* 定義一個編碼結構體數組， 同時定義一個臨時變數來存放求解編碼時的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input 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; /* 設置下一循環條件 */
} /* end while */

/* 保存求出的每個葉結點的哈夫曼編碼和編碼的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */

/* 輸出已保存好的所有存在編碼的哈夫曼編碼 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" start:%d",HuffCode[i].start);

printf (" ");

}
/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" ");
}*/
printf("Decoding?Please Enter code: ");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}

7. 求哈夫曼解碼C語言程序 請各位大俠在我原有的程序上加上哈夫曼解碼的程序，不勝感激！

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

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

typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
MinCode Select(HuffmanTree HT,int n);

HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
{ /* w存放n個字元的權值(均>0),構造哈夫曼樹HT,並求出n個字元的哈夫曼編碼HC.*/
int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
int f,c,start,m;
MinCode min;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0號單元未用*/
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++){ /*建哈夫曼樹*/
/*在HT[1..i-1]選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2.*/
min=Select(HT,i-1);
s1=min.s1;
s2=min.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=0;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); /*釋放工作空間*/
return HC;
}

MinCode Select(HuffmanTree HT,int n)
{
int min,secmin;
int temp;
int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=0;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=0;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}

void main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
int i,n=27;
char c[27]={' ','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'};
int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
HC=HuffmanCoding(HT,HC,w,n);
printf("HuffmanCode:\n");
printf("Char\t\tWeight\t\tCode\n");
for(i=0;i<=n-1;i++)
printf("%c\t\t%d\t\t%s\n",c[i],w[i],HC[i]);
{
char cs[128];
char results[64];
char buf[64];
int ps=0,pe=1;
results[0]=0;
printf("Input code:\n");
scanf("%s",cs);
while (cs[ps]!=0) {
strncpy(buf,&cs[ps],pe-ps); /*返回字元*/
buf[pe-ps]=0;
for(i=0;i<n;i++)
{
if (strcmp(buf,HC[i])==0)
{
int len=strlen(results);
results[len]=c[i];
results[len+1]=0;
ps=pe;
pe++;
break;
}
}
if (cs[pe]==0) break;
pe++;
}
printf("RESULT: %s",results);
}
getch();
}

8. 數據結構中哈夫曼樹的應用（C語言）

#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;

typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;

struct worder
{
char words; /*字元*/
}word[100];
struct weighted
{
int weighter; /*轉換權值有利於文件的存儲*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉樹*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}

BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}

void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼樹*/
{
int i,j,m1,m2,x1,x2;

for(i=0;i<2*n-1;i++)
{

if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}

for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*將每個權值賦值給二維數組a[][],利用這個二維數組可以進行建立二叉樹*/
a[i+1][2]=haffTree[n+i].weight;
}
}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*對已經建立好的哈夫曼樹進行編碼*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;

for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}

for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}

void PrintBiTree(BiTreeNode *bt ,int n) /*將哈夫曼樹轉換成的二叉樹進行列印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}

int search(int a[][3],int m) /*查找和a[][2]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失敗返回數字0 查找成功返回和a[][2]相等的數的行數 i*/
else return i;
}

int searcher(int a[][3],int m) /*查找和a[][1]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失敗返回數字0 查找成功返回和a[][1]相等的數的行數 i*/
i++;
if(i==m) return 0;
else return i;
}

void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼樹*/（利用遞歸）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]為左子樹*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]為右子樹*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等則只要進行一個的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}

void code(Code myHaffCode[],int n ) /*編碼*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存儲編碼的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*讀取存儲字元的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*輸出每個權值的編碼*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字元找到對應的編碼*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*輸出相應的編碼*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}

fclose(fp2);
}

void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存儲權值個數的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存儲字元的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存儲權值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;

printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}

void menu() /*界面*/
{

printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*編碼*/
printf("\t\t\t2. Decoding:\n\n"); /*解碼*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*列印哈夫曼樹*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}

void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;

HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;

case 5:exit(0);
}
}
}
getch();
}

9. 哈夫曼樹編碼解碼，C語言做的，第17行就是錯，搞不懂啊，求高手指點一下啊

首先一個錯誤是
HaffmanTree 這個打錯了 應該是HuffmanTree 這個才是你定義的數據類型

除了這個以外 由於代碼不全 所以無法確定是否還有其他問題

10. C語言編的haffuman編解碼，要求可以從文件中讀取，然後編碼/解碼，在線等，很急哈

#include <stdio.h>
#include <string.h>
#define N 50 /*葉子結點數*/
#define M 2*N-1 /*樹中結點總數*/
typedef struct
{
char data[5]; /*結點值*/
int weight; /*權重*/
int parent; /*雙親結點*/
int lchild; /*左孩子結點*/
int rchild; /*右孩子結點*/
} HTNode;
typedef struct
{
char cd[N]; /*存放哈夫曼碼*/
int start;
} HCode;
void CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++) /*所有結點的相關域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*構造哈夫曼樹*/
{
min1=min2=32767; /*lnode和rnode為最小權重的兩個結點位置*/
lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1) /*只在尚未構造二叉樹的結點中查找*/
{
if (ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) /*根據哈夫曼樹求哈夫曼編碼*/
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) /*循序直到樹根結點*/
{
if (ht[f].lchild==c) /*處理左孩子結點*/
hc.cd[hc.start--]='0';
else /*處理右孩子結點*/
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++; /*start指向哈夫曼編碼最開始字元*/
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
int sum=0,m=0,j;
printf(" 輸出哈夫曼編碼:\n"); /*輸出哈夫曼編碼*/
for (i=0;i<n;i++)
{
j=0;
printf(" %s:\t",ht[i].data);
for (k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n 平均長度=%g\n",1.0*sum/m);
}
void main()
{
int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
HTNode ht[M];
HCode hcd[N];
for (i=0;i<n;i++)
{
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
}
你可以改一下從文件讀取