数据结构与算法|大话数据结构读书笔记系列（三）线性表数据结构与算法|c

2019独角兽企业重金招聘Python工程师标准>>>
文章图片

3.1 开场白
各位同学，大家好。今天我们要开始学习数据结构中最常用和最简单的一种结构，在介绍它之前先讲个例子。
我经常下午去幼儿园接送儿子，每次都能在门口看到老师带着小朋友们，一个拉着另一个的衣服，依次从教室出来。而且我发现很有规律的是，每次他们的次序都是一样。比如我儿子排在第5个，每次他都是在第5个，前面同样是那个小女孩，后面一直是那个小男孩。这点让我很奇怪，为什么一定要这样？
有一天我就问老师原因。她告诉我，为了保障小朋友的安全，避免漏掉小朋友，所以给他们安排了出门的次序，事先规定好了，谁在谁的前面，谁在谁的后面。这样养成习惯后，如果有谁没有到位，他前面和后面的小朋友就会主动报告老师，某人不在。这样养成习惯后，如果有谁没有到位，他前面和后面的小朋友就会主动报告老师，某人不在。即使以后如果要外出到公园或者博物馆等情况下，老师也可以很快清点人数，万一有人走丢，也能在最快时间知道，及时去寻找。
我一想，还真是这样。小朋友们始终按照次序排队做事，出意外的情况就可能会少很多。毕竟，遵守秩序是文明的标志，应该从娃娃抓起。而且，真要有人丢失，小孩子反而是最认真负责的监督员。
3.2 线性表的定义
线性表，从名字上你就能感觉到，是具有像线一样的性质的表。在广场上，有很多人分散在各处，当中有些是小朋友，可也有很多大人，甚至还有不少宠物，这些小朋友的数据对于整个广场人群来说，不能算是线性表的结构。但像刚才提到的那样，一个班级的小朋友，一个跟着一个排着队，有一个打头，有一个收尾，当中的小朋友每一个都知道他前面一个是谁，他后面一个是谁，这样如同有一根线把他们串联起来了。就可以称之为线性表。
公司的组织架构，总经理管理几个总监，每个总监管理几个经理，每个经理都哟各自的下属和员工。这样的组织架构是不是线性关系呢？
不是，为什么不是呢？哦，因为每一个元素，都有不只一个后继，所以它不是线性表。那种让一个总经理只管着一个总监，一个总监只管一个经理，一个经理只管一个员工的公司，俗称皮包公司，岗位设置等于就是在忽悠外人。
班级同学之间的友谊关系，是不是线性关系？哈哈，不是，因为每个人都可以和多个同学建立友谊，不满足线性的定义。嗯？有人说爱情关系就是了。胡扯，难道每个人都要有一个爱的人和一个被爱的人，而且他们还都不可以重复爱同一个人这样的情况出现，最终形成一个班级情感人物串联？这怎么可能，也许网络小说里可能出现，但现实中是不可能的。
班级同学的点名册，是不是线性表？是，这和刚才的友谊关系是完全不同了，因为它是有限序列，也满足类型相同的特点。这个点名册（如表3-2-1所示）中，每一个元素除学生的学号外，还可以有同学的姓名、性别、出生年月什么的，这其实就是我们之前讲的数据项。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。
文章图片

