C语言 题目 1701: 数据结构-自顶向下的赫夫曼编码

题目描述

输入格式

输出格式

样例输入

8
5 29 7 8 14 23 3 11

样例输出

0110
10
1110
1111
110
00
0111
010

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct HuffmanCode{
	int weight;
	int parent;
	int lchild;
	int rchild;
}HuffmanCode,*HuffmanTree;
void initialHuffmanCode(HuffmanTree,int,int);//初始化结点 
void creatHuffmanTree(HuffmanTree,int,int);//构造哈夫曼树 
void HuffmanCoding(char**,HuffmanTree,int);//对哈夫曼树进行编码 
void TraverseHuffmanCode(char**,int);//自下而上进行遍历 
int sum_(HuffmanTree,int);//求哈夫曼树中所有结点权重和 
int main(){
	int n;
	scanf("%d",&n);
	int m=2*n-1;//n个叶子结点共有2*n-1个结点 
	char **HC=(char**)malloc(n*sizeof(char*));//动态分配内存，可以看成二维数组 
	HuffmanCode hc[m];//结点 
	initialHuffmanCode(hc,n,m);
	creatHuffmanTree(hc,n,m);
	HuffmanCoding(HC,hc,n);
	TraverseHuffmanCode(HC,n);
} 
void initialHuffmanCode(HuffmanTree ht,int n,int m){
	for(int i=0;i<m;i++){
		if(i<n){
			scanf("%d",&(ht[i].weight));
		}
		ht[i].parent=-1;//初始化为-1 
		ht[i].lchild=-1;
		ht[i].rchild=-1;		
	}
}
int sum_(HuffmanTree ht,int i){
	int sum=0;
	for(int j=0;j<i;j++){
		if(ht[j].parent==-1)//当某结点的已经成为左或右子树时，此结点不参与运算 
		sum+=ht[j].weight;
	}
	return sum;
}
void creatHuffmanTree(HuffmanTree ht,int n,int m){
	int min1,min2;//min1为权重最小，min2为次小 
	int index1,index2;//index1位序最小，index2位序次小 
	for(int i=n;i<m;i++){
		min1=sum_(ht,i);//每次遍历获得当前哈夫曼树权重 
		min2=min1;
		for(int j=0;j<i;j++){//先获得最小权重及下标 
			if(ht[j].parent==-1){
				if(ht[j].weight<min1){
					min1=ht[j].weight;//
					index1=j;
				}
			}
		}
		ht[index1].parent=i;//双亲结点位序赋值 
		for(int j=0;j<i;j++){//获得次小权重及下标 
			if(ht[j].parent==-1){
				if(ht[j].weight<min2){
					min2=ht[j].weight;
					index2=j;
				}
			}
		}
		ht[index2].parent=i;
		ht[i].weight=min1+min2;
		if(index1>index2){//需要注意，这里需要比较一下最小和次小的位序！！！ 
			int t=index2;
			index2=index1;
			index1=t;
		}
		ht[i].lchild=index1;//左子树为最小位序，右子树为次小位序 
		ht[i].rchild=index2;
	}
}
void HuffmanCoding(char** HC,HuffmanTree ht,int n){
	int m=2*n-2;//因为下标从0开始，所以m值设为2*n-2 
	int cnt=0;//编码字符下标 
	char* p=(char*)malloc(sizeof(char)*n+1);//因为不确定n个结点最大编码长度为多少，所以分配内存为n+1 
	for(int i=0;i<2*n-1;i++){
		ht[i].weight=0;//初始化，全设置为0 
	}
	while(m!=-1){//当最终遍历回到根结点时，也就是根结点的parent==-1时，停止遍历 
		if(ht[m].lchild==-1){//因为哈夫曼树只有度为0和2的结点，没有左孩子，也就是没有右孩子，开始拷贝 
				p[cnt]='\0';
				HC[m]=(char*)malloc(sizeof(char)*(cnt+1));
				strcpy(HC[m],p);
				m=ht[m].parent;//这里直接返回其父结点 
				cnt--;
				continue;//不再执行剩余语句，回到根结点重新判断 
			}
		if(ht[m].weight==0){//当weight为0时，访问其左结点 
			ht[m].weight++;//当前结点weight++，代表访问过一次 
			if(ht[m].lchild!=-1){//当前结点有左孩子，让左孩子成为下一个新根结点 
				m=ht[m].lchild;
				p[cnt++]='0';//路径为'0' 
			}
		}
		else if(ht[m].weight==1){//当访问次数为一时，表示访问过它的左结点，现在开始访问他的右结点 
			ht[m].weight++;//访问次数加一 
			if(ht[m].rchild!=-1){
				m=ht[m].rchild;
				p[cnt++]='1';
			}
		}
		else{//当访问次数为二时，也返回它的父结点，cnt减一 
			m=ht[m].parent;
			cnt--;
		}
	}
}
void TraverseHuffmanCode(char** HC,int n){//遍历 
	for(int i=0;i<n;i++){
		printf("%s\n",HC[i]);
	}
}