顺序表的查找

'各位同学大家好', '在这个小节中', '我们会学习顺序表的查找操作怎么实现', '那分为两种查找', '一种是按位查找', '一种是按值查找',

 '那首先来看按位查找怎么实现'

'对一个线性表进行按位查找', '就是要从这个线性表l当中', '取得第二个元素', '那如果这个线性表示用顺序表的方式实现', '并且是用静态分配这样的方式实现的话', '那么所有的数据元素', '就是存放在data这个数组当中',

'那在这种情况下', '想要获得第二个数据元素', '其实非常简单', '唯一需要注意的是第二个元素啊', '它对应的数组下标应该是i减一', '因为这个位序是从一开始的', '而数组下标是从零开始的', '那这个元素的返回值', '和你的数据元素的类型是相同的', '

当然如果想让你的代码', '健壮性更强一些的话', '在这个地方是不是还可以判断一下', '这个a的值是否合法好', '那这个也很简单', '就不再展开好', '接下来看一下'

, '如果我们采用动态分配方式', '来实现顺序表的话

', '那么data这个变量它其实是一个指针', '这个指针指向了顺序表当中的', '第一个数据元素', '那存储这个顺序表所需要的内存空间', '是用mlock函数申请的一整片的连续空间', '

虽然data这个变量它是一个指针', '但是同样可以用这种数组下标的方式', '访问相应的元素', '这有可能是跨考的同学不知道的点好', '那我们来分析一下', '计算机在背后它做了一些什么',

'你的这个data变量它其实是一个指针', '指针指向了malloc函数', '给它分配的一整片连续内存空间', '的起始地址也就指向了这个地址'

, '那我们假设现在这个指针', '它所指向的地址是2000', '然后在这个图当中', '我们假设这样的一小格', '代表一个字节的大小', '也就是1b的大小', '那如果说你的一个数据元素', '也就是你的type需要占六个字节的话', '那么你用l.data 0这样的方式取得的值', '其实就是从data这个指针所指向的这个地址', '再往后六个字节的内容', '

你在这儿给他return了一个data 0', '其实就是给他返回了这六个字节的内容', '而这六个字节当中对应的内容', '刚好就是你的第一个数据元素好'

, '那同理', '如果你的代码里写的是data一的话', '那data一所对应的数据', '就应该是从2006这个地址开始', '往后的六个字节', '也就是你的第二个数据元素',

那在这个地方我们所定义的data指针', '它所指向的数据类型', '就是aletype这种类型', '所以如果你按这种数组下标的方式', '来写代码的话',

'那其实计算机在背后会根据你的这个指针', '所指向的数据类型', '它所占用的空间大小来给你计算', '每一个数组下标', '它应该对应的是哪几个字节的数据好', '

那如果说我们定义另外的一个指针', '这个指针它所指向的地址也是', '这也是2000',

'不过我们把这个指针', '它的类型规定为指向int型', '而一个int型的变量是占四个字节', '那么你用类似的这种呃指针', '加上数组下标的方式来取得数据的话', 'p0 它所对应的数据就应该是', '从2000这个位置开始', '往后的四个字节', '这四个字节的内容是p0

', '再往后的四个字节是p1 ', '再往后的四个字节是p2 ', '

'用某一个类型的指针', '加上数组下标的这种方式来访问数据的话', '那么系统在背后为你取数据的时候', '每一次取几个字节', '其实和你的这个指针所指向的类型有关',

'

 '如果你用malloc函数', '申请一片连续的内存空间', '那么mlock函数返回的这个指针', '你需要把它强制转换为', '和你的这个数据类型相对应的', '同类型的指针', '因为虽然指针指向的都是同一个地址', '但是如果你的这个指针所指向的数据类型', '你给它定义错了', '那么在访问你的数据元素的时候', '也会出现问题

时间复杂度

', '好的', '那么既然顺序表按位查找这个操作', '他只需要这样的一个return语句', '都没有任何的循环', '也没有递归调用', '所以按位查找这样的操作', '它时间复杂度就应该是o1 ', '

那这也是我们之前提到过的顺序表', '随机存取的特性', '能够实现随机存取的基础', '就在于顺序表当中', '所有的数据元素', '在内存里边都是连续存放的', '并且这些数据元素的数据类型相同', '也就是说', '每一个数据元素所占的内存空间', '是一样大的', '所以我们只需要知道一个', '顺序表的起始地址', '然后再知道每一个数据元素的大小', '就可以立即找到第二个元素', '它存放的位置好的', '那这是按位查找',

按值查找

'接下来来看按值查找', '按值查找操作', '就是要找到这个线性表l当中', '有没有哪个数据元素', '和我们传入的这个参数e是相等的', '如果能找到这样的数据元素的话', '那么就要返回这个数据元素的存放位置好',

, '我们在这儿传入一个参数e', '然后这个地方执行一个for循环', '从这个顺序表最开始的那个元素开始', '依次往后检索', '依次判断这个顺序表当中的各个数据元素', '和我们传入的这个数据元素e是否相等', '如果相等的话', '那么返回这个数据元素的位序', '由于这个地方我们返回的是位序变量', 'i指的是数组下标', '所以我们在返回的时候', '需要用数组下标加一好',

'那来看一个实际的例子啊', '我们定义了这样的一个顺序表', '这个顺序表当中', '数据元素的数据类型是int类型', '并且这个顺序表已经初始化', '而且插入了六个数据元素', '也就插入了六个int型的变量', '那由于这个顺序表存放的是int型的变量', '

所以我们要对比啊', '两个int型的变量', '只需要用这样的一个运算符', '来进行比较就可以了', '除了int型变量之外', '像char double float等等这些基本数据类型', '都可以直接用判断相等的这个运算符', '来进行比较好',

'那现在假设有人调用了你这个函数', '他想找的是在这个线性表l当中', '有没有等于九的数据元素',

'那首先会执行这个for循环', '刚开始i是等于零的', '并且length的值等于六', '那第一个数据元素它的值和九是不相等的', '也就是这个if条件不满足', '所以会进行i加加的操作', 'i的值由零变为一',

'然后进行第二轮的循环', '第二轮循环扫描的就是这个数据元素', '和九依然不相等', '因此i的值会变为二', '然后进行第三轮的循环', '第三轮循环就找到了', '和这个参数相等的数据元素', '因此会返回这个数据元素的位序', '也就是三好的',

'那接下来要思考的问题是', '如果说我们的这个顺序表当中', '它所存放的数据元素类型', '是一个更复杂的结构类型的话', '那么两个结构类型的比较', '是否也可以用这种等于等于这个运算符呢', '答案是不能'

, '我们在这儿定义了一个叫做customer的', '结构类型', '然后写了

一个简单的函数', '声明了a和b这样的两个变量', '这两个变量都是customer这种类型', '并且我们故意把这两个customer', '里边的字段值都设为一', '然后在这儿写一个if语句', '我们想尝试用等于等于这样的运算符', '判断', 'a和b这两个结构类型的数据是否相等', '但是会发现这个ide提示我们说', '你的这个运算符', '它是不可以用于比较', '两个customer类型的变量的', '所以如果用这样的运算符来比较', '两个结构类型的变量的话', '那别说是让这段代码运行了', '你的这段代码连编译都编译不了'

, '所以如果要对比两个结构体的话', '那么你必须自己写代码来分别的对比', '这个结构体里边的各个分量是否相等', '如果这些分量都相等的话', '那么就可以认为这个结构体是相等的', '当然你也可以实现一个基本操作用', '来判断你所定义的两个结构体是否相等好', '总之在c语言当中', '你是不可以直接用等于等于这个运算符', '来判断两个结构类型是否相等的', '而如果使用c加加的话', '

、, '如果说这个学校', '他说他考的科目就叫数据结构', '那你在判断两个数据元素是否相等的时候', '可以直接使用等于等于这个运算符', '不管你的这个数据元素', '到底是基本数据类型还是结构类型', '因为数据结构这门课', '它更多的是考察你对数据结构', '还有数据结构相关的算法的一个理解', '并不会过分严格的要求', '你的这个代码是否严格', '遵照某一种编程语言的规则', '但是如果你报考的那个学校', '他考的科目里边', '他告诉你是考c语言程序设计', '那么这个学校在改卷的时候', '也许他就会比较在意', '你的这个c语言语法是否够严格', '当然了', '这个具体问题具体分析', '大家最好还是看一下相关的历年真题', '它题目里边是否要求你的c语言语法啊', '要足够的标准', '那这个地方给大家一个小小的提醒好', '那接下来分析一下'

, '按照查找这个操作的时间复杂度', '要算时间复杂度的话', '我们需要关注的是最深层循环的', '这个语句的执行次数', '也就是循环了几次', '这个循环次数和问题规模n之间', '的关系是什么', '那我们这儿的问题规模n指的是线性表的', '表长好', '那时间复杂度分为

最好', '最坏和平均三种情况', '最好的情况肯定是', '如果你要找到这个值', '刚好和表头元素的值相同的话', '那这个循环是不是就只需要执行一次', '所以最好时间复杂度应该是o一常数阶的

', '那由于我们检索这些数据元素是从头到尾', '一个一个往后检索的', '所以如果你要查找的这个值', '它是最后一个数据元素的话', '那么循环的次数就需要循环n次', '需要把n个数据元素全部扫描一遍', '才可以找到目标', '所以最坏时间复杂度应该是o n',

'而平均时间复杂度我们可以先假设啊', '你要找的这个目标元素', '出现在任何一个位置的概率都相同', '那总共有n个元素', '也就是说', '出现在任何一个位置的概率都是n分之一', '而如果这个目标元素在第一位的话', '那么循环只需要循环一次', '在第二位的话循环两次', '以此类推', '如果在第n位', '那就循环n次', '因此平均来看', '这个平均所需要的循环次数', '就应该是这个循环的次数乘以', '这种情况发生的概率', '然后相乘相加', '最终得到的结果应该是二分之n加一',

'因此平均时间复杂度应该是大o n好的

小结

', '那这个小节的内容很简单', '我们学习了按位查找和按值查找', '

那由于顺序表当中的各个元素', '都是连续存放的', '所以如果想要找到顺序表第i个元素的话', '只需要o一的时间就可以立即找到', '也就是说顺序表就随机存取的特性',

'而如果是按值查找的话', '那么我们需要从第一个元素开始', '依次往后检索', '当然如果这个顺序表当中的数据元素', '它是按照某一种顺序', '比如说从大到小或者从小到大的排列的', '那对于数据元素有序的这种顺序表的查找', '其实会有很多更高效的算法', '那这个我们会在之后查找那个章节', '来学习其他的更高效的查找算法', '

但是如果顺序表当中的数据元素', '它们本身存放就是没有任何规律的', '那就只能从第一个元素依次开始往后寻找', '平均来看', '找到目标元素', '时间复杂度应该是o n', '那再次强调', '跨考的同学', '需要注意位序和数组下标的关系', '另外还需要注意怎么判断两个结构体', '也就是struct数据类型', '它们是否相等', '

