数据布局：哈夫曼树及其哈夫曼编码 - ToB企服应用市场:ToB评测及商务社交产业平台

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

复制代码

#define Initsize 100
typedef int Elemtype;
int Node[Initsize][2]; //定义二维数组Node存储输入的字符和字符所含的权值
int NodeValue[Initsize]; //定义一维数组NodeValue存储经排序过的字符的权值
int Hand = 0; //定义整形变量Hand作为数组NodeValue的头指针
int CodeHead = 0; //定义int类型变量CodeHead作为指针数组Code的头指针
typedef struct HTree {
Elemtype value; //存储结点权值
Elemtype Lvalue, Rvalue; //存储孩子标识
struct HTree* lchild; //存储左孩子树
struct HTree* rchild; //存储右孩子树
}HTree,*HfmTree;
HfmTree Head; //定义全局变量Head作为哈夫曼树的根节点指针
HfmTree Code[Initsize]; //定义HTree类型的指针数组Code，存储结点的地址

复制代码

void InitHTree(HfmTree& A); //用于初始化哈夫曼树
void InsertNode(int A); //用于输入字符和其权值
void SortNodeV(int A); //用于对输入的权值进行排序
void InitLHfm(HfmTree& A); //用于哈夫曼树的左子树进行初始化并赋值
void InitRHfm(HfmTree& A); //用于哈夫曼树的右子树进行初始化并赋值
void InsertHTree(HfmTree& A,int B); //用于创建哈夫曼树
void PostOrder(HfmTree A); //用于对哈夫曼树进行后序遍历
void InputBTree(HfmTree A); //用于对哈夫曼树的结点权值输出
void SeekHTreeL(HfmTree A, int B); //用于单独寻找哈夫曼树的左子树的字符及权值
void SeekHTreeR(HfmTree A, int B); //用于寻找哈夫曼树的右子树的字符及权值
void InputHfmCode(HfmTree A,int B); //用于输出哈夫曼编码
void InitRootHfm(HfmTree& A,HfmTree &B,HfmTree &C); //用于对哈夫曼树的根结点进行初始化并赋值

复制代码

