霍夫曼编码

1)包含任务或问题描述和分析

霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。

霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

2)设计与实现

设计一个带父指针的二叉树,将节点排序后放入一个堆中保存,循环构造二叉树,最后遍历二叉树,再用堆保存叶节点回溯的数值,最后输出数值得到霍夫曼编码

3)测试例子与结果分析

测试用例:(这里的测试用例为出现的频度)

 结果:

4)带注释的源代码

#include<stdio.h>
#include<stdlib.h>
#define MAX  99
typedef struct {
	int data;
	struct Node* lchild, * rchild,* father;//创建三叉链表 
}Node, * Root;
typedef struct {//指针数组 
	Root HTree[99];
	int top;
}List;

List* SortNode(List* l)//对表中的结点进行排序以选出最小的两个点 
{
	int i, j;
	for (i = 0; i < l->top; i++)
	{

		for (j = 0; j < l->top - i; j++)
		{
			if (l->HTree[j]->data < l->HTree[j + 1]->data)
			{
				Node* temp = l->HTree[j];
				l->HTree[j] = l->HTree[j + 1];
				l->HTree[j + 1] = temp;
			}
		}
	}
	return l;

}
List* CreatList(List* l)
{
	if (l == NULL)//若表为空则申请一个新的表并初始化 
	{
		l = (List*)malloc(sizeof(List));
		if (l == NULL)exit(0);
		else
			l->top =-1;
	}
	int num;
	while ((scanf_s("%d", &num)) != EOF && l->top != MAX)//循环输入表的结点 
	{
		Node* temp = (Node*)malloc(sizeof(Node));
		temp->data = num;
		temp->lchild = NULL;
		temp->rchild = NULL;
		l->top++;
		l->HTree[l->top] = temp;
		
	}
	return SortNode(l);
}

Root CreatHUffmanTree(List* l)
{
	while (l->top >= 1)//如果表中有两个或以上的元素则循环 
	{
		Node* temp = (Node*)malloc(sizeof(Node));
		temp->data = l->HTree[l->top]->data + l->HTree[l->top - 1]->data;
		temp->lchild = l->HTree[l->top];
		l->HTree[l->top]->father=temp;
		temp->rchild = l->HTree[l->top - 1];
		l->HTree[l->top-1]->father=temp;
		l->top--;
		if (l->top == 0){
			temp->father=NULL;
			return temp;
		}
		else l->HTree[l->top] = temp;
		l = SortNode(l);//每次加入结点就进行一次排序 
	}
}
void Printcode(Node *n)//回溯输出哈夫曼编码 
{
	int stack[99];//用栈保存数据 
	int top=-1; 
	Node *temp=n->father;
	while(temp!=NULL){
	if(temp->lchild==n){
		stack[++top]=0;
		n=temp;
		temp=temp->father;
	}
	else if(temp->rchild==n)
	{
		stack[++top]=1;
		n=temp;
		temp=temp->father;
	}
	
	}
	while(top>=0)printf("%d",stack[top--]);
}

void PrintTree(Node* n) {//前序遍历哈夫曼树 
	if (n != NULL)
	{
		if(n->lchild==NULL&&n->rchild==NULL)
		{
			printf("%d   :",n->data);
			Printcode(n);
			printf("\n");
		}
		PrintTree(n->lchild);
		PrintTree(n->rchild);
	}

}
int main()
{
	List* l = NULL;
	l = CreatList(l);
	Node* node = CreatHUffmanTree(l);
	PrintTree(node);

	return 0;
}