首页 文章

链接列表中队列的实现

提问于
浏览 次
0

我得到了这些结构声明，以实现使用循环链表的队列集合 .

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是前面的，但我认为这是问题所在 . 非常感谢所有帮助 . 谢谢！

c linked-list queue

1 回答

  • 1

    您的问题出现在这一行：

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

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

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

    编辑

    为了解决您的评论，以下是如何以图形方式考虑具有三个元素的列表：

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

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

    回复于

相关问题