循环双链表结束函数

在bool end（）函数中，程序将知道标记是开始还是结束？有没有我可以检查的结果，以确保它正在读取哨兵作为结束？循环双链表结束函数

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

struct node { 
    int item; 
    struct node *prev; 
    struct node *next; 
}; 
typedef struct node node; 

struct ring { 
    node *sentinel; 
    node *current; 
}; 

ring *new_ring() { 
    ring *p; 
    node *n; 

    p = (ring *) malloc (sizeof(ring)); 
    n = malloc(sizeof(node)); 
    p->sentinel = n; 
    n->next = n; 
    n->prev = n; 
    return p; 
} 

void start(ring *r) { 
    r->current = r->sentinel; 
} 

bool end(ring *r) { 
    return r->current == r->sentinel; 
} 

void forward(ring *r) { 
    while (r->current != r->sentinel) { 
    r->current = r->current->next; 
    } 
}

来源

2015-12-07 user5647965

请详细描述圆形列表应该如何工作。哨兵的角色究竟是什么？ – Codor

其目的是为了让第一个和最后一个节点指向它，以便在任何地方都没有NULL指针，因此不需要对NULL进行特殊测试。当列表为空时，它只包含前哨节点，前哨节点向前和向后指向自身。 – user5647965

由于您使用* bool *，因此您需要包含* stdbool.h *。 –

您的规格有：

环的第一个元素之前的起始位置（OK）
终端的测试，如果目前是过去的最后一个元素（OK）
向前档的一个元素（OK，除非在拨打start()之后，你有current == sentinel，所以forward什么都不做！）

但是你应该回答这个问题：你需要实现对称函数吗？

如果答案是否定的，只需将开始位置改为sentinel->next即环上的第一个元素（如果存在的话），并且如果环是空的则结束，并且结束。

如果答案是肯定的，那么你必须要能够一方面前第一区分，而在另一过去结束。

有2点为简单的方法：

使用一个布尔值来区分：

struct ring { node *sentinel; node *current; bool end; };

刚才设置end到true当你直接过去的结束位置时forward（或任何其他读取功能）结束，并在相反的情况下为真。

使用2个哨兵

struct ring { node *before; node *after; node *current; };

你应该before->next = after;初始化它们和after->prev = before

来源

2015-12-07 15:20:41

据我了解，你需要你的最终功能，以确定这是否是你的最后一个节点戒指还是这个开始。

你可以修改你的最终功能，看起来像这样。

bool end(ring *r) { 
    return r->current->next == r->sentinel; 
}

如果只有一个环形元件，那么你的启动功能后始终，最终病情会是真的。

但是如果有多个元素，那么一旦结束返回true，r-> current将是sentinel之前的最后一个元素。

来源

2015-12-07 16:21:28 rango

循环双链表结束函数

回答

相关问题