c - 链表中队列的实现

Question

我给出这些结构声明是为了实现使用循环链表的队列集合。

typedef struct intnode {
    int value;
    struct intnode *next;
} intnode_t;

typedef struct {
    intnode_t *rear;   // Points to the node at the tail of the 
                       // queue's linked list
    int size;          // The # of nodes in the queue's linked list
} intqueue_t;

intnode_t *intnode_construct(int value, intnode_t *next)
{
    intnode_t *p = malloc(sizeof(intnode_t));
    assert (p != NULL);
    p->value = value;
    p->next = next;
    return p;
}


/* Return a pointer to a new, empty queue.
 * Terminate (via assert) if memory for the queue cannot be allocated.
 */

intqueue_t *intqueue_construct(void)
{
    intqueue_t *queue = malloc(sizeof(intqueue_t));
    assert(queue != NULL);

    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

我正在尝试创建一个函数，该函数将以指定值入队(将其附加到队列的末尾)，并且我需要考虑队列为空以及队列有一个或一个的两种情况更多元素。这是我到目前为止的代码:

void intqueue_enqueue(intqueue_t *queue, int value)
{

    intnode_t *p = intnode_construct(value, NULL);

    if(queue->rear->next == NULL) {
        //the queue is empty
        queue->rear->next =p;
    } else {
        //the queue is not empty
        queue->rear=p;
    }
    queue->rear=p;
    queue->size++;
}

这段代码给了我一个运行时错误，所以我不确定出了什么问题。在代码中，我假设queue->rear->next是前面，但是我认为这可能是问题所在。非常感谢所有帮助。谢谢!

Answer 1

您的问题出现在这一行:

if(queue->rear->next == NULL) {

第一次调用该函数时，queue->rear为NULL。因此，当您尝试取消引用它以获取 queue->rear->next 时，您会收到运行时错误。

要修复此代码，请更新 intqueue_enqueue 以仅检查 queue->size==0 是否，如果是，则需要通过设置 来初始化它队列->rear=p 和p->next=p。然后更新 else 子句，以便将元素插入到两个现有元素之间。提示:您需要将 queue->rear->next 存储在 p 中。

编辑

为了回应您的评论，以下是如何以图形方式思考包含三个元素的列表:

<element1: next==element2> <element2: next==element3> <element3: next==element1>

并且queue->rear指向element3。因此，要插入第四个元素，您需要使 queue->rear 指向 element4 并且 element4->rear 需要指向element1。请记住，element 的位置存储在 rear->next 中。