如何在 C 中实现基本队列？

Question

我正在努力学习数据结构，但我正在努力让这段代码发挥作用。问题是我使用 gcc C 编译器得到 segmentation fault(core dumped)。它应该是一个队列。代码：

#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 50

struct node{
    int data;
    struct node * next;
};

struct queue{
    int count;
    struct node * rear ,* front;
};

void create (struct queue * q) {
    q -> front = NULL;
    q -> rear = NULL;
    q -> count = 0;
}

int isempty(struct queue * q) {
    if(q -> count == 0)
        return 1;
    return 0;
}

int full(struct queue * q) {
    if(q -> count == STACK_SIZE) {
        return 1;
    }
    return 0;
}

void enqueue(struct queue * q , int x) {
    struct node * temp;
    temp = (struct node*) malloc(sizeof(struct node));

    temp -> data = x;
    temp -> next = NULL;

    if (full(q)) {
        printf("Not possible. Overflow.");
    }
    else if(isempty(q)) {
        q -> front = q -> rear = temp;
    } else {
        q -> rear -> next = temp;
        q -> rear = temp;
    }
    q -> count++;
}

int dequeue (struct queue * q) {
    struct node * p;
    p = (struct node*) malloc (sizeof(struct node));
    p = q -> front;

    if(isempty(q)) {
        printf("Not possible. Underflow.");
    } else {
        q -> front = q -> front -> next;
        q -> count--;
    }
    int x = (p -> data);
    return x;
}

int main (void) {
    struct queue *q;
    create (q);
    enqueue(q, 5);
}

问题很可能是指针的使用。我已经审查了几次，但没有解决方案。 Valgrind 和 gdb 调试器也没有太大帮助。

Answer 1

您没有为 main() 中的 q 分配内存，因此在尝试访问 create() 中的 q->front 时崩溃。

int main (void) {
    struct queue *q; // No allocation here
    ...
}

您可能想要这个，效果很好：

int main (void) {
    struct queue q;
    create (&q);
    enqueue(&q, 5);
}

Answer 2

如 OctaveL 所述，在函数 create 中，您尝试设置队列的字段，但传递给该函数的指针未指向队列，它未初始化.如果您将选项 -Wall 添加到 gcc，它实际上会警告您：

$ gcc -o test -Wall test.c
test.c: In function 'main':
test.c:71:5: warning: 'q' is used uninitialized in this function [-Wuninitialized]
     create (q);
     ^~~~~~~~~~

方案一：将q声明为一条记录，将q的地址传给函数create:

struct queue q;
create (&q);

解决方案 2：将 q 声明为指针并分配一个新的队列变量：

struct queue *q;
q = malloc(sizeof *q);
create(q);

我还建议您将函数 create 重命名为 init 或 clear 因为它不会创建新队列，它只会初始化（或清除）它。

为了更容易分配内存并正确处理错误，引入两个宏很方便：

#define NEW_ARRAY(ptr, n) \
    (ptr) = malloc((n) * sizeof (ptr)[0]); \
    if ((ptr) == NULL) { \
        fprintf(stderr, "Memory allocation failed: %s\n", strerror(errno)); \
        exit(EXIT_FAILURE); \
    }

#define NEW(ptr) NEW_ARRAY(ptr, 1)

有了这些，如果 create 重命名为 init 你可以将解决方案 2 写成

struct queue *q;
NEW(q);
init(q);

如何在 C 中实现基本队列？

How can I implement a basic queue in C?

c

queue

data-structures