c-循环双链表结束函数

Question

在bool end（）函数中，程序会知道sentinel是开始还是结束吗？有没有一个检查我可以确保它读哨兵作为结束？

#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;
  }
}

Answer 1

您的规格是：

• 环的第一个元素之前的起始位置（ok）
• 结束测试电流是否超过最后一个元素（ok）
• 转发环上的一个元素（好吧，除非在调用start()之后，您有current == sentinel，所以forward什么都不做！）

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

如果答案是否定的，只需将开始位置更改为sentinel->next上的位置，即如果环存在，则更改为环的第一个元素上的位置；如果环为空，则更改至环的结束位置，即可完成操作。

如果答案是肯定的，那么你必须能够一方面区分第一个之前的，另一方面区分第二个之后的。

有两种简单的方法：

• 使用布尔值进行区分：

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

  当位置直接超过forward（或任何其他read函数）经过终点时，只需将end设置为true，在相反的情况下设置为true。

• 使用2个哨兵

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

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

Answer 2

据我所知，您需要结束函数来确定这是环的最后一个节点还是开始。

您可以修改您的结束函数，使其看起来像这样。

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

如果环中只有一个元素，那么总是在开始函数之后，结束条件为true。

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