哈弗曼编码

数据压缩中的编码问题实验

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>

#define Minwight -1

typedef struct Node* ElementType;
struct Node {
	int Weight;
	char Key;
};
typedef struct HfTNode* HuffmanTree;
struct HfTNode {
	ElementType Data;
	HuffmanTree Left, Right;
};
typedef struct Heapstruct* MinHeap;
struct Heapstruct {
	HuffmanTree* Elements;
	int Size;
	int Capacity;
};
typedef struct SNode* PtrToSNode;
struct SNode {
	ElementType Data;
	PtrToSNode Next;![在这里插入图片描述](https://img-blog.csdnimg.cn/20200909153931694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Zpc2h5RmluZQ==,size_16,color_FFFFFF,t_70#pic_center)

};
typedef PtrToSNode Stack;

Stack CreateStack(void);//创建一个栈
int IsEmpty_Stack(Stack);//判断栈是否为空
void Push(Stack, ElementType);//将元素放入栈中
ElementType Pop(Stack);//将元素从栈顶拿出
ElementType GetStackTop(Stack);//查看栈顶元素
MinHeap CreateMinHeap(int MaxSize);
int IsEmpty_MinHeap(MinHeap H);
int IsFull_MinHeap(MinHeap H);
void Insert_MinHeap(MinHeap H, HuffmanTree Item);
HuffmanTree Delete_MinHeap(MinHeap H);
void MinMaking(MinHeap H, int Root);
void BuildMinHeap(MinHeap H);
HuffmanTree Huffman(MinHeap H);
void PrintPath(HuffmanTree T, int MaxSize);

int main(void)
{
	Stack S;
	int MaxSize;
	MinHeap H;
	HuffmanTree T;

	S = CreateStack();
	printf("输入关键字个数(#不可为关键字)\n");
	scanf("%d", &MaxSize);
	getchar();
	H = CreateMinHeap(MaxSize);
	for (int i = 1; i <= MaxSize; i++) {
		H->Elements[i] = (HuffmanTree)malloc(sizeof(struct HfTNode));
		H->Elements[i]->Left = NULL;
		H->Elements[i]->Right = NULL;
		H->Elements[i]->Data = (ElementType)malloc(sizeof(struct HfTNode));
		printf("输入关键字及出现频率\n");
		scanf("%c %d", &H->Elements[i]->Data->Key,&H->Elements[i]->Data->Weight);
		getchar();
	}//建立一个任意顺序存放关键字和权重的数组
	T = Huffman(H);//将这个数组转换成哈弗曼树
	PrintPath(T,MaxSize);//将哈弗曼树转换成编码![在这里插入图片描述](https://img-blog.csdnimg.cn/20200909153911872.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Zpc2h5RmluZQ==,size_16,color_FFFFFF,t_70#pic_center)

}
//将哈弗曼树转换成编码
void PrintPath(HuffmanTree T,int MaxSize)
{
	HuffmanTree PtoT;

	for (int i = 0; i < MaxSize; i++) {
		PtoT = T;
		while (1) {
			if (!PtoT->Left && !PtoT->Right) {
				printf("%c\n", PtoT->Data->Key);
				PtoT->Data->Key = '&';
				break;
			}
			else if (PtoT->Left && PtoT->Left->Data->Key != '&') {
				printf("1");
				PtoT = PtoT->Left;
			}
			else if (PtoT->Right && PtoT->Right->Data->Key != '&') {
				printf("0");
				PtoT = PtoT->Right;
			}
		}
	}
}
//以下为用到的堆函数
MinHeap CreateMinHeap(int MaxSize)
{
	MinHeap H;

	H = (MinHeap)malloc(sizeof(struct Heapstruct));
	H->Elements = (HuffmanTree*)malloc(sizeof(HuffmanTree) * (MaxSize + 1));
	H->Size = MaxSize;
	H->Capacity = MaxSize;
	H->Elements[0] = (HuffmanTree)malloc(sizeof(struct HfTNode));
	H->Elements[0]->Data = (ElementType)malloc(sizeof(struct Node));
	H->Elements[0]->Data->Key = '#';
	H->Elements[0]->Data->Weight = Minwight;

	return H;
}

int IsEmpty_MinHeap(MinHeap H)
{
	return (H->Size == 0);
}

int IsFull_MinHeap(MinHeap H)
{
	return (H->Size == H->Capacity);
}

void Insert_MinHeap(MinHeap H, HuffmanTree Item)
{
	int i;

	if (IsFull_MinHeap(H)) return;
	i = ++H->Size;//i相当于子结点下标，i/2相当于父结点下标 
	for (; H->Elements[i / 2]->Data->Weight > Item->Data->Weight; i /= 2)
		H->Elements[i] = H->Elements[i / 2];
	H->Elements[i] = Item;

}

HuffmanTree Delete_MinHeap(MinHeap H)
{
	HuffmanTree Item, MinItem;
	int Parent, Child;

	if (IsEmpty_MinHeap(H))
		return NULL;
	MinItem = H->Elements[1];
	Item = H->Elements[H->Size--];
		for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
			Child = Parent * 2;
			if (H->Elements[Child]->Data->Weight > H->Elements[Child + 1]->Data->Weight)
				Child++;
			if (H->Elements[Child]->Data->Weight > Item->Data->Weight)
				break;
			else
				H->Elements[Parent] = H->Elements[Child];
		}
	H->Elements[Parent] = Item;

