在 C 中使用链表实现队列

Question

我正在尝试使用链表实现队列。这是我的程序

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

struct queue_struct{
    int ele;
    struct queue_struct *next;
};

struct Queue{
    struct queue_struct *front, *rear;
};

int isEmpty(struct Queue *q){
    return (q->front==NULL||q->rear==NULL);
}

void enqueue(struct Queue *q, int x){
    struct queue_struct *temp=(struct queue_struct *)malloc(sizeof(struct queue_struct));
    temp->ele=x;
    temp->next=NULL;
    if(isEmpty(q)){
        q->front=q->rear=temp;
        return;
    }
    q->rear=temp;
    printf("The item %d has been enqueued into the queue\n", x);
}

void dequeue(struct Queue *q){
    if(isEmpty(q)){
        printf("The queue is already empty. No more elements can be removed!\n");
        return;
    }
    struct queue_struct *temp=q->front;
    printf("The item %d has been dequeued from the queue\n", temp->ele);
    q->front=q->front->next;
    if(q->front=NULL)
        q->rear=NULL;
    free(temp);
}

void display(struct Queue *q){
    struct queue_struct *temp=q->front;
    int len;
    printf("The contents of the queue are:\n");
    if(isEmpty(q)){
        printf("Nothing to be shown, the queue is empty.\n");
        return;
    }
    while(temp!=NULL){
        temp=temp->next;
        len++;
    }
    temp=q->front;
    for(int i=1;i<len-1;i++){
        printf("|  %d  |\n", temp->ele);
        printf(" ------ \n");
        temp=temp->next;
    }
    printf("|  %d  |\n", temp->ele);
}

int main()
{
    int choice, element;
    printf("LET'S START WITH AN EMPTY QUEUE\n\n");
    struct Queue *q=(struct Queue *)malloc(sizeof(struct Queue));
    q->front=q->rear=NULL;
    while(1){
        printf("\nMENU\n");
        printf("----\n");
        printf("\t1. Enqueue\n");
        printf("\t2. Dequeue\n");
        printf("\t3. Display queue\n");
        printf("\t4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch(choice){
            case 1: printf("Enter the element to be enqueued: ");
                    scanf("%d", &element);
                    enqueue(q, element);
                    break;
            case 2: dequeue(q);
                    break;
            case 3: display(q);
                    break;
            case 4: printf("Program terminated successfully!\n");
                    return 0;
            default: printf("Invalid input");
        }
    }
}

但是，当我尝试对元素进行排队时，我遇到了分段错误

经过调试，我发现我的 isEmpty() 函数是罪魁祸首，但我似乎找不到问题所在。考虑到问题的性质，我认为 front OR rear 应该是 NULL 才能使队列为空。我的理解错了吗？感谢任何帮助。

编辑
正如@interjay 所建议的，我对 main() 方法的 q=NULL 部分进行了更改。但是，我的 display 方法现在出错了。我不明白为什么。

Answer 1

存在以下问题：

您不应该将 NULL 分配给 q，因为那是指向您刚刚分配的内存的指针，它包含指针 front 和rear，您将始终需要，即使队列为空。相反，您应该将 front 和 rear 指针设置为 NULL:
```
q->front = q->rear = NULL;
```
在 dequeue 中，您在 if 条件中有一个赋值，您实际上需要一个比较。改变这个：
```
if(q->front=NULL)
```
至：
```
if(q->front==NULL)
```
在 display 中，您在第一个循环后取消引用 temp，您确定它实际上是 NULL。所以这将引发异常。你应该只有 one 循环。任何使用相同 temp 指针再次遍历列表的尝试都需要将 temp 指针重置为 front。这是 display 函数的简单替换：
```
void display(struct Queue *q){
    struct queue_struct *temp=q->front;
    printf("The contents of the queue are:\n");
    if(isEmpty(q)){
        printf("Nothing to be shown, the queue is empty.\n");
        return;
    }
    while(temp!=NULL){
        printf("%d->", temp->ele);
        temp=temp->next;
    }
    printf("NULL\n");
}
```
如果您还希望显示 i 计数器，则只需在上面的循环中递增它即可。

通过这些更改，您的代码将正常工作。

Answer 2

有一些问题。

在main中，做q = NULL;是内存泄漏，会产生段错误。初始化空队列的正确方法是：

q->front = NULL;
q->rear = NULL;

队列显示使用while循环寻找队列的末尾，从而保证temp在随后的for循环中会是NULL（即段错误）。只需要 for 循环

enqueue 不正确处理附加到非空列表。

