C言語でハフマンの木を実現する方法
本論文の実例はC言語のハフマンツリー実現の具体的なコードを共有しています。
準備：
1、構造体を定義し、ノードを表す。この構造体には4つのメンバー変数があり、それぞれはこのノードの権利値であり、親ノードおよび左右のサブノードの下付きであることを表している。
2、各ノードの権能値を保存するための整形配列を定義する。
3、整形配列を定義し、ハフマンコードを保存するために使用します。もちろん、ハフマンコードを保存するために整形配列を定義することもできます。
ハフマンツリーを構築する:
1、このハフマンツリーに構造体の配列を作成します。割り当てられた空間は2＊n−1です。ハフマンの木の性質を知っています。与えられたn個の葉っぱのノードで、このn個の葉っぱのノードからなるハフマンの木は全部で2＊n－1個のノードを含んでいます。
2、構造体配列の前のn個はn個の葉っぱノードを保存するために使用され、後のn−1個のノードは親ノードを保存するために使用される。この時、私たちはこの構造体配列を遍歴して、すべてのノードの初期化を行う必要があります。すなわち、ノードの権利値は構造体配列のそれぞれの下付き標的に対応する値です。そして、ノードの親ノードとサブノードの下に−1と表示されます。このノードに親ノードがないと同時に、サブノードもないということです。
3、配列を巡回して、配列の中の2つの最小の葉っぱノードを取得し、その後、それらの権能値を統合して新しいノードを構成する。このステップでは、この2つの最小ノードが構造体配列における下付きスケーリングを知る必要があります。このようにしてこそ、親ノードの左右のサブノードの下付きを知ることができ、親ノードを初期化する際に必要となります。
4、n-1回操作したら、構築が完了したことを示します。
ハフマンコードを取得:
1、私たちはすべてのノードの権利値を一つの配列に割り当て、そしてハフマンツリーのノードの下付き文字とこの配列の下付き文字は一つに対応しているので、私たちはまず配列の中でこの数字の下付き文字を取得する必要があります。彼がハフマンツリーの中の下付き文字もこれです。そして、その親ノードの方向に行きます。現在のノードが親ノードの右サブノードである場合、配列arr 2に1を格納します。さもなければ、文字は0を配列arr 2に格納します。このステップを繰り返して、現在のノードの親ノードが空になるまで、およびルートノードを巡回しました。
2、手順を繰り返します。一、数字を保管する配列はすでにいっぱいになりました。この時はすでにすべての数字のハフマンコードを出力しました。
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。
準備：
1、構造体を定義し、ノードを表す。この構造体には4つのメンバー変数があり、それぞれはこのノードの権利値であり、親ノードおよび左右のサブノードの下付きであることを表している。
2、各ノードの権能値を保存するための整形配列を定義する。
3、整形配列を定義し、ハフマンコードを保存するために使用します。もちろん、ハフマンコードを保存するために整形配列を定義することもできます。
ハフマンツリーを構築する:
1、このハフマンツリーに構造体の配列を作成します。割り当てられた空間は2＊n−1です。ハフマンの木の性質を知っています。与えられたn個の葉っぱのノードで、このn個の葉っぱのノードからなるハフマンの木は全部で2＊n－1個のノードを含んでいます。
2、構造体配列の前のn個はn個の葉っぱノードを保存するために使用され、後のn−1個のノードは親ノードを保存するために使用される。この時、私たちはこの構造体配列を遍歴して、すべてのノードの初期化を行う必要があります。すなわち、ノードの権利値は構造体配列のそれぞれの下付き標的に対応する値です。そして、ノードの親ノードとサブノードの下に−1と表示されます。このノードに親ノードがないと同時に、サブノードもないということです。
3、配列を巡回して、配列の中の2つの最小の葉っぱノードを取得し、その後、それらの権能値を統合して新しいノードを構成する。このステップでは、この2つの最小ノードが構造体配列における下付きスケーリングを知る必要があります。このようにしてこそ、親ノードの左右のサブノードの下付きを知ることができ、親ノードを初期化する際に必要となります。
4、n-1回操作したら、構築が完了したことを示します。
ハフマンコードを取得:
1、私たちはすべてのノードの権利値を一つの配列に割り当て、そしてハフマンツリーのノードの下付き文字とこの配列の下付き文字は一つに対応しているので、私たちはまず配列の中でこの数字の下付き文字を取得する必要があります。彼がハフマンツリーの中の下付き文字もこれです。そして、その親ノードの方向に行きます。現在のノードが親ノードの右サブノードである場合、配列arr 2に1を格納します。さもなければ、文字は0を配列arr 2に格納します。このステップを繰り返して、現在のノードの親ノードが空になるまで、およびルートノードを巡回しました。
2、手順を繰り返します。一、数字を保管する配列はすでにいっぱいになりました。この時はすでにすべての数字のハフマンコードを出力しました。
#include<stdio.h>
#define MAX_SIZE 1000
typedef struct NODE Node;
struct NODE{
int weight;//
int parent,lchild,rchild;
};
/*
， ， ，
，
*/
void initNode(Node &node,int weight,int parent,int lchild,int rchild){
node.weight = weight;
node.lchild = lchild;
node.rchild = rchild;
node.parent = parent;
}
/*
1、 n ， ， n * 2 - 1 ， n
， n - 1
2、 ， ， ，
、 -1， n
3、 ， ， ， ，
4、 。
5、 3，4 ， ，
*/
void createHuffmanTree(Node *node,int *arr,int n){
//n n ，arr
int i,j,min1,min2,x1,x2,total;//min1: ，min2: ,x1: ，x2:
for(i = 0; i < n; i++){
initNode(node[i],arr[i],-1,-1,-1);// initNode ，
}
total = n * 2 - 1;//total
for(i = n; i < total; i++){
//i n ， （ n ）
min1 = 65432;//
min2 = min1;
x1 = x2 = 0;// 0
for(j = 0; j < i; j++){
//
if(node[j].parent == -1){
// parent -1， ，
if(node[j].weight < min1){
// min1 ， min2，min1，
min2 = min1;
x2 = x1;
min1 = node[j].weight;
x1 = j;
}else if(node[j].weight < min2){
/*
，
， ， min2, x2
*/
min2 = node[j].weight;
x2 = j;
}
}
}
/*
， i，
i ,
*/
node[x1].parent = i;
node[x2].parent = i;
initNode(node[i],min1 + min2,-1,x1,x2);//
}
}
void huffmanCode(Node *node,int child,int *str){
//str
int i,parent,j = 0,e;
parent = node[child].parent;//
while(parent != -1){
if(node[parent].lchild == child){
// ， 0 , 1
str[j++] = 0;
}else{
str[j++] = 1;
}
child = parent;
parent = node[child].parent;
}
e = j;// ，j ， j - 1 ，
for(j = e - 1; j>= 0; j--)
printf("%d",str[j]);
printf("
");
}
int main(){
Node node[MAX_SIZE];
int arr[MAX_SIZE];// ，
int arr2[MAX_SIZE];//arr2
int n,i,j,e;
printf(" :");
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%d",&arr[i]);
createHuffmanTree(node,arr,n);//
/*
:
1、 arr，
2、 ， ，
， 0 ， 1 arr2
3、 arr2
*/
for(i = 0; i < n; i++){
huffmanCode(node,i,arr2);// ，
}
return 0;
}以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。