	return MinItem;
}

void MinMaking(MinHeap H, int Root)
{
	int Parent, Child;
	HuffmanTree Item;

	Item = H->Elements[Root];
	for (Parent = Root; Parent * 2 <= H->Size; Parent = Child) {
		Child = Parent * 2;
		if (Child + 1 < H->Size && H->Elements[Child]->Data->Weight > H->Elements[Child + 1]->Data->Weight)
			Child++;
		if (H->Elements[Child]->Data->Weight > Item->Data->Weight)
			break;
		else
			H->Elements[Parent] = H->Elements[Child];
	}
	H->Elements[Parent] = Item;

}

void BuildMinHeap(MinHeap H)
{
	int i;

	for (i = H->Size / 2; i >= 1; i--) {
		MinMaking(H, i);
	}
}

HuffmanTree Huffman(MinHeap H)
{
	int i;
	HuffmanTree T;

	BuildMinHeap(H);
	while(H->Size > 1) {
		T = (HuffmanTree)malloc(sizeof(struct HfTNode));
		T->Left = Delete_MinHeap(H);
		T->Right = Delete_MinHeap(H);
		T->Data = (ElementType)malloc(sizeof(struct Node));
		T->Data->Key = '#';
		T->Data->Weight = T->Left->Data->Weight + T->Right->Data->Weight;
		Insert_MinHeap(H, T);//将新T插入最小值 
	}
	T = Delete_MinHeap(H);

	return T;
}
//以下为所用到的栈函数
Stack CreateStack(void)
{
	Stack S = (Stack)malloc(sizeof(struct SNode));

	S->Next = NULL;

	return S;
}

int IsEmpty_Stack(Stack S)
{
	return (S->Next == NULL);
}

void Push(Stack S, ElementType Sdata)
{
	PtrToSNode P;

	P = (PtrToSNode)malloc(sizeof(struct SNode));//创建新的栈结点
	P->Data = Sdata;
	P->Next = S->Next;//将栈顶链接在新栈顶后
	S->Next = P;//将新栈顶链接在栈头后
}

ElementType Pop(Stack S)
{
	if (IsEmpty_Stack(S)) {
		printf("The Stack is Empty.");

		return NULL;
	}
	else {
		PtrToSNode P;
		ElementType Sdata;

		P = S->Next;//找到栈顶结点
		Sdata = P->Data;//取出数据
		S->Next = P->Next;//栈头链接新的栈顶
		free(P);//释放原栈顶

		return Sdata;
	}
}

ElementType GetStackTop(Stack S)
{
	if (IsEmpty_Stack(S)) {
		printf("The Stack is empty.");

		return NULL;
	}
	else
		return S->Next->Data;
}