huffmantree.c

这是一系列关于二叉树的创建,查找,霍夫曼等数据结构编程,

#include "malloc.h"
#include "stdio.h"
#include "string.h"
typedef struct 
{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组赫夫曼树
typedef char **HuffmanCode;//动态分配数组存储赫夫曼树编码表

void select(HuffmanTree HT,int i,int *s1,int *s2)
{ // 在赫夫曼数中选择两个其parent为0 且他们的权值最小的结点的序号
	int j,r,k;//控制循环的变量
	unsigned int first,second;//保存权值最小的两个结点的变量0
	for(j = 1;j <= i;j++)
	{
		if(HT[j].parent == 0)
		   first = HT[j].weight;		
	       break;
	}
	for(r = 1;r <= i;r++)//寻找最小权值
	{
		if( first > HT[r].weight && HT[r].parent == 0 )
		first = HT[r].weight;
	}
	r = 1;
	while(first != HT[r].weight && r <= i )//寻找权值最小的序号

		r++;
		*s1 = r;

	for(k = 1;k <= i;k++)
	{
		if(HT[k].parent == 0 && k != j)
			second =HT[k].weight;	
			break;
	}
	for(r = 1;r <= i;r++)//寻找最小权值（其序号不同于first所指的序号）
	{
		if(r != k && second > HT[r].weight && HT[r].parent == 0 && r != *s1 )
		second = HT[r].weight;
	}
	r = 1;
	while( second != HT[r].weight&& r <= i )//寻找权值最小的序号
		r++;
	*s2 = r;
	
	if(*s1 > *s2)
	{ //若s1在赫夫曼树中的位置比s2小则将他们进行交换
		r = *s1;
		*s1 = *s2;
		*s2 = r;
	}


}
void main(void)
{
	HuffmanTree p,HT;
	HuffmanCode HC;
	unsigned int c,f;
	int i;
	int	*w;//字符的权
	int m,n;
	int s1,s2;//分别为两个带权最小且其parent为零的结点的序号
	char *cd;//编码结束位置
	int start;//编码结束位置
	printf("please input the number of n: ");
	scanf("%d",&n);
	printf("\n");
	if(n <= 1) return;
	m = 2*n - 1;
	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
	for(p = HT + 1,i = 1;i <= n; ++i,++p,++w)
	{ //给赫夫曼树前n个结点赋初值
		w = (int *)malloc(sizeof(int));
		printf("please input the value of the weight :");
		scanf("%d",w);
		printf("\n");
		p->weight = *w;
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
	}
	for(;i <= m;++i,++p)
	{ //给赫夫曼树后n - 1个结点赋初值
		p->weight = 0;
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
	}
	for(i = n + 1;i <= m;++i)
	{ //建立赫夫曼数
		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; 
	}
	HC = (HuffmanCode)malloc((n + 1) * sizeof(char *));//分配n个字符编码的头指正向量
	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[start]);//从cd复制编码到HC
	}
	printf("output the code :\n");
	for(i =1;i<= n;i++)
		printf("%s\n",HC[i]);
	free(cd);
}