单链表

'那顺序表就是用顺序存储这样的存储结构', '实现的线性表', '

而这个小节之后的内容', '我们会学习', '怎么用链式存储的这种存储结构', '来实现线性表', '

那用链式存储实现的线性表', '我们统称为链表',

'而链表又可以具体分为单链表', '双链表', '循环链表和静态链表', '

这个小节我们先学习单链表怎么定义', '

也就是说怎么用代码实现一个单链表', '在之后还会用几个小节来介绍', '基于单链表这种存储结构', '怎么实现', '线性表所要求实现的那些基本操作好', '

那这个小节中', '我们首先会介绍什么是单链表', '

然后会用代码定义一个单链表', '

单链表可以有两种实现方式', '分别是带头节点的和不带头节点的好', '

那先来看第一个问题''什么是单链表'

', '就知道单链表是什么意思了', '单链表当中的这样一个节点', '它需要存放数据元素', '同时还需要包含一个', '指向下一个节点的指针', '由于每一个节点它只包含这样的一个指针', '所以它才叫单链表',

'那经过之前的学习', '我们知道顺序表它的优点是可以而单链表就可以很好地解决这个问题', '单链表

随机存取的不足

随机存取', '并且存储密度高', '但是它也存在缺点', '由于各个数据元素要求', '在物理上是连续存放的', '所以如果用顺序表的方式来实现', '这种线性结构的话', '那就会要求使用大片的连续空间', '如果要拓展这个顺序表的容量的话', '那是很不方便的', '中

的各个节点'

不足的改进

, '在物理上可以是离散存放的', '所以当我们要拓展单链表的长度的时候', '其实只需要在呃', '内存当中随便抠一小块区域', '把它作为存放新节点的区域就可以了', '因此采用这种链式存储的方式的话', '那改变容量会很方便', '不过呢如果采用这种方式的话', '那么我们要找到某一个位序的节点', '那么我们只能从第一个节点开始', '利用这个指针的信息依次往后寻找', '直到找到我们想要的那个节点', '也就是说', '单链表这种实现方式不支持随机存取好的', '

单链表定义

那接下来看一下', '怎么用代码定义一个单链表', '不难看出', '我们的单链表', '是由这样一个一个的节点组成的', '而一个节点当中', '它需要有一片空间是用于存放数据元素的', '还需要有另一片空间是存放', '指向下一个节点的指针', '所以我们可以定义一个', 'struct类型的结构体', '用于表示一个节点', '那这个节点当中有一个叫data的变量', '用于存放这个数据元素', '我们把它称之为数据域', '

另外还需要定义一个', '指向下一个节点的指针', '这个指针变量的名字叫next', '我们把这个变量称为指针域好了', '那有了这个结构体的定义之后',

'如果我们想要往这个单链表当中', '增加一个新的节点的话', '那么我们是不是就可以用malloc函数', '来申请一片存储这个节点的空间', '并且用指针p来接收my log函数的返回值', '让它指向这个节点的起始地址之后',

'是不是就可以设计一些代码逻辑', '把p节点插入到这个单链表当中好', '那按照我们这儿的这种写法以后', '当我们想要定义一个新的节点的时候', '或者想要定义一个指向节点的指针的时候', '是不是都得写这种struct node', '也就是说每次都得带上struct这个关键字', '那这么写有点麻烦', '

所以我们的教材里面使用了type define', '这个c语言的关键字', '用这个关键字', '可以把这个数据类型给重命名', '把他的名字稍微缩短一些', '把它简化', '其实我们在之前的小节中也用过', 'type define这个关键词', '只不过我们一直没有强调而已', '那结合这个小节的内容', '希望能够让跨考的同学们啊', '真正的理解这个关键词', '它的用法', '其实用法很简单', '

就是在你的代码里先写一个这个关键字', '然后后面跟一个你想要重命名的数据类型', '接下来空一格', '然后写入你想要给它取得另一个别名', '比如说你可以把int这种数据类型', '给它取一个别的名字', '叫做整数', '汉语拼音是不是超亲切', '当然你也可以用下面的这种方式', '把指向int型变量的指针', '把它重新命名为整数指针好', '那加了这两行代码之后', '以前你定义一个int型的变量', '还有指向int型的指针', '是不是这样的方式定义的', '而现在你可以用这样的方式来定义', '同样的道理', '

我们是不是可以把struct node这种数据类型', '给它取一个别名', '就叫l node', '把他名字缩短一点', '那这样的话之后你在写代码的时候', '就不需要再带struct', '就直接l node就可以了', '这样的话你写代码是不是更简洁一些好', '

那我们在这儿是先定义了一个struct air node', '然后再单独写了这样的一个语句', '来把它重命名', '但是我们的教材里面', '用了一种更简洁的方式', '课本中的这段代码', '其实等价于你自己', '先定义一个叫做struct or node', '的一个数据类型', '然后你把struck air node把它重命名为air node', '并且用link list来表示', '这是一个指向struct node的指针', '

那当我们要表示一个单链表的时候', '是不是我们只需要声明一个所谓的头指针', 'l', '这个头指针指向了单链表的

第一个节点', '而由于各个节点是用这个next指针', '把它们一个一个连起来的', '所以是不是我们只要找到了第一个节点', '那就相当于我们其实已经找到了', '整个单链表好', '那既然l这个指针它是指向了某一个节点', '那我们是不是定义l的时候', '可以用这样的方式来定义l node心', '而根据这个地方的重命名', '其实我们的air note新l', '是不是又可以等价于link list l', '那这两种声明方式', '

从效果上来看其实是一模一样的', '只不过采用后面这种方式来声明', '投指针的话', '那代码可读性会更强一点', '看一个例子大家就明白了',

'我们在之后会学习一个基本操作', '就get', '就是说把l这个链表当中的第', '二个节点给取出来', '并且return返回', '那注意他在这段代码里面', '既使用了l no的心', '也使用了link list', '虽然这两种表示方式本质上它们是等价的', '但是在这个函数当中', '它最终要return', '要返回的是第二个节点', '所以它的这个返回值的类型', '它把它定义为了l no的星'

, '其实他是想强调说我返回的这是一个节点', '而这个参数links他想强调的其实是', '这是一个单链表', '我要从这个单链表当中', '找到它的第二个节点', '

所以虽然这其实可以用l no的星', '新l这样的方式来定义l这个参数', '但是由于这个地方他想强调的', '并不是说l它是一个节点', '而是要把它看成一个单链表', '因此他才使用了这样的命名方式', '这个大家可以好好体会一下',

'因为我们的课本当中很多示例代码', '这两种表示方式都会出现', '如果这个地方没理解的话', '那大家在看代码的时候可能会觉得很懵', '为什么有的地方用左边这种方式', '而有的地方用右边这种方式', '其实主要就是在这个代码当中', '他想强调的点是不一样的', '比如大家可以看一下自己的课本', '这个头插法建立单链表', '它里面就使用到link list', '也使用到了air note新', '所以这个小细节还是值得注意的', '在我们之后学习的一些数据结构当中', '比如说像数这种数据结构', '它也会采用类似这样的重命名的方', '式和方法', '所以这个地方希望大家好好体会好', '

怎么初始化一个单链表',

不带头结点

'我们先看不带头结点的单链表', '首先声明一个指向单链表的指针l', '那其实本质上', '这个指针它是指向某一个节点的对吧', '只不过这个地方我们想强调的是', '它指向的是一个单链表', '所以我们用link list这个别名来定义好', '那执行这一句之后', '内存当中会开辟一小片空间', '用于存放这个头指针l好', '那再往后执行我们这儿的初始化函数', '这

个初始化函数很简单', '就是把a的值设为纳', '用这样的方式表示当前它是一个空表', '做这个操作是为了防止这一小片内存当中', '以前有遗留的脏数据', '另外当我们传入这个指针变量的时候', '我们是传入了它的引用', '因为如果没有这个引用符号的话', '那么在这个函数里边修改的所谓的l', '其实是这个头指针l的一个复制品', '

好那对于这种不带头结点的单链表', '判断它是否为空的依据', '就是看它的这个头指针l', '此时是不是等于n', '如果等于nn的话', '说明此时是空的', '当然这段代码还可以写的更简洁一些', '直接return l等于now', '因为这个条件判断它的运算结果', '本身就是true或者false', '所以你直接把它return就可以了', '好那这是不带头结点的情况',

带头节点的情况',

'前面的步骤一样', '先声明一个指针l指向一个单链表', '在它的初始化函数当中', '会用malloc申请一片空间', '可以存得下这样的一个节点', '并且把malloc返回的地址赋给l', '也就是说头指针l是指向了这个节点', '接下来需要把l这个指针指向的节点当中', 'next这个指针域把它设为none', '也就是这个样子', '那这个头节点是不存储数据的', '

我们加这个头节点', '只是为了之后再实现某一些', '基本操作的时候会更方便一些好', '那对于这种带头结点的单链表', '要判断它是否为空的话', '那我们要判断的就是这个头节点的', 'next指针域它是否等于n', '如果它等于none的话', '那它就是空的好', '

那单链表的这两种实现方式有什么区别呢', '简单来说就是如果不带头节点的话', '写代码会更麻烦一些', '如果带头节点的话', '那写代码会更方便一些', '所

小结

以大多数情况下', '我们都会用带头节点的这种方式', '来实现我们的代码', '而为什么这样我们会用下一小节', '用具体的代码让大家亲自感受一下', '在这个小节中', '我们只需要知道', '如果不带头节点的话', '那么头指针它所指向的下一个节点', '这个节点就是实际用于存放数据的节点', '

而如果带头节点的话', '那么头指针它所指向的这个节点', '把它称为头节点', '这个头节点是不存放实际的数据元素的', '只有这个头节点之后的下一个节点', '才会用于存放数据',

'好的', '那这个小节中', '我们学习了怎么定义一个单链表', '单链表其实就是用链式存储的方式', '实现了线性结构', '各个数据元素的先后关系', '是用节点里边的指针域来表示的', '然后需要注意单链表的实现方式', '分为带头节点和不带头节点', '那两种实现方式', '他们呃对于空表的判断条件是不一样的', '另外对于c语言基础不太好', '还有跨考的同学', '希望大家通过这个小节', '能够呃理解type define这个关键词', '它到底是什么意思', '然后之后看代码的时候', '要注意什么地方应该用link list', '什么地方应该用air note心这样的方式', '虽然他们俩是等价的', '希望大家在刚开始学习这部分内容的时候', '把这些细节给理解透彻了', '这样之后的理解吸收速度才会越来越快', '好了', '那以上就是这个小节的全部内容']

单链表的插入与删除

一个单链表它带头节点或者不带头节点的话    那怎么实现按位序插入这个功能       
那除了按位序插入之外我们还需要掌握如果给定一个节点那么怎么在这个节点之后和之前插入一个新的节点删除操作也是类似的给你一个位序你要知道怎么删除这些节点或者直接给你这个节点的指针

你也要知道怎么把它删除
 