一群同学排队买演唱会门票，每人限购一张，此时排队的人群是不是线性表？是，对的。此时来了三个同学要插当中一个同学A的队，说同学A之前拿着的三个书包就是用来占位的，书包也算是在排队。如果你是后面早已来排队的同学，你们愿不愿意？肯定不愿意，书包怎么能算排队的人呢，如果这也算，我浑身上下的衣服裤子都在排队了。于是不让这三个人进来。
这里用线性表的定义来说，是什么理由？嗯，因为要相同类型的数据，书包根本不算是人，当然排队无效，三个人想不劳而获，自然遭到大家的谴责。看来大家的线性表学得都不错。
3.3 线性表的抽象数据类型
前面我们已经给了线性表的定义，现在我们来分析一下，线性表应该有一些什么样的操作呢？
还是回到刚才幼儿园小朋友的例子，老师为了让小朋友有秩序地出入，所以就考虑给他们排了一个队，并且是长期使用的顺序，这个考虑和安排的过程其实就是一个线性表的创建和初始化过程。
一开始没经验，把小朋友排好队后，发现有的高有的矮，队伍很难看，于是就让小朋友解散重新排 -- 这是一个线性表重置为空表的操作。
排好了队，我们随时可以叫出队伍某一位置的小朋友名字及他的具体情况。比如有家长问，队伍里第五个孩子，怎么这么调皮，他叫什么名字呀，老师可以很快告诉这位家长，这就是封清扬的儿子，焦封云汴。我在旁就非常扭捏，看来是我给儿子的名字没取好，儿子让班级"风起云变"了。这种可以根据位序得到数据元素也是一种很重要的线性表操作。
还有什么呢，有时我们想知道，某个小朋友，比如麦兜是否是班里的小朋友，老师会告诉我说，不是，麦兜在春田花花幼儿园里，不在我们幼儿园。这种查找某个元素是否存在的操作很常用。
而后有家长问老师，班里现在到底有多少个小朋友呀，这种获得线性表长度的问题也很普遍。
显然，对于一个幼儿园来说，加入一个新的小朋友到队列中，或因某个小朋友生病，需要移除某个位置，都是很正常的情况。对于一个线性表来说，插入数据和删除数据都是必须的操作。
所以，线性表的抽象数据类型定义如下：
文章图片

文章图片

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。
比如，要实现两个线性表集合A和B的并集操作。即要使得集合A=A U B。说白了，就是把存在集合B中但不存在A中的数据元素插入到A中即可。
仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。
我们假设La表示集合A，Lb表示集合B，则实现的代码如下：
文章图片

这里，我们对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、ListInsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。
3.4 线性表的顺序存储结构
3.4.1 顺序存储定义说这么多的线性表，我们来看看线性表的两种物理结构的第一种 -- 顺序存储结构。

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表(a1,a2,...,an)的顺序存储示意图如下：

文章图片

我们在第一课时已经讲过顺序存储结构。今天我再举一个例子。
记得大学时，我们同宿舍有一个同学，人特别老实、热心，我们时常会让他帮我们去图书馆占座，他总是答应，你想想，我们一个宿舍连他共有九个人，这其实明摆着是欺负人的事。他每次一吃完早饭就冲去图书馆，挑一个好地儿，把他书包里的书，一本本地按座位放好，若书包里的书不够，他会把他的饭盒、水杯、水笔都用上，长长一排，九个座硬是被他占了，后来有一次因占座的事弄得差点都要打架。

文章图片

3.4.2 顺序存储方式
线性表的顺序存储结构，说白了，和刚才的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型元素依次放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言（其他语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
我那同学占座时，如果图书馆里空座很多，他当然不必一定要选择第一排第一个座位，而是可以选择风水不错、美女较多的地儿。找到后，放一个书包在第一个位置，就表示从这开始，这地方暂时归我了。为了建立一个线性表，要在内存中找一块地，于是这块地的第一个位置就非常关键，它是存储空间的起始位置。
接着，因为我们一共九个人，所以他需要占九个座。线性表中，我们估算这个线性表的最大存储容量，建立一个数组，数组的长度就是这个最大存储容量。
可现实中，我们宿舍总有那么几个不是很好学的人，为了游戏，为了恋爱，就不去图书馆自习了。假设我们九个人，去了六个，真正被使用的座位也就只是六个，另外三个是空的。同样的，我们已经有了起始的位置，也有了最大的容量，于是我们可以在里面增加数据了。随着数据的插入，我们线性表的长度开始变大，不过线性表的当前长度不能超过存储容量，即数组的长度。想想也是，如果我们有十个人，只占了九个座，自然是坐不下的。
来看线性表的顺序存储的结构代码。

文章图片
这里，我们就发现描述顺序存储结构需要三个属性：

存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度MaxSize。
线性表的当前长度：length。

