霍夫曼樹創建c語言,如何構建霍夫曼樹

本文目錄一覽：

• 1、怎麼樣用c語言程序編碼哈夫曼樹？
• 2、哈夫曼樹的建立
• 3、哈夫曼樹應用（C語言）
• 4、哈夫曼樹的c語言編程，急急急！
• 5、關於C語言建立赫夫曼樹的問題，我不是很明白，下面是代碼：
• 6、數據結構中哈夫曼樹的應用（C語言）

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

#includestdio.h

#includestdlib.h

#includestring.h

#include ctype.h

#includelimits.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].weightkt[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(s1s2)

{

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); // 從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; icount; 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; ij; i++)

*(m+i)=0;

for(t=0; tj; t++)

{

for(i=0; icount; i++)

{

if(*(s2+t)==*(s1+i))

*(m+t)+=1;

}

}

for(i=0;ij;i++)

while(flag)

{

flag = 0;

for (t=0; tj-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;

}

哈夫曼樹的建立

。。作業吧，運行可用，自己再試試。

//huffman_h.h 哈夫曼樹的頭文件

#include”iostream.h”

#include “stdio.h”

#include “stdlib.h”

#include “string.h”

typedef char ElemType;

typedef struct{

ElemType elem;

unsigned int weight;

unsigned int parent,lchild,rchild,tag;

}HTNode,*HuffmanTree;

typedef char** HuffmanCode;

typedef int Status;

typedef struct weight

{

char elem;

unsigned int m_weight;

}Weight; // 保存符號信息;

void Select(HuffmanTree HT,int n,int s1,int s2)

{

int i;

s1=s2=0;

for(i=1;i=n;i++){

if(HT[i].weightHT[s2].weightHT[i].parent==0s2!=0){

if(HT[i].weightHT[s1].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].weightHT[s1].weight) {

s2=s1; s1=i; }

else s2=i;

} // end of else if

if(s1s2) {i=s1; s1=s2; s2=i;}

// end of if

// end of for

}

void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, Weight* w, int n) {

// w存放n個字符的權值(均0)，構造哈夫曼樹HT，

// 並求出n個字符的哈夫曼編碼HC

//本函數實現選擇方式：從左往右選擇兩個小權值結點，結點信息在前面的為左子樹，其後為右子樹

//修改選擇方式：依序選擇兩個小權值結點，權值小的為左子樹。！！

int i, j, m, s1,s2;

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].elem=w[i-1].elem;

HT[i].weight=w[i-1].m_weight;

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哈夫曼樹的構造過程如下所示：\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, 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(“\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();

}//for

//——無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));

cd = (char *)malloc((n+1)*sizeof(char)); // 分配求編碼的工作空間

p = m; cdlen = 0;

for (i=1; i=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標誌

HT[i].tag = 0;

while (p) {

if (HT[p].tag==0) { // 向左

HT[p].tag = 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].tag==1) { // 向右

HT[p].tag = 2;

if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] =’1′; }

} else { // HT[p].weight==2，退回退到父結點，編碼長度減1

HT[p].tag = 0; p = HT[p].parent; –cdlen;

}//else

}//while

} // HuffmanCoding

/*

//— 從葉子到根逆向求每個字符的哈夫曼編碼 —

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); // 從cd複製編碼(串)到HC

}

free(cd); // 釋放工作空間

*/

void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)

{

int i;

printf(“\nnumber—element—weight—huffman code\n”);

for(i=1;i=n;i++)

printf(” %d %c %d %s\n”,i,HT[i].elem,HT[i].weight,HC[i]);

}

//主函數

//huffman.cpp

#include”huffman_h.h”

void main()

{

HuffmanTree HT;

HuffmanCode HC;

Weight *w;

char c; // the symbolizes;

int i,n; // the number of elements;

int wei; // the weight of a element;

printf(“請輸入構建哈夫曼樹的結點數:” );

cinn; //coutendl;

w=(Weight *)malloc(n*sizeof(Weight));

for(i=0;in;i++)

{

//cout”請輸入第”i+1″個結點編號及其權值（如a 100）:”endl;

printf(“請輸入結點編號及其權值（如a 100）:” );

scanf(“%1s%d”,c,wei);

w[i].elem=c;

w[i].m_weight=wei;

}

HuffmanCoding(HT,HC,w,n);

OutputHuffmanCode(HT,HC,n);

}

哈夫曼樹應用（C語言）

Huffman(C)

Input: C一組節點，節點中儲存了字符以及該字符在文件中出現的頻率

Output: Huffman樹的根節點

Algorithm:

n=length(C)

insert(Q,C) //註：把C中的每一個節點都插入minHeap中

for i 從0到n-2 do

創建一個新的空節點z

z.leftchild=x=extract-min(Q)

z.rightchild=y=extract-min(Q)

z.frequence=x.frequence+y.frequence