下面探讨第一个问题
如果这个单链表它是带头节点的话
那么怎么实现按位序插入这个操作
 

我们要在第二个位置插入一个指定的元素e那这样的话我们是不是需要找到第二减一个节点

因为我们肯定需要把第二减一个节点的next指针给修改
比如说如果i等于二

后用malloc申请一个新的节点
往这个节点里存入数据元素e
接下来对指针进行修改
这样的话这个新的节点是不是就变成了第二个节点诶

那如果我们想要在第一个位置
 

想在这个地方插入一个新的节点的话
怎么办呢
那这个地方大家就能够体会到带头节点的这种单链表的好处
我们可以把这个头节点看成是第零个节点
所以当i等于一的时候

来看一下具体的代码实现这个函数当中传入了一个呃单链表
 

插入节点

然后这个单链表是带头节点的
 

如果i等于一
也就是要在表头的位置插入一个新元素的话
首先这个地方有一个判断

如果i小于一的话
那说明这个i的值不合法
因为i表示的是位序嘛

所以如果传入的这个参数本身不合法的话
直接return false

那由于此时我们的i等于一因此这会声明一个指针p然后这个指针p它是指向了啊和l相同的位置
也就是指向了这个头节点,然后这我们定义了一个变量

jj表示的是当前p它指向的是第几个节点

 

那之前说了头节点
我们可以把它看成是第零个节点
所以此时j的值应该是零

其实单链表当中实际存放的是后面这些节点对吧
而这些节点的编号它是从一开始的
所以我们不允许i值小于一好

接下来就会
开始执行这个while循环
此时p不等于那只是满足的
但是j小于i减一这个条件不满足
因此这个循环不会执行
它会直接跳到下面好

申请一个新的节点空间
然后把参数e存到新节点里面
接下来这一句它会让s指向的这个节点的next这个指针
让它等于p节点的next指针指向的这个位置
也就是指向这最后这一句它会让p节点点的next指针指向这个新的节点
s也就是这样子好
那这样的话
我们是不是就实现了在第一个位置插入数据元素e这个事情
那由于i等于一这个while循环直接被跳过了
所以这种情况下只需要o (1)这样的时间复杂度就可以执行完成

不能调换

果先执行黄色箭头这一句
在执行绿色箭头这一句
也就是先让p节点的next指向s这个节点

后再执行绿色这一句
也就是让s节点的next指针和p节点的next指针指向同一个位置

那这样的话这个指针就会指向它自己

 

其他情况，如i=3=4

如果i等于三的话那此时i减一就应该是二 那前面的这些操作会导致j的值等于零

然后p指向头节点

此时p不等于null,因为是p指向了头节点为0
那同时g也小于二，

所以会执行这个循环里边的代码

p等于p的next
也就是让它指向下一个节点
所以g的值就变成了一好
那由于此时g依然是小于二的
所以第二轮循环的条件也是满足的
因此还会在执行这个循环里面的代码
p会指向再下一个节点
同时g的值会再加一
也就是变成二
 

由于这个条件此时已经不满足了
所以这个循环结束会执行后续的语句
那再往后的话是不是和刚才一样
就是申请一个节点
然后把这个指针给一次修改
这样的话我们就在第三个位置插入了数据元素e好
 

i等于5时

如果a的值等于五的话那么，首先p同样是会先指向这个头节点然后i减一的值就应该是四
g的值刚开始也是零第一次执行这个循环p会往移一位，然后j的值变为一第二次循环p又会指向再下一个节点然后j的值变为二第三次是这样第四次是这样好那当g等于四的时候
这个条件不满足了对吧然后就可以跳出循环执行之后的语句对了。

逻辑再次强调这个g的值表示的是当前p指向的是第几个节点

而我们执行这个循环的本质原因
最终的目的是想要找到第i减一个节点
因为我们要插入的是第二个节点
所以只要我们找到了第二减一个节点
然后我们就可以用后续的这些代码
把新节点连到第二减一个节点之后就可以了
所以大家在看代码的时候
除了能够看懂每一句它是什么意思之外
也应该有一个全局的宏观的思维
比如你要知道这整篇代码其实他就是要找到第i减一个节点
然后后续的这些代码就是要在第二减一个节点之后
再插入一个新的节点
这样的话你的这个算法逻辑是不是就很清晰了
好继续往后分析

到表尾的情况

儿的my luck会申请一个新的节点
然后把数据元素填到里边
接下来会让s的next指向p的next
而由于p节点以前是指向当的
所以经过这一步运算
s节点也会指向
那最后再让p的next指向新的这个节点
那这样的话我们就在第五个位置
也就是表尾的位置加入了一个新的节点
那由于此次要找的这个节点是最后一个节点
所以这个while循环的循环次数是最多的
因此把新节点插到表尾
这种操作就是最坏的情况
这种情况下它的时间复杂度就应该是o n这儿的问题

到第六个节点情况

此时这个表它的实际长度其实 只有四对吧
所以在这种情况下
如果要插入新节点的话
那最多是插入第五个节点
不可能直接插入第六个节点

处理流程

先还是一样的p是指向头节点然后j的值刚开始是零然后i减一的值是五经过第一次循环
p会往下移一位然后j的值变成一第二次循环p再往后移一位j的值变为二第三轮循环j的值变为三
第四轮循环j的值变为四好此时p不等于那这个条件是满足的同时四也小于五
这个条件也是满足的
所以还会进行第五轮循环
第五轮循环p指针会指向当前节点的next
也就是指向这个位置，是null
 

这个条件就已经不满足了对吧

while循环结束就可以执行这个if语句
那p等于none
是不是说明d i减一个节点是不存在的
现在连第二减一个节点我都找不到
那我怎么可能插入第二个节点呢
所以就直接return一个false
那么最终会因为这个条件不满足而跳出循环好
那这就是带头结点的单链表

时间复杂度

如果要按位序插入的话
那平均时间复杂度应该是o n这个数量级。1+2+3+。。。n/n

,等差数列相加除以n

不带节点

如果说这个单链表它不带头节点的话
这个操作的实现有没有什么区别

基本思路

这个操作的实现有没有什么区别
其实基本思路是一样的
你可以先找到第二减一个节点
然后把新节点放到这第二减一个节点之后就可以了
只不过由于不带头节点
所以不存在所谓的第零个节点

那具体的代码实现是这样子

首先也是会my lock先申请一个新的节点，接下来把e写到里边

需要修改头指针l让l指向这个新的节点

然后return to表示插入成功
所以可以看到
如果这个单链表它是不带头结点的单链表的话

如果这个单链表它是不带头结点的单链表的话
那么当我们插入
或者当我们删除第一个节点
第一个元素的时候
我们肯定需要更改这个头指针的指向
但是如果带头节点的话
那头指针肯定永远都是指向那个头节点的
所以由于不带头节点的情况下
对第一个节点的操作需要专门写一段逻辑来处理
所以到这大家应该就能够体会到
为什么说不带头结点的单链表
它的那个代码写起来一般会更麻烦一些

如果i大于1的情况

i大于一的话
那其实后续的这些处理是不是和带头节点的那种情况是一样的
唯一需要注意的是
这儿我们把这个j的值把它设置为一表示p指针
刚开始指向的这个节点是第一个节点
那后续的代码逻辑都是一样的
就不再分析
那推荐大家自己写代码的时候使用带头节点的这种方式
我们在之后的讲解当中
除非特别声明
不然我们默认使用带头节点的这种方式来实现代码
当然考试当中两种情况都有可能考察
那大家在做题的时候就一定需要注意审题
别看错了
条件好
 

指定节点的实现后插操作
 

这个节点之后插入一个数据元素e
那由于单链表的这个链接指针只能往后寻找
所以如果给定一个节点p的话
那其实p之后的那些节点我们都是可知的

我们都可以用循环的方式把它们都给找出来
但是p节点之前的那些节点我们是不是就没办法知道了
好那我们要实现的是在p节点之后插入数据元素e

malloc申请一片空间，然后这儿我们加了一个条件判断
如果mo函数执行的结果
它返回的值是一个nn的话
那么说明此次内存分配失败
这种情况其实是有可能出现的
比如说内存已经满了之类的
这个小细节我们之前没有说过

数据元素e填到这个新节点当中，然后就像之前那样修改各个指针，这样的话就完成了
把数据元素e插入到p节点之后
这个事情显然这段代码并没有循环什么的
它的时间复杂度就是o一好它的时间复杂度就是o一好
那之前我们在第二个位置插入数据元素e这个基本操作它是不是做的
就是先找到第二减一个节点
然后就是在这个节点之后插入数据元素e啊
所以在实现后插操作之后

前插操作

是给定一个节点p
你要在这个节点p之前插入一个新的数据元素e
诶
是不是出问题了
我们的这个单链表它只能往后找
不能往前找
所以对于给定的节点p它之前有哪些节点
我们是看不到的
跟大家看视频的时候
有些地方打上了马赛克
你想看却又看不到好
那怎么办呢
那我们其实可以传入一个头指针
如果给了头指针的话
那整个链表的所有信息我们就都可以知道了
那这样的话我们要在节点p之前插入一个新的元素
那我们是不是可以依次遍历各个节点
然后找到这个节点p的前驱节点
然后在这个前驱节点之后插入数据元素e
这样就可以了对吧
显然如果用这种方式实现的话
那时间复杂度应该是o n这个数量级

可能他真的就是看不到
也就是说如果他不给你传这个头指针的话
那刚才的这个思路是不是就没办法实现了

另一种

 p的前面插入一个数据元素e
首先申请一个新的节点
然后把这个节点作为p节点的后继节点

我的节点不能跑路
 

是我节点里面的数据可以跑路对吧
这句代码会把p节点当中以前存放的这个数据元素x给复制过来
然后再下一句会把这次要新插入的数据元素e
把它放到p这个节点里边
诶你看虽然我们没办法找到p节点的前驱节点
但是用这样的方式是不是逻辑上也可以实现同样的效果啊
并且这种实现方式它的时间复杂度是o1 

而前面那种思路就是要找它前驱节点的那种思路
时间复杂度是o n
因为你必须循环遍历各个节点
所以这个偷天换日的操作还是挺骚的
那我们这儿实现了这个功能

那王道书里给的代码是这样的
他是直接给传了这个节点s也就是新的要插入的这个节点
处理的方法是一样的
找不到p的前驱节点
那么就先把s这个节点先连到p之后
然后声明一个temp变量
先把p节点的内容保存下来
接下来把s节点的内容复制到p里边
也就是这里边就变成了e
最后再把tempt的值复制到s里边
也就是x复制到了这个地方
那这样的话就实现了节点的前叉操作好
那以上就是和插入相关的所有的操作实现
 

怎么删除一个节点
如果此次要删除第二个位置的元素的话
 

怎么删除一个节点
如果此次要删除第二个位置的元素的话
那我们是不是也需要找到它的前驱节点
因为我们需要更改它前驱节点的next指针
那对于删除操作的实现
我们只探讨带头节点的这种情况
 

