C语言 在链接列表中删除和插入节点的行为不同(?)

kwvwclae  于 2023-01-04  发布在  其他
关注(0)|答案(2)|浏览(151)

我正在学习King(2008)"C编程:现代方法",第2版,我对删除操作与插入操作相比的行为感到困惑。
作者写道(第429页):
注意,add_to_list并不修改列表指针,而是返回一个指向新创建节点的指针......让add_to_list更新first是一件棘手的事情。
现在,删除第一个节点不会修改原始列表,删除内部或末尾的节点会修改原始列表,但是delete_from_list也复制了first指针,那么为什么它可以修改first(而add_to_list不能)?
我错过了什么?

#include <stdio.h>
#include <stdlib.h>

struct node {
  int value;
  struct node *next;
};

struct node *delete_from_list(struct node *, int);
struct node *add_to_list(struct node *, int n);

int main(int argc, char **argv) {

  // setup a linked list
  
  // list's head
  struct node *first= NULL;

  // first node
  struct node *new_node= malloc(sizeof(struct node));
  new_node->value= 10;
  new_node->next= first;
  first= new_node;

  //second node
  new_node = malloc(sizeof(struct node));
  new_node->value= 20;
  new_node->next= first;
  first= new_node;

  //third node
  new_node= malloc(sizeof(struct node));
  new_node->value= 40;
  new_node->next= first;
  first= new_node;

  //fourth node
  new_node= malloc(sizeof(struct node));
  new_node->value= 30;
  new_node->next= first;
  first= new_node;

  int i;
  struct node *head= first;

  
  printf("\n------------------------\n");
  printf("    Original nodes: ");
  for(i=0; head!= NULL; head= head->next, i++)
    printf("\n%d-ith value: %d ", i, head->value);
  printf("\n------------------------\n");

  struct node *first_no20= delete_from_list(first, 20);
  struct node *head_no20= first_no20;
  
  printf("\n------------------------\n");
  printf("    Nodes without 20: ");
  for(i=0; head_no20!= NULL; head_no20= head_no20->next, i++)
    printf("\n%d-ith value: %d ", i,head_no20->value);
  printf("\n------------------------\n");

  
  printf("\n------------------------\n");
  head=first;
  printf("    Original nodes: ");
  for(i=0; head!= NULL; head= head->next, i++)
    printf("\n%d-ith value: %d ", i, head->value);
  printf("\n------------------------\n");

  struct node *first_no30= delete_from_list(first, 30);
  struct node *head_no30= first_no30;
 
  printf("\n------------------------\n");
  printf("    Nodes without 30: ");
  for(i=0; head_no30!= NULL; head_no30= head_no30->next, i++)
    printf("\n%d-ith value: %d ", i,head_no30->value);
  printf("\n------------------------\n");
  

  printf("\n------------------------\n");
  printf("    Original nodes: ");
  head=first;
  for(i=0; head!= NULL; head= head->next, i++)
    printf("\n%d-ith value: %d ", i, head->value);
  printf("\n------------------------\n");

  return 0;

}

struct node *delete_from_list(struct node *list, int n) {
  struct node *cur, *prev;

  for(cur=list, prev=NULL;
      cur != NULL && cur->value !=n;
      prev= cur, cur= cur->next)
    ;

  if(cur == NULL)
    return list;
  if(prev== NULL)
    list= list->next;
  else
    prev->next= cur->next;
  free(cur);

  return list;
}

struct node *add_to_list(struct node *list, int n) {
  struct node *new_node;

  new_node= malloc(sizeof(struct node));
  if(new_node == NULL) {
    printf("Error: malloc failed in add_to_list\n");
    exit(EXIT_FAILURE);
  }

  new_node->value = n;
  new_node->next= list;

  return new_node;
}
2fjabf4q

2fjabf4q1#

我认为这句话
注意add_to_list并不修改列表指针,而是返回一个指向新创建节点的指针......让add_to_list先更新,结果是很棘手的。
表示如下。
当新节点被添加到列表时,指向列表中已经存在的节点的所有指针(例如,所传递的指针和数据成员next的值)不改变。
另一方面,当删除节点时,则可以改变指向节点的指针(例如,指向所删除节点的指针或前一节点的数据成员next的值)。

fnvucqvd

fnvucqvd2#

在OP下的注解中,我们已经 * 尝试**教导 * OP代码中过多的指针是问题的根源,除了演示如何正确使用指向演化LL的第一个节点的一个指针(以及一个可以遍历LL的有用指针)之外,我们几乎没有别的办法。
下面是为执行所需任务而编写的main()函数。

int main( void ) {
    struct node *first = NULL;
    struct node *p = NULL;

    // first node
    p = malloc(sizeof(struct node));
    p->value = 10;
    p->next = first; first = p;

    //second node
    p = malloc(sizeof(struct node));
    p->value = 20;
    p->next = first; first = p;

    //third node
    p = malloc(sizeof(struct node));
    p->value = 40;
    p->next = first; first = p;

    //fourth node
    p = malloc(sizeof(struct node));
    p->value = 30;
    p->next = first; first= p;

    puts( "Created nodes:" );
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );

    first = delete_from_list( first, 20 );
    puts( "Nodes without 20:" );
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );

    first = delete_from_list( first, 30 );
    puts( "Nodes without 30:");
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );

    first = delete_from_list( first, 10 );
    puts( "Nodes without 10:");
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );

    printf( "There are no \"original nodes\". There are only those nodes on the list." );

    return 0;
}

省略了对那些多个malloc()调用成功的验证。这是读者的练习。

相关问题