使用双指针在C中插入链表

Question

嗨，我是一个学习链表的新手，我创建了这个示例程序，但它并没有填充所有列表，只有最后两个被填充(或覆盖第一个链接元素(

有人能帮我解决问题的原因吗？

#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *link;
};  
void appendNode(int data, struct node **ptr) {
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = data;
newnode->link = NULL;
if(*ptr == NULL) {
*ptr = newnode;
} else {
while((*ptr)->link != NULL ) {
*ptr = (*ptr)->link;
}
(*ptr)->link = newnode;
}
}
void printList(struct node *node) 
{ 
while (node != NULL) 
{ 
printf(" %d ", node->data); 
node = node->link; 
} 
} 
int main() {
struct node *head = NULL ;
appendNode(23,&head);
appendNode(45,&head);
appendNode(32,&head);
appendNode(11,&head);
appendNode(98,&head);
printList(head);
}

Ir打印

11  98 

是什么导致了这里的问题？

Answer 1

您的问题是在appendNode^[1]中使用指针本身进行迭代。这是在每次为*ptr分配内容时更改列表地址，例如

*ptr = newnode;
...
*ptr = (*ptr)->link;

每次分配*ptr时，列表地址都会发生变化(如appendNode和main()中所示(

您的列表操作是正确的，您所需要做的就是使用临时指针来迭代列表(下面的iter(

void appendNode (int data, struct node **ptr) {
struct node *newnode = malloc (sizeof *newnode),
*iter = *ptr;
if (!newnode) { /* VALIDATE every allocation */
perror ("malloc-newnode");
exit (EXIT_FAILURE);
}
newnode->data = data;
newnode->link = NULL;
if (iter == NULL) {
*ptr = newnode;
}
else {
while (iter->link != NULL) {
iter = iter->link;
}
iter->link = newnode;
}
}

(注意使用与sizeof一起使用的去引用指针来设置类型大小。如果使用去引用指针设置大小，则可以消除设置所需实际类型时的任何错误。此外，如果每次分配(必须验证(

随着这一变化(以及随后对printList的变化(

void printList (struct node *node) 
{ 
while (node != NULL) 
{ 
printf(" %d ", node->data); 
node = node->link; 
}
putchar ('n');     /* tidy up with newline */
} 

您的列表运行良好，例如

示例使用/输出

$ ./bin/lllast2
23  45  32  11  98

脚注：

1。虽然不是错误，但C通常避免使用camelCase或MixedCase变量名，而支持所有小写，同时保留大写名称用于宏和常量。这是一个风格问题——所以这完全取决于你，但如果不遵循它，可能会在某些圈子里给人留下错误的第一印象。

Answer 2

替换：

while((*ptr)->link != NULL ) {
*ptr = (*ptr)->link;
}
(*ptr)->link = newnode;

带有：

struct node* last = *ptr;
while (last->link) {
last = last->link;
}
last->link = newnode;

尽管将其提取到自己的功能中可能会很好：

struct node* findLastNode(struct node* ptr) {
while (ptr->link) {
ptr = ptr->link;
}
return ptr;
}

然后，在appendNode:内部

struct node* last = findLastNode(*ptr);
last->link = newnode;