当前位置：首页 > 编程日记 > 正文

二维指针操作链表

编程日记 2024-03-11 14:30:01

背景

Linus slashdot: https://meta.slashdot.org/story/12/10/11/0030249

Linus大婶在slashdot上回答一些编程爱好者的提问，其中一个人问他什么样的代码是他所喜好的，大婶表述了自己一些观点之后，举了一个指针的例子，解释了什么才是core low-level coding。

下面是Linus的教学原文及翻译——

“At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the “prev” entry, and then to delete the entry, doing something like。（在这段话的最后，我实际上希望更多的人了解什么是真正的核心底层代码。这并不像无锁文件名查询（注：可能是git源码里的设计）那样庞大、复杂，只是仅仅像诸如使用二级指针那样简单的技术。例如，我见过很多人在删除一个单项链表的时候，维护了一个”prev”表项指针，然后删除当前表项，就像这样）”

if (prev)prev->next = entry->next;elselist_head = entry->next;

and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common.（当我看到这样的代码时，我就会想“这个人不了解指针”。令人难过的是这太常见了。

我尝试用二维指针操作链表，写了如下code。

希望领悟到二维指针的精髓。

#include <stdio.h>
#include <stdlib.h>typedef struct Node {struct Node *next;int data;
} node;void initList(node **head, unsigned int size)
{node **cur = head;for (int i=0; i<size; i++){*cur = (node *)malloc(sizeof(node));(*cur)->data = i;(*cur)->next = NULL;cur = &(*cur)->next;		}
}void deleteList(node **head, int data)
{for (node **cur=head; *cur;){node *entry = *cur;if (entry->data == data){*cur = entry->next;free(entry);entry = NULL;}elsecur = &entry->next;}
}void freeList(node **head)
{for (node **cur=head; *cur;){node *entry = *cur;*cur = entry->next;free(entry);entry = NULL;}
}int main()
{node *head = NULL;unsigned int size = 5;initList(&head, 5);if (NULL == head){printf("head is null, init list failed");return -1;}else{printf("init list suc, addr is: \n");node *cur = head;while(NULL != cur){printf("%X ", cur);cur = cur->next;}		}printf("\n\n");node *cur = head;printf("list data: \n");while(NULL != cur){printf("%d ", cur->data);cur = cur->next;}printf("\n\n");printf("delete node 3 from list\n\n");deleteList(&head, 3);cur = head;printf("list data: \n");while(NULL != cur){printf("%d ", cur->data);cur = cur->next;}printf("\n\n");printf("free list\n\n");freeList(&head);cur = head;printf("list data: \n");	while(NULL != cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");return 0;
}

运行结果如下：

init list suc, addr is:
4B8260 4B8280 4B82A0 4B82C0 4B82E0

list data:
0 1 2 3 4

delete node 3 from list

list data:
0 1 2 4

free list

list data:

Q1: 如果我们用下面的initList_1来代替原来的initList，重新build，运行，你想想会发生什么？

list 能初始化成功吗？

void initList_1(node **head, unsigned int size)
{node **cur = head;for (int i=0; i<size; i++){node *entry = *cur;entry = (node *)malloc(sizeof(node));entry->data = i;entry->next = NULL;cur = &entry->next;		}
}

A：list不能初始化成功，*head 并没有指向分配的内存，依然为NULL, entry 指向的内存并不能返回到函数外部。

Q2: 上面的freeList 函数是否把list中分配的内存在free后设置成了NULL,杜绝野指针？

void freeList(node **head)
{for (node **cur=head; *cur;){node *entry = *cur;*cur = entry->next;free(entry);entry = NULL; /* is this lie useful? avoid wild pointer ?*/}
}

A: No, 内存free后并没有被置为NULL.

其实在循环过程中，*head(也就是*cur) 一直在链表中后移，最后指向了最后一个node的next 指针，也就是为NULL。

所以在这个函数执行完后，list的首节点指向了NULL(最后一个node的next 指针),而其它的node所分配的内存虽然被free了，但是并没有设置为NULL。这样做也没有问题，list暴露给用户的就是head 指针，非head节点并没有提供给用户，没有置为NULL,也就没有什么问题了。

https://www.dkcj.cn/info/2998.html

二维指针操作链表

背景

我尝试用二维指针操作链表，写了如下code。

相关文章：

php多选框怎么传值,tp3.2如何处理多选框传参和判断状态

UIWebView和UIActivityIndicatorView的结合使用

Python对象类型——字符串、列表、元组

leetcode--1:（python）Two Sum

memset初始化内存

php 数字变量,php入门变量之数字_PHP教程

BZOJ 1597: [Usaco2008 Mar]土地购买( dp + 斜率优化 )

雨季来临对车辆涉水说“NO”

C#编写dll进行sql server数据库扩展储存过程

malloc(0)-malloc 0 字节

php常见排序算去,PHP兑现常见排序算法

C#中 int.TryParse 的用法

2022-2028年中国综艺节目市场深度调研及投资前景预测报告

cocos2d-js 自定义事件监听派发

URL编码转义，冒号和/不转，否则导致http链接失效

C面向对象之透明指针的运用

支付宝 php rsa算法,：PHP支付宝接口RSA验证

int与string转换

更改Jenkins升级站点

Android 模仿微信启动动画（转）

navicat for mysql收藏夹

C 变量的作用域

oracle字段重复新增错误,oracle在已有重复数据的列上创建唯一约束

poj_3067 树状数组

2022-2028年中国自主可控行业深度调研及投资前景预测报告(全卷)

linux /etc/fstab文件参数求解释

C运算符优先级笔记

移动应用开发—— 如何搭建开发大型的应用架构？

4104 oracle 数据文件名,Oracle 11g 常遇到ora-01034错误，这是为什么？

Linux(CentOS6.5)中安装maven