Demo entry 6590514

11

   

Submitted by anonymous on Jun 04, 2017 at 11:18
Language: C. Code size: 1.4 kB.

HTNode *HuffmanCoding(int n)//构造哈夫曼树
{ 	
	void select(HTNode *HT,int l,int *s1,int *s2); //函数声明 
    int i,m,s1,s2;
	HTNode *HT;
    if(n<=1) 
    {
    	printf("结点个数过少,不能组建哈弗曼树!\n"); 
        return NULL;//只有一个结点不进行编码,直接exit(1)退出。
    }

    m=2*n-1;//哈弗曼编码需要开辟的结点大小为2n-1
    HT=(HTNode *)malloc((m+1)*sizeof(HTNode));//开辟哈夫曼树结点空间 m+1 。为了对应关系,我们第0个空间不用。
    
	for(i=1;i<=m;i++)//不使用0号单元
	{
		HT[i].parent=0; 
		HT[i].lchild=0; 
		HT[i].rchild=0;//初始化 
	}
    //输入结点权值
    for(i=1;i<=n;i++)
    {  
        printf("请输入HT[%d]的数据和权值:",i);  
        scanf(" %c %d",&HT[i].data,&HT[i].weight); 
    }
    //构造哈夫曼树
    for(i=n+1;i<=m;i++)
    {
        select(HT,i-1,&s1,&s2);//按权值查找出最小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;//赋权和
    }
    return HT;
}
void select(HTNode *HT,int l,int *s1,int *s2)//搜索最小的两个结点 
{
	int i,max1=32767,max2=32767,temp;//max1和max2用来判断权值最大
	for(i=1;i<=l;i++)//从头开始遍历 
	{
		if (HT[i].parent==0&&HT[i].weight<max1)//父结点为空并且权值小于max1 
		{
			max1=HT[i].weight;//则将将权值赋给max1 
			*s1=i;//用s1存住该点的i值 
		}
	}	
	temp=HT[*s1].weight;//记录最小权值 
	HT[*s1].weight=32767;//权值设为最大,目的是为了寻找第二小的值 
	for(i=1;i<=l;i++)
	{
		if(HT[i].parent==0&&HT[i].weight<max2)
		{
			max2=HT[i].weight;
			*s2=i;
		}
	}
	HT[*s1].weight=temp;//将最小结点得权值赋回 
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).