3.4.3 数据长度与线性表长度区别
注意哦，这里有两个概念"数组的长度"和"线性表的长度"，需要区分一下。
数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。有个别同学可能会问，数组的大小一定不可以变吗？我怎么看到有书中谈到可以动态分配的一维数组。是的，一般高级语言，比如C、VB、C++都可以用编程手段实现动态分配数组，不过这会带来性能上的损耗。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
3.4.4 地址计算方法
由于我们数数都是从1开始数的，线性表的定义也不能免俗，起始也是1，可C语言中的数组却是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系（如图3.4.3所示）。

文章图片

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
其实，内存中的地址，就和图书馆或电影院里的座位一样，都是有编号的。存储器中的每个存储单元都有自己的编号，这个编号称为地址。当我们占座后，占座的第一个位置确定后，后面的位置都是可以计算的。试想一下，我是班级成绩第五名，我后面的10名同学成绩名次是多少呢？当然是6,7，...，15，因为5+1,5+2，...，5+10。由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是C个存储单元，那么线性表中第I+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

文章图片
所以对于第i个数据表元素ai的存储位置可以有a1推算得出：

文章图片

从图3-4-4来理解：

文章图片
那么通过这个公式，你可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用我们算法中学到的时间复杂度的概念来说，它的存取时间性能为:O(1)。我们通常吧具有这一特点的存储结构称为随机存取结构。
3.5 顺序存储结构的插入与删除
3.5.1 获得元素操作对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。来看代码：

文章图片

文章图片
注意这里返回值类型status是一个整型，返回OK代表1，ERROR代表0。之后代码中出现就不再详述。
3.5.2 插入操作刚才我们也谈到，这里的时间复杂度为O(1)。我们现在来考虑，如果我们要实现ListInsert(*L,i,e),即在线性表L中的第i个位置插入新元素e，应该如何操作？
举个例子，本来我们在春运时去买火车票，大家都排队排得好好的。这时来了一个美女，对着队伍中排在第三位的你说，"大哥，球球你帮帮忙，我家母亲有病，我得急着回去看她，这队伍这么长，你可否让我排在你的前面？"，你心一软，就同意了。这时，你必须得后退一步，否则她是没法进到队伍来的。这可不得了，后面的人像蠕虫一样，全部都得退一步。骂声四起。但后面的人也不清楚这加塞是怎么回事，没什么办法。

文章图片

插入算法的思路：

如果插入位置不合理，抛出异常；
如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置i处；
表长加1。

实现代码如下：

文章图片
应该说这代码不难理解。如果是以前学习其他语言的同学，可以考虑把它转换成你熟悉的语言再实现一遍，只要思路相同就可以了。
3.5.3 删除操作
接着刚才的例子。此时后面排队的人群意见都很大，都说怎么可以这样，不管什么原因，插队就是不行，有本事，找火车站开后门去。就在这时，远处跑来一胖子，对着这美女喊，可找到你了，你这骗子，还我钱。只见这女子二话不说，突然就冲出了队伍，胖子追在其后，消失在人群中。哦，原来她是倒卖火车票的黄牛，刚才还装可怜。于是排队的人群，又像蠕虫一样，均向前移动了一步，骂声渐息，队伍又恢复了平静。
这就是线性表的顺序存储结构删除元素的过程（如图3-5-2所示）。

文章图片

删除算法的思路：

如果删除位置不合理，抛出异常；
取出删除元素；
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
表长减1。

实现代码如下：

文章图片

文章图片

现在我们来分析一下，插入和删除的时间复杂度。

先来看最好的情况，如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素的，就如同来了一个新人要正常排队，当然是排在最后，如果此时他又不想排了，那么他一个人离开就好了，不影响任何人。
最坏的情况呢，如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度是多少呢？那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为O(n)。
至于平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要移动n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等，为(n-1)/2。

我们前面讨论过时间复杂度的推导，可以得出，平均时间复杂度还是O(n)。
这说明什么？线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。当然，它的优缺点还不只这些.....
3.5.4 线性表顺序存储结构的优缺点线性表的顺序存储结构的优缺点如图3-5-3所示。

文章图片
好了，大家休息一下，我们等会儿接着讲另外一个存储结构。
3.6 线性表的链式存储结构
3.6.1 顺序存储结构不足的解决办法前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢？
要解决这个问题，我们就得考虑一下导致这个问题的原因。
为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3，...，n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题旧出在这里。