dequeue 有一个 if 语句，它使用赋值运算符 if (q->front = NULL) 而不是相等运算符 if (q->front == NULL)。但是，即使进行了该修复，它仍然无法正确处理操作。

isEmpty 函数与其他函数并没有多大用处，因为它们 can/should 只是检查 front。

不要转换 malloc 的 return 值。请参阅：Do I cast the result of malloc? 转换会引入难以发现的细微错误。

这是修复问题的重构版本。我对一些 struct 名称做了一些 cleanup/renaming 以便更能描述功能。

在下面的代码中，我使用 cpp 条件来显示更改（例如）：

#if 0
// old code
#else
// new code
#endif

我已经在可能的地方注释了错误：

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

typedef struct queue_element QElement;
struct queue_element {
    int ele;
    QElement *next;
};

typedef struct Queue {
    QElement *front, *rear;
} Queue;

int
isEmpty(Queue *q)
{
    return (q->front == NULL || q->rear == NULL);
}

void
enqueue(Queue *q, int x)
{
    QElement *temp = malloc(sizeof(*temp));

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

// NOTE/BUG: this does _not_ append correctly to a non-empty list
#if 0
    if (isEmpty(q)) {
        q->front = q->rear = temp;
        return;
    }

    q->rear = temp;
#else
    // link old rear node to new node
    if (q->rear != NULL)
        q->rear->next = temp;

    // set new rear node
    q->rear = temp;

    // set the front of the list if it was empty
    if (q->front == NULL)
        q->front = temp;
#endif

    printf("The item %d has been enqueued into the queue\n", x);
}

void
dequeue(Queue *q)
{
    QElement *temp = q->front;

    if (temp == NULL) {
        printf("The queue is already empty. No more elements can be removed!\n");
        return;
    }

    printf("The item %d has been dequeued from the queue\n", temp->ele);

    q->front = temp->next;
    if (q->rear == temp)
        q->rear = NULL;

    free(temp);
}

void
dequeue_OLD(Queue *q)
{
    if (isEmpty(q)) {
        printf("The queue is already empty. No more elements can be removed!\n");
        return;
    }
    QElement *temp = q->front;

    printf("The item %d has been dequeued from the queue\n", temp->ele);
    q->front = q->front->next;
// NOTE/BUG: this if is invalid -- it is using the assignment operator in
// place of the [desired] equality operator
// NOTE/BUG: even with this fix, the dequeue is still broken -- see the fix
// above
#if 0
    if (q->front = NULL)
        q->rear = NULL;
#else
    if (q->front == NULL)
        q->rear = NULL;
#endif
    free(temp);
}

void
display(Queue *q)
{
    QElement *temp = q->front;

    printf("The contents of the queue are:\n");

    if (temp == NULL) {
        printf("Nothing to be shown, the queue is empty.\n");
        return;
    }

// NOTE/BUG: doing the while loop ensures that temp will be NULL so that the
// for loop will try to dereference temp and it will segfault
#if 0
    int len;
    while (temp != NULL) {
        temp = temp->next;
        len++;
    }
    for (int i = 1; i < len - 1; i++) {
        printf("|  %d  |\n", temp->ele);
        printf(" ------ \n");
        temp = temp->next;
    }
    printf("|  %d  |\n", temp->ele);
#else
    int sep = 0;
    for (;  temp != NULL;  temp = temp->next) {
        if (sep)
            printf(" ------ \n");
        sep = 1;
        printf("|  %d  |\n", temp->ele);
    }
#endif
}

int
main(void)
{
    int choice, element;

    printf("LET'S START WITH AN EMPTY QUEUE\n\n");
    Queue *q = malloc(sizeof(*q));
// NOTE/BUG: setting q to NULL ensures a segfault and is a memory leak
#if 0
    q = NULL;
#else
    q->front = NULL;
    q->rear = NULL;
#endif

    while (1) {
        printf("\nMENU\n");
        printf("----\n");
        printf("\t1. Enqueue\n");
        printf("\t2. Dequeue\n");
        printf("\t3. Display queue\n");
        printf("\t4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch (choice) {
        case 1:
            printf("Enter the element to be enqueued: ");
            scanf("%d", &element);
            enqueue(q, element);
            break;
        case 2:
            dequeue(q);
            break;
        case 3:
            display(q);
            break;
        case 4:
            printf("Program terminated successfully!\n");
            return 0;
        default:
            printf("Invalid input");
            break;
        }
    }

    return 0;
}

在 C 中使用链表实现队列

Implementing Queue using Linked list in C

c

queue

linked-list