您好、欢迎来到现金彩票网!
当前位置:在线斗牛棋牌游戏 > 尾递归删除 >

LINUS:利用二级指针删除单向链表

发布时间:2019-07-22 04:07 来源:未知 编辑:admin

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

  Linus举了一个单向链表的例子,但给出的代码太短了,一般的人很难搞明白这两个代码后面的含义。正好,有个编程爱好者阅读了这段话,并给出了一个比较完整的代码。他的话我就不翻译了,下面给出代码说明。

  如果我们需要写一个remove_if(link*, rm_cond_func*)的函数,也就是传入一个单向链表,和一个自定义的是否删除的函数,然后返回处理后的链接。

  这个代码不难,基本上所有的教科书都会提供下面的代码示例,而这种写法也是大公司的面试题标准模板:

  这里remove_fn由调用查提供的一个是否删除当前实体结点的函数指针,其会判断删除条件是否成立。这段代码维护了两个节点指针prev和curr,标准的教科书写法——删除当前结点时,需要一个previous的指针,并且还要这里还需要做一个边界条件的判断——curr是否为链表头。于是,要删除一个节点(不是表头),只要将前一个节点的next指向当前节点的next指向的对象,即下一个节点(即:prev-next = curr-next),然后释放当前节点。

  但在Linus看来,这是不懂指针的人的做法。那么,什么是core low-level coding呢?那就是有效地利用二级指针,将其作为管理和操作链表的首要选项。代码如下:

  同上一段代码有何改进呢?我们看到:不需要prev指针了,也不需要再去判断是否为链表头了,但是,curr变成了一个指向指针的指针。这正是这段程序的精妙之处。(注意,我所highlight的那三行代码)

  1)(第12行)如果不删除当前结点 —— curr保存的是当前结点next指针的地址。

  (转载本站文章请注明作者和出处酷 壳 – CoolShell,请勿用于任何商业用途)

  最后的图片,如果补充强调一下蓝色的内存区域可能是节点内next 字段也不错。

  不过当被删除的节点是第一个的时候,就不能这样用了,因为没有前一个节点,只能这样:

  但是 PrePtr->next和head的作用几乎一样啊,都是指向下一个节点,有什么办法统一表示吗?

  当pp保存的是 PrePtr->next 的地址的时候,它就可以代表 PrePtr->next,当pp保存的是head的地址的时候它就可以代表head。

  这样用*pp就可以统一代表“ 前一个节点的next指针 ” ,而且改变*pp所代表的指针也是很容易的(只要改pp所保存的地址就可以了)。

  另外一楼 @Leo 所举的例子是不对的。实际上从“第三次解”那里就没有意义了。如果dummy的值是头指针的地址的话,那么*dummy代表头指针,它的值也就是第一个节点的地址。而**dummy代表的是第一个节点,它的类型不是一个指针。因而*(*(*dummy))就没有意义了。多级(大于三级)的指针在c语言中用处应该是不大的。

  除非有一个返回值是地址的节点类型才有可能满足你所说的,不过这种类型太复杂吧,c看起来不适合做这个。

  换言之,如果一个单向链表,next是第一个字段,我们可以用一个二级指针dummy引用一条链表上的所有节点。

  如果我们需要找到从head开始的第N个节点,那么对dummy进行N次解引用即可,当然现实工程中一般不会用到这么tricky的语法糖,但使用一个变量同时引用相邻三个节点是很有用的;-)。

  linux中的list_head和windows中的LIST_ENTRY都是双向链表的实现,两者的实现基本是等同的,和这里的单链表一样,也使用了一个dummy的头来指示链表的头尾。当dummy的头的prev/next指向dummy自身的时候,链表为空。利用dummy的头,可以避免一些不必要的判断,使代码变得精简。

  Pingback:利用二级指针删除单向链表——笔记 KryptosX 实验室

  @Neuron Teckid他们还可能会因为看不懂你的代码要求你写得和他们一样。

  图画错了,curr是node的二重指针,所以通过两个“箭头”指向以后就应该指向一个node实体,蓝色方块是多余的。

  图画错了,curr是node的二重指针,所以通过两个“箭头”指向以后就应该指向一个node实体,蓝色方块是多余的。

  我觉得理解的关键在于,在C++中,变量名的意义是拷贝一个值。之前的常见做法,cur = head-next,仅仅是把指针head-next的值copy给了指针cur,使得cur可以访问链表的下一个节点;而声明为二级指针的cur,*cur不是head-next的copy值,它“就是”head-next这个变量名的别名,它获得的是head-next这个变量的读写权

  關鍵在於,我們完全可以把head-next想像成為另一個鏈表的head。

  所以你瞧,函數式語言多棒啊,讓你可以理解類型的本質,雖說我還沒真正用過函數式語言……

  个人认为,简洁不能以难懂作为代价。也许对于内核开发人员来说,像Linus那样是容易懂的写法。

  这段代码,乍一看很牛其实仔细一琢磨,唯一的作用是用来炫耀。首先 取地址 运算符 只能作用于lvalue,所以创建的时候 还是需要一个临时变量指向 链表节点。 如果这样 真不如 只用一级指针然后

  这个实际上非常简单,主要是两种删除节点的对比。怎么会被解释得这么复杂了呢?

  这样理解的话就算函数不是返回node *,而是和下面一样使用node **, 返回值为void 也没有

  综上: 这个实际上是两种删除节点方法的比较,和二维指针真心关系不是特别大。

  我觉得理解的关键在于,在C++中,变量名的意义是拷贝一个值。之前的常见做法,cur = head-next,仅仅是把指针head-next的值copy给了指针cur,使得cur可以访问链表的下一个节点;而声明为二级指针的cur,*cur不是head-next的copy值,它“就是”head-next这个变量名的别名,它获得的是head-next这个变量的读写权

  我觉得你这个回答,是这里最精辟的。我用自己的语言描述一遍:因为“链表操作”的对象都是指针,所以用二级指针来操作“指针”这种特殊的变量,就像一般情况下传递一个指针给函数,来操作普通变量一样。可以获得变量的读写权,由于头指针又同时作为函数的参数,所以这里用二级指针,同时获得了改变外部变量(不用返回新的头指针)和内部的权限,省却一个临时内部变量。

  其实,那个所谓的“教科书标准示例代码”,也是可以简化的,不用定义prev指针,也是可以的。但是新的头指针必须返回。没有二级指针,是无法改变函数外“指针”类型的实参的。

  原来 cur 存的是每个节点里next变量的地址, *cur 是当前节点的下一个节点的地址, *cur = (*cur)-next 是把当前节点的next 修改为下一个节点的下一个节点的地址, cur = &(*curr)-next 是让cur存下一个节点的next变量的地址; 这么写简单 但是是不是太绕了

  Pingback:二级指针实现单链表的插入、删除及 linux内核源码双向链表之奇技 – CodingBlog

  文章转载至举了一个单向链表的例子,但给出的代码太短了,一般的人很难搞明白这两个代码后面的含义。正好,有个编程爱好者...博文来自:initHeart的博客

  想写这样一篇站在巨人肩上的文章很久了,很久之前在CoolShell上就看到这篇文章:Linus:利用二级指针删除单向链表,当时第一眼看完十分之震惊,大神就是大神!这才是真正的CoreLow-level...博文来自:weixin_34413802的博客

  错误总结:无头结点链表的创建(二级指针)无头结点链表的创建(二级指针)这是上次关于无头链表的操作的所有操作,这些是通过传链表头指针本身(一级指针)所做的操作(其实忘记写释放链表的操作,这是个大问题,不...博文来自:men_wen的博客

  首先可能大家有以下疑惑:为什么在链表的删除或者插入的操作中要用二级指针?为什么无头节点的单链表尾插必须使用二级指针,而带头节点的可以不用?这也是我曾经疑惑的问题,但是当我看到下面这段话的时候心里几个大...博文来自:阿巴卡的博客

  二维数组、指针数组、二级指针、行指针互转1.一维数组在讲二维数组之前,先回忆一维数组。定义一个一维数组inta[10],其内存结构如图: 图1在中括号[]之前的a表示数组的首地址,a+i则表示第i个i...博文来自:wan974896411的博客

  问题        给出链表头指针,删除单链表中值为给定值的某个结点,若有重复结点则只需删除第一个。思路采用一级指针删除链表节点        采用一级指针删除链表结点需要判断前驱结点、后续结点,代码...博文来自:donghuaan的博客

  对于一个函数,如果未加引用,则是按值传递,实际上只是复制了一个传入参数相同类型相同值的变量进行操作,当函数结束时,传入变量并未改变,如:代码1:voidFunc(intnum){num+=1;}int...博文来自:N1neDing的博客

  Linus曾经在网上吐槽很多程序员不会写真正的底层核心代码,并用简单的单链表删除举例。常规的链表删除除了当前的遍历指针还需要维护一个prev指针,用来连接被删除节点的下一个节点,但实际上利用二级指针就...博文来自:姚光超的专栏

  这么基础的操作,都忘光了....二级指针参数传递之后,一级解引用不知道要解成什么类型,就会报错,所以需要(int*)强转一次转回来。调用方法不是网上说的(*(MatrixA+i))[j],也不是*(*...博文来自:lonelyrains的专栏

  前言  最近用C语言写LeetCode有的题目给的函数把二维数组用二级指针传进来并传入行数和列数引起一些疑惑本来以为C语言学得海星,查了一些资料后,觉得自己还是个弟弟:(按一维数组的思路处理二维数组,...博文来自:kafmws的博客

  链表操作总结(创建,遍历,就地逆置,删除偶数结点…)1、随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。2、遍历单向链表(显示)。3、把单向链表中元素逆置(不允许申请新的结点空间)。4...博文来自:子子谖谖谖的博客

  数组元素是指针类型的数组就称为指针数组。指针数组的每一个元素都是指针变量。定义形式:类型名*数组名[数组长度],如:  int*p[10]  二级指针,就是指向指针的指针。#includeintmai...博文来自:str999_cn的专栏

  使用二级指针返回二维数组的值一直以来都不会将函数的结果以数组的形式返回,今天终于碰巧解决了!函数功能:功能十分简单,实现两个二维数组的减法,并将结果以数组的形式返回。void**SubArray(vo...博文来自:的博客

  拿上面的链表的插入函数举例,它使用了二级指针是因为:如果使用一级指针,当我们向空链表中插入节点时,新节点就是头节点,我们会改动头指针,但函数调用完后,head还是一个空指针。用一级指针和二级指针的区别...博文来自:JayChan

  描述输入一个单向链表和一个节点的值,从单向链表中删除等于该值的节点,删除后如果链表中无节点则返回空指针。链表结点定义如下:struct ListNode{      int       m_nKey;...博文来自:yiqiwangxi的专栏

  题目描述输入一个单向链表和一个节点的值,从单向链表中删除等于该值的节点,删除后如果链表中无节点则返回空指针。详细描述:本题为考察链表的插入和删除知识。链表的值不能重复构造过程,例如1lt;-...博文来自:无情Array

  一、二级指针做输入与输出    做输入,主调函数分配内存,被调函数使用;做输出。被调函数分配内存,把运算的结果,以指针做函数参数甩出来。 #define_CRT_SECURE_NO_WARNINGS#...博文来自:愚公求道

  题目:在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。如输入链表:1-amp;gt;2-amp;gt;3-amp;gt;3...博文来自:sixingmiyi39473的博客

  链表相比于数组的优势有:1.增加和删除元素效率非常高;2.可以不需要预先知道存储元素的数量。相比于数组的劣势有:1.查找元素的效率低;2.由于存储额外节点指针,带来的空间消耗。采用C语言形式实现插入和...博文来自:HHHUANG

  高清音视频文件由H.264视频和AAC音频合成;采用FFmpeg解码库对音视频文件进行格式封装解码;采用硬件分别对音频、视频进行解码;最后,实现音视、视频的同步播放。其整体解决方案如下图:......博文来自:Xminyang的博客

  接口参考严蔚敏老师的数据结构课本这个类bugde了好长时间,在于二级指针的使用(C语言学的不好用指针真的伤)实现环境为linux下面先讲一点关于二级指针的知识点voidchange(char**x){...博文来自:perry0528的博客

  二维数组名不能赋值给二级指针,否则运行中可能会出现错误。博文来自:wu_nan_nan的专栏

  在我们实现初始化、头插、尾插、头删、尾删要先做哪些工作呢?首先我们要vim两个文件Linklist.hLinklist.c。在h文件中写入函数名、结构体等,真正实现的代码在c文件中实现。1.创建节点的...博文来自:晴时有风阴有雨的博客

  由于最近刚写完火车票的管理系统,里面大量的用到了链表的部分,所以在这里总结一下链表的几种基本操作。链表是什么要用链表首先要知道链表是什么。简单的说链表就是一串存储数据的结构。说到这我们一定都会想到数组...博文来自:weixin_41666244的博客

  单向链表是列表中常用的一种,所有节点串成一列,而且指针所指的方向一样。列表中每个数据除了要存储原本的数据,还必须存储下一个数据的存储地址。下面的程序示例演示了如何构建链表节点,向单向链表插入节点、删除...博文来自:样young的博客

  链表的创建查看删除节点就是将某一节点从链中摘除。将待删节点与其前一节点解除联系(中间或尾部)或本阶段删除(头节点),并释放相应空间(free)。删除的第一步是找到要删除的节点,同链表查找,如果找不到或...博文来自:peng_fp的博客

http://missartypants.com/weidiguishanchu/331.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有