#include <stdio.h>
#include <stdlib.h>
typedef struct Tree
{
int weight;
int left;
int right;
int parent;
电网技术
}*tree;
void CreateHuffman(int n)
{
int i;
int m1,m2,x1,x2;
tree Huffman[100];
for(i=0;i< 2*n-1;i++)
{
Huffman[i] = (tree) malloc(sizeof(struct Tree));
}
for(i=0;i<n;i++)
{
scanf("%d",&Huffman[i]->weight);
}
for(i=0;i<2*n-1;i++)
{
Huffman[i]->parent = -1;
Huffman[i]->left = -1;
Huffman[i]->right = -1;
}
int j;
for(i=0;i<n-1;i++)
{
m1= m2= 65536;
x1 =x2 = 0;
for(j=0;j<n+i;j++)
{
if( Huffman[j]->weight < m1 && Huffman[j]->parent == -1)
{
m1 = Huffman[j]->weight ;
x1 = j;
}宝泉岭公安局
for(j=0;j<n+i;j++)
{
if( Huffman[j]->weight < m2 && Huffman[j]->parent == -1 && x1 != j)
{
m2 = Huffman[j]->weight ;
x2 = j;
}
}
Huffman[x1]->parent = n+i; Huffman[x2]->parent = n+i;
Huffman[n+i]->weight =Huffman[x1]->weight + Huffman[x2]->weight ;
Huffman[n+i]->left =x1; Huffman[n+i]->right =x2;
}
for(i=0;i<2*n-1;i++)
{
printf("%d,", Huffman[i]->weight);雅芳贿赂门
}
printf("\n");
威海市城里中学for(i=0;i<2*n-1;i++) {
printf("%d的左结点的下标为%d，右结点的下标为%d\n",Huffman[i]->weight,Huffman[i]->left,Huffman[i]->right); }
char s[100]; int x; i--; x = i; int k; k=0;
int rs[100];int ls[100]; i=1; tree q[100];
int sum=0;
for(j=0; j<100 ;j++)
{
rs[j] =0;ls[j] =0; s[j]='\0';
}
while( i != 0)
{
if(i==1 && k==0 )
{
q[i] = Huffman[x];
s[i-1] = '*';
k++;
}
while(q[i]->left !=-1 && ls[i] == 0)
{
x =Huffman[x]->left;
ls[i] = 1; i++; k++;
q[i] = Huffman[x];
s[i-1] ='0';
通感ls[i] =0; rs[i] = 0;
}
if(( q[i]->left ==-1&& q[i]->right != -1 && rs[i] ==0 ) || (ls[i] ==1 && q[i]->right != -1&& rs[i] ==0 ) )
{
x =Huffman[x]->right;
rs[i] =1; i++; k++;
q[i] = Huffman[x];
s[i-1] ='1';
ls[i] =0; rs[i] = 0;
}
if( (q[i]->left ==-1 && q[i]->right ==-1 ) )
{
printf("%d:",q[i]->weight);
for( j =1 ; j <i;j++)
printf("%c",s[j]);
printf("\n"); sum+= q[i]->weight *(i-1);
}
if( (q[i]->left ==-1 && rs[i] == 1 ) ||(q[i]->left ==-1 && q[i]->right == -1)
||(q[i]->right ==-1 && ls[i] == 1 ) ||( rs[i] ==1&& ls[i] == 1 ) )
{
i--; k++;
Huffman[x] =q[i];
}
}
}
void main()
{
int num; printf("输入叶子结点个数：");scanf("%d",&num);
CreateHuffman( num);
printf("\n");
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议