A 同学思路：让当中每个元素之间都留有一个空位置，这样要插入时，就不至于移动。**可一个空位置如何解决多个相同位置插入数据的问题呢？**所以这个想法显然不行。
B 同学思路：那就让当中每个元素之间都留足够多的位置，根据实际情况制定空隙大小，比如10个，这样插入时，就不需要移动了。万一10个空位用完了，再考虑移动使得每个位置之间都有10个空位置。如果删除，就直接删掉，把位置留空即可。这样似乎暂时解决了插入和删除的移动数据问题，可这对于超过10个同位置数据的插入，效率上还是存在问题。对于数据的遍历，也会因为空位置太多而造成判断时间上的浪费。而且显然这里空间复杂度还增加了，因为每个元素之间都有若干个空位置。
C 同学思路：我们反正也是要让相邻元素留有足够余地，那干脆所有的元素都不要考虑相邻位置了，哪有空位就到哪里，而只是让每个元素知道它下一个元素的位置在哪里，这样，我们可以在第一个元素时，就知道第二个元素的位置（内存地址），而找到它；在第二个元素时，再找到第三个元素的位置（内存地址）。这样所有的元素我们就都可以通过遍历而找到。

好！太棒了，这个想法非常好！C同学，你可惜生晚了几十年，不然，你的想法对于数据结构来讲就是划时代的意义。我们要的就是这个思路。
3.6.2 线性表链式存储结构定义在解释这个思路之前，我们先来谈另一个话题。前几年，有一本书风靡了全世界，它叫《达.芬奇的密码》，成为世界上最畅销的小说之一，书的内容集合了侦探、惊悚和阴谋论等多种风格，很好看。
我由于看的时间太过于久远，情节都忘得差不多了，不过这本书和绝大部分侦探小说一样，都是同一种处理办法。那就是，作者不会让你事先知道整个过程的全部，而是在一步一步地到达某个环节，才根据现场的信息，获得或推断出下一步是什么，也就是说，每一步除了对侦破的信息进一步确认外（之前信息也不一定都是对的，有时就是证明某个信息不正确），还有就是对下一步如何操作或行动的指引。
不过，这个例子也不完全与线性表相符合。因为案件侦破的线索可能是错综复杂的，有点像我们之后要讲到的树和图的数据结构。今天我们要谈的是单线索，无分支的情况。即线性表的链式存储结构。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元是可以连续的饿，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任何位置（如图3-6-1所示）。

文章图片
以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
n个结点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,...,an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序连接在一起，如图3-6-2所示。

文章图片

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后续指针指向的位置。想象一下，最后一个结点，它的指针指向哪里？
最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为"空"（通常用NULL或"^"符号表示，如图3-6-3所示）。

文章图片

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如图3-6-4所示。

文章图片

3.6.3 头指针与头结点的异同头指针与头结点的异同点，如图3-6-5所示。

文章图片

3.6.4 线性表链式存储结构代码描述若线性表为空表，则头结点的指针域为"空"，如图3-6-6所示。

文章图片

这里我们大概地用图示表述了内存中单链表的存储状态。看着满图的省略号"....."，你就知道是多么不方便。而我们真正关心的：它是在内存中的实际位置吗？不是的，这只是它所表示的线性表中的数据元素及数据元素之间的逻辑关系。所以我们改用更方便的存储示意图来表示单链表，如图3-6-7所示。

文章图片

若带有头结点的单链表，则如图3-6-8所示。

文章图片

空链表如图3-6-9所示。

文章图片

单链表中，我们在C语言中可用结构指针来描述。

文章图片

从这个结构定义中，我们也就知道，结点由存放数据元素的数据域存放后继结点地址的指针域组成。
假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i+1个元素，即指向ai+1的指针。也就是说，如果p->data=https://www.it610.com/article/ai，那么p->next->data=https://www.it610.com/article/ai+1（如图3-6-10所示）。

文章图片

