哈夫曼树构造和解码
#include <stdio.h>#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
// 哈夫曼树结点定义
typedef struct hfmTNode {
int element;
int w;
struct hfmTNode* lChild;
struct hfmTNode* rChild;
}HFMTNode;
typedef int BOOL;
typedef HFMTNode ElemType;
typedef struct priorityQueue {
ElemType* element;
int n;
int maxSize;
}PriorityQueue;
// 创建一个空的优先权队列
void CreatPQ(PriorityQueue* PQ, int mSize) {
PQ->maxSize = mSize;
PQ->n = 0;
PQ->element = (ElemType*)malloc(mSize * sizeof(ElemType));
}
// 销毁一个优先权队列，释放其占有的内存空间
void DestroyPQ(PriorityQueue* PQ) {
free(PQ->element);
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;
}
// 向上调整
void AdjustUp(HFMTNode heap[], int current) {
int p = current;
ElemType temp;
while (p > 0) {
if (heap.w < heap[(p - 1) / 2].w) {
temp = heap;
heap = heap[(p - 1) / 2];
heap[(p - 1) / 2] = temp;
}
else {
break;
}
}
}
//在优先权队列中增加一个新元素x
void Append(PriorityQueue* PQ, HFMTNode x) {
if (IsFull(PQ)) {
printf("优先权队列已满，加入元素失败！\n");
return;
}
PQ->element = x;
PQ->n++;
AdjustUp(PQ->element, PQ->n - 1);
}
// 向下调整
void AdjustDown(ElemType heap[], int current, int border) {
int p = current;
int minChild;
ElemType temp;
while (2 * p + 1 <= border) { // 若不是叶结点，则进行调整
if (2 * p + 2 <= border && heap.w > heap.w) {
minChild = 2 * p + 2;
}
else {
minChild = 2 * p + 1;
}
if (heap.w <= heap.w) {
break;
}
else {
temp = heap;
heap = heap;
heap = temp;
p = minChild;
}
}
}
// 取出优先级最高的元素，利用参数x返回，并在优先权队列删除该元素
void Serve(PriorityQueue* PQ, ElemType* x) {
*x = PQ->element;
PQ->n--;
PQ->element = PQ->element;
AdjustDown(PQ->element, 0, PQ->n - 1);
}
HFMTNode* CreateHFMTree(int w[], int m, int e[]) {
PriorityQueue* PQ = (PriorityQueue*)malloc(sizeof(PriorityQueue));
HFMTNode* x = NULL;
HFMTNode* y = (HFMTNode*)malloc(sizeof(HFMTNode));
HFMTNode* z = NULL;
//创建优先队列
CreatPQ(PQ, m);
for (int i = 0; i < m; i++) {
x = (HFMTNode*)malloc(sizeof(HFMTNode));
x->w = w;
x->element = e;
x->lChild = NULL;
x->rChild = NULL;
Append(PQ, *x);
}
while (PQ->n > 1) {
Serve(PQ, x);
Serve(PQ, y);
if (x->w < y->w) {
z = (HFMTNode*)malloc(sizeof(HFMTNode));
z->w = x->w + y->w;
z->lChild = x;
z->rChild = y;
}
else {
z = (HFMTNode*)malloc(sizeof(HFMTNode));
z->w = x->w + y->w;
z->lChild = y;
z->rChild = x;
}
Append(PQ, *z);
}
//返回哈夫曼树的根结点
HFMTNode* temp = (HFMTNode*)malloc(sizeof(HFMTNode));
Serve(PQ, temp);
DestroyPQ(PQ);
return temp;
}
void HFMCode(HFMTNode* root) {
if (!root) {
return;
}
if (root->lChild == NULL && root->rChild == NULL) {
printf("%d的哈夫曼编码为：", root->element);
for (int i = 0; i < path.size(); i++) {
cout << path;
}
}
path.push_back(0);
HFMCode(root->lChild);
path.pop_back();
path.push_back(1);
HFMCode(root->rChild);
path.pop_back();
}
int main() {
int w = { 74, 2, 72, 54, 93, 52, 28 }; // 权值矩阵
int e = { 0, 2, 4, 6, 8, 10, 12 }; // 数据域矩阵
HFMTNode* root = CreateHFMTree(w, 7, e); // 构造哈夫曼树
HFMCode(root);
return 0;
}
构造的哈夫曼树是错的，但是我觉得构造过程没有问题，感觉是指针指向有问题 void AdjustUp(HFMTNode heap[], int current) {
int p = current;
ElemType temp;
while (p > 0) {
if (heap.w < heap[(p - 1) / 2].w) {
temp = heap;
heap = heap[(p - 1) / 2];
heap[(p - 1) / 2] = temp;
p = (p - 1) / 2;// 添加这行代码，修复向上调整的问题
} else {
break;
}
}
}
在向上调整的过程中，需要更新当前节点的索引 p ，以确保正确比较和交换。添加了 p = (p - 1) / 2; 这行代码后，修复了向上调整的问题。 你好，根据你提供的代码，我看到在CreateHFMTree函数中，对于x和y指向的结点进行操作时，并没有为z分配新的内存空间。这会导致后续对z结点的修改影响到之前的x或y结点。你可以尝试修改代码，在创建z结点时为其分配新的内存空间，然后再进行赋值操作。希望这能够帮助你解决问题。 isdkz 发表于 2023-11-20 09:15
在向上调整的过程中，需要更新当前节点的索引 p ，以确保正确比较和交换。添加了 p = (p - 1) / 2; 这行 ...
加上还是不行 Mike_python小 发表于 2023-11-20 09:15
你好，根据你提供的代码，我看到在CreateHFMTree函数中，对于x和y指向的结点进行操作时，并没有为z分配新的 ...
z最开始是没有用的，不用申请 念123 发表于 2023-11-20 09:18
z最开始是没有用的，不用申请
我有点不理解你的意思，但是好像就是你说的这个问题，我不知道怎么修改
页:
[1]