使用二重指针进行单链表操作
本帖最后由 -Shizuku- 于 2023-12-13 01:18 编辑链表是一种非常基本的数据结构。链表结构十分简单，分为数据域与指针域。数据域存储了表中的数据，指针域则表示链表的连接方式。
单链表仅包含一个指针，即next指针，表示本节点的下一个节点的位置，链表因此也有了易修改的特性，文件系统也充分利用了该特性。
本帖将以Pure C为背景进行说明。
- 指针的本质
指针本身是一个变量，本身储存的值是其指向的对象的地址，可以通过改变指针的值来移动指针，也可以通过改变指针所指的值来间接修改变量。
本次要讲述的是利用上述性质，通过二重指针的操作来实现单链表删除。
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node* next;
};
struct node* assign_linked_list(struct node* head);
void print_list(struct node* head);
void del_list(struct node* head,int val);
int main(int argc, const char * argv[]) {
struct node* head=NULL;
head=assign_linked_list(head);
int val;
scanf("%d",&val);
del_list(head,val);
print_list(head);
return 0;
}
struct node* assign_linked_list(struct node* head){
int n;
scanf("%d",&n);
if(n==0){
return NULL;
}
struct node* ptr=(struct node*) calloc(1,sizeof(struct node));
ptr->data=n;
ptr->next=assign_linked_list(ptr->next);
return ptr;
}
void print_list(struct node* head){
for(struct node* curr=head;curr;){
printf("%d ",curr->data);
curr=curr->next;
}
}
void del_list(struct node* head,int val){
struct node* prev=NULL;
for(struct node* curr=head;curr;){
if(curr->data==val){
if(prev){
prev->next=curr->next;
}
else{
prev=curr;
}
struct node* ptr=curr;
curr=curr->next;
free(ptr);
}
else{
prev=curr;
curr=curr->next;
}
}
}
以上是一段再正常不过的单链表创建，删除，以及输出的一个程序，可以看到在链表删除的时候利用了prev指针，记录了上一个位点的地址，以方便链表的删除操作，即prev->next=curr->next，移动curr指针后再将现有节点占据的内存释放。这样的写法思想上非常好理解。
void del_list(struct node** head,int val){
for(struct node** curr=head;*curr;){
struct node* entry=*curr;
if(entry->data==val){
*curr=entry->next;
free(entry);
}
else{
curr=&entry->next;
}
}
}
而在本例中，则利用二重指针的特性，基于此prev将不再必要。
在curr移动的过程中，如果需要释放二重指针所指向的当前节点，由于二重指针curr指向的是entry->next这个指针，所以可以直接对二重指针curr解引用获取entry->next的地址，并将其赋值为下一节点的地址，这就是通过指针间接修改值。在此情况下，entry和curr毫无联系，需要移动的也是curr而不是entry，所以可以直接调用free(entry)删除节点。又由于这是单链表，所以也不存在右边与左边连接的问题。
而如果不需要释放当前节点，这时候可以直接修改二重指针的地址，移动二重指针，让它指向entry->next这个指针，即下一节点。
参考：
Linus所述Low-Level Coding问题，信源并不惟一，这里给出一个参考过的文章：https://wordaligned.org/articles/two-star-programming
上述内容的思考是自己的体会，仅作记录。
代码由自己重写。
测试样例中，输入以空格分隔的多个数字，以0结尾作为结束输入标志；
然后再输入一个数字代表需要从链表中删除的值。 lihl 发表于 2024-2-4 21:16
链表算比较经典的C（pp）开发实例了，我还记得在链表里倒腾prev、data、next的痛苦时光... ...
不看建议不回复。
页: [1]