数据结构学习笔记（11）哈夫曼树与哈夫曼编码

完整代码+测试函数

#pragma once
#include
#include

//定义哈夫曼树的每个结点，设计哈夫曼树的结点存储结构为双亲孩子存储结构
typedef struct
{
	int weight;
	int flag;
	int parent;
	int leftChild;
	int rightChild;
}HaffNode;


//定义哈夫曼编码的结构，start表示每个哈夫曼编码在数组中的起始位置，
//weight表示从权值为几的叶节点开始遍历到根节点
typedef struct
{
	int bit[MaxBit];
	int start;
	int weight;
}Code;

//构造哈夫曼树
//建立叶结点个数为n,权值数组为weight的哈夫曼树haffTree
void Haffman(int weight[], int n, HaffNode haffTree[])
{
	int i, j, m1, m2, x1, x2;
	//哈夫曼树初始化，（刚开始时每个结点都是一颗独立的树），n个叶结点的二叉树共有2n-1个结点
	for (i = 0; i < 2 * n - 1; i++)
	{
		if (i < n)
		{
			haffTree[i].weight = weight[i];
		}
		else
		{
			haffTree[i].weight = 0;
		}
		haffTree[i].parent = -1;
		haffTree[i].flag = 0;
		haffTree[i].leftChild = -1;
		haffTree[i].rightChild = -1;
	}
	//构造哈夫曼树的n-1个非叶结点
	for(i=0;istart = n - 1;//不等长编码的最后一位为n-1
		cd->weight = haffTree[i].weight;//取得编码对应的权值
		child = i;
		parent = haffTree[child].parent;
		//由叶结点向上直到根结点
		while (parent != -1)
		{
			if (haffTree[parent].leftChild == child)
			{
				cd->bit[cd->start] = 0;//左孩子分支编码0
			}
			else
			{
				cd->bit[cd->start] = 1;//右孩子分支编码1
			}
			cd->start--;
			child = parent;
			parent = haffTree[child].parent;
		}
		for (j = cd->start + 1; j < n; j++)
		{
			haffCode[i].bit[j] = cd->bit[j];//保存每个叶结点的编码
		}
		haffCode[i].start = cd->start + 1;//保存叶结点编码的起始位
		haffCode[i].weight = cd->weight;//保存编码对应的权值
	}
	}

#include
#include
#define Maxvalue 10000//初始设定的最大权值
#define MaxBit 4//初始设定的最大编码位数
#include"Haffman.h";

void main()
{
	int i, j, n = 4;
	int weight[] = { 1,3,5,7 };
	HaffNode* myHaffTree = (HaffNode*)malloc(sizeof(HaffNode) * (2 * n - 1));
	Code* myHaffCode = (Code*)malloc(sizeof(Code) * n);
	if (n > 4)
	{
		printf("给出的n越界，修改nn");
		exit(1);
	}
	Haffman(weight, n, myHaffTree);
	HaffmanCode(myHaffTree, n, myHaffCode);
	//输出每个叶结点的哈夫曼编码
	for (i = 0; i < n; i++)
	{
		printf("weight=%d  Code= ", myHaffCode[i].weight);
		for (j = myHaffCode[i].start; j < n; j++)
		{
			printf("%d", myHaffCode[i].bit[j]);
			
		}
		printf("n");
	}
}