哈夫曼树构造和解码

念123

#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[p].w < heap[(p - 1) / 2].w) {
                        temp = heap[p];
                        heap[p] = 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[PQ->n] = 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[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;
                }
        }
}
// 取出优先级最高的元素，利用参数x返回，并在优先权队列删除该元素
void Serve(PriorityQueue* PQ, ElemType* x) {
        *x = PQ->element[0];
        PQ->n--;
        PQ->element[0] = PQ->element[PQ->n];
        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[i];
                x->element = e[i];
                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[i];
                }
        }
        path.push_back(0);
        HFMCode(root->lChild);
        path.pop_back();
       
        path.push_back(1);
        HFMCode(root->rChild);
        path.pop_back();
}
int main() {
        int w[7] = { 74, 2, 72, 54, 93, 52, 28 }; // 权值矩阵
        int e[7] = { 0, 2, 4, 6, 8, 10, 12 }; // 数据域矩阵
        HFMTNode* root = CreateHFMTree(w, 7, e); // 构造哈夫曼树

        HFMCode(root);

        return 0;
}
构造的哈夫曼树是错的，但是我觉得构造过程没有问题，感觉是指针指向有问题

isdkz

1. void AdjustUp(HFMTNode heap[], int current) {
   
2.     int p = current;
   
3.     ElemType temp;
   
4.     while (p > 0) {
   
5.         if (heap[p].w < heap[(p - 1) / 2].w) {
   
6.             temp = heap[p];
   
7.             heap[p] = heap[(p - 1) / 2];
   
8.             heap[(p - 1) / 2] = temp;
   
9.             p = (p - 1) / 2;  // 添加这行代码，修复向上调整的问题
   
10.         } else {
    
11.             break;
    
12.         }
    
13.     }
    
14. }
    

复制代码

在向上调整的过程中，需要更新当前节点的索引 p ，以确保正确比较和交换。添加了 p = (p - 1) / 2; 这行代码后，修复了向上调整的问题。

Mike_python小

你好，根据你提供的代码，我看到在CreateHFMTree函数中，对于x和y指向的结点进行操作时，并没有为z分配新的内存空间。这会导致后续对z结点的修改影响到之前的x或y结点。你可以尝试修改代码，在创建z结点时为其分配新的内存空间，然后再进行赋值操作。希望这能够帮助你解决问题。

念123

isdkz 发表于 2023-11-20 09:15
在向上调整的过程中，需要更新当前节点的索引 p ，以确保正确比较和交换。添加了 p = (p - 1) / 2; 这行 ...

加上还是不行

念123

Mike_python小 发表于 2023-11-20 09:15
你好，根据你提供的代码，我看到在CreateHFMTree函数中，对于x和y指向的结点进行操作时，并没有为z分配新的 ...

z最开始是没有用的，不用申请

念123

念123 发表于 2023-11-20 09:18
z最开始是没有用的，不用申请

我有点不理解你的意思，但是好像就是你说的这个问题，我不知道怎么修改