insert(Q,z)

end for

return extract-min(Q)

如圖所示，因為每次都取出2個最小的節點，然後合併它們。所以第一次選擇C和D合併為新的節點它的頻率是2。然後把這個新節點插入Q。而B和R的頻率都是2，和新的節點頻率相同，根據不同的min-heap算法，在此處可能有所不同。本例選擇的是先入先出，因此先合併B和R得到一個新節點4。之後再取出2個最小的節點，即新的2和新的4，合併它們得到新節點6。最後合併節點A和新節點6得到根節點11。

哈夫曼樹的c語言編程，急急急！

我寫的你看下！！有什麼問題可以交流下！！！

#include stdio.h

#includestring.h

#define N 26

typedef struct

{

int W,P,R,L;

}HTNode;

typedef struct

{

char ch;

char code[10];

}HTCode;

HTCode HC[27];

void select(HTNode HT[],int *min1,int *min2,int *a,int *b)

{

int i;int mina=100,minb=100;

int m,n;

for(i=1;i=2*N-1;i++)

{

if(HT[i].WminaHT[i].P==0HT[i].W)

{

mina=HT[i].W;

m=i;

}

if(HT[i].WminbHT[i].P==0HT[i].Wi!=m)

{

minb=HT[i].W;

n=i;

}

}

*min1=mina;

*min2=minb;

*a=m;

*b=n;

}

void Ecode(HTNode HT[])

{

char temp[10];

int i,j,k;

int c,ff;

for(i=1;i=26;i++)

HC[i].ch=96+i;

for(i=1;i=N;i++)

{ j=0;

for(c=i,ff=HT[c].P;ff;c=ff,ff=HT[c].P)

{

if(HT[ff].L==c) {temp[j]=’0′;j++;}

else {temp[j]=’1′;j++;}

}

j–;

for(k=0;k=j;k++)

HC[i].code[k]=temp[j-k];

HC[i].code[k]=’\0′;

}

printf(“以下為各字母的哈弗曼編碼：\n”);

for(i=1;i=26;i++)

printf(“%c: %s\n”,HC[i].ch,HC[i].code);

}

void Displaycode(HTCode HC[])

{

char ch;int i;

printf(“請輸入字符串：\n”);

while((ch=getchar())!=EOFch!=’\n’)

{

for(i=1;i=26;i++)

if(ch==HC[i].ch)

{

printf(“%s”,HC[i].code);

break;

}

}

}

void main()

{

HTNode HT[2*N-1];

int min1=100,min2=100;

int i,j,a=0,b=0;

int w[27]={0,8,3,2,4,2,2,1,3,4,2,3,2,1,5,3,3,2,1,2,5,3,3,3,2,3,6};

//各節點初始化。

for(i=1;i=N;i++)

{

HT[i].W=w[i];

HT[i].P=0;

HT[i].L=0;

HT[i].R=0;

}

//剩餘節點初始化。

for(i=N+1;i=2*N-1;i++)

{

HT[i].W=0;

HT[i].P=0;

HT[i].L=0;

HT[i].R=0;

}

for(j=N+1;j=2*N-1;j++)

{

select(HT,min1,min2,a,b);

HT[j].W=min1+min2;

HT[j].L=a;

HT[j].R=b;

HT[a].P=j;

HT[b].P=j;

}

Ecode(HT);

Displaycode(HC);

getchar();

}

關於C語言建立赫夫曼樹的問題，我不是很明白，下面是代碼：

下面是我寫程序的時候的注釋，兩種方法都寫上了。這個程序不能運行，主要是為了理解，注釋寫的很清楚的。

/*這只是講解，程序並不能運行*/

#includestdio.h

#includestdlib.h

#define OK 1

#define ERROR 0

typedef struct

{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

int a[100];

int s1,s2;

int Select()

/*在Select函數中，選取了兩個根節點權值最小的樹構造了一棵新的數，需要將這兩個最小的刪掉，將新的加入，再找兩個最小的，但如果這樣，我們就修改了樹了，最後得到

的樹中，我們刪除了一些結點，所以我想，將這些樹的權值放在一個整型數組中，去尋找最小的兩個*/

{

min=a[1];

s1=1;

for(i=2;i=a[0];++i)

if(mina[i])

{

s2=s1;

s1=i;

}

for(i=s1;in;++i)

a[i]=a[i+1];

for(i=s2;in;++i)

a[i]=a[i+1];

a[0]=a[0]-2;

return OK;

}

HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)

/*HT是樹，HC存放赫夫曼樹的葉結點的編碼，w存放葉結點的權值，n是葉結點的個數*/

