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