3.7 单链表的读取
在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪？没办法一开始就知道，必须的从头开始找。因此，对于单链表实现获取第i个元素的数据的caozuoGetElem，在算法上，相对要麻烦一些。
获得链表第i个数据的算法思路：

声明一个结点p指向链表第一个结点，初始化j从1开始；
当j
若到链表末尾p为空，则说明第i个元素不存在；
否则查找成功，返回结点p的数据。

实现代码算法如下：

文章图片

文章图片

说白了，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需要遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。
由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是"工作指针后移"，这其实也是很多算法的常用技术。
此时就有人说，这么麻烦，这数据结构有什么意思！还不如顺序存储结构呢。
哈，世间万物总是两面的，有好自然有不足，有差自然就有优势。下面我们来看一下单链表中是如何实现"插入"和"删除"。
3.8 单链表的插入与删除
3.8.1 单链表的插入先来看单链表的插入。假设存储元素e的结点为s，要实现结点p、p->next和s之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。可如何插入呢（如图3-8-1所示）？

文章图片

根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改变即可。

文章图片
解读这两句代码，也就是说让p的后继结点改为s的后继结点，再把结点s变成p的后继结点（如图3-8-2所示）。

文章图片

考虑一下，这两句的顺序可不可以交换？
如果先p->next=s; 再s->next=p->next；会怎么样？哈哈，因为此时第一句会使得将p->next给覆盖成s的地址了。那么s->next=p->next,其实就等于s->next=s。这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的，这点初学者一定要注意。
插入结点s后，链表如图3-8-3所示。

文章图片

对于单链表的表头和表尾的特殊情况，操作是相同的，如图3-8-4所示。

文章图片

单链表第i个数据插入结点的算法思路：

声明一结点p指向链表第一个结点，初始化j从1开始；
当j
若到链表末尾p为空，则说明第i个元素不存在；
否则查找成功，在系统中生成一个空结点s；
将数据元素e赋值给s->data。
单链表的插入标准语句s->next=p->next; p->next=s;
返回成功。在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放e数据s结点。

3.8.2 单链表的删除现在我们再来看单链表的删除。设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可，如图3-8-5所示。

文章图片

我们所要做的，实际上就是一步，p->next=p->next->next，用q来取代p->next，即是

文章图片
解读这两句代码，也就是说让p的后继的后继结点改为p的后继结点。有点拗口呀，那我再打个形象的比方。本来是爸爸左手牵着妈妈的手，右手牵着宝宝的手在马路边散步。突然迎面走来一美女，爸爸一下子看呆了，此情景被妈妈逮个正着，于是她生气地甩开牵着的爸爸的手，绕过他，扯开父子俩，拉起宝宝的左手就快步朝前走去。此时妈妈是p结点，妈妈的后继是爸爸p->next，也可以叫q结点，妈妈的后继的后继是儿子p->next->next，即q->next。当妈妈去牵儿子的手时，这个爸爸就已经与母子俩没有牵手联系了，如图3-8-6所示。

文章图片

单链表第i个数据删除结点的算法思路：

声明一结点p指向链表第一个结点，初始化j从1开始；
当j
若到链表末尾p为空，则说明第i个元素不存在；
否则查找成功，将欲删除的结点p->next赋值给q；
单链表的删除标准语句p->next=q->next；
将q结点中的数据赋值给e，作为返回；
释放q结点；
返回成功。

实现代码算法如下：