同样的头节点我们把它看作第零个节点
所以如果我们要删除的是第一个节点的话
那么按照刚才我们提出的这种思路
我们要找到第i减一个节点
也就是第零个节点
然后把第零个节点的next指针把它指向
再往后的一个节点
然后我们还需要用free函数把第二个节点给释放掉
好那接下来我们来看一下具体的代码实现来分析一下

如果i是等于4的话

如果i等于四的话

么我们首先需要根据之前的这些逻辑找到第三个节点
也就是此次要删除的这个节点的前驱节点
那这些逻辑是不是和插入操作其实是一样的
所以我们就不再慢慢分析
总之最后p会指向第三个节点好
接下来会定义一个指针
q q指针指向了p节点的next
也就是指向了第四个节点

接下来会把q节点的这个数据元素复制到变量e里边
注意这个变量e需要把此次删除的这个节点的值
给带回到这个函数的调用者
那所以e这个参数是引用类型的好
再往后p的next要指向q的next
也就是指向n然后最后调用free函数把q节点给释放掉
那这样的话我们就删除了第四个节点
那由于需要依次循环的来找到第i减一个节点
所以这个算法的最坏时间复杂度和平均时间复杂度
应该是o n这个量级

而如果此次要删除的是第一个节点的话
那么是不需要进行这个循环的
所以最好的情况时间复杂度应该是o一这个数量级好
 

如果要删除指点节点

我们没办法找到它的前驱节点
除非像刚才一样
要么就是传入一个头指针
然后从链表头依次往后寻找p的前驱节点
第二种方法呢就类似于刚才前插操作的实现
我们此次要删除的是节点p
首先声明一个指针q指向p的后继节点
然后我们把p的后继节点的这个数据
这个数据元素把它复制到p节点的数据域里边
也就是这个样子
然后再让p节点的next指针指向q节点之后的那个位置
当然q节点之后有可能是一个实际的节点
也有可能是none
但是无所谓好了
最后还需要把这个q节点释放掉
把这内存归还给系统
那这种实现方式
它的时间复杂度也是一
有没有感觉自己还挺聪明的好

我们在极限的节点

那接下来问题来了
我们来考虑一种极限情况
如果此次要删除的这个p节点，它刚好就是这个单链表的最后一个节点的话
 

如果此次要删除的这个p节点
它刚好就是这个单链表的最后一个节点的话
那看一下这个代码
首先q指针是指向了p的
next也就指向了
那那再往后执行到这一句的时候
是不是就会出错了

此时q节点它并没有指向某一个具体的节点
所以想在q节点里边取得他的du是不是就会出现空指针的错误

以这段代码其实它是有bug的
我们的王道书上给的也是这小段代码
那如果说p节点刚好是最后一个节点的话
我们只能从表头开始依次往后寻找
找到它的前驱
就是用之前提的那种比较土的思路来解决这个问题
当然如果考试的时候迫不得已
你只能这么写的话
那估计最多扣你一分
甚至不扣你的分
那这个时候大家是不会体会到这个单链表
它只能单向的来搜索
来检索各个节点
而不能逆向的检索
是不是有时候会确实不太方便
那如果说各个节点还有往前的这个指针呢
情况是不是就不一样了
那像这种可以双向寻找
双向检索的链表
就是双链表
 

小结

中在讨论按位序插入的时候
我们具体探讨了带头节点和不带头节点的代码实现
从代码中大家应该能够体会到这两种情况的区别
同时就能理解上一小节提到的那个点
带头节点写代码会更方便一些
当然两种情况代码都要会写
大家在做题的时候一定要注意审题是不是带头节点的
那这个小节的这些操作的实现都是十分重要的
另外不知道大家有没有体会到
我们之前花了不少的时间来讲什么mlock函数
free函数
然后画了各种各样的内存
但是当我们在前期花时间把这些基础打牢了之后
是不是理解起来会越来越快
所以前期的这些内容我们学慢一点没关系
因为很多代码里面遇到的问题都是相通的
你学之后的内容也会遇到
那这些问题
如果我们能在刚开始的时候就把它解决
那之后的理解才会越来越深
并且会学得越来越快
另外在这个小节当中
希望大家能够用我们的这个示例代码来体会一下封装的好处
我们不是实现了一个后叉操作吗
实现了这个函数之后
我们按位序插入数据元素e
这段代码是不是就变得很简洁并且清晰明了
当我们要在第二个位置插入数据元素e的时候
我们首先是要先找到第i减一个节点
然后在这个节点之后插入新的数据元素e
你看把这个小功能模块把它封装成一个函数之后
是不是你的代码逻辑就变得更清晰了
当然了
前面这个部分我们也可以把它封装成一个函数
一个基本操作
这个我们会在下一小节当中进行介绍好的
那以上就是这个小节的全部内容
 

单链表的查找

按位查找

好那首先来看按位查找怎么实现那所谓按位查找
就是你要找到l这个单链表当中的第二个节点
把这个节点给返回好
那上一小节中我们在按位插入和按位删除这两个基本操作里边
其实已经实现了按位查找相关的代码逻辑
只不过上一小节当中我们是找到第二减一个节点
那代码是不是类似的
如果我们要找的是第二个节点的话
把这个地方改成i不就行了好
那所以要找到一个单链表l当中的第i个节点就很简单了
首先要判断一下这个a的值是否小于零
如果小于零的话
那返回一个none
因为我们这讨论的是带头节点的这种情况
所以我们可以把头节点认为是第零个节点
因此如果此次传入的参数i等于零的话
那么首先经过上面这一系列执行
p指针会指向头节点
而j的值等于零
i的值此时也是零
所以这个条件是不满足的
因此会直接跳过这个循环
直接返回当前p指向的这个节点
也就是返回这个头节点好

如果i=0边界

如果i=8

那这是一种极端情况
再来看另一种极端情况
如果i的值大于链表的实际长度比如说i等于八的话
那么来分析一下这个代码

首先这个p它是指向了头节点
然后j的值刚开始是零
好第一轮循环之后
p指针指向下一个节点
j的值变为一
第二轮循环p再往后指一个节点
j的值变为二
第三轮循环p指向第三个节点
然后j的值变成三
第四个循环是这样
第五个循环是这样子好
那接下来是不是循环的这个条件不满足
于是循环结束返回p指针
此时指向的这个值也就是返回一个n
所以你看当i值不合法的时候
它最终返回的值就是一个n
因此如果别人调用你这些基本操作的话
那他是不是只需要判断一下此次的返回值是不是等于
那它就可以知道这次的安慰查找操作到底是否执行成功了
那这些边界情况都是我们在写程序的时候必须考虑到的
要让我们的这个算法具有健壮性好
那接下来如果i等于三的话
那这个分析起来也是一样的
即便是初学者
只要耐下性子来
肯定可以分析出这个代码执行的过

时间复杂度

写这一段代码有必要吗
但是如果在左边这种情况下
这个条件判断就会显得十分重要
因为刚才我们说了
如果说此次传入的这个i值不合法的话
那么get in这个函数的返回值应该是会返回一个none对吧
所以p指针有可能是指相当的
那接下来你再往这个函数里传入p指针的话
是不是就说明其实这种情况是有可能发生的
当p等于none的时候
说明第i减一个节点是不存在的
在这种情况下直接返回一个false表示后插操作失败
那这个按位插入的操作直接return这个函数的返回值
也就是说它也会返回一个false
那是不是就意味着这个案例插入也失败了
所以你看尽可能地提高代码的健壮性

按值查找        

就是给你一个数据元素e，然后看一下在你的这个单列表当中，有没有哪个节点的值是等于e的
那这个代码很简单
那我们假设这个我们这儿的所谓aletype
它是int型的变量
然后这次传入的e这个变量它等于八的话
那首先会让一个p指针指向头节点的下一个节点
也就是指向第一个数据节点之后进行while循环
此时p不等于none是满足的
并且p这个节点的数据域它的值不等于e的值
也就是不等于八
因此会让p指针指向下一个节点
接下来要进行第二轮循环

但是由于p节点当中存储的这个数据
它的值和e的值是相等的
所以循环条件不满足
因此会执行之后的依据
也就是return这个p指针
因此会跳出循环
把这个p节点给返回
这样的话我们就找到了一个和给定的元素值相等的节点

好再来看一个不能找到节点的情况
如果e的值此次传入的是六的话
那么和刚才一样
通过这个while循环的执行
p指针会一次一次的往后移
一直移到最后面这个位置

当p指向nn的时候
这个条件得不到满足

于是跳出while循环
然后返回p也就是返回一个n
那当这个函数的调用者接收到none的时候
就说明并不存在数据域等于六的节点
好
那刚才我们是假设这个alan type数据元素的类型是int类型
那我们对struct类型的呃相等的判断是不是就不能用这个操作符
这一点我们在之前的小节中强调过
大家可以再回忆一下
如何比较两个struct类型
它是否相等
这就不再重复好呢
由于按值查找操作只能从第一个节点开始
用这个循环依次的往后扫描p指针
所以很显然这个算法它的时间复杂度应该是o n这个数量级
 

单链表的长度

小结

建立单链表

这小节要探讨的问题就是
如果给你很多个数据元素
也就是很多个type
那么让你把它们存到一个单点表里
你应该怎么处理呢
其实很简单
第一步肯定是要从无到有
先创建一个单链表对吧
也就是说先初始化一个单链表
然后接下来每一次取一个数据元素
然后把这个数据元素插到表尾的位置
或者每一次都插到表头的位置
 

尾插法建立单链表

先我们要探讨的是尾插法
第一步是不是要先初始化一个单链表
怎么初始化一个带头结点的单链表啊
这个相关的操作
我们已经在单链表的定义
那个小节当中有过详细的介绍
这就不再赘述

好那现在已经有了一个单链表
接下来我们每次取一个数据元素
插到这个单链表的尾部
那这个操作

我们是不是可以用之前已经实现的
按位序插入这个基本操作来实现
那由于我们每一次都是要把数据元素
插入到这个单链表的表尾

所以我们可以设置一个变量叫l
用这个变量来记录单链表的当前长度
然后再写一个while循环
每次取出一个数据元素e
然后调用按位序插入这个基本操作
每次都把这个数据元素e插入到dlss
加一个位置
像下面这个例子
length加一应该等于四
所以应该就是插入到这个位置
也就是表尾的位置
而每一次插入一个新的元素之后
都会导致单链表的长度
lins加一
那是不是这样的方式就可以实现
 

当只有一个节点时 ，在while用的时候只用0次，2个的时候1,3的时候循环2次

上面的数字是需要循环多少次

那么当你每一次要在表尾的位置
插入一个元素的时候
它都会用这个循环从表头的位置开始
依次往后便利
直到找到最后一个节点
按照这个逻辑
当我们要插入第一个元素的时候
也就是只有一个头节点的时候
这个while循环可以直接跳过
也就是循环次数是零次
而当我们要插入第二个元素的时候
while循环需要循环一次
要插入第三个元素的时候
需要循环两次好以此类推
所以如果我们要插入n个元素