{

int m,i,j,start,t;

if(n=1)

return OK;

m=2*n-1; /*因為有n個葉結點，所以共有2*n-1個結點*/

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*為m個節點分配空間，0結點不使用*/

if(!HT)

return ERROR;

for(p=HT,i=1;i=n;++i,++p)

{

p-weight=w[i]; /*數組w中存放葉結點的權值，從下標1開始*/

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;

} /*為非葉結點初始化，非葉結點的權值是待計算的*/

a[0]=n;

for(p=HT,i=1;i=a[0];++i,++p)

a[i]=p-weight;

for(i=n+1;i=m;++i)

{

Select(); /*找到a數組中兩個最小的元素是s1,s2，並且刪除它們,a[0]中存儲a中元素個數，要及時修改a[0]的值*/

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; /*將求得的新的結點的權值加入a數組中*/

a[0]=a[0]+1;

a[a[0]]=HT[i].weight;

} /*該循環是建赫夫曼樹*/

/*以下從葉子到根逆向求每個字符的赫夫曼編碼*/

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));

if(!HC)

return ERROR; /*為n個字符編碼分配頭指針向量，0號單元不使用*/

cd=(char *)malloc(n*sizeof(char));

if(!cd)

return ERROR; /*分配求編碼的工作空間*/

cd[n-1]=’\0′; /*編碼結束符*/

for(i=1;i=n;++i)

{

start=n-1; /*由於n-1位置已經存放了’/0’，所以下面用–start,從n-2的位置存放0,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)); /*各字符的編碼長度不等，故為每一個頭指針向量動態分配它所指向的空間大小，就是n-start*/

if(!H[i])

return ERROR;

t=1;

printf(“\n%d:”,i);

for(j=start;j=n-2;j++)

{

HC[i][t++]=cd[j];

printf(“%c”,cd[j]);

}

}

free(cd);

return HT;

}

/*由此得到的赫夫曼樹的前n個分量表示葉子結點，最後一個分量表示根結點*/

/*以上算法是從葉子到根逆向處理的*/

/*以下算法是從根出發，遍歷整棵赫夫曼樹，求得各個葉子結點所表示的字符的赫夫曼編碼*/

/*譯碼的過程是分解電文中字符串，從根出發，按字符’0’或’1’確定找左孩子或右孩子，直至葉子結點，便求得該子串相應的字符。*/

HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)

/*HT是樹，HC存放赫夫曼樹的葉結點的編碼，w存放葉結點的權值，n是葉結點的個數*/

{

HuffmanTree p;

char *cd;

int m,i,j,start,t,c,f;

if(n=1)

exit(OK);

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

if(!HT)

return ERROR;

for(p=HT+1,i=1;i=n;++i,++p)

{

p-weight=w[i];

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;

}

a[0]=n;

for(p=HT+1,i=1;i=a[0];++i,++p)

a[i]=p-weight;

for(i=n+1;i=m;++i)

{

Select();

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;

a[0]=a[0]+1;

a[a[0]]=HT[i].weight;

}

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));

if(!HC)

return ERROR; /*分配n個字符編碼的頭指針向量*/

p=m; /*m是結點總數*/

cdlen=0; /*應該是計數每一個編碼的長度*/

for(i=1;i=m;++i)

HT[i].weight=0; /*遍歷赫夫曼樹時用作結點的標誌(是否是weight域為0，表示沒有遍歷過，weight域為1，表示遍歷過)*/

while(p)

{

if(HT[p].weight==0)

{

HT[p].weight=1;

if(HT[p].lchild!=0)

{

p=HT[p].lchild;

cd[cdlen++]=’0′;

} /*左孩子不等於0，表示沒有走到左邊的盡頭，0就是NULL，*/

/*我們將一直執行這個if語句，直到走到左邊的盡頭，將所有左邊的邊全部賦值為0*/

else

if(HT[p].rchild==0)

{

HC[p]=(char *)malloc((cdlen+1)*sizeof(char));

cd[cdlen]=’\0′;

strcpy(HC[p],cd); /*當走到最左邊的時候，我們就得到了最左下那個結點的編碼，存儲在cd數組中，將它賦值到HC[p]中*/

}

}

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; /*因為這個編碼和上一個編碼只有最後一位是不一樣的，所以cdlen-1*/

}

}

return HT;

}

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

#includestdio.h

#includestdlib.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;i2*n-1;i++)

{

if(in)

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;in-1;i++)

{

m1=m2=MaxValue;

x1=x2=0;

for(j=0;jn+i;j++)

{

if(haffTree[j].weightm1haffTree[j].flag==0)

{

m2=m1;

x2=x1;

m1=haffTree[j].weight;

x1=j;

}

else if(haffTree[j].weightm2haffTree[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;in;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;jn;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;in;i++)

printf(” “);

if(bt-data!=0bt-data100)

{

if(n0)

{

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]im)

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]im) /*查找失敗返回數字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;p1word+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;jn;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;kn;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;p1word+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;p3weight+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(nMaxN)

{

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;in;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;p2weight+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!=1w!=2w!=3w!=4w!=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();

}