马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
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 类型的内存空间。
|