投稿
程序员

哈夫曼树的创建和编码和译码等操作c语言

作者：admin 2021-06-10 我要评论

有一说一我太菜了编码花了我十几个个小时才完成终究是我不配了。 今天花了点时间把哈夫曼树的编码和译码也完成了在这儿补充更新一下源文件。 后续会补充一下注释...

（在说正事之前，我要推荐一个福利：你还在原价购买阿里云、腾讯云、华为云服务器吗？那太亏啦！来这里，新购、升级、续费都打折，能够为您省60%的钱呢！2核4G企业级云服务器低至69元/年，点击进去看看吧>>>)

有一说一，我太菜了，编码花了我十几个个小时才完成，终究是我不配了。
今天花了点时间，把哈夫曼树的编码和译码也完成了，在这儿补充更新一下源文件。
后续会补充一下注释。

运行结果如下

在这里插入图片描述

源文件：

#include "优先权队列.h"
#include "哈夫曼的stack.h"
//构造一棵空的二叉树
void Create(BinaryTree* bt)   
{
	bt->root = NULL;
}

HFMTNode* NewBTNode(ElemType w, HFMTNode* lC, HFMTNode* rC)
{
	HFMTNode* p = (HFMTNode*)malloc(sizeof(HFMTNode));
	p->w = w;
	p->lChild = lC;
	p->rChild = rC;
	p->Element = 0;
	return p;
}
void MakeTree(BinaryTree* bt,ElemType w, BinaryTree* left, BinaryTree* right)
{
	if (left == NULL || right == NULL)
		return;
	else
	{
		bt->root = NewBTNode(w, left->root,right->root);
		left->root = right->root = NULL;
	}
}
//哈夫曼先序遍历
void PreOrder(HFMTNode* t)
{
	if (!t)
		return;
	printf("%d ", t->w);
	PreOrder(t->lChild);
	PreOrder(t->rChild);
}
void PreOrderHFMTree(BinaryTree* bt)
{
	printf("\n先序遍历哈夫曼树的结果为：\n");
	PreOrder(bt->root);
}
// 哈夫曼中序遍历
void InOrder(HFMTNode* t)
{
	if (!t)
		return;
	InOrder(t->lChild);
	printf("%d ", t->w);
	InOrder(t->rChild);
}
void InOrderHFMTree(BinaryTree* bt)
{
	printf("\n中序遍历哈夫曼树的结果为：\n");
	InOrder(bt->root);
}
//构造哈夫曼树算法
void CreateHFMTree(BinaryTree*bt,int w[], int m)
{
	PriorityQueue PQ; //定义优先权队列PQ，用于存放二叉树根节点指针
	BinaryTree x,h,g; //x,y,z为二叉树变量
	int size;
	Create(&h);
	Create(&g);
	CreatePQ(&PQ, m); // 初始化优先权队列PQ，设优先权值存在于根节点的数据域
	for (int i = 0; i < m; i++)
	{
		if (w[i] != 0)
		{
			MakeTree(&x, w[i], &h, &g);
			Append(&PQ, x.root);  //把传进来的数组里面的每一个元素都当做权值放入优先权队列中
		}
	}
	printf("原森林为：\n");
	for (int i = 0; i < PQ.n; i++)
	{
		   printf("%d ", PQ.elements[i].w);
	}
	printf("\n");
	while (PQ.n > 1)
	{
		HFMTNode* X = NewBTNode(0 ,NULL, NULL);
		HFMTNode* Y = NewBTNode(0, NULL, NULL);
		HFMTNode* Z = NewBTNode(0, NULL, NULL);
		Serve(&PQ, X);  //取出此时权值最小的
		Serve(&PQ, Y); //取出此时权值最小的
		//下面进行合并节点操作，再讲新的值放入优先权队列
		if (X->w < Y->w)
		{
			Z->w = X->w + Y->w;
			Z->lChild = X;
			Z->rChild = Y;
			Append(&PQ, Z);
		}
		else
		{
			Z->w = X->w + Y->w;
			Z->lChild = Y;
			Z->rChild = X;
			Append(&PQ, Z);
		}
	}
	*bt->root = PQ.elements[0];
}

