优先级队列分段故障

Question

我使用的是一个优先级队列，其中的优先级是double。我猜这就是问题的原因。我首先使用了这些数字，没有任何问题。

34.365681 34.481879 34.539832 36.715120

然后我使用了这些数字，但有一个分段错误。

45.411042 40.481879 37.702110 38.951187

struct PRIORITYQUEUE
    {
    int x_pq; 
    int y_pq;
    double heuristic_pq;
    int priority;
    int info;
    struct PRIORITYQUEUE *next;
}*start, *q, *temp, *new;

typedef struct PRIORITYQUEUE *N;

void insert(int x, int y, double heuristic)
{

    int item; 
    double itprio;
    //new = ( N* ) malloc( sizeof( N ) );
    new = malloc( sizeof( N ) );

    itprio = heuristic;
    new->x_pq = x;
    new->y_pq = y;
    new->heuristic_pq = itprio;

    if ( start == NULL || itprio < start->heuristic_pq )
    {
        new->next = start;
        start = new;
    }
    else
        {
            q = start;
            while ( q->next != NULL && q->next->heuristic_pq <= itprio )
                q = q->next;

            new->next = q->next;
            q->next = new;
        }
}

void del()
{
    if ( start == NULL )
    {
         printf( "\nQUEUE UNDERFLOW\n" );
    }
    else
    {
    new = start;
    printf( "\nDELETED ITEM IS %d\n", new->info );
    start = start->next;
    free( start );

    }

}

void display()
{
    temp = start;
    if ( start == NULL )
        printf( "QUEUE IS EMPTY\n" );

    else
    {
        printf( "QUEUE IS:\n" );

        while ( temp != NULL )
        {
            printf( "\t x is %d y is %d[heuristic=%lf] \n", temp->x_pq, temp->y_pq, temp->heuristic_pq );
            temp = temp->next;
        }
     }
}

Answer 1

您的问题出在以下代码上：

typedef struct PRIORITYQUEUE *N;
:
new = malloc( sizeof( N ) );

类型N是指向您的结构的指针，而不是结构本身。这意味着sizeof(N)可能比结构小得多，这意味着您没有分配足够的内存。

您可以通过在分配后立即插入以下内容来查看：

printf ("%zd %zd\n", sizeof (N), sizeof (struct PRIORITYQUEUE));

您可能会看到一系列格式为4 32或8 32的代码行，它们显示，虽然已经分配了4个或8个字节，但需要32个字节。

这就是导致你崩溃的原因。现在，至于如何修复它，它只是确保您为结构分配了足够的空间，这可以使用以下任一方法来完成：

new = malloc (sizeof (struct PRIORITYQUEUE));
new = malloc (sizeof (*N));

但我更喜欢的是：

new = malloc (sizeof (*new));

我更喜欢它的原因是它将分配量与您使用的变量联系在一起。虽然前两个将处理对结构大小的任何更改，但这一个甚至可以将new声明为一个完全不同的结构，而不必在多个位置更改信息。

我的意思是，如果更改new的类型，如下所示：

struct FASTER_PRIO_Q *new;

然后，对于前两种情况，您也需要更改分配语句。第三个就不是这样了。