文章图片
这段算法代码里，我们又用到了另一个C语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。
分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实就是由两部分组成：第一部分就是遍历查找第i个元素；第二部分就是插入和删除元素。
从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是o(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。
3.9 单链表的整表创建
回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构**。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成**。
所以创建单链表的过程就是一个动态生成链表的过程。即从"空表"的初始状态起，依次建立各元素结点，并逐个插入链表。
单链表整表创建的算法思路：

声明一结点p和计数器变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
- 生成一新结点赋值给p；
- 随机生成一数字赋值给p的数据域p->data；
- 将p插入到头结点与前一新结点之间。

实现代码算法如下：

文章图片

文章图片

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法，如图3-9-1所示。

文章图片

可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。
实现代码算法如下：

文章图片

文章图片

注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。
这里需解释一下，r->next=p; 的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，如图3-9-2所示，当中(1)位置的连线就是表示这个意思。

文章图片

r->next=p; 这一句应该还好理解，我以前很多学生不理解的就是后面这一句r=p; 是什么意思？请看图3-9-3。

文章图片

它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai，所以应该要将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。
循环结束后，那么应该让这个链表的指针域置空，因此有了"r->next=NULL"，以便以后遍历时可以确认其是尾部。
3.10 单链表的整表删除
当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。
单链表整表删除的算法思路如下：

声明一结点p和q；
将第一个结点赋值给p；
循环：
- 将下一结点赋值给q；
- 释放p；
- 将q赋值给p。

实现代码算法如下：

文章图片

这段算法代码里，常见的错误就是有同学会觉得q变量没有存在的必要。在循环体内直接写free(p); p=p->next; 即可。可这样会带来什么问题？
要知道p是一个结点，它除了有数据域，还有指针域。你在做free(p)时，其实是在对它整个结点进行删除和内存释放的工作。这就好比皇帝快要病死了，却还没有册封太子。他儿子五六个，你说要是你脚一瞪倒是解脱了，这国家咋办，你那几个儿子咋办？这要是为了皇位，什么亲兄弟血肉情都成了浮云，一定会打起来。所以不行，皇帝不能马上死，得先把遗嘱写好，说清楚，哪个儿子做太子才行。而这个遗嘱就是变量q的作用，它使得下一个结点是谁得到了记录，以便于等当前结点释放后，把下一结点拿回来补充。明白了吗？
好了，说了这么多，我们可以来简单总结一下。
3.11 单链表结构与顺序存储结构优缺点
简单地对单链表结构和顺序存储结构做对比：

文章图片

通过上面的对比，我们可以得出一些经验性的结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如游戏开发中，对于用户注册得个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚，当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。

总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。
3.12 静态链表
其实C语言真是好东西，它具有的指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。后来的面向对象语言，如Java、C#等，虽不使用指针，但因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。但对于一些语言，如Basic、Fortran等早期的编程高级语言，由于没有指针，链表结构按照前面我们的讲法，它就没法实现了。怎么办呢？
有人就想出来用数组来代替指针，来描述单链表。真实不得不佩服他们的智慧，我们来看看他是怎么做到的。
首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。
我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。
为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

文章图片

文章图片

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为02.如图3-12-1所示。

文章图片

此时的图示相当于初始化的数组状态，见下面代码：

文章图片

假设我们已经将数据存入静态链表，比如分别存放着"甲"、"乙"、"丁"、"戌"、"已"、"庚"等数据，则它将处于如图3-12-2所示这种状态。

文章图片
此时"甲"这里就存有下一元素"乙"的游标2，"乙"则存有下一元素"丁"的下标3。而"庚"是最后一个有值元素，所以它的cur设置为0。而最后一个元素的cur则因"甲"是第一有值元素而存有它的下标为1。而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7。
3.12.1 静态链表的插入操作现在我们来看看如何实现元素的插入。
静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。
我们前面说过，在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

文章图片

这段代码有意思，一方面它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标。从上面的图示例子来看，其实就是返回7.
那么既然下标为7的分量准备要使用了，就得有接替者，所以就把分量7的cur值赋值给头元素，也就是把8给space[0].cur，之后就可以继续分配新的空闲分量，实现类似malloc()函数的作用。
现在我们如果需要在"乙"和"丁"之间，插入一个值为"丙"的元素，按照以前顺序存储结构的做法，应该要把"丁"、"戌"、"庚"这些元素都往后移一位。但目前不需要，因为我们有了新的手段。
新元素"丙"，想插队是吧？可以，你先悄悄地在队伍最后一排第7个游标位置待着。我一会就能帮你搞定。我接着找到了"乙"，告诉他，你的cur不是游标为3的"丁"了，这点小钱，意思意思，你把你的下一位的游标改为7就可以了。"乙"叹了口气，收了钱把cur值改了。此时再回到"丙"那里，说你把你的cur改为3。就这样，在绝大多数人都不知道的情况下，整个排队的次序发生了改变（如图3-12-3所示）。
实现代码如下，代码左侧数字为行号。

文章图片

当我们执行插入语句时，我们的目的是要在"乙"和"丁"之间插入"丙"。调用代码时，输入i值为3.
第4行让k=MAX_SIZE-1=999.
第7行，j=Malloc——SSL（L）=7.此时下标为0的cur也因为7要被占用而更改备用链表的值为8。
第11~12行，for循环1由1到2.执行两次。代码k=L[2].cur=3.这就是刚才我说的让"丙"把它的cur改为3的意思。
第14行，L[k].cur = j; 意思就是L[2].cur=7。也就是让"乙"得点好处，把它的cur改为指向"丙"的下标7。

就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作（如图3-12-3所示）。没理解可能觉得有些复杂，理解了，也就那么回事。

文章图片

3.12.2 静态链表的删除操作
故事没完，接着，排在第一个的甲突然接到一电话，看着很急，多半不是家里有紧急情况，就是单位有突发状况，反正稍有犹豫之后就急匆匆离开。这意味着第一位空出来了，那么自然刚才那个收了好处的乙就成了第一位--有人走运起来，喝水都长肉。
和前面一样，删除元素时，原来是需要释放结点的函数free()。现在我们也得自己实现它：

文章图片

文章图片

有了刚才的基础，这段代码就很容易理解了。前面代码都一样，for循环因为i=1而不操作，j=k[999].cur=1, L[k].cur=L[j].cur 也就是L[999].cur=L[1].cur=2。这其实就是告诉计算机现在"甲"已经离开了，"乙"才是第一个元素。Free_SSL（L,j）; 是什么意思呢？来看代码：

文章图片

意思就是"甲"现在要走，这个位置就空出来了，也就是，未来如果有新人来，最优先考虑这里，所以原来的第一个空位分量，即下标是8的分量，它降级了，把8给"甲"所在下标为1的分量的cur，也就是space[1].cur=space[0].cur=8，而space[0].cur=k=1 其实就是让这个删除的位置成为第一个优先空位，把它存入第一个元素的cur中，如图3-12-4所示。

文章图片
当然，静态链表也有相应的其他操作的相关实现。比如我们代码中的ListLength就是一个，来看代码。

文章图片
另外一些操作和线性表的基本操作相同，实现上也不复杂，我们在课堂上就不讲解了。
3.12.3 静态链表优缺点
总结一下静态链表的优缺点(见图3-12-5)：

文章图片
总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。
3.13 循环链表
在做的各位都很年轻，不会觉得日月如梭。可上了点年纪的人，比如我-的父辈们，就常常感慨，要是可以回到从前该多好。网上也盛传，所谓的成功男人就是3岁时不尿裤子，3岁能自己吃饭...80岁能自己吃饭，90岁能不尿裤子。

文章图片

对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就像我们刚才说的，不能回到从前。
比如，你是一业务员。家在上海。需要经常出差，行程就是上海到北京一路上的城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务，如图3-13-2所示。

文章图片

有一次，你先到南京开会，接下来要对以上的城市走一遍，此时有人对你说，不行，你得从上海开始，因为上海是第一站。你会对这人说什么？神经病。哪有这么傻的，直接回上海根本没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链表，这都是原来的单链表结构解决不了的问题。
事实上，把北京和上海之间连起来，形成一个环就解决了前面所面临的困难。这就是我们现在要将的循环链表。
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。
从刚才的例子，可以总结出，循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。
为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如图 3-13-3所示：

文章图片

对于非空的循环链表就如图3-13-4所示。

文章图片

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。
在单链表中，我们有了头结点时，我们可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描一遍。
有没有可能用O(1)的时间由链表指针访问到最后一个结点呢？当然可以。
不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表（如图3-13-5所示），此时查找开始结点和终端结点都很方便了。

文章图片

从上图中可以看到，终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点，其实就是rear->next->next，其时间复杂也为O(1)。
举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB，如图3-13-6所示。

文章图片

要想把它们合并，只需要如下的操作即可，如图3-13-7所示。

文章图片

文章图片

3.14 双向链表
继续我们刚才的例子，你平时都是从上海一路停留到北京的，可是这一次，你得先到北京开会，谁叫北京是首都呢，会就是多。开完会后，你需要例行公事，走访各个城市，此时你怎么办？

文章图片

有人又出主意了，你可以先飞回上海，一路再乘火车走遍这几个城市，到了北京后，你再飞回上海。
你会感慨，人生中为什么总会有这样出馊主意的人存在呢？真要气死人才行。哪来这么麻烦，我一路从北京坐火车或汽车回去不就完了吗。

文章图片

对呀，其实生活中类似的小智慧比比皆是，并不会那么的死板教条。我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗？当然可以，只不过需要加点东西而已。
我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1)。可以入股我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。
为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继。另一个指向直接前驱。

