C自由链表

Question

我需要知道如何修改 free 函数以删除列表的第一个元素（最后添加）。我不能干扰主要功能。这就是添加到我的最后一个元素如何保留在列表中。

typedef struct TEmployee
{
    struct TEmployee *m_Next;
    struct TEmployee *m_Bak;
    char *m_Name;
} TEMPLOYEE;


TEMPLOYEE *newEmployee (const char *name, TEMPLOYEE *next)
{
    TEMPLOYEE *n = (TEMPLOYEE*) malloc(sizeof(*next));
    
    n->m_Name = (char*) malloc(sizeof(char)*100);
    strcpy(n->m_Name, name);
    n->m_Bak = NULL;
    
    n->m_Next = next;
    
    return n;
    
}


void freeList ( TEMPLOYEE *q )
{
    TEMPLOYEE *x = q;
    
    while( x != NULL)
    {
        TEMPLOYEE *tmp = x->m_Next;
        free(x);
        x = tmp;
    }
    free(x);
    x=NULL;
}

Answer 1

目前freeList方法删除链表中的所有元素

只删除链表的第一个元素，算法如下：

给定 head 作为输入。
可能 head 本身是 NULL 意味着列表已经是空的，在这种情况下我们可以简单地 return.
在另一种情况下，我们可以简单地设置head = head->m_Next。
现在，由于我们还有之前的指针，我们需要更新当前头的之前指针，即head->m_Back = NULL。

请尝试使用上述算法并编写更新后的freeList方法。

Answer 2

如果不修改调用者就无法可靠地完成。

在它的基本形式中，您只需要释放节点并相信没有人再使用它：

void freeFirst ( TEMPLOYEE *q )
{
    if (q) {
        free(q->m_Name);
        free(q);
    }
}

现在为了让它更可靠一点，您还应该修改队列头节点。这可以通过传递一个双指针来允许修改头节点指针来完成：

void freeFirst ( TEMPLOYEE **q )
{
    TEMPLOYEE *x = *q;

    if (*q) {
        *q = (*q)->m_Next;
        free(*x->m_Name);
        free(*x);
    }
}

现在重要的是修改调用者，而不是 freeList(list) 您现在需要 freeList(&list).

并不是说我也释放了 m_Name 成员，否则你会泄漏内存。

您还应该使用 strdup 而不是任意长度的 malloc 和 strcpy 的组合，这可能会导致缓冲区溢出。

Answer 3

问题是您将指针按值传递给第一个元素。如果要修改head指针的值，需要通过引用传递，如：

void freeList ( TEMPLOYEE **q )
{
    TEMPLOYEE *x = *q;
    
    while( x != NULL)
    {
        TEMPLOYEE *tmp = x->m_Next;
        free(x);
        x = tmp;
    }
    /* free(x); this is incorrect, tmp is already NULL when you
     * get out of the while loop
     * x=NULL;  // and this is nonsense, it's already NULL and you are not
     *          // using x anymore.
     */
    *q = NULL; /* this is what you lack, to assign NULL to the pointer. */
}

稍后需要调用freelist()如下：

    freelist(&list_head);

传递指针的引用而不是指针的值。

C自由链表

C free linked list

c

linked-list