void InputHfmCode(HfmTree A,int B) { //用于输出哈夫曼编码
int i,j;
while (A != NULL) { //对哈夫曼树的左子树进行进栈操作
Code[CodeHead] = A;
A = A->lchild;
CodeHead++;
}
printf("\n");
SeekHTreeL(A, B); //使用函数SeekHtreeL对其哈夫曼树进行寻找左子树的字符及权值
for (i = 1; i < CodeHead; i++) {
printf("%d", Code[i]->Lvalue);
//对栈里结点所含的Lvalue进行输出(从根结点开始输出其含有的LvaLue)
}
CodeHead--; //出栈操作
while (CodeHead != 0) { //判断栈是否为空
printf("\n");
SeekHTreeR(A, B); //使用函数SeekHTreeR对其哈夫曼树进行寻找右子树的字符及权值
for (i = 0; i <= CodeHead - 1; i++) {
//对栈里结点所含的Lvalue进行输出(从根结点开始输出其含有的LvaLue)
if (i == CodeHead - 1) { //若为栈尾结点则输出其右子树
printf("%d", Code[i]->Rvalue);
break;
}
printf("%d", Code[i]->Lvalue);
}
CodeHead--; //出栈操作
}
}
void SeekHTreeR(HfmTree A, int B) { //用于寻找哈夫曼树的右子树的字符及权值
int i,j;
for (i = CodeHead - 1; i >= 0; i++){ //遍历栈
if (i == CodeHead-1) { //判断是否为栈的倒数第二个结点(跟定义的结点的有关)
for (j = 0; j < B; j++) { //遍历存储字符及权值的数组，寻找对应的字符和权值
if (Node[j][1] == Code[i]->rchild->value) {
Node[j][1] = -1;
//未防止字符不一样，但权值相同的出现，造成输出哈夫曼编码错误
printf("%c的哈夫曼编码为：", Node[j][0]);
break;
}
}
}
break;
}
}
void SeekHTreeL(HfmTree A, int B){ //用于单独寻找哈夫曼树的左子树的字符及权值
int i,j;
for (i = 0; i < CodeHead; i++) { //遍历栈
if (i == CodeHead - 1) { //判断是否为栈的倒数第二个结点(跟定义的结点的有关)
for (j = 0; j < B; j++) { //遍历存储字符及权值的数组，寻找对应的字符和权值
if (Node[j][1] == Code[i]->value) {
Node[j][1] = -1;
//未防止字符不一样，但权值相同的出现，造成输出哈夫曼编码错误
printf("%c的哈夫曼编码为：", Node[j][0]);
break;
}
}
}
}
}
void InputBTree(HfmTree A) { //用于对哈夫曼树的结点权值输出
printf("%d ", A->value);
}
void PostOrder(HfmTree A) { //用于对哈夫曼树进行后序遍历
if (A != NULL) {
PostOrder(A->lchild);
PostOrder(A->rchild);
InputBTree(A);
}
}
void InsertHTree(HfmTree& A,int B) {//用于创建哈夫曼树
if(Hand<B-1){ //判断是否已将所有字符及权值进行构建对应的哈夫曼树的结点
if (A == NULL) {
HfmTree Q = (HTree*)malloc(sizeof(HTree));
HfmTree W = (HTree*)malloc(sizeof(HTree));
InitLHfm(Q); //使用函数InitLHfm对其左子树初始化
Hand++;
InitRHfm(W); //使用函数InitRHfm对其右子树初始化
InitRootHfm(A, Q, W); //使用函数InitRootHfm对其根结点初始化
Head = A; //更新哈夫曼树的头指针的指向
InsertHTree(A, B);
}
else {
HfmTree Q = (HTree*)malloc(sizeof(HTree));
HfmTree W = (HTree*)malloc(sizeof(HTree));
Hand++;
InitRHfm(Q); //使用函数InitRHfm对其右子树初始化
InitRootHfm(W, A, Q); //使用函数InitRootHfm对其根结点初始化
Head = W;
InsertHTree(W, B);
}
}
}
void InitRootHfm(HfmTree& A, HfmTree& B, HfmTree& C) {
//用于对哈夫曼树的根结点进行初始化并赋值
A = (HTree*)malloc(sizeof(HTree));
A->value = B->value + C->value; //根结点的权值为两个子结点的权值之和
A->Lvalue = 1; //添加左子树标识
A->Rvalue = 0;
A->lchild = B; //添加根结点指向的左子树
A->rchild = C; //添加根结点指向的右子树
printf("新建的根结点的权值数据为%d\n", A->value);
}
void InitRHfm(HfmTree& A) { //用于哈夫曼树的右子树进行初始化并赋值
A->value = NodeValue[Hand]; //对结点所含的权值进行更新
A->Lvalue = 0;
A->Rvalue = 1; //添加右子树标识
A->lchild = NULL;
A->rchild = NULL;
printf("新建的右孩子的权值数据为%d\n", A->value);
}
void InitLHfm(HfmTree& A) { //用于哈夫曼树的左子树进行初始化并赋值
A->value = NodeValue[Hand]; //对结点所含的权值进行更新
A->Lvalue = 1; //添加左子树标识
A->Rvalue = 0;
A->lchild = NULL;
A->rchild = NULL;
printf("新建的左孩子的权值数据为%d\n", A->value);
}
void SortNodeV(int A) { //用于对输入的权值进行排序
int i, j, Q;
for (i = 0; i < A - 1; i++) { //冒泡排序
for (j = 0; j < A - 1 - i; j++)
if (NodeValue[j] > NodeValue[j + 1]) {
Q = NodeValue[j];
NodeValue[j] = NodeValue[j + 1];
NodeValue[j + 1] = Q;
}
}
}
void InsertNode(int A) { //用于输入字符和其权值
int i, j;
char Q;
for (i = 0; i < A; i++) {
j = 0;
printf("请输入结点的字符");
getchar(); //清除缓冲区，防止赋值脏数据
Q=getchar();
Node[i][j] = (int) Q;
j++;
printf("请输入结点的权值");
scanf_s("%d", &Node[i][j]);
NodeValue[i] = Node[i][j];
}
}
void InitHTree(HfmTree& A) { //用于初始化哈夫曼树
A = NULL;
printf("初始化哈夫曼树成功\n");
}

复制代码

void main() {
int NodeSize,i;
HfmTree X;
InitHTree(X);
printf("请问需要输入多少个字符");
scanf_s("%d", &NodeSize);
InsertNode(NodeSize);
SortNodeV(NodeSize);
InsertHTree(X, NodeSize);
printf("创建哈夫曼树成功\n");
printf("后序遍历的哈夫曼树为：");
PostOrder(Head);
printf("\n");
InputHfmCode(Head,NodeSize);
}

复制代码