C 链表中的哨兵节点

Question

我正在尝试了解有关 C 中链表的更多信息，我最近偶然发现了 Sentinel Node 概念，但我无法理解它。根据我的幻灯片，哨兵节点在创建时应该是列表中的第一个，在添加其他节点时应该是最后一个。应该有一个指针永久指向哨兵节点。所有这些东西让我感到困惑，我希望在实施方面得到一些帮助。

/*this is a simple LL implementation*/
#include <stdio.h>
#include <stdlib.h>

struct List
{
    int data;
    struct List *next;
};

void ListInsert(int new_data)
{
    struct List *p;
    p = (struct List *)malloc(sizeof(struct List));
    p->data = new_data;
    p->next = (head);
    head = p;
}

void printList(struct List *q)
{
    q = head;
    while (q != NULL)
    {
        printf("%d ", q->data);
        q = q->next;
    }
    printf("\n");
}

int main()
{
    ListInsert(5);
    ListInsert(7);
    ListInsert(6);
    ListInsert(4);
    ListInsert(2);
    printList(head);
    return 0;
}

现在，如果我想创建哨兵节点，我该如何进行？

Answer 1

创建它。你说“应该有一个指针永久指向哨兵节点”，所以创建指针。然后使用指针作为列表的终止符而不是 NULL.

Sentinel node - Wikipedia

/*this is a simple LL implementation*/
#include <stdio.h>
#include <stdlib.h>

struct List
{
    int data;
    struct List *next;
};

struct List sentinel_node_instance;
/* a pointer to permanently point to the Sentinel Node */
struct List* const SENTINEL_NODE = &sentinel_node_instance;

/* the sentinel node should be the first thing on the list when it's created */
struct List* head = SENTINEL_NODE;

void ListInsert(int new_data)
{
    struct List *p;
    p = (struct List *)malloc(sizeof(struct List));
    p->data = new_data;
    p->next = (head);
    head = p;
}

void printList(void)
{
    struct List* q = head;
    while (q != SENTINEL_NODE)
    {
        printf("%d ", q->data);
        q = q->next;
    }
    printf("\n");
}

int main()
{
    ListInsert(5);
    ListInsert(7);
    ListInsert(6);
    ListInsert(4);
    ListInsert(2);
    printList();
    return 0;
}

Answer 2

According to the slides i have, the sentinel node should be the first thing on the list when its created and the last when other nodes are added.There should be a pointer to permanently point to the Sentinel Node.

先说最重要的一点：sentinel节点的目的，就是标记链表的结束。不会有与哨兵节点关联的真实数据，因此仅包含哨兵节点的列表在逻辑上是空的。

一些事情由此而来，包括：

哨兵节点的身份是整个列表的属性，而不是任何（其他）特定节点的身份
列表操作算法需要为末端由标记标记的链表和末端由其他方式标记的链表编写不同的方式。
每个列表都需要一个地方来存储哨兵的身份
一个预期有哨兵的列表如果没有哨兵则无效

实现细节的方法有很多，各有优缺点。

就个人而言，我倾向于（在非哨兵情况下也是如此）有一个结构来表示整个列表，与用于表示列表节点的结构分开。指向列表头节点的指针将是该结构的成员，在哨兵终止列表的情况下，指向哨兵节点的指针也是如此。当你创建一个新列表时，你也为它创建了一个哨兵节点；最初，列表的头指针和哨兵指针都指向该节点。头指针可以改变，但哨兵指针不能。当您追加到列表时，追加的节点会被放置在哨兵之前。尝试从列表中删除哨兵是错误的。

自己编写代码对你有利。

Answer 3

哨兵节点的另一种变体是循环双向链表，它既是头节点又是哨兵节点。 Visual Studio 以这种方式实现 std::list。

head.next  = pointer to first node or to head if empty list
head.prev  = pointer to last  node or to head if empty list
first.prev = pointer to head node
last.next  = pointer to head node

C 链表中的哨兵节点

Sentinel Node in a C Linked List

c

linked-list

singly-linked-list

sentinel