文章图片

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。
双向链表的循环带头结点的空链表如图3-14-3所示。

文章图片

非空的循环的带头结点的双向链表如图3-14-4所示。

文章图片

由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是谁？当然还是它自己。它的前驱的后继自然也是它自己，即：

文章图片
这就如同上海的下一站是苏州，那么上海的下一站的前一站是哪里？哈哈，有点废话的感觉。
双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength，查找元素的GertElem，获取元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。
就像人生一样，想享乐就得先努力，欲收获就得付代价。双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。
插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。
我们现在假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间需要下面几步，如图3-14-5所示。

文章图片

文章图片

关键在于它们的顺序，由于第2步和第3步都用到了p->next。如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后是解决前结点的后继。
如果插入操作理解了，那么删除操作，就比较简单了。
若要删除结点p，只需要下面两步骤，如图3-14-6所示。

文章图片

文章图片

好了，简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟它多了prior指针。对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多一些的。不过，由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。
3.15总结回顾
这一章，我们主要讲的是线性表。
先谈了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型，如它的一些基本操作。
之后我们就线性表的两大结构做了讲述。先讲的是比较容易的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。
后来是我们的重点，有顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式，比如单链表、循环链表和双向链表做了讲解，另外我们还讲了若不使用指针如何处理链表结构的静态链表方法。
总的来说，线性表的这两种结构（如图3-15-1所示）其实是后面其他数据结构的基础，把它们学明白了，对后面的学习有着至关重要的作用。