么当插入第n个元素的时候
总共需要循环n减一次
因此循环的次数总共就应该是0+1+2
一直加加加加到n减一
算出来应该是o的n方
这样的一个时间复杂度
这个时间复杂度还是很高的
等差数列相加了 

不是还需要把这个表尾指针往后移
就指向新的这个表为元素
这样的话你在插入下一个数据的时候
是不是还是对r进行后插操作就可以了
好那来看一下我们课本里给的代码
在这个代码里边
首先声明了一个局部变量x
然后用my lock申请了一个头节点
也就是说
它这里边其实做了
初始化一个单链表的操作
 

只不过我们自己初始化一个单链表的时候
会把这个头结点的指针先把它设为n
但是他这个地方没有做这样的操作
因为头节点的这个指针会在后面被修改好
那继续往后在这儿声明了两个指针
s和r这两个指针都是指向了头节点
然后这个地方调用了gf
也就是让用户从键盘里边输入一个整数
这些整数x

就是此次要插入单链表当中的数据元素
也就是说我们这儿的island tap
也就是数据元素类型
它就是整形的变量好
那假设此次输入的整数是十
那接下来while循环
它首先会检查x的值是否不等于9999
他这设置了一个这样的数字
其实就是取一个比较特殊的值

就是这样循环

当用户输入9999的时候
认为这个单链表的建立已经结束
所以你不要觉得奇怪
这为什么选g999 
其实就随便挑选了一个比较特殊的数字

于此时x的值是十，它不等于这个特殊的值
因此会开始执行循环里边的这些代码，后面这两句会申请一个新的节点
然后让s这个指针指向新节点
并且把新节点的这个数值设为x
也就是此次输入的这个数字
接下来把r节点的next指针指向s这个节点
也就是这样子
最后再让r指针指向s这个节点
接下来就可以输入下一个数据元素

那假设我们此次输入的数字是16
那由于16不等于这个特殊的数值
所以这个循环的条件满足
因此接下来还会申请一个新的节点
并且把这个新的数据元素
放到这个节点当中
再往后让r节点的next指针指向s之后
再让r指针指向s这个节点
接下来又可以输入
再下一个数字好
那由于这次输入的数字
依然不等于9999
所以还会进行一次循环
那处理的过程和刚才是一样的
总之r这个指针
永远要让它指向表尾的那个数据节点
然后每一次取得一个新的数据元素的时候
都把这个新的数据元素
存到一个新的节点当中
并且把它连到表尾节点之后好
那接下来如果用户输入的是9999
那么这个循环条件不满足
 

这样就设置成了，每次都将s元素设置在r元素之后。

把它连到表尾节点之后好
那接下来如果用户输入的是9999
那么这个循环条件不满
足
于是就可以跳过这个循环
然后执行这一句
让r节点的next指向n
最后再给调用者返回这个头指针
也就返回这个单链表
 

一次都从头开始往后寻找
那其实我们是不是可以设置一个指针
让这个指针指向表尾的最后一个数据节点

然后当我们要在尾部
插入一个新的数据元素的时候
是不是
只需要对r这个节点做一个后插操作
就可以了

代码的实现应该就很简单了在前面这个地方无非就是做了一个初始化空表
然后在这个while循环里
其实就是做了一个指定节点的后叉操作
虽然和我们实现的后插操作
有那么一丢丢区别
但是最起码后插操作的实现思想
就可以直接迁移到这个地方
唯一需要注意的就是这个r指针

它永远是指向最后一个节点的
显然如果要插入n个节点的话
那么这个循环的次数也是n次
所以这个算法
它的时间复杂度应该是o n这个数量级
那同学们可以暂停思考一下
如果不带头结点的单链表
它的尾插法实现会有什么不同呢
好接下来我们再来看第二种方法

头插法建立单链表

每一次取得一个新的数据元素的时候
我都把它插入到这个单链表的表头
这个位置就是这个样子
那其实实现这个算法的核心
是不是和刚才一样
它也是一个对指定节点的后插操作
每插入一个数据元素
其实就是对这个头节点执行一次
  

每一次取得一个新的数据元素的时候
我都把它插入到这个单链表的表头
这个位置就是这个样子
那其实实现这个算法的核心
是不是和刚才一样
它也是一个对指定节点的后插操作
每插入一个数据元素
其实就是对这个头节点执行一次
 

这里边他每次取得数据元素
依然是用这个skin f
也就是让用户用键盘输入一个整数
作为此次要插入的新的数据元素
那你看这两句
是不是实现了对单链表的初始化
然后while循环里边这个部分的代码

其实就是实现了一个后插操作
只不过他每一次执行后插操作的指定节点
都是指定了头节点

头插法的话是链表的逆向

当他在初始化头节点的时候，他把头节点的next指针指向了null。但是尾插法里面没有好
那大家可以暂停思考一下，如果我们像尾插法那样，把这一句代码给它去掉呢，会发生什么情况，首先前面这句代码会申请一个新的节点，那如果我们不执行这句代码的话，那是不是头节点的这个指针，有可能指向内存当中的某一片，神秘的区域啊，因为之前和大家强调过
其实这种动态分配申请的这片内存，空间里面，它以前可能是会有脏数据的，你不知道以前这个数据是什么，所以说如果你不把它初始化的话，那么这个指针它有可能是指向某一个
你不可知的地方的
好了
再往后执行的话
申请一个新的节点
 

s这个s节点的data域把设成x再往后的话
s节点的next指针指向了L节点的next指针
这个地方也就是指向了这片地方。然后头节点再指向这个新的节点，也就是这样子好
那如果还有别的新的节点陆续插入的话。是不是情况是类似的
最后一个节点的next指针
他最终肯定都会指向这个

 

 

逻辑判断

也就是先输入十，再输入16，再输入27
最后输入9999的话
那么按照头插法的这种规则
我们最终形成的这个单链表
就应该是二七十60
 

刚好是这些输入元素的逆序，
其实头插法的这种性质是十分重要的
大家做课后习题的时候就会发现
其实在很多题目当中
都会用得到这种单链表的逆制这样的操作
那像这段代码当中
我们是用caf取得一个一个的数据元素，那如果现在给你一个单链表l
让你把这个单链表逆置的话
其实核心的代码逻辑是不变的
只不过你取数据元素的时候
并不是用scaf的方式取得的
而是可以用一个指针循环着扫描

按顺序从这个l当中
依次取得各个数据元素对吧
然后当你取出一个数据元素之后
又用头插法
把它插入到另一个新的列表当中
那你用这种方式建立的新链表
是不是
就相当于把这个以前的老链表给逆制了
当然你也可以

每一次从这个列表当中取下一个节点
然后把这个取下的节点
又重新插回到这个头节点之后
这样的话你就不需要建立一个新的链表
而是把lg的链表原地逆置

小结
 

双链表

双链表操作

         

在单链表当中，由于每一个节点只包含，指向它的后继节点的指针
所以如果给定一个节点p的话。那么想要找到它的前驱节点是很麻烦的
那双链表呢

就是在单链表的基础上再增加一个指针域，这个指针。prior是指向这个节点的前驱节点
the prior这个单词的意思是先前的

还有一个很有趣的意思
叫男修道院副院长好
那我们的一个双链表中的节点

我们把它命名为dna的
这儿的d其实指的是double
好的
来看一下怎么从无到有创建一个双链表

带头节点的情况

我们讨论的是带头节点的情况，首先这个地方声明了一个指向头结点的指针l

后调用双链表的这个初始化函数
这一句代码会申请一片空间
用来存放头节点
并且让指针l2 指向这个头节点

然后接下来需要把这个头节点的
前向指针和后向指针都设为null
这个头节点之前
肯定不会再有其他的节点了
所以这个头节点的prior指针域
肯定是永远都指向当的好
那这个地方我们做了类似于单链表那样的

那这和单链表那边类似
有的地方使用dealing list是想强调这个东西
它是一个链表
而有的地方我们使用dna的心
是想强调这个东西它是一个节点好
那这块的内容
我们在单链表的定义那个小节中
重点强调过
所以这个地方就不再展开好
那对于带头节点的这种双链表来说
如果要判断它是否为空的话
是不是只需要判断这个头节点的next指针
是否等于none就可以了
如果等于nn的话
说明这个表
此时暂时还没有存入任何数据元素好

双链表的插入

过程

也就是说要在p节点之后插入s这个节点，好第一步会把s节点的next指针，指向p节点的下一个节点
也就是这个样子

第二步二步会把p节点的后继节点
它的前向指针指向
此次新插入的s这个节点也就是这个样子

  第三步把s节点的前向指针指向p节点也就是这样

四步再把p节点的后向指针指向s节点
也就是这样
 

节点的这种情况好
那来看一下
假设现在p节点是最后一个节点
那第一句代码会让s节点的next指针指向
p节点的next指针相同的位置
也就是同样是指向
当然后第二句先判断p节点
此时还有没有后继节点
如果它没有后继节点的话
那当然就不需要再修改它
后继节点的前向指针
因此在这种情况下
if条件不满足
会跳到之后一句执行
让s节点的前向指针指向p节点
第四局再把p节点的后向指针指向
新插入了s节点
那加了这句代码之后
是不是后插操作就没有问题了
那大家自己写代码的时候

更严谨点

修改这些指针的一个啊语句的顺序
修改指针的这些语句
如果语序不合理的话
那么有可能会导致一些错误
比如说如果我们写代码的时候没注意
把四这一句写在了前面
先执行四再执行一的话
那么首先四这一句会让p节点的next指针
指向此次的新节点s
接下来执行第一句
会让s节点的next指针
和p节点的next指针指向同一个位置
也就会指向s节点它自己
那这种情况肯定是错误的
所以大家自己写代码的时候

后插和前插操作

其实指的是后插操作对吧
就是在p节点之后插入s这个节点
其实只要搞定了后插操作
那么按位序插入或者一个节点的前叉操作
这些都很容易实现
如果我们想要按位序 ，插入一个新的节点的话，那么我们是不是只需要从头节点开始
找到某一个位序的前驱节点，然后对这个前驱节点执行后查操作
就可以了
而如果我们想要在某一个节点前面，进行一个前叉操作的话
那么由于双链表的这种特性，我们可以很方便地找到，给定节点的前驱节点
然后再对它的前驱节点执行后插操作
这样的话我们就可以实现所谓的前叉操作
也就是其他的这些插入操作
其实最终都可以转换成，用这个后差来实现好

双链表的删除
 

次要删除的是指定节点，p的后继节点q节点
第一句代码会让p节点的next指针向q节点的next指针相同的位置
也就是指向q的后继节点
二句代码会把q节点的后继
节点的前向指针指向p节点
也就是这个样子
第三句代码在释放q节点
这样的话就完成了对q节点的删除
 

又有问题

果此次要删除的节点，q刚好是双链表的最后一个节点的话，那么第二句代码
同样是会出现一个空指针的错误
所以我们可以增加一些条件判断
用来提升这个代码的健壮性好

们要删除的是给定节点
 

