编译可通过,无法运行:
单步调试,此处出错:
代码如下:
#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);
}