我正在学习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;
}
2条答案
按热度按时间2fjabf4q1#
我认为这句话
注意add_to_list并不修改列表指针,而是返回一个指向新创建节点的指针......让add_to_list先更新,结果是很棘手的。
表示如下。
当新节点被添加到列表时,指向列表中已经存在的节点的所有指针(例如,所传递的指针和数据成员
next
的值)不改变。另一方面,当删除节点时,则可以改变指向节点的指针(例如,指向所删除节点的指针或前一节点的数据成员
next
的值)。fnvucqvd2#
在OP下的注解中,我们已经 * 尝试**教导 * OP代码中过多的指针是问题的根源,除了演示如何正确使用指向演化LL的第一个节点的一个指针(以及一个可以遍历LL的有用指针)之外,我们几乎没有别的办法。
下面是为执行所需任务而编写的
main()
函数。省略了对那些多个
malloc()
调用成功的验证。这是读者的练习。