会声明一个q指针
让q指针指向p的后继节点
如果q等于none的话
那说明p节点是没有后继节点的
这种情况下返回false好
 

那接下来首先是让p节点的next指针，指向q节点的next指针相同的位置也就是这样子
再往后我们需要先判断一下q节点，还有没有后继节点，
如果q节点有后继节点的话，那么我们才会尝试修改它
后继节点的前向指针
那像这种情况
q节点之后已经没有其他节点了
所以这个if的条件不满足
因此就会直接把q节点释放掉
好那实现了这个删除操作之后

如果我们想要销毁一个双链表的话
那我们是不是可以用一个while循环

每一次都删除这个头节点的后继节点
依次把这些节点占用的空间给释放掉
直到头节点之后再无其他节点
也就是说这个表变空了

最后再把这个头节点占的空间也给释放掉
然后让头指针指向null

双链表的遍历

要打印出这个节点的数值啊之类的.指定的节点p
然后每次你让这个p指针往前移一位.

然后在这个while循环里
对节点p做相应的处理就可以了
好那如果你在这个循环里边
只想处理那些数据节点
并不想处理头节点的话
那只需要把这个while
循环的条件给改一下就行了
如果说p节点的前向指针
已经等于nn的话
那么说明此时p节点指向的
就已经是头节点了
这样的话while循环条件不满足
也就不会对当前p节点指向的这个
头节点进行处理好
你只需要累加一个计数器
用于记录
此时我指向的是哪个位序的元素就可以了
而如果你要按值查找的话
在这个循环里边
是不是
你只需要对当前指向的这个节点
进行一个值的对比就可以好
那由于双链表它并没有随机存取的特性
所以这种查找操作时间
复杂度就是o n这个量级
因为你只能用这种循环的方式
一个一个对比
依次往后找好

小结

其实对双链表的这些操作的实现
和单链表本质上没有太大的区别
只不过双链表
它就是多了一个前向的指针吗
所以大家在写代码的时候
只需要注意这些指针它怎么修改
然后不要出错就可以了
然后当我们实现插入和删除
相关的代码的时候
大家可能要注意一下
如果此次插入的是最后一个位置
或者被删除的节点是最后一个节点的话
那严格一点来说
书上给的那个代码逻辑是有一点点bug的
那基础不好的同学也需要注意便利操作
它的循环应该怎么实现
怎么写好的
那以上就是这个小节的全部内容
 

循环单链表

各位同学大家好
其实就是在单链表和双链表的基础上
加一个小小的改进
然后就变成了相对应的循环
单链表和循环双链表
所以这个小节的内容其实十分简单
看一个图就明白了
它最后一个节点的next指针是指向当
但是循环单链表当中
最后一个节点的next指针是指回了
这个头节点

初始化一个循环单链表的时候，我们需要把头节点的next指针指向头节点它自己

所以判断头结点为空，就只有一个节点并且为空的时候

应的如果要判断它是否为空的话
你只需要检查它的头节点的next指针
是否是指向它自己就可以了
当它为空的时候
头节点的next指针是指向空的
也就指向n那刚才也说了
如果这个循环单链表不为空的话
就需要把最后一个节点的next指针
指向头节点
那相应的
 

你要判断某一个节点p，它是否是循环单链表的表尾节点的话。你只需要看一下这个p节点的下一个节点。是否是头节点，所以当大家写代码、遍历这个循环单链表的时候
判断这个扫描指针p是否到达表尾的条件，和普通的单链表也是有一些不一样
相信这些都不难理解
那之前我们提到过
 

对于一个普通的单链表，
如果说给你一个节点p
那么其实你只能知道这个节点p
后续的这些节点
对于它前面的这些节点是什么情况
那你是不可知的
除非你也能获得头结点的指针

但是对于循环单链表来说

要给你一个节点p
那你肯定可以找到整个循环单链表当中的
任意一个节点
那这种特性还是有一些作用的，因为这个循环链表的表尾总是指向了表头了。

 

对吧，实现这个功能

如果现在要让你实现一个功能
让你删除节点p
那删除这个节点之后
肯定需要修改它的前驱节点的next指针
但是对于这种普通的单链表
你只知道节点p的指针
你肯定找不到它的前驱节点
而对于循环单链表来说
你可以顺着这条链依次往后找
然后直到找到此次要删除的节点p
它的前驱节点
然后修改它前驱节点的next指针
这样的话就可以完成删除节点p的工作
所以可以循环遍历各个节点
这个特性还是有一些作用的好
那之前我们在讲单链表的时候呃

小结我们对链表的操作都是在链表的头部或者链表的尾部，比如说我们之前提到的用头插法建立链表。或者用尾插法建立链表好，那如果这个单链表它是普通的单链表。也就是最后一个节点
它的next指针是指向none的话
此时如果我们只知道
这个链表的头节点的话
那么要从头节点开始
找到最后一个表尾的节点
我们只能写一个循环

依次往后扫描直到找到最后一个节点所以找到最后一个节点的时间复杂度是o n这个数量级
而对于循环单链表来说。如果我们让这个单链表的指针l不是指向头节点而是指向尾部的这个节点那么从这个尾节点出发到头节点只需要o一的复杂度
因为只要往后找一个节点就可以了
而由于l这个指针是指向尾部的
所以当我们需要对链表的尾部
进行操作的时候
也可以在o一的时间复杂度内
就直接找到我们要操作的那个位置
而不需要像刚才说的这样
从头往后依次循环便利
所以如果在你的应用场景当中
需要经常对表头或者表委进行操作的话
那么当你使用循环单链表的时候
你可以让你的这个呃单链表的指针l2 
让它指向最表尾的这个元素
当然如果你要这么做的话
当你在表尾插入和删除一个元素的时候
就需要修改这个指针l的指向
那这就不再展开好
 

那接下来要看的是循环双链表
其实循环双链表也很简单

表尾节点的next指针它会指向这个头节点
然后头节点的prior指针，它又会指向尾结点，也就是说所有的这些next指针，它其实是形成了一个闭环，一个循环

而所有的这些prior指针
它也形成了另外一个方向的闭环循环。那这就是循环双链表

空的双链表的时候

那当我们在初始化一个空的
循环双链表的时候
我们需要让这个头节点的前指针和后指针
都指向头节点自己
而普通的双链表它们都是指向量对吧
所以循环双链表的判空也有一点点区别
就是判断此刻这个头节点的next指针
是否是指向了他自身

 

指向了头节点，所以当我们在判断一个节点p，它是不是循环双链表表尾节点的时候啊
判断的条件应该是这个节点的next指针，是否指向了头节点
如果满足的话
那么说明这个节点它就是尾部的节点
 

完美闭环

当循环双链表为空表的时候啊
这个头节点它的next指针
也是指向了头节点本身
所以这个头节点它既是第一个节点
也是最后一个节点

下循环双链表和普通的双链表
他们在实现基本操作的时候有哪些区别

错：

在节点p之后插入一个节点s
如果用这小段代码处理
这种普通的双链表的话
当p节点它刚好是表尾节点的时候
第二句代码的执行会出现错误
因为p节点它没有后继节点
所以我们就无法修改

所谓的它的后继节点的前向指针
但是如果我们用的是循环双链表的话
那这个逻辑其实就是正确的
因为即便p节点它是表尾的最后一个节点
但是它的next指针依然是非空的
这个指针指向了头节点
当我们插入一个新节点的时
候
把这个头节点的prior
也就是前向指针
让它指向这个新的节点
其实是没有问题的

双链表的删除

双链表的删除也是一样的，如果说我们此次要删除的节点
q它刚好是最后一个节点的话
那么和刚才一样
q节点没有它的后继节点

所以在执行第二句代码的时候
就会出现一个空指针的错误
而如果使用的是循环双链表的话
第一句代码首先会把p节点的next
指针指向q节点的next
也就是指向头节点的位置
接下来第二句它会把q节点的next
也就是这个头节点
它的prior指针前向指针指向p节点
也就是变成这样
最后第三句再把q节点给释放掉
所以如果采用循环双链表的话
那课本当中给了这一小段代码
逻辑就是没有问题的
 

小结

所谓循环单链表
其实就是把单链表当中最后一个元素的next
指针指向头节点
所以当循环单链表为空的时候
就有点像是你单手抱住了空虚的自己

而对于循环双链表来说
当它为空的时候
头节点的后向指针和前向指针
都是指向了他自己
就像你用双手抱住了空虚的自己

而对于普通双链表来说
当表为空的时候
它的前向指针和后向指针都是指向null的
所以就有点像是这个样子
 

那到这儿我们就学完了
所有的用指针实现的链表
不管是对单链表
双链表
还是这儿提到的循环链表
大家在写这些链表的具体代码的时候
都需要关注这样的几个方面
首先是怎么判断啊
一个表它是否为空
你知道一个空表的状态
你是不是就可以知道
这个表应该怎么初始化
另外还可以思考怎么判断一个节点
p它是表尾的节点还是表头的节点
当你知道这个条件怎么判断之后
你是不是就可以知道你怎么写
前项便利和后项便利了
因为所有的这些链表
它都不具备随机访问的特性
所以当你要寻找其中的某一个节点的时候
核心肯定都是要实现一个便利的逻辑
也就是一个while循环
而while循环停在什么地方
其实无非就是停在表头或者停在表尾
然后最后大家在尝试插入或者
删除一个节点的时候

值得关注的是果你此次插入或者删除的这个节点
它在表头需不需要特殊的处理
在表中应该怎么处理
在表尾的时候又是否需要特殊的处理
当你考虑到所有的这三种情况的时候
你基本上就可以覆盖那些比较容易出错的
边界条件了。

知识总览

静态链表

不同之处

怎么实现静态链表相关的那些基本操作，那首先来看一下什么是静态链表
那之前我们已经学过单链表，单链表中的各个节点。它是离散的分布在内存中的各个角落
每一个节点会存放一个数据元素。还有指向下一个节点的指针，它是离散的分布在内存中的各个角落，每一个节点会存放一个数据元素。还有指向下一个节点的指针。

而静态链表是要分配一整片的
连续的内存空间
各个数据元素存放在这一整片空间中的
其中某些位置
静态链表中的每一个节点包含了数据元素
还有下一个节点的数组下标

在静态链表中
数组下标为零的这个节点
他充当了头节点的角色
也就是说这个节点当中
它是不存放实际的数据元素的
而头节点的下一个节点
它是存放在数组下标为二的这个位置
也就是说这个节点就是第一个数据节点
也就是位序为一的节点
那再往后的节点就是数组下标为一的节点
也就是上面这个节点
所以静态链表中的这个数组下标
或者呃也有的地方把它称为游标
这个东西，它充当的角色

想同点

其实和单链表当中的指针是差不多的
只不过指针是指明了具体的内存地址
而这个地方的游标只是指明了下一个元素
它的数组下标
那单链表的表尾元素
它的next指针是指向n的
在静态链表当中
如果要表示这个节点
它是最后一个节点的话
那么它的这个游标的值可以设为-1
这就表示在这个节点之后
已经没有其他节点了
好

