个性化阅读
专注于IT技术分析

如何编写修改链表头指针的C函数?

点击下载

考虑链表的简单表示(没有任何虚拟节点)。在此类链接列表上运行的功能可以分为两类:

1)不会修改头指针的函数:

此类功能的示例包括:打印链接列表, 更新节点的数据成员(如将给定值添加到所有节点)或其他一些访问/更新节点数据的操作

通常很容易确定此类功能的原型。我们总是可以将头指针作为参数传递并遍历/更新列表。例如, 以下函数将x添加到所有节点的数据成员。

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”

解决问题的算法是一个简单的3个步骤:(a)存储头指针(b)更改头指针以指向下一个节点(c)删除前一个头节点。

以下是在deleteFirst()中更新头指针的不同方法, 以便列表在任何地方都可以更新。

2.1)使头指针全局化:

我们可以将头指针设为全局, 以便可以在我们的函数中对其进行访问和更新。以下是使用全局头指针的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()使其返回修改后的头部指针的方式。谁在使用此功能, 都必须使用返回的值来更新头节点。

//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;
}

这种方法比以前的方法好得多。只有一个问题, 如果用户错过了将返回值分配给head的事情, 事情就会变得混乱。 C / C ++编译器允许在不分配返回值的情况下调用函数。

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

2.3)使用双指针:

这种方法遵循简单的C规则:

如果要在另一个函数中修改一个函数的局部变量, 请将指针传递给该变量。因此, 我们可以将指针传递到头指针, 以在deleteFirst()函数中修改头指针。

//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);
     }
}

这种方法似乎是所有这三种方法中最好的, 因为出现问题的机会更少。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

赞(0)
未经允许不得转载:srcmini » 如何编写修改链表头指针的C函数?

评论 抢沙发

评论前必须登录!