C语言 数据结构

Question

 

Answer 1

#include <stdio.h>
#include <stdlib.h>
 
/*	
author:YXP
e-mail:[e-mail]
如有问题，欢迎和我联系~
转载请标明出处~
*/
 
#define USED 1
#define UNUSED 0 
#define CHILDNUM 2
 
struct Node {
	int weight;
	int *child;/*存储孩子的位置*/
	int parent;/*存储父亲的位置*/
	int state;/*used = 1; Unsed = 0*/
	int level;/*当前点所在的层数*/
	int code;/*编码*/ 
};
 
struct Node** ini_Node_arr (int len,int* element);				/*初始化Haffman编码数数组*/ 
struct Node** Build_Haffman_tree (int* element,int len);		/*构建Haffman编码树*/ 
int Find_2min_position (int* store, struct Node** Arr,int len);	/*在Arr中，找到最小和次小的权值的位置*/
int Create_newNode (struct Node** Arr,int* store,int All_len);	/*创建新的Haffman编码树 节点*/ 
int Decode (struct Node** Arr,int len);							/*解码 Haffman树*/ 
int Print_Code (struct Node** Arr,int len);						/*打印待编码树的编码*/ 
 
int main() {
	
	int len = 8;	/*待编码数 的个数*/ 
	int element[8] = {5,8,17,3,24,2,7,49};/*待编码数*/ 
	
	struct Node** Arr = Build_Haffman_tree (element,len);
	
	int i, All_len = (int)((len*(len+1)/2)+1);
	
//	for (i=0;i<All_len;i++){ //显示Haffman树创建过程 
//		if (Arr[i] != NULL){
//			printf("%d-",Arr[i]->weight);
//		}
//	}
	
	printf ("##Haffman Code##");
	Decode (Arr,len);
	Print_Code (Arr,len);
		
	return 0;
}
 
 
struct Node** ini_Node_arr (int len,int* element)	/*初始化Haffman编码数数组*/ 
{
	int All_len = (int)((len*(len+1)/2)+1);
	struct Node** Arr = (struct Node**)malloc((All_len)*sizeof(struct Node*));
	int i;
	for (i = 0;i<len;i++){
		Arr[i] = (struct Node*)malloc(sizeof(struct Node));
		Arr[i]->child = NULL;
		Arr[i]->parent = -1;
		Arr[i]->level = 0;		
		Arr[i]->state = 0;
		Arr[i]->weight = element[i];
		Arr[i]->code = 0;
	}
	for (i = len;i<All_len;i++){
		Arr[i] = NULL;
	}
	return Arr;
}
 
 
struct Node** Build_Haffman_tree (int* element,int len)/*构建Haffman编码树*/
{
	int store [2];
	store [0] = 0;store [1] = 0;
	
	struct Node** Arr = ini_Node_arr (len,element);
	
	int All_len = (int)((len*(len+1)/2)+1);
	
	while (1){
		store [0] = -1;store [1] = -1;
		Find_2min_position (store, Arr,All_len);
		if (store[1] == -1){
			goto END;
		}
		Create_newNode (Arr,store,All_len);
	}
	
	END:;
	return Arr;
}
 
 
int Find_2min_position (int* store, struct Node** Arr,int len)	/*在Arr中，找到最小和次小的权值的位置*/ 
{
	int min_p1 = -1, min_p2 = -1;
	int i;
	for (i=0;i<len;i++){
		if (Arr[i] != NULL){
			if (Arr[i]->state == UNUSED){
				if (min_p1 == -1){
					min_p1 = i;
				}else{
					if (Arr[i]->weight < Arr[min_p1]->weight){
					min_p2 = min_p1;
					min_p1 = i;					
					}else{
						if (min_p2 == -1){
							min_p2 = i;
						}else{
							if (Arr[i]->weight < Arr[min_p2]->weight){
								min_p2 = i;
							}
						}
					}											
				}
			}		
		}	
	}
	store[0] = min_p1;
	store[1] = min_p2;
	
	return 0;
}
 
int Create_newNode (struct Node** Arr,int* store,int All_len)	/*创建新的Haffman编码树 节点*/ 
{
	int child1 = store[0], child2 = store[1];
	int i = 0;
	
	while (Arr[i] != NULL){
		i++;
	}
	 
	Arr[i] = (struct Node*)malloc(sizeof(struct Node));
	
	Arr[i]->child = (int*)malloc(CHILDNUM*sizeof(int));
	Arr[i]->child[0] = child1;
	Arr[i]->child[1] = child2;
	
	Arr[child1]->state = USED;
	Arr[child1]->code = 0;/*左边*/
	Arr[child1]->parent = i;
	
	Arr[child2]->state = USED;
	Arr[child2]->code = 1;/*右边*/ 
	Arr[child2]->parent = i;
	
	Arr[i]->weight = Arr[child1]->weight + Arr[child2]->weight;
	Arr[i]->level ++;
	Arr[i]->state = 0;
	
	return 0;
}
 
 
int Decode (struct Node** Arr,int len)/*解码 Haffman树*/ 
{
	int temp_parent = -1,Total_parent = 0;
	while (Arr[Total_parent] != NULL){
		Total_parent++;
	}
	
	int i;
	for (i=0;i<len;i++){
		temp_parent = Arr[i]->parent;
		while(temp_parent != (Total_parent-1)){
			Arr[i]->code = (Arr[i]->code)*2+Arr[temp_parent]->code;
			Arr[i]->level ++;
			temp_parent = Arr[temp_parent]->parent;
		}	
	}
	
	return 0; 
}
 
 
int Print_Code (struct Node** Arr,int len)	/*打印待编码树的编码*/ 
{
	int i;
	int temp,code;
	for (i=0;i<len;i++){
		printf("\n>>NUM = %d\t",Arr[i]->weight);
		temp = Arr[i]->level;
		code = Arr[i]->code;
		printf("Code: ");
		while (temp >= 0){
			printf ("%d",code%2);
			code = code/2;
			temp--;
		}
	}
	return 0;
}