C-检查指针是否为null会产生分割故障

Question

问题语句：我们必须删除链接列表的每个替代节点。例如：原始列表：1-> 2-> 3-> 4-> 4-> 5 to：1-> 3-> 5

完整的问题声明：https：//practice.geeksforgeeks.org/problems/delete-alternate-nodes/1/?ref= self

您可以看到，这是一个功能问题，因此我实际上并不是编写完整的代码（只需完成功能）即可。这是我正在编写的代码：

void deleteAlt(struct Node *head){
    // Code here
    struct Node *traverse=head,*alternate=head->next;
    if(alternate->next==NULL)
    {
        head->next=NULL;
        return;
    }
    while(traverse->next!=NULL && alternate->next!=NULL)
    {
        traverse->next = alternate->next;
        traverse = traverse->next;
        alternate = traverse->next;
        if((alternate->next)==NULL) //presence of this if statement causes segmentation fault
        {
            traverse->next=NULL;
        }
    }
}

我在Stackoverflow上遇到了类似的问题，但是它们的代码和目标是不同的，例如，没有初始化指针并进行比较。但是，我的问题是不同的。

在节点数量的情况下， alternate始终将是无效的，因此没有初始化问题。

Answer 1

你做

while(traverse->next!=NULL && alternate->next!=NULL)
  traverse->next = alternate->next;
  traverse = traverse->next;
  alternate = traverse->next;
  if((alternate->next)==NULL) //presence of this if statement causes segmentation fault

所以实际上

while(traverse->next!=NULL && alternate->next!=NULL)
  traverse = alternate->next;
  alternate = traverse->next;
  if((alternate->next)==NULL) //presence of this if statement causes segmentation fault

所以实际上

while(traverse->next!=NULL && alternate->next!=NULL)
  alternate = alternate->next->next;
  if((alternate->next)==NULL) //presence of this if statement causes segmentation fault

所以实际上

while(traverse->next!=NULL && alternate->next!=NULL)
  if((alternate->next->next->next)==NULL) //presence of this if statement causes segmentation fault

当alternate->next->next为null时（未由检查）alternate->next->next->next导致您的分割故障

---

解决方案是：

void deleteAlt(struct Node * head)
{
  if (head != NULL) {
    while (head->next != NULL) {
      Node * d = head->next;
      head->next = head->next->next;
      free(d);
      head = head->next;
    }
  }
}

一个完整的程序要证明：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
  int v;
  struct Node * next;
} Node;
Node * make(int v, Node * n)
{
  Node * r = malloc(sizeof(Node));
  r->v = v;
  r->next = n;
  return r;
}
void pr(Node * l)
{
  while (l != NULL) {
    printf("%d ", l->v);
    l = l->next;
  }
  putchar('n');
}
void deleteAlt(struct Node * head)
{
  if (head != NULL) {
    while (head->next != NULL) {
      Node * d = head->next;
      head->next = head->next->next;
      free(d);
      head = head->next;
    }
  }
}
int main()
{
  Node * l = make(1, make(2, make(3, make(4, make(5, NULL)))));
  pr(l);
  deleteAlt(l);
  pr(l);
  /* free rest of list */
  while (l != NULL) {
    Node * n = l->next;
    free(l);
    l = n;
  }
}

汇编和执行：

pi@raspberrypi:/tmp $ gcc -pedantc -Wextra l.c
pi@raspberrypi:/tmp $ ./a.out
1 2 3 4 5 
1 3 5 
pi@raspberrypi:/tmp $ 

在 valgrind下执行检查内存访问/泄漏

pi@raspberrypi:/tmp $ valgrind ./a.out
==2479== Memcheck, a memory error detector
==2479== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2479== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2479== Command: ./a.out
==2479== 
1 2 3 4 5 
1 3 5 
==2479== 
==2479== HEAP SUMMARY:
==2479==     in use at exit: 0 bytes in 0 blocks
==2479==   total heap usage: 6 allocs, 6 frees, 1,064 bytes allocated
==2479== 
==2479== All heap blocks were freed -- no leaks are possible
==2479== 
==2479== For counts of detected and suppressed errors, rerun with: -v
==2479== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

---

（编辑）如果列表的长度可以是甚至必须更改为：

的定义。

void deleteAlt(struct Node * head)
{
  while ((head != NULL) && (head->next != NULL)) {
    Node * d = head->next;
    head->next = head->next->next;
    free(d);
    head = head->next;
  }
}

修改 main 检查：

int main()
{
  {
    Node * l = make(1, make(2, make(3, make(4, make(5, NULL)))));
    pr(l);
    deleteAlt(l);
    pr(l);
    /* free rest of list */
    while (l != NULL) {
      Node * n = l->next;
      free(l);
      l = n;
    }
  }
  {
    Node * l = make(1, make(2, make(3, make(4, NULL))));
    pr(l);
    deleteAlt(l);
    pr(l);
    /* free rest of list */
    while (l != NULL) {
      Node * n = l->next;
      free(l);
      l = n;
    }
  }
}

汇编和执行：

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra l.c
pi@raspberrypi:/tmp $ ./a.out
1 2 3 4 5 
1 3 5 
1 2 3 4 
1 3 

和 valgrind ：

pi@raspberrypi:/tmp $ valgrind ./a.out
==3450== Memcheck, a memory error detector
==3450== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3450== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3450== Command: ./a.out
==3450== 
1 2 3 4 5 
1 3 5 
1 2 3 4 
1 3 
==3450== 
==3450== HEAP SUMMARY:
==3450==     in use at exit: 0 bytes in 0 blocks
==3450==   total heap usage: 10 allocs, 10 frees, 1,096 bytes allocated
==3450== 
==3450== All heap blocks were freed -- no leaks are possible
==3450== 
==3450== For counts of detected and suppressed errors, rerun with: -v
==3450== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

Answer 2

尝试以下：

void deleteAlt(struct Node *head){
    struct Node * head_tmp=head;
    struct Node * tmp=NULL;
    while(head_tmp->next!=NULL){
        tmp=head_tmp->next;
        head_tmp->next=tmp->next;
        head_tmp=tmp->next;
        //do something for freeing tmp node 
    }

}

Answer 3

我可以在

中看到代码气味

if(alternate->next==NULL)
    {
        head->next=NULL;
        return;
    }

如果我有一个节点怎么办？在这种情况下， alternate指向null。