RanenLove
JettLv
采纳率50%
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条回答

  • RanenLove JettLv 4年前

    问题在于对结构体变量的指针,遗漏了对其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;
    

    }

    
    
    点赞 评论 复制链接分享