那由于静态链表当中，存放各个节点的这些空间，它们是连续的，所以如果说一个静态链表，它的这个数据元素占四个字节，游标也占四个字节，也就是说这一整个的呃节点，它需要占八个字节的话

那假设静态链表的起始存放地址，是这个地址，那数组下标为二的那个节点
它的存放地址就应该是0号
节点的存放地址
加上每一个节点的大小乘以
接下来要寻找的这个节点的啊
数组下标
那用这样的方式

是不是就可以把静态链表当中的游标，
或者说数组下标
把它映射成某一个数组下标
所对应节点的实际存放地址

那这就是静态链表的一个基本原理好
那怎么用代码定义一个静态链表呢
 

我们可以定义一个结构体啊
叫做note
然后每一个note也就是每一个节点里边

它包含了一个数据元素d
还包含了下一个节点的游标
或者说数组下标
那这个数组下标可以用一个int型来表示好
那这是静态链表的一个节点
那我们需要的是多个连续存放的节点
那我们可以用数组的方式来定义来声明它
就像这样
 

我们定义一个数组a，这个数组a有max size，也就是有十个数组元素
然后每一个数组元素的类型都是struct node
也就是我们上面定义的这样的一个节点
所以用这样的方式声明一个数组的话
那么这个数组a其实就是占用了内存当中
这样的一整片连续的存储空间
那这是我们自己比较容易想到的
一种定义方法

另一种写法

这用了type define，然后在这个部分说明了，你的struct结构体里边包含了哪些字段。
一个data和一个next，然后后面跟了一个，看起来像是数组的一个东西
后来我自己写了一些代码之后
发现他这种定义方式

type define给它重命名，不过这个地方它跟的是一个，看起来像是一个数组的东西，用这给出的这种写法，你之后用link list去定义一个变量a的话，那么当你声明这个变量a的时候
其实这儿的a你是声明了一个数组，这个数组的元素个数有max size这么多，也就是有十个元素，而每一个数组元素就是这样的一个struct，node
也就是你这儿定义的这样的一个结构体
它等价于你用这样的方式声明a这个数组
反正我问了身边好几个
经常用c c加加的同学
很少有人见过这样的一种定义方式啊
这希望大家可以暂停来体会一下诶
那为什么课本中要用这样的方式来定义
静态链表
用我们熟悉的这种数组的方式
来定义静态链表
难道它不香吗
其实这个地方和我们之前学习单链表的时
候提到过的link list
还有air no的星是完全相通的
因为其实我们在这个地方想定义的
所谓的a这个东西
它是一个静态链表
但是如果用下面的这种方式来定义a的话
那么我们从代码的这个角度来看
会觉得说a它看起来是一个note型的数组
而上面的这种定义方式
虽然效果上和下面这种是等价的
不过上面这种定义方式
你一看这个代码
你就知道a这个东西它是一个静态链表
所以这个地方这种比较少见的
type define的用法
也希望大家能够了解它的原理是什么
我写了一小段程序验证过刚才的那种猜想
这我用了我们比较容易想到的那种方法
来定义了一个struct node
里面包含了两个int型的变量
然后下面这个地方我用了课本中的那种方
式
使用了type define，然后后面跟了一个类似于数组一样的东西
max size的值是十
然后在这个函数里边
首先声明了一个struct node
也就是一个节点x
然后在这个地方打印输出一个节点的大小
也就是用size of关键字
然后可以看到一个节点
它是八个字节这么大
然后在这个地方
我们用我们比较熟悉的方式
定义了一个数组a
这个数组a的大小是max size
也就是有十个元素
然后每一个元素它就是一个struct node
那由于每一个元素的大小是八个字节
所以数组a的大小用size of测出来
就应该是80个字节这么大小
然后在最后这个地方我声明了一个变量b
这b的类型是s link list
然后也用size of测出了b的大小啊
发现它也是80
也就是说它和a是一样的
所以这就说明
当我们声明这个变量b的时候
其实它在背后它是一个大小为十的数组
并且数组元素
每个数组元素是这样的一个struct
其中包含了一个data和一个next
那由于每个int型的变量都是四个字节
所以这样的一个struct
它应该是八个字节的大小
和我们这儿测出来的结果是一样的
那这小段程序的这个运行结果
就证明了刚才提出的那种猜想好
那现在我们已经声明了一个静态链表
接下来来看一下这个静态链表
相关的一些基本操作
应该做一些什么事情
首先声明了它之后
肯定需要对它进行初始化
那么我们在单链表当中
初始化一个单链表的时候
需要把这个头节点的next指针指向
那所以对应到这个静态链表里面的话
我们在初始化的时候
肯定需要把这个头节点
也就是a0 这个节点的next把它设为-1
因为-1其实等价于nm
就是它没有指向任何一个元素好
那在静态链表当中
 

简单操作的基本实现

要查找某一个位序的节点的话
那我们肯定只能从这个头节点出发
通过这个游标记录的这些线索
依次的往后寻找后一个节点
然后直到找到我们想要的那个节点为止
所以在这种静态链表当中
 

果你要找到某一个位序的节点的话，那么时间复杂度应该是o n这个数量级，注意我们这儿说的是某一个位序的节点，而不是某一个数组下标的节点
未序指的是各个节点在逻辑上的顺序
而这儿的数组下标
其实只是反映了各个节点在物理上的一
个顺序好那这是查找操作
接下来看一下
如果要在未戌为i的这个地方
插入一个节点的话
那不难想到

操作步骤

第一步肯定是要找到一片空闲的空间
用来存放这个新的节点对吧
所以像这个图当中
45789这些地方都是空闲的
所以可以按照某一种算法
比如说从上到下扫描啊
或者从下到上扫描之类的
就是找到一个此时空弦的节点
用于存放此次要存入的这个新的数据元素
第二步
既然要插入位序为i的节点
那么我们肯定需要把位序为i减一的
这个节点
它的后向指针或者说它的游标给改了
这个其实和单链表很类似。

比如说在左边这种情况下
此时已经有四个数据元素了
那假设我们要插入位数为五的数据元素
也就是说要在表尾插入一个新的数据元素
假设是在这个位置
那这个位置作为新的标位
那按照第二步
我们是不是需要找到它的前驱节点
也就是第四个元素
把它的后向指针next改成四
也就是指向我们这个新节点的存放位置
然后接下来还需要把我们新节点的next
设成-1

们是直接用肉眼的方式
就可以看到这几个地方
他们是没有存数据的
但是从计算机的视角来看
其实内存当中的任何一个地方
肯定都会有数据
只不过这些数据是脏数据而已
所以为了让计算机识别出哪些节点
它此时暂时没有存放数据
其实我们还应该在初始化的时候
把这些空闲节点的next
把它设置为某一个特殊的值
比如说你可以设置为-2
那这样的话你写代码的时候
是不是只需要判断一下
如果它是-2的话
那么就说明此时这个节点是空闲的
你就可以用这个节点来存放新的数据元素
所以刚才讲初始化的时候
其实我们还漏了这样的一个步骤
你要在初始化的时候
把这些空闲的节点给它标记出来好
那相应的在删除一个节点的时候
除了你要修改这些游标这些东西之外
你是不是也需要把此次删除的那个节点
把它的next给它设置为-2
用这样的方式表示这个节点中
此时已经没有数据了
已经被回收了
好
 

知识点回顾重要考点

总结一下静态链表呢
它其实就是用数组的这种方式
实现的一个链表
虽然说静态链表的这个存储空间
它是一整片的连续存储空间
但是在这一片空间内
各个逻辑上相邻的数据元素
也可以在物理上不相邻
各个元素之间的先后关系
这种逻辑关系是用啊这儿的游标
或者说数组下标来表示的
 

小结

那在静态链表中，如果你要增加或者删除一个数据元素的话，你并不需要像顺序表那样大量的移动元素，你只需要修改相关节点的游标就可以，那静态链表和单链表一样
它也不能支持随机存取
每次只能从头节点依次往后开始查找
另外还有一个缺点
静态链表它的容量是固定的不变的
只要你声明了一个静态链表
那么它所能存放的最大容量
就已经被定死了
不可以拓展
所以静态链表现在用的相对来说少一些，就早期的一些不支持指针的低级语言，会用静态链表这样的方式
实现和单链表同样的功能
另外如果在你的这个应用场景当中
数据元素的数量几乎是固定不变的
在这种情况下
用静态链表还是比较合适的
比如说大家之后学习操作系统的文件管理
那一章的时候会学到一个东西
叫做文件分配表
fat其实本质上fat它就是一个静态链表
现在大家还没有学到这个地方
所以可以先在你的操作系统的课本上
做一个笔记
等你学到文件管理的时候
可以再回头来体会一下
静态链表它到底有什么作用
好的那以上就是这个小节的全部内容

顺序表和链表比较

我们会对顺序表和链表
相关的特性做一个对比，也算是对这个章节的内容做一个总结

his mother 的终于完成这章了

那我们之前说过

当我们在聊起一个数据结构的时候
我们应该关注数据结构的三要素，也就是逻辑结构，物理结构，还有数据的运算
所以这个小节的复习
我们依然会按照这样的一个思路来
对相关的内容分别进行一个回忆
那最后我们还需要探讨

在什么时候我们应该使用顺序表
什么时候又应该使用链表好

首先来看数据元素的第一个要素
逻辑结构
其实不管是顺序表还是链表
他们在逻辑上看其实都是线性结构的

也就是说它们都属于线性表
各个数据元素之间有这样的一对一的关系
好再来看第二个方面，存储结构，顺序表是采用了这样顺序存储的方式
实现了这个线性表。那由于采用了顺序存储，并且各个数据元素的大小是相等的
因此我们只需要知道这个，          顺序表的起始地址，那么我们就可以立即找到
第二个元素存放的位置
也就是说顺序表拥有随机存取的特性
另一方面

顺序表当中的各个节点
只需要存储数据元素
本身不需要存储其他的冗余信息
因此顺序表的存储密度也会更高
另一方面

顺序存储的这种呃存储结构
要求系统给它分配一整片的,连续的存储空间,所以在给顺序表分配空间的时候
会比较不方便
并且如果我们想要改变顺序表的容量,也会很不方便

而如果我们采用链表
也就是链式存储的方式,来实现这种线性结构的话,那么由于各个节点
可以离散的存放在不同的空间当中

所以我们每次要添加一个节点的时候
只需要用mo函数
动态的申请一小片的空间就可以了
同时由于各个节点的存储空间不要求连续
因此改变容量也会方便一些

那链式存储带来的问题是
当我们要找到第二个节点的时候
我们只能从第一个节点表头的这个节点开
始依次往后寻找
所以链式存储是不可随机存取的

