2017-07-17 03:12

# 优先队列问题。编译可通，无法运行。单步调试出错0xC0000005:Access Violation

`````` #ifndef _BinHeap_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

typedef int ElementType;

PriorityQueue Initialize(int MaxElements);
void Destroy (PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(ElementType X,PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int Isfull(PriorityQueue H);

struct HeapStruct
{
int Capacity;
int Size;
ElementType *Elements;
};

#endif

``````
`````` #include "BinHeap.h"
#include <stdio.h>
#include <stdlib.h>

#define MinPQSize 5
#define MinData 0

//int MaxElements=19;

void Error(char *str)
{
printf("%s\n", str);
exit(0);
}

int Isfull(PriorityQueue H)
{
if(H->Size>H->Capacity)
return 1;
else
return 0;
}

int IsEmpty(PriorityQueue H)
{
if(H->Size==0)
return 1;
else
return 0;
}

//初始化优先队列
PriorityQueue Initialize (int MaxElements)
{
PriorityQueue H;           //数组型
if(MaxElements<MinPQSize)
Error("Priority queue size is too small");

H->Elements=(int *)malloc((MaxElements+1)*sizeof(ElementType));

if(H->Elements==NULL)
Error("Out of space!");

for(int i=0;i<=MaxElements;i++)           //数组元素置NULL
{
H->Elements[i]=NULL;
}

H->Capacity=MaxElements;
H->Size=0;
H->Elements[0]=MinData;                   //MinData

return H;
}

//插入操作    Percolate up    上滤    最小的元素在根部
void Insert(ElementType X,PriorityQueue H)
{
int i;
if(Isfull(H))
{
Error("Priority queue is full");
return;
}

for(i=++H->Size;H->Elements[i/2]>X;i/=2)
H->Elements[i]=H->Elements[i/2];
H->Elements[i]=X;
}

//DeleteMin    percolate down    下滤    用最后的元素作最后一步空穴填充
ElementType DeleteMin(PriorityQueue H)
{
int i,Child;
ElementType MinElement,LastElement;

if(IsEmpty(H))
{
Error("Priority queue is empty");
return H->Elements[0];
}

MinElement=H->Elements[1];
LastElement=H->Elements[H->Size--];

for(i=1;i*2<=H->Size;i=Child)
{
Child=i*2;
if(Child!=H->Size&&H->Elements[Child+1]<H->Elements[Child])
Child++;
if(LastElement>H->Elements[Child])
H->Elements[i]=H->Elements[Child];
else break;
}
H->Elements[i]=LastElement;
return MinElement;
}

//PercolateDown(i)
PriorityQueue PercolateDown(int i,PriorityQueue H)
{
int C=i*2;
int j=i;
ElementType Middle;

for(j;j*2<=H->Size;j=C)
{
C=j*2;
if(H->Elements[C+1]<H->Elements[C])
C++;
if(H->Elements[j]>H->Elements[C])
{
Middle=H->Elements[C];
H->Elements[C]=H->Elements[j];
H->Elements[j]=Middle;
}

else break;
}

return H;
}

//BuildHeap    构建堆
PriorityQueue BuildHeap(ElementType *X,int N)
{
int i;
PriorityQueue H=NULL;                     //定义个空数组H
H=Initialize (2*N);

for(i=0;i<N;i++)
{
H->Elements[i+1]=X[i];                //将堆的元素直接放入数组中
}

for(i=N/2;i>0;i--)                        //由上一个for循环结束时，得i=N. 则倒序Procolate Down.
{
PercolateDown(i,H);
}

return H;
}

void main()
{
PriorityQueue h;

int x[]={13,21,16,24,31};
h=BuildHeap(x,11);
Insert(19,h);
Insert(68,h);
}

``````
• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 1条回答默认 最新

• JettLv 2017-07-17 09:08
已采纳

问题在于对结构体变量的指针，遗漏了对其malloc开辟空间。刚开始只是对结构体中的*Elements 开辟了空间。
PriorityQueue Initialize (int MaxElements)
{
PriorityQueue H; //数组型
if(MaxElements<MinPQSize)
Error("Priority queue size is too small");

``````H=(struct HeapStruct*)malloc(sizeof(struct HeapStruct));                    ///////此步骤重要！！！！！！！！！！！！！
if(H==NULL)
Error("Out of space!");

H->Elements=(int *)malloc(sizeof(ElementType)*(MaxElements+1));
if(H->Elements==NULL)
Error("Out of space!");

H->Capacity=MaxElements;
H->Size=0;
H->Elements[0]=MinData;                   //MinData
return H;
``````

}

``````
``````
点赞 评论