论坛 › C\C++交流 › 关于给结构体内数组分配内存空间的问题求解！

a905448839 发表于 2023-7-18 12:59:02

关于给结构体内数组分配内存空间的问题求解！

代码如下：
#include <stdio.h>
#include <stdlib.h>

int MinData = -1;
typedef struct TreeNode *HuffmanTree;
typedef struct Heap *MinHeap;
typedef int ElenmentType ;
struct TreeNode
{
    ElenmentType Weight;//权值
    HuffmanTree Left;
    HuffmanTree Right;
};
struct Heap
{
    HuffmanTree *Data;
    ElenmentType Size;
    ElenmentType Capacity;
};

MinHeap CreateHeap(int MaxSize);   // 建堆
void InsertHeap(MinHeap H,HuffmanTree T);
HuffmanTree DeleteHeap(MinHeap H);
HuffmanTree CreateHuffman(MinHeap H);
void Print(HuffmanTree HF);
void P(MinHeap H);

MinHeap CreateHeap(int MaxSize)
{
    MinHeap H = malloc(sizeof(struct Heap));
    H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode));
    H->Size = 0;
    H->Capacity = MaxSize;
    //H->Data = malloc(sizeof(struct TreeNode));
    H->Data->Weight = MinData;
    int i;
    for(i = 1;i <= MaxSize;i++)
            H->Data = NULL;

    return H;
}

void InsertHeap(MinHeap H,HuffmanTree T)
{
        if(H->Size == H->Capacity)
        {
                printf("最小堆满");
                return;
        }
        int i = ++H->Size;
        for(;H->Data->Weight > T->Weight;i/=2)
                H->Data = H->Data;
        H->Data = T;
}

HuffmanTree DeleteHeap(MinHeap H)
{
        if(H->Size == 0)
        {
                printf("最小堆空");
                return;
        }
        HuffmanTree MinData = H->Data;
        HuffmanTree temp = H->Data;
        int i,j;
        for(i = 1;i*2 <= H->Size;i = j)
        {
                j = i*2;
                if((j != H->Size) && (H->Data->Weight > H->Data->Weight))
                j++;
                if(temp->Weight <= H->Data->Weight)break;
                else
                        H->Data = H->Data;
        }
        H->Data = temp;
       
        P(H);
        return MinData;
}
HuffmanTree CreateHuffman(MinHeap H)
{
        while(H->Size > 1)
        {
                HuffmanTree A = DeleteHeap(H);
                HuffmanTree B = DeleteHeap(H);
                HuffmanTree Troot = (HuffmanTree)malloc(sizeof(struct TreeNode));
                Troot->Weight = A->Weight+B->Weight;
                Troot->Left = A;
                Troot->Right = B;
                InsertHeap(H,Troot);
        }
        return H->Data;
}

void Print(HuffmanTree HF)
{
        if(HF)
        {
                printf("%d ",HF->Weight);
                Print(HF->Left);
                Print(HF->Right);
        }
                        printf("\n");
}

void P(MinHeap H)
{
        int i = 1;
        if(H->Size > 0)
                for(;i <= H->Size;i++)
                        printf("%d ",H->Data->Weight);
                printf("\n");
}
int main()
{
       
        int i;
        scanf("%d\n",&i);
        MinHeap H = CreateHeap(i);
        while(i--)
        {
                char a;
                ElenmentType Weight;
                scanf("%c %d",&a,&Weight);
                HuffmanTree T= malloc(sizeof(struct TreeNode));
                T->Left = T->Right = NULL;
                T->Weight = Weight;
                getchar();
                InsertHeap(H,T);
        }
        HuffmanTree HF = CreateHuffman(H);
        Print(HF);

return 0;
}

在CreateHeap函数里，首先生成了一个H的最小堆指针
MinHeap H = malloc(sizeof(struct Heap));
然后为其H堆里的数组成员Data分配内存空间
    H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode));
分配了之后，访问H->Data居然是无效空间
必须加一句我注释掉的 H->Data = malloc(sizeof(struct TreeNode));

蓝色这行代码就是出错的地方，我分配了内存空间为什么还是无效访问?

陶远航 发表于 2023-7-18 12:59:14

在给结构体内的数组分配内存空间时，你出现了无效访问的问题。这是因为你分配了H->Data的内存空间，但没有为H->Data分配内存空间。

解决这个问题的方法是，你可以在分配H->Data的内存后，再单独为H->Data分配内存空间，例如：

H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode));
H->Data = malloc(sizeof(struct TreeNode));


这样，你就为H->Data分配了内存空间，之后就可以正常使用了。希望能帮到你！

isdkz 发表于 2023-7-18 12:59:34