另外由于各个节点当中
除了存储数据元素之外
还需要花费一定的空间来存储这个指针
所以它的存储密度也会更低一些
那这就是顺序表和链表
在存储结构方面的不同点
好接下来再来看数据结构的第三个要素
也就是基本操作
或者说基本运算
我们用之前提到的这种思路来依次回忆
对于任何一个数据结构的基本操作
最重要的无非就是这样的几种
畅销增删改查
首先你得知道如何初始化
也就是如何创建一个数据结构
还需要知道如何销毁一个数据结构
那如何销毁这个问题
其实在考研当中考察的并不多
但是我们实际写代码的时候
销毁数据结构
相关的基本操作肯定也是十分重要的
那在之前的课程内容当中
我们着重强调的是如何创建
如何初始化
然后如何增加一个元素
如何删除一个元素和如何查找一个元素
如何更改一个数据元素
其实很简单
只要你能查到你想要更改的那个数据元素
那么要更改这个数据元素的值
无非就是一个赋值操作
所以增删改查的改
我们之前一直都没有聊那销毁操作
我们之前强调的也不是特别多
一会儿我们会快速的带过一下好
接下来我们按照这样的思路来一次回忆
首先来看一下
当我们创建
也就是当我们初始化一个顺序表
或者初始化一个链表的时候
需要做的事情有什么不同
由于顺序表要求给它分配的是这样的
一整片的连续空间
所以当我们在初始化一个顺序表的时候
我们就需要给这个顺序表预分配
大片的连续空间
那如果刚开始给它分配的空间太小
那我们之后想要拓展这个顺序表的长度
会很不容易
而如果我们刚开始给它分配的空间
过大的话
那么又会有大量的空间
是长时间处于空闲的状态
也就是会导致内存资源的利用率不高
浪费内存这样的一个现象
而对于链表来说
当我们在初始化
也就是当我们在创建一个链表的时候
其实只需要声明一个头指针
并且分配一个头节点所需要的空间
就可以了
当然我们也可以让这个链表没有头节点
那无论是有头节点还是没有头节点
对于一个链表来说
当它之后想要拓展这个链表的容量的时候
其实是很方便的
每次需要拓展的时候
只需要用malloc再申请一小片新的空间
然后再用指针的方式
把它连到这个链表里面就可以了
所以对于存储容量的弹性
或者说灵活性肯定是链表会更胜一筹
如果我们的顺序表示
采用静态分配的方式实现的话
那么我们顺序表的这个容量
就是不可更改的
而即便顺序表采用动态分配的方式来实现
虽然它的容量可以更改
但是更改它的容量也需要移动大量的元素
所以时间代价也会很高
因此从顺序表和链表的创建
这个基本操作出发
我们可以联想到的是
关于存储空间的灵活性方面的问题
在这个方面显然链表是更胜一筹的好
接下来要回忆的是销毁操作
先来看列表
其实我们在聊链表的基本操作的时候
我们是不是聊过
如何删除链表当中的某一个节点
那如果要销毁一个链表的话
那无非就是把链表当中的各个节点
都依次的删除
所以对列表的销毁操作
它的核心其实就是一个free函数
你可以写一个循环
然后依次扫描各个节点
把各个节点都给分解掉
这样的话就可以把链表占用的这些节点空
间都依次回收
那对于顺序表来说
如果你觉得它之后没用了
需要销毁
那首先你需要把它练s值改为零
也就表示这个顺序表
当前已经变成了一个空表
那这一步操作只是在逻辑上
把这个顺序表把它标记为了一个空表
但是顺序表它所占用的这片存储空间
应该怎么回收呢
分两种情况
如果说你的顺序表
是用静态分配的方式实现的话
那么也就意味着
你的顺序表所占用的这片存储空间
是你通过呃声明一个静态数组的方式
来请求系统分配的
那在这种情况下
这片存储空间的回收是由系统自动进行的
当你定义的这个静态数组
它的生命周期结束之后
系统会自动的把这一片空间给回收
也就是说
如果你采用的是静态分配的方式
那么对于空间回收的问题
你是不需要管的
你只需要把length的值改为零就可以了
那如果你采用的是动态分配的方式
也就是说你的这个动态数组
是用mo函数申请的一片空间
那在这种情况下
你就需要手动的把这一片空间给free掉
由melo函数申请的内存空间
是属于内存当中的堆区
在堆区的内存空间不会由系统自动的回收
也就是说在你实际写代码的时候啊
你的程序里边
mlock和free这两个函数肯定是成对出现的
对于链表也是一样
任何一个节点我们都是用mk函数来申请的
所以当我们销毁这个链表的时候
也相应的需要对每一个节点执行free操作
那什么叫内存中的堆区
什么叫内存中的战区
这些我们现在暂时不展开
在这儿大家只需要记住这样一个结论
你用my luck申请的空间
肯定需要你手动的free
而如果你用声明一个数组
或者声明一个变量
这样的方式申请的内存空间
会由系统自动的帮你完成回收工作
你不需要管好
这是顺序表和链表的销毁操作
那接下来我们需要回忆的是增删改查对吧
那按照顺序
我们首先来看
增加或者说插入一个数据元素
和删除一个数据元素
那插入和删除这两个操作
它们之间的联系比较紧密
所以把它们放在一起来回忆
首先来回忆一下顺序表的插入和删除
需要做的是什么事
那这就需要联系到它的存储特性
那由于顺序存储这样的存储结构
要求各个数据元素在内存里面是相邻的
并且是有序的
所以当我们在插入和删除
一个数据元素的时候
都需要把我们此次插入的这个位置
之后的那些元素都给后移或者前移
如果插入一个元素的话
那么就需要后移
如果删除一个元素的话
就需要前移
而相比之下
对于链表的插入和删除就会更简单一些
我们只需要修改相应的指针
就可以
不需要像顺序表那样
大量的移动元素的存储位置
对于顺序表来说
插入和删除这两个操作的
最坏时间复杂度和平均时间复杂度
都是o n这个数量级
这个时间开销
主要是来自于移动元素所需要的时间开销
那链表的插入和删除
它的时间复杂度也是o n
不过链表的这个时间开销
主要是来自于查找目标元素
就是你需要从第一个元素开始
依次往后寻找
直到找到你想要插入的那个位置
或者找到你想要删除的那个数据节点
那从这个角度来看
虽然说呃顺序表和链表的插入
删除它的时间复杂度都是o n这个数量级
但是考虑到有的时候
我们的这个数据元素它可能很大
比如说一个数据元素
它就占一兆个字节
那么也许你移动这么多的数据
你就需要用10ms左右的时间
那如果要移动n个数据元素的话
那所花的这个时间代价其实还是很高的
而对于链表来说
通过一个节点找到下一个节点
这样的时间开销
很显然
要比这种移动大量的数据
所带来的时间开销要更短很多
比如说假设每往后找一个节点
只需要花1微秒的时间
那么即便往后找n个节点
所需要花费的时间
很显然
也远小于移动元素所带来的时间开销
所以虽然说从大o表示法这样的角度来看
顺序表和链表的插入
删除它们的时间
复杂度都是o n这样的一个数量级
但是当我们结合考虑一些现实因素的时候
不难发现
其实对于插入一个数据元素
或者删除一个数据元素
这样的基本操作来说
链表的效率肯定要比顺序表要高得多好
那这是增删这两个基本操作
接下来看的是查找操作
那我们在学习这个章节的时候
查找操作我们探讨过按位查找和按值查找
对于顺序表来说
你想要找到某一个位序的元素
所存放的位置
只需要o的时间复杂度
也就是说它具有随机存取的特性
而链表只能从第一个元素开始
依次往后查找
所以它的按位查找
时间复杂度是o n这个数量级
那对于按值查找这些操作来说
如果顺序表当中各个数据元素的排列
本来就是无序的
那么我们就只能从第一个元素开始
依次往后对比
所以时间复杂度是o n这个数量级
而如果说这个顺序表中的元素它是有序的
那我们就可以用一些查找算法
比如说像折半查找这样的算法
可以在log n这样的时间复杂度内
就可以找到目标元素
那对于链表来说
无论它里面的这些数据元素
是有序还是无序
当我们在进行按值查找的时候
都只能从第一个元素开始依次往后便利
所以无论数据元素它有序还是无序啊
在列表当中按值查找
肯定都是on这样的时间复杂度
所以对于查找相关的操作
肯定顺序表的效率会高很多好
那最后根据顺序表和链表各自不同的特性
我们就可以知道什么时候应该使用顺序表
什么时候应该使用链表
如果在你的应用场景当中
你的线性表表长难以估计
并且经常会使用插入和删除
这样的基本操作的话
那很显然使用链表会让你更开心一些
比如你要开发一个小程序
这个小程序是要让奶茶店实现排队取号
或者较好这样的功能
那你是不是很难估计你的这个店里边
到底会有多少顾客来取号
同时当有一个新顾客取号的时候
你就需要增加一个数据元素
当一个顾客取到餐之后
你就需要删除一个数据元素
所以在这种应用场景下
使用链表肯定是很合适的
那相反如果你的应用场景当中
你的线性表的表长是可预估的
比较稳定的
并且查询操作会比较多
那你用顺序表的方式来实现
肯定会效率更高
比如说让你开发一个小程序
用于实现课堂上呃
学生点名这样的事情
那我们知道每一个班级的学生
基本上就是固定的
在一个学期之内
基本上一个班里边有几个学生
这个事情是可以预估的
基本不会改变的
而你要实现课堂点名这样的功能的话
那很显然就是需要搜索
或者说需要查询这个表里边
各个数据元素嘛
那在这种情况下
你用顺序表来实现
肯定会有更好的效率
好的
那这个小节中
我们用数据元素的三要素
作为我们总体的思路地图
对顺序表和链表相关的内容
进行了一个回顾和对比
当大家在考试的时候
遇到一些开放性的问题
其实也可以用这样的思路
来让自己的这个答题逻辑更加清晰
现在有很多自主命题的学校
都喜欢考察这种简答题
并且分值还不低
所以如果你在考卷当中遇到一个题目
一个简答题它占了六分
那你答题的时候
这个逻辑的清晰度其实就很重要了
就比如说你可以像我们刚才说的那种
你可以先探讨一下逻辑结构
这个方面来看是怎么样的
然后存储结构方面来看是怎么样的
然后最后再探讨一些比较重要的啊
基本操作它的实现效率又分别是什么样的
最终在得出结论到底是顺序比较好
还是链表好
那在这个地方想给大家强调的
就是这种框架性的思维
我们很多理科生其实很怕
遇到这种开放式的问题
都不知道从哪儿打起
但是如果你的脑子里边有这样的一个思
路的导航地图
那么当你在面对这种开放式的问题的时候
你的答题思路就会比别人更清晰很多
你的分数肯定也会比你的对手更好
也不是说所有的这些东西都需要答上去
但是至少你可以根据这样的思路来回忆
来分析
然后你自己再来决定
到底要把哪些内容给答上去
你的思路是清晰的
那除了答题有用之外
这种框架性的思维
其实也有助于大家自己回忆
复习好的
那第二章的学习到此结束
希望大家不要急着进入第三章的学习
先把我们的课后习题都给做一做
一定要把基础打牢好的
那么以上就是这些小节的全部内容