C语言哈夫曼树创建输出（静态链表）

小灰灰 2023-06-16 05:57 43阅读 0赞

#include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #define N 30
    #define M 2*N-1
    typedef struct {
    	int weight;
    	int parant;
    	int Lchild;
    	int Rchild;
    }HTNode,HuffmanTree[M+1];
    
    void Create_HuffmanTree(HuffmanTree ht,int w[],int n);//创建哈夫曼树 
    void select(HuffmanTree ht,int n,int *s1,int *s2);//在前n个选项中选权值最小，且双亲为0的两个结点 
    
    
    main()
    {
    	int n=5;
    	HuffmanTree ht;
    	int w[n]={5,7,3,2,8};
    	Create_HuffmanTree(ht,w,n);
    	int i;
    	 
    	printf("HuffmanTree\n"); 
    	for(i=0;i<2*n-1;i++)
    	{
    		printf("%d  %d %d %d %d\n",i,ht[i].weight,ht[i].parant,ht[i].Lchild,ht[i].Rchild);
    	}
    		
    } 
    
    void Create_HuffmanTree(HuffmanTree ht,int w[],int n)
    {
    	int i,j,s1,s2;
    	int m=2*n-1;
    	for(i=0;i<n;i++)
    	{
    		ht[i].weight=w[i];
    		ht[i].parant=0;
    		ht[i].Rchild=0;
    		ht[i].Lchild=0;
    	}
    	
    	for(i=n;i<m;i++)
    	{
    		ht[i].Lchild=0;
    		ht[i].parant=0;
    		ht[i].Rchild=0;
    		ht[i].weight=0;
    	}//right
    	
    	for(i=n;i<m;i++)
    	{
    		select(ht,i,&s1,&s2);
    		ht[i].weight=ht[s1].weight+ht[s2].weight;
    		ht[i].Lchild=s1; 
    		ht[i].Rchild=s2;
    		ht[s1].parant=i;
    		ht[s2].parant=i;
    	}
    	
    }
    
    void select(HuffmanTree ht,int n,int *s1,int *s2)
    {
    	int i,min1,min2;
    	min1=min2=100;
    	*s1=*s2=0;
    	for(i=0;i<n;i++)
    	{
    		if(ht[i].parant==0 && ht[i].weight<min1)
    		{
    			min2=min1;
    			min1=ht[i].weight;
    			*s2=*s1;
    			*s1=i;
    		}
    		else if(ht[i].parant==0 && ht[i].weight<min2 )
    		{
    			min2=ht[i].weight;
    			*s2=i;
    		}
    	 } 
    }

运行结果：

![20191124203555315.png][]

[20191124203555315.png]: https://img-blog.csdnimg.cn/20191124203555315.png