//进行哈夫曼编码
HFMTNode* HFMBMFirst(BinaryTree *tree,Stack *S,char * temp,int * index,int *w,int length,int *frequency)
{
	int fre = *frequency;
	HFMTNode* p = tree->root;
	if (!p||(fre>=length))
		return NULL;
	int k = *index;
	while (p->lChild!=NULL)
	{
		stackPush(S, p);
		p = p->lChild;
		temp[k++] = '0';
	}
	*w = p->w;
	temp[k] = '\0';
	*index = k;
	fre++;
	*frequency = fre;
	return p;
}
HFMTNode* HFMBMNext(HFMTNode* current, Stack* S, char* temp, int* index, int* w, int length, int* frequency)
{
	int fre = *frequency;
	int k = *index;
	HFMTNode* change, * again = current;
	HFMTNode* p;
	BinaryTree h, i, j;
	Create(&h);
	Create(&i);
	Create(&j);
	MakeTree(&h, 'H', &i, &j);
	change = h.root;
	if (current->rChild && current->Element != 1 && (fre < length))
	{
		current->Element = 1;
		stackPush(S, current);
		p = current->rChild;
		temp[k++] = '1';
		while (p->lChild != NULL)
		{
			stackPush(S, p);
			p = p->lChild;
			temp[k++] = '0';
		}
		*w = p->w;
		temp[k] = '\0';
		*index = k;
		fre++;
		*frequency = fre;
		return p;
	}
	else if ((fre < length) && (!stackIsEmpty(S)))
	{
		stackTop(S, change);
		stackPop(S);
		if ((change->rChild) && (change->Element != 1) && (fre < length))
		{
			temp[--k] = '\0';
			change->Element = 1;
			stackPush(S, change);
			p = change->rChild;
			temp[k++] = '1';
			while (p->lChild != NULL)
			{
				stackPush(S, p);
				p = p->lChild;
				temp[k++] = '0';
			}
			*w = p->w;
			temp[k] = '\0';
			*index = k;
			fre++;
			*frequency = fre;
			return p;
		}
		else if (change->rChild && change->Element == 1 && (fre < length))
		{

			while (change->Element == 1 && (fre < length))
			{
				stackTop(S, change);
				stackPop(S);
				temp[--k] = '\0';
			}
			if ((change->rChild) && (change->Element != 1) && (fre < length))
			{
				temp[--k] = '\0';
				change->Element = 1;
				stackPush(S, change);
				change = change->rChild;
				temp[k++] = '1';
				while (change->lChild != NULL)
				{
					stackPush(S, change);
					change = change->lChild;
					temp[k++] = '0';
				}
			}
				*w = change->w;
				temp[k] = '\0';
				*index = k;
				fre++;
				*frequency = fre;
				return change;

		}
	}
	else
	{
		p = current;
		p->w = 0;
		return p;
	}
}
void HFMBMAll(BinaryTree* bt,int * list,int length, char BMofchar[26][8])
{
	char temp[STACKSIZE] = "";
	int index = 0;
	int w=0;
	int frequency = 0;
	Stack S;
	stackCreate(&S, STACKSIZE);
	HFMTNode* current = HFMBMFirst(bt, &S, temp, &index,&w,length,&frequency);
	while (current->w!=0)
	{
		for (int i = 0; i < 26; i++)
		{
			if (w == list[i])
			{
				printf("%c的编码是", i + 97);
				puts(temp);
				printf("其权重为%d\n\n", w);
				for (int j = 0; temp[j] != '\0'; j++)
				{
					BMofchar[i][j] = temp[j];
				}

			}
		}
		current = HFMBMNext(current, &S, temp, &index, &w,length,&frequency);
	}
}


