时间戳

首页 > 解决方案 > 无分支链表删除 C 中的条目

c - 无分支链表删除 C 中的条目

问题描述

在这个 TED 演讲中，Torvalds 提出了一个没有 if 条件的删除入口函数。我尝试在下面的代码中进行模拟，但如果要删除的条目是列表的头部，则它不起作用。1.）为什么这不能专门去除头部？2.) 这种方法不会产生内存泄漏，因为我们从不释放条目吗？

/** a data structure representing a node **/
struct node {
        int data;
        struct node* next;
};

/** create a new node and return a pointer to it**/
struct node* new_Node(int data)
{
        struct node* newP = malloc(sizeof(struct node));
        newP-> data = data;
        newP-> next = NULL;
        return newP;
}
/** function to print out a list**/
void list_print(struct node* head)
{
        printf("Begin List Print:\n");
        struct node* tmp = malloc(sizeof(struct node));
        tmp = head;

        while(tmp != NULL ) {
                printf("%d\n", tmp->data);
                tmp = tmp->next;
        }
        printf("End List Print\n\n");

}
 /** function to delete one node **/
void list_remove_entry(struct node* head, struct node* entry)
{
        struct node** indirect = &head;
    
        while((*indirect) != entry) {
                indirect = &(*indirect)->next;
        }
        *indirect = (*indirect)->next;
}
    
/** the program entry point**/
int main()
{
        struct node* head = new_Node(1);
        struct node* n1 = new_Node(2);
        struct node* n2 = new_Node(3);
        head->next = n1;
        n1->next = n2;
    
        list_print(head);
    
        list_remove_entry(head, head);
        list_print(head);
    
        return 0;
}

标签： cpointerssingly-linked-list

解决方案

TED 演讲中的代码不head作为参数，它是一个全局变量。

结果，当它发生

*indirect = entry->next;

head如果要删除的条目等于，它将修改变量head，因为while循环立即停止并且indirect仍然包含&head。

当您创建参数时，这并不相同head，因为现在您只是修改局部变量，而不是调用者的变量。请参阅使用函数更改指针包含的地址，了解如何重新设计函数来解决这个问题（它也在@tadman 的答案中）。

在回答您的第二个问题时，是的，这会造成内存泄漏。Linus 的示例只是为了说明编写此函数的两种方法的一个特定方面，因此他省略了与该差异无关的所有内容。您可以通过将作业替换为以下内容来解决此问题：

(*indirect)->next = (*indirect)->next->next;
free(*indirect);

请注意，他还遗漏了错误检查。他的代码假定会找到该条目，因此他*indirect == NULL在取消引用之前从不检查（并且我上面的分配不检查双重间接）。

这不是一堂编码课，它只是一个需要放在幻灯片上的简单示例。

推荐阅读