在你的代码中，你首先为 MinHeap H 结构体变量的 Data 成员，也就是一个指向 HuffmanTree 的指针数组，分配了内存空间。然后你尝试访问 H->Data 并尝试修改其 Weight 属性。然而，你只为 Data 指针数组分配了内存空间，这意味着你已经有了一个可以存储 HuffmanTree 指针的内存空间，但你并没有实际为这些指针所指向的 HuffmanTree 节点分配内存。也就是说，你的数组可以存储指向 HuffmanTree 的指针，但是这些指针本身现在指向的是未分配的内存。

在你尝试执行 H->Data->Weight = MinData; 这行代码时， H->Data 指向的内存区域还没有被分配，所以你遇到了无效访问。

因此，你需要对每个 HuffmanTree 结构体实例分配内存，这就是为什么你需要使用 H->Data = malloc(sizeof(struct TreeNode)); 这行代码的原因。这行代码会为 H->Data 指针分配一个 struct TreeNode 类型的内存空间，所以你可以在这个内存区域上进行操作，例如修改其 Weight 属性。这样，你就不会遇到无效访问的问题了。

以下是你可能需要修改的部分：

MinHeap CreateHeap(int MaxSize)
{
    MinHeap H = malloc(sizeof(struct Heap));
    H->Data = malloc((MaxSize + 1) * sizeof(struct TreeNode *));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data = malloc(sizeof(struct TreeNode));
    H->Data->Weight = MinData;
    int i;
    for(i = 1; i <= MaxSize; i++)
      H->Data[ i] = NULL;

    return H;
}


在这段代码中，我将 H->Data 的内存分配改为 malloc((MaxSize + 1) * sizeof(struct TreeNode *)); ，因为 Data 是一个 HuffmanTree （也就是 struct TreeNode * ）类型的数组。然后，我为 H->Data 分配了一个新的 struct TreeNode 类型的内存空间。

a905448839 发表于 2023-7-18 13:50:34

isdkz 发表于 2023-7-18 12:59
在你的代码中，你首先为 MinHeap H 结构体变量的 Data 成员，也就是一个指向 HuffmanTree 的指针数组，分配 ...

谢谢你的回答，你能帮我看一下我构造的这个哈夫曼树是正确的吗？正常分配空间后构造的哈夫曼树WPL值好像不对。

sfqxx 发表于 2023-7-18 14:39:53

a905448839 发表于 2023-7-18 13:50
谢谢你的回答，你能帮我看一下我构造的这个哈夫曼树是正确的吗？正常分配空间后构造的哈夫曼树WPL值好像 ...

你在代码中创建了一个 `MinHeap` 堆，并为 `H->Data` 分配了内存空间，这个内存空间的大小是 `(MaxSize + 1) * sizeof(struct TreeNode)`。然而，你需要注意的是 `H->Data` 是一个指针数组，它存储的是 `HuffmanTree` （也是指针）类型的数据。因此，你分配的内存应该是用来存储 `HuffmanTree` 指针的，而不是 `struct TreeNode` 结构体。

当你尝试访问 `H->Data->Weight` 时，事实上你正在试图访问一个 `HuffmanTree` 结构的 `Weight` 成员。但是在这个时候，`H->Data` 还没有被初始化，它指向的是一个未知的内存位置，这就是为什么你会遇到无效访问的问题。

如果你想要初始化 `H->Data`，你确实需要为其分配内存空间。你注释掉的这行代码 `H->Data = malloc(sizeof(struct TreeNode));` 是正确的，它会为 `H->Data` 分配一个新的 `struct TreeNode` 结构体的内存空间，并将 `H->Data` 指向这个新的内存空间。这样你就可以通过 `H->Data` 访问并修改这个 `struct TreeNode` 结构体的成员了。

所以，你的代码应该修改为：

MinHeap CreateHeap(int MaxSize)
{
        MinHeap H = malloc(sizeof(struct Heap));
        H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode *));
        H->Size = 0;
        H->Capacity = MaxSize;

        H->Data = malloc(sizeof(struct TreeNode));
        H->Data->Weight = MinData;

        int i;
        for(i = 1;i <= MaxSize;i++)
                H->Data = NULL;

        return H;
}

上述代码中，我将 `H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode));` 修改为 `H->Data = malloc((MaxSize + 1)* sizeof(struct TreeNode *));`，以确保为 `H->Data` 分配的内存空间足够存储 `(MaxSize + 1)` 个 `HuffmanTree` 指针。此外，我取消了 `H->Data = malloc(sizeof(struct TreeNode));` 这行代码的注释，以确保 `H->Data` 能指向一个有效的内存空间。

查看完整版本: 关于给结构体内数组分配内存空间的问题求解！