void main()
{
	int list[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
	BinaryTree bt,h,i,bt1;
	Create(&bt);
	Create(&bt1);
	Create(&h);
	Create(&i);
	MakeTree(&bt, 0, &h, &i);
	MakeTree(&bt1, 0, &h, &i);
	CreateHFMTree(&bt,list, 26);	
	PreOrderHFMTree(&bt);
	InOrderHFMTree(&bt);
	printf("\n");


	char str[20000];
	char BMofchar[26][8] = {};
	printf("\n请输入你想进行哈夫曼编码的字符串：\n");
	gets_s(str);
	int length = 0;
	int num[128] = { 0 };
	for (int i = 0; str[i] != '\0'; i++)
	{
		num[str[i]]++;
	}
	int list2[26] = { 0 };
	for (int i = 97; i < 123; i++)
	{
		if (num[i] != 0)
			list2[i - 97] = num[i];
	}
	for (int i = 0; i < 26; i++)
	{
		printf("%c:%d ",i+97, list2[i]);
		if (list2[i] != 0)
		{
			length++;
		}
	}
	printf("\n\n");
	CreateHFMTree(&bt1, list2,26);
	PreOrderHFMTree(&bt1);
	InOrderHFMTree(&bt1);
	printf("\n\n");
	HFMBMAll(&bt1,list2,length,BMofchar);

	//输出哈夫曼编码算法如下：
	char AllBM[1000] = "";
	char temp1[8] = "";
	printf("此时存在已有的编码为：\n");
	for (int i=0; i < 26; i++)
	{
		if (BMofchar[i][0] != '\0')
			puts(BMofchar[i]);
	}
	/*
	for (int i = 0; str[i] != '\0'; i++)
	{
		printf("%c", str[i]);
	}*/
	printf("\n");
	for (int i = 0; str[i] != '\0'; i++)
	{
		temp1[0] = str[i];
		int direction = int(temp1[0])-97;
		for (int num = 0; num < 26; num++)
		{
			if (num == direction)
			{
				strcat_s(AllBM, BMofchar[direction]);
				//printf("%s ", BMofchar[direction]);
			}
		}
	}
	printf("\n");
	printf("字符转换为哈夫曼编码后的数据为：\n");
	puts(AllBM);
	printf("\n");
	//下面进行哈夫曼译码操作：
	printf("哈夫曼译码之后结果为：\n");
	char temp2[8] = "";
	char AllYM[1000] = "";
	int Y = 0;
	char thechar[2] = "";
	for (int i = 0; AllBM[i] != '\0'; i++)
	{
		temp2[Y++] = AllBM[i];
		temp2[Y] = '\0';
		for (int num = 0; num < 26; num++)
		{
			if (strcmp(temp2, BMofchar[num])==0)
			{
				thechar[0] = char(num + 97);
				strcat_s(AllYM, thechar);
				Y = 0;
			}
		}
	}
	puts(AllYM);
}

优先权队列.h:

#pragma once
#include "HFMBTNODE.h"
typedef struct priorityQueue
{
	HFMTNode* elements;
	int n;
	int maxSize;
}PriorityQueue;
void AdjustUp(HFMTNode heap[], int current)
{
	int p = current;
	HFMTNode temp;
	while (p > 0)
	{
		if (heap[p].w < heap[(p - 1) / 2].w)
		{
			temp = heap[p];
			heap[p] = heap[(p - 1) / 2];
			heap[(p - 1) / 2] = temp;
			p = (p - 1) / 2;  //将p向上移动至当前考查元素的双亲节点位置
		}
		else  //若p指向的元素不小于其双亲节点，则调整完毕
			break;
	}
}
void AdjustDown(HFMTNode heap[], int current, int border)
{
	int p = current;
	int minChild;
	HFMTNode temp;
	while (2 * p + 1 <= border)
	{
		if ((2 * p + 2 <= border) && (heap[2 * p + 1].w > heap[2 * p + 2].w))
		{
			minChild = 2 * p + 2;
		}
		else
		{
			minChild = 2 * p + 1;
		}
		if (heap[p].w <= heap[minChild].w)
		{
			break;
		}
		else
		{
			temp = heap[p];
			heap[p] = heap[minChild];
			heap[minChild] = temp;
			p = minChild;
		}
	}
}

//创建一个空的优先权队列
void CreatePQ(PriorityQueue* PQ, int mSize)
{
	PQ->maxSize = mSize;
	PQ->n = 0;
	PQ->elements = (HFMTNode *)malloc(mSize * sizeof(HFMTNode));
}

// 销毁一个优先权队列，释放其占用的空间
void Destory(PriorityQueue* PQ)
{
	free(PQ->elements);
	PQ->n = 0;
	PQ->maxSize = 0;
}

//判断优先权队列是否为空
BOOL IsEmpty(PriorityQueue* PQ)
{
	if (PQ->n == 0)
		return TRUE;
	else
		return FALSE;
}

//判断优先权队列是否已满
BOOL IsFull(PriorityQueue* PQ)
{
	if (PQ->n == PQ->maxSize)
		return TRUE;
	else
		return FALSE;
}

//获取当前优先权队列中的元素的数量
int Size(PriorityQueue* PQ)
{
	return PQ->n;
}

//在优先权队列中增加一个新元素x
void Append(PriorityQueue* PQ, HFMTNode *x)
{
	if (IsFull(PQ))
		return;
	PQ->elements[PQ->n] = *x;
	PQ->n++;
	AdjustUp(PQ->elements, PQ->n - 1);
}

//取出优先级最高的元素，利用参数x返回，并在优先权队列中删除该元素
void Serve(PriorityQueue* PQ, HFMTNode* x)
{
	if (IsEmpty(PQ))
		return;
	*x = PQ->elements[0];
	PQ->n--;
	PQ->elements[0] = PQ->elements[PQ->n];
	AdjustDown(PQ->elements, 0, PQ->n - 1);
}

哈夫曼的stack.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include "HFMBTNODE.h"
#define STACKSIZE 100
typedef struct Stack
{
	int top;
	int maxSize;
	HFMTNode* element;
}Stack;
void stackCreate(Stack* S, int mSize)
{
	S->maxSize = mSize;
	S->element = (HFMTNode*)malloc(sizeof(HFMTNode) * mSize);
	S->top = -1;
}
void stackDestory(Stack* S)
{
	S->maxSize = 0;
	S->top = -1;
	free(S->element);
}
BOOL stackIsEmpty(Stack* S)
{
	return S->top == -1;
}
BOOL stackIsFULL(Stack* S)
{
	return S->top == S->maxSize - 1;
}
BOOL stackTop(Stack* S, HFMTNode* x)
{
	if (stackIsEmpty(S))
	{
		return FALSE;
	}
	*x = S->element[S->top];
	return TRUE;
}
BOOL stackPush(Stack* S, HFMTNode *x)
{
	if (stackIsFULL(S))
		return FALSE;
	S->top++;
	S->element[S->top] = *x;
	return TRUE;
}
BOOL stackPop(Stack* S)
{
	if (stackIsEmpty(S))
		return FALSE;
	S->top--;
	return TRUE;
}
void Clear(Stack* S)
{
	S->top = 1;
}

HFMBTNODE.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string>
typedef int ElemType;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
typedef struct hfmTNode
{
	int Element;
	int w;
	struct hfmTNode* lChild;
	struct hfmTNode* rChild;
}HFMTNode;
typedef struct binarytree
{
	HFMTNode* root;
}BinaryTree;

上半部分介绍了哈夫曼的中序遍历等

哈夫曼编码已完成，译码已完成，更新完毕，由此结束。

；原文链接：https://blog.csdn.net/VAEaaaa/article/details/115605896

版权声明：本文转载自网络，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本站转载出于传播更多优秀技术知识之目的，如有侵权请联系QQ/微信：153890879删除

相关文章
  • Windows 10新增磁盘分析工具：文件夹占

    Windows 10新增磁盘分析工具：文件夹占

  • 鸿蒙HarmonyOS环境搭建遇到的坑，分享

    鸿蒙HarmonyOS环境搭建遇到的坑，分享

  • Zabbix5.2由浅入深系列之制作网络设备

    Zabbix5.2由浅入深系列之制作网络设备

  • 转手赚1000，开源抢茅台神器，真香！

    转手赚1000，开源抢茅台神器，真香！

腾讯云代理商
精彩导读
/images/defaultpic.gif

MySQL分页查询方法及优化

/images/defaultpic.gif

CSS3 实现图形下落动画效果

/images/defaultpic.gif

新零售行业优质解决方案分享【大促营销

/images/defaultpic.gif

Ajax实现phpcms 点赞功能实例代码

/uploads/allimg/210511/12004a501-0-lp.gif

TIOBE 4 月榜单：上古编程语言 Fortran

/images/defaultpic.gif

轻松教你搞定组件的拖拽, 缩放, 多控制

海外云服务器
热门资讯
备案：湘ICP备15009499号-1
网站简介 投稿须知 商务合作 版权申明 技术支持：TOP云