念123 发表于 2023-11-20 09:15:06

哈夫曼树构造和解码

#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;
}
构造的哈夫曼树是错的,但是我觉得构造过程没有问题,感觉是指针指向有问题

isdkz 发表于 2023-11-20 09:15:26

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; 这行代码后,修复了向上调整的问题。

Mike_python小 发表于 2023-11-20 09:15:30

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

念123 发表于 2023-11-20 09:17:41

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

加上还是不行

念123 发表于 2023-11-20 09:18:51

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

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

念123 发表于 2023-11-20 10:00:06

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

我有点不理解你的意思,但是好像就是你说的这个问题,我不知道怎么修改
页: [1]
查看完整版本: 哈夫曼树构造和解码