为什么 C 中的这个队列实现会出现分段错误？

Question

我已经在 C 中实现了一个简单的队列，但是当我尝试在出列后访问 Q.front 时出现分段错误（例如，请参见 int main()）。

更准确地说，问题发生在我 -

入队单个元素。
将其出队。
入队一个或多个元素。
尝试访问 Q.front

但是当我 -

时，程序不会给出分段错误或任何错误

入队不止一个元素。
出列一次。
排队更多元素（可选）
访问 Q.front 成功。

所以这是我的完整程序 -

#include <stdio.h>
#include <stdlib.h> //for malloc

struct qnode
{
    int r;
    struct qnode *link;
};

typedef struct qnode qNode;

typedef struct
{
    qNode *front;
    qNode *rear;
    int qsize;
}QUEUE;

QUEUE initializeQueue(void)
{
    QUEUE q;
    q.front = NULL;
    q.rear = NULL;
    q.qsize = 0;
    return q;
}


qNode *createQueueNode(int e)
{
    qNode *temp;
    temp = (qNode *) malloc(sizeof(qNode));
    if(temp == NULL)
    {
        printf("INSUFFICIENT MEMORY\n");
        exit(0);
    }
    temp->r = e;
    temp->link = NULL;
    return temp;
}
QUEUE enqueue(QUEUE q, int e)
{
    if(q.rear == NULL)
    {
        q.rear = createQueueNode(e);
        q.front = q.rear;
        q.qsize++;
    }
    else
    {
        q.rear->link = createQueueNode(e);
        q.rear = q.rear->link;
        q.qsize++;
    }
    return q;
}

QUEUE dequeue(QUEUE q)
{
    qNode *temp;
    if(q.front == NULL)
    {
        printf("queue is empty\n");
        exit(0);
    }
    else
    {
        temp = q.front;
        q.front = q.front->link;
        free(temp);
    }

    q.qsize--;
    return q;
}



int main(){

    QUEUE Q = initializeQueue();
    Q = enqueue(Q, 2);
    printf("%d\n",Q.front->r);
    Q = dequeue(Q);
    Q = enqueue(Q,4);
    printf("%d\n",Q.front->r); // This line is giving segmentation fault 

    return 0;
}

Answer 1

Program terminated with signal 11, Segmentation fault.
#0  0x0000000000400859 in main () at ./2.c:87
87          printf("%d\n",Q.front->r); // This line is giving segmentation fault 
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.80.el6.x86_64
(gdb) p Q
 = {front = 0x0, rear = 0x1636010, qsize = 1}

front 为空，您访问它。你只需要一个像 gdb 这样的调试器来查看你的程序出了什么问题。

Answer 2

dequeue 将 q.front 设置为 NULL（从 q.front->link，之前在 createQueueNode 中设置为 NULL）并留下垃圾指针（指向 free()'d内存）在 q.rear 中。由于 q.rear 不为 NULL，因此在第二次调用 enqueue 时执行 enqueue 中 if 语句中的第二个块。它写入 free() 的内存 (q.rear->link)，然后将其取消引用到 q.rear。我很惊讶它并没有在那里崩溃，实际上，写入 free() 的内存。如果队列为空，快速修复可能是在出队时将 q.rear 设置为 NULL。您还应该添加健全性检查，以便出队不会运行在空队列上。

此外，您有一种有趣的方式可以像烫手山芋一样传递该结构。为什么不通过引用传递它并就地修改它而不是返回它？

为什么 C 中的这个队列实现会出现分段错误？

Why is this queue implementation in C giving segmentation fault?

c

queue

priority-queue

segmentation-fault