如何编写修改链表头指针的C函数？-yiteyi-C++库

考虑链表的简单表示（没有任何哑节点）。在此类链表上运行的功能可分为两类：

null

1）不修改头指针的函数： 此类功能的示例包括打印链表、更新节点的数据成员（如向所有节点添加给定值），或访问/更新节点数据的某些其他操作通常很容易确定这类函数的原型。我们总是可以将head指针作为参数传递，并遍历/更新列表。例如，下面的函数将x添加到所有节点的数据成员中。

C

                         void                                     addXtoList(                                     struct                                     Node *node,                                     int                                     x)                       
                         {                       
                                                 while                                     (node != NULL)                       
                                                 {                       
                                                 node->data = node->data + x;                       
                                                 node = node->next;                       
                                                 }                       
                         }                       

2）修改头部指针的函数： 例如，在开始处插入节点（此函数中始终修改头指针）、在结束处插入节点（仅当插入第一个节点时才修改头指针）、删除给定节点（当删除的节点是第一个节点时修改头指针）。在这些函数中，可能有不同的方法来更新头指针。让我们用以下简单问题来讨论这些方法：

给定一个链表，编写一个函数deleteFirst（）来删除给定链表的第一个节点。例如，如果链表为1->2->3->4，则应将其修改为2->3->4 解决这个问题的算法是一个简单的三步过程：（a）存储头部指针（b）将头部指针更改为指向下一个节点（c）删除前一个头部节点。

以下是更新deleteFirst（）中的头指针的不同方法，以便在任何地方更新列表。

2.1) 使头部指针全局化：我们可以将头指针设为全局指针，以便在函数中访问和更新它。下面是使用全局头指针的C代码。

C

                         // global head pointer                       
                         struct                                     Node *head = NULL;                       
           
                         // function to delete first node: uses approach 2.1                       
                         // See                           http://ideone.com/ClfQB                          for complete program and output                       
                         void                                     deleteFirst()                       
                         {                       
                                                 if                                     (head != NULL)                       
                                                 {                       
                                                 // store the old value of head pointer                       
                                                 struct                                     Node *temp = head;                       
                                   
                                                 // Change head pointer to point to next node                       
                                                 head = head->next;                       
           
                                                 // delete memory allocated for the previous head node                       
                                                 free                                     (temp);                       
                                                 }                       
                         }                       

看见这对于使用上述功能的完整运行程序。

这不是一个推荐的方法，因为它有很多问题，比如： a） head是全球可访问的，因此它可以在项目中的任何位置进行修改，并可能导致不可预测的结果。 b）如果有多个链表，则需要多个具有不同名称的全局头指针。

看见这了解为什么我们应该在项目中避免全局变量。

2.2) 返回头指针：我们可以编写deletefirst（），使其返回修改后的头指针。无论是谁在使用这个函数，都必须使用返回的值来更新head节点。

C

                         // function to delete first node: uses approach 2.2                       
                         // See                           http://ideone.com/P5oLe                          for complete program and output                       
                         struct                                     Node *deleteFirst(                                     struct                                     Node *head)                       
                         {                       
                                                 if                                     (head != NULL)                       
                                                 {                       
                                                 // store the old value of head pointer                       
                                                 struct                                     Node *temp = head;                       
           
                                                 // Change head pointer to point to next node                       
                                                 head = head->next;                       
           
                                                 // delete memory allocated for the previous head node                       
                                                 free                                     (temp);                       
                                                 }                       
           
                                                 return                                     head;                       
                         }                       

看见这用于完整的程序和输出。这种方法比前一种方法要好得多。这只有一个问题，如果用户没有将返回值分配给头部，那么事情就会变得一团糟。C/C++编译器允许在不指定返回值的情况下调用函数。

C

head = deleteFirst(head); // proper use of deleteFirst()

deleteFirst(head); // improper use of deleteFirst(), allowed by compiler

2.3) 使用双指针：这种方法遵循简单的C规则： 如果要修改 一个函数的局部变量在另一个函数中传递指向该变量的指针 。因此，我们可以将指针传递给head指针，以便在deletefirst（）函数中修改head指针。

C

                         // function to delete first node: uses approach 2.3                       
                         // See                           http://ideone.com/9GwTb                          for complete program and output                       
                         void                                     deleteFirst(                                     struct                                     Node **head_ref)                       
                         {                       
                                                 if                                     (*head_ref != NULL)                       
                                                 {                       
                                                 // store the old value of pointer to head pointer                       
                                                 struct                                     Node *temp = *head_ref;                       
           
                                                 // Change head pointer to point to next node                       
                                                 *head_ref = (*head_ref)->next;                       
           
                                                 // delete memory allocated for the previous head node                       
                                                 free                                     (temp);                       
                                                 }                       
                         }                       

看见这用于完整的程序和输出。这种方法似乎是三种方法中最好的，因为出现问题的可能性较小。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章