Linus曾谈到，他喜欢core low-level coding。今天来用一个简单的例子看一下什么叫core low-level coding。
这个问题是在做一道简单的算法题的时候发现的，自己从来没有看过这样做法，指针真是蕴含着无穷的魅力。
1. 标准化的删除
定义链表结点结构和一个指向判断结点是否满足删除条件的函数的指针。设计和实现一个删除函数删除满足特定条件的结点。
实现函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| typedef struct node{
struct node * next;
...
}node;
typedef bool (* remove_fn)(node const *v);
node * remove_if(node *head, remove_fn rm){
for (node *prev = NULL, *curr = head; curr != NULL;){
node * const next = curr->next;
if (rm(curr)){
if (prev){
prev->next = next;
}
else {
head = next;
}
free(curr);
}
else
curr = next;
}
return head;
}
|
常见问题
- 需要一个额外的指针，也是大多数教科书中提到的，previous；
- 需要做边界条件检查：看curr是否为链表头。
2. 二级指针
实现函数
1
2
3
4
5
6
7
8
9
10
11
| void remove_if(node **head, remove_fn rm){
for (node ** curr = head; *curr;){
node * entry = *curr;
if (rm(entry)){
*curr = entry->next;
free(entry);
}
else
curr = &(entry->next);
}
}
|
常见问题
- 不再需要previous指针，这里使用的链表指针的指针，curr代表当前结点的next指针的地址，*curr代表了当前结点的next指针，即指向下一结点的指针。
- 比较抽象，画图可以更好的理解，一般，curr指向当前结点，代表其地址，而现在，curr指向当前结点中的next指针域，代表其地址。
- 这里的关键是：在链表中的链接本身就是指针，所以可以使用指针的指针来作为改变链表的优先选择。
3. 简单的应用
删除链表中倒数第n个结点，并返回该链表。
实现函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| LinkNode* rm(LinkNode * head, int n){
LinkNode** t1 = &head, *t2 = head;
for (int i = 1; i < n; i++){
t2 = t2->next;
}
while (t2->next != NULL){
t1 = &((*t1)->next);
t2 = t2->next;
}
*t1 = (*t1)->next;
return head;
}
|