释放链表节点时出现分段错误

Question

LNode * deleteNext (LNode *L) {
if (L == NULL) { return L; }
LNode *deleted = L->next;
L->next = L->next->next;
//L->next->next = NULL;
delete deleted;
return L->next;
}

这是一个删除下一个指向节点的函数，逻辑简单。当前代码运行良好。但如果我取消注释注释行，就会出现分段错误，这对我来说很奇怪。提前谢谢。

Answer 1

这是一个错误的实现。如果L->next为NULL怎么办？

以下是一种可能(正确)的实现方式：

LNode * deleteNext (LNode *L) 
{
if (L == NULL || L->next == NULL) return NULL;
LNode *deleted = L->next; //L->next is NOT NULL
L->next = L->next->next;  
//^^^^^^^^^^^^ could be NULL though
delete deleted;
return L->next; //L->next could be NULL here
}

现在，由您决定要从函数返回什么。您可以返回L而不是L->next，也可以返回包含L和指示是否完成删除的布尔值的std::pair<LNode*, bool>。

Answer 2

这完全取决于列表的头和尾是如何实现的。我将假设列表的最后一个元素的下一个链接设置为null(即列表不是一个封闭的环)。

这个调用在概念上是错误的。如果不保留对其头(第一个元素)的引用，就无法处理单个链表，除非使用第一个元素作为头，这既不美观又低效。

此外，您还必须决定如何处理已删除的元素。删除它，然后返回一个指向它仍然温暖的尸体的指针，无论如何都不是最好的选择。

我假设调用方可能在检索元素时受到干扰(在这种情况下，调用方在使用完元素后必须删除它)。

LNode * removeNext (LNode *L)
{
if (L == NULL) panic ("Caller gave me a null pointer. What was he thinking?");
// should panic if the caller passes anything but a valid element pointer,
// be it NULL or 0x12345678
LNode * removed = L->next;
if (removed = NULL) return NULL; // L is the end of list: nothing to remove
L->next = removed->next; // removed does exist, so its next field is valid
// delete removed; // use this for the void deleteNext() variant
return removed;
}

这将无法完全清空列表。至少有一个元素会被卡在其中(可以说是伪头)。

此外，您还必须使用所述伪头初始化列表。使用伪头调用removeNext是安全的，这相当于将列表用作LIFO。但是，由于没有简单的方法来维护对列表尾部(最后一个元素)的固定引用，因此这种实现将不允许简单地用作FIFO。

我会这样做：

typedef struct _buffer {
struct _buffer * next;
unsigned long    data;
} tBuffer;
typedef struct {
tBuffer * head;
} tLIST; 
/* ---------------------------------------------------------------------
Put a buffer into a list
--------------------------------------------------------------------- */
static void list_put (tLIST * mbx, tBuffer * msg)
{
msg->next = mbx->head;
mbx->head = msg;
}
/* ---------------------------------------------------------------------
get a buffer from a list
--------------------------------------------------------------------- */
static tBuffer * list_get (tLIST * mbx)
{
tBuffer * res;
/* get first message from the mailbox */
res = mbx->head;
if (res != NULL)
{
/* unlink the buffer */
mbx->head = res->next;
}
return res;
}

(我在90年代中期写了这篇文章。真正的复古ANSI C.啊，那是那些日子…)

归根结底：如果你要实现一个单链表，不要把它当作一个随机访问的数据结构。它充其量是效率低下的，而且往往是一窝虫子。一个单链表可以用作FIFO，也可以用作堆栈，仅此而已

std：在存储结构方面，模板为您提供了您梦寐以求的一切，并且在过去20年左右的时间里，它们经过了测试和优化。没有一个活着的人(可能除了Donald Knuth)能在从头开始的设计中做得更好。