文章图片

3.16 结尾语
知道为什么河里钓起来的鱼要比鱼塘里养的鱼好吃吗？因为鱼塘里的鱼，天天有人喂，没有天敌追，就等着养肥给人吃，一天到晚游快游慢都一样，身上鱼肉不多，鱼油不少。而河里的鱼，为了吃饱，为了避免被更大的鱼吃掉，它必须要不断地游，这样生存下来的鱼，那鱼肉吃起来自然有营养、爽口。
五六十年代出生的人，应该也就是我们父母那一辈，当年计划经济制度下，他们的生活都被社会安排好了，先科员再科长、后处长再局长，混到哪算哪；学徒、技工、高级技工；教室、中级教师、高级教师，总之无论哪个行业都论资排辈。这样的生活如何让人奋发努力，所以经济发展缓慢。就像我们的线性表的顺序存储结构一样，位置是排好的，一切都得慢慢来。
可见，舒适环境是很难培养出坚强品格，被安排好的人生，也很难做出伟大事业。
市场经济社会下，机会就大多了，你可以从社会的任何一个位置开始起步，只要你真有决心，没有人可以拦着你。事实也证明，无论出身是什么，之前是凄苦还是富足，都有出人头地的一天。当然，这也就意味着，面临的竞争也是空前激烈的，一不小心，你的位置就可能被人插足，甚至就得out出局。这也多像我们线性表的链式存储结构，任何位置都可以插入和删除。
不怕苦，吃苦半辈子，怕吃苦，吃苦一辈子。如果你觉得上学读书是受罪，假设你可以活到80岁，其实你最多也就吃了20年苦。用人生四分之一的时间来换取其余时间的幸福生活，这点苦不算啥。再说了，跟着我学习，这也能算是吃苦？
好了，今天课就到这，下课。
【数据结构与算法|大话数据结构读书笔记系列（三）线性表】转载于:https://my.oschina.net/u/2484728/blog/1817510