|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
代码如下：
- #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[0] = malloc(sizeof(struct TreeNode));
- H->Data[0]->Weight = MinData;
- int i;
- for(i = 1;i <= MaxSize;i++)
- H->Data[i] = NULL;
- return H;
- }
- void InsertHeap(MinHeap H,HuffmanTree T)
- {
- if(H->Size == H->Capacity)
- {
- printf("最小堆满");
- return;
- }
- int i = ++H->Size;
- for(;H->Data[i/2]->Weight > T->Weight;i/=2)
- H->Data[i] = H->Data[i/2];
- H->Data[i] = T;
- }
- HuffmanTree DeleteHeap(MinHeap H)
- {
- if(H->Size == 0)
- {
- printf("最小堆空");
- return;
- }
- HuffmanTree MinData = H->Data[1];
- HuffmanTree temp = H->Data[H->Size--];
- int i,j;
- for(i = 1;i*2 <= H->Size;i = j)
- {
- j = i*2;
- if((j != H->Size) && (H->Data[j]->Weight > H->Data[j+1]->Weight))
- j++;
- if(temp->Weight <= H->Data[j]->Weight)break;
- else
- H->Data[i] = H->Data[j];
- }
- H->Data[i] = 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[1];
- }
- 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[i]->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[0]居然是无效空间
必须加一句我注释掉的 H->Data[0] = malloc(sizeof(struct TreeNode));
蓝色这行代码就是出错的地方，我分配了内存空间为什么还是无效访问?
在你的代码中，你首先为 MinHeap H 结构体变量的 Data 成员，也就是一个指向 HuffmanTree 的指针数组，分配了内存空间。然后你尝试访问 H->Data[0] 并尝试修改其 Weight 属性。然而，你只为 Data 指针数组分配了内存空间，这意味着你已经有了一个可以存储 HuffmanTree 指针的内存空间，但你并没有实际为这些指针所指向的 HuffmanTree 节点分配内存。也就是说，你的数组可以存储指向 HuffmanTree 的指针，但是这些指针本身现在指向的是未分配的内存。
在你尝试执行 H->Data[0]->Weight = MinData; 这行代码时， H->Data[0] 指向的内存区域还没有被分配，所以你遇到了无效访问。
因此，你需要对每个 HuffmanTree 结构体实例分配内存，这就是为什么你需要使用 H->Data[0] = malloc(sizeof(struct TreeNode)); 这行代码的原因。这行代码会为 H->Data[0] 指针分配一个 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[0] = malloc(sizeof(struct TreeNode));
- H->Data[0]->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[0] 分配了一个新的 struct TreeNode 类型的内存空间。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-7-18 12:59:02
置顶卡
千斤顶
显身卡
发表于 2023-7-18 12:59:14
楼主