数据结构——线性表（2）

上接 数据结构——线性表（1） 上文中介绍了线性表的顺序存储结构和单链表的介绍与代码实现，接下来，继续介绍线性表的链式存储

循环链表

  在座的各位都很年轻，不会觉得日月如梭。可上了点年纪的人，比如我——的父辈们，就常常感慨，要是可以回到从前该多好。网上也盛传，所谓的成功男人就是3岁时不尿裤子，5岁能自己吃饭……80岁能自己吃饭，90岁能不尿裤子。——《大话数据结构》   对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就像我们刚才说的，不能回到从前。   比如，你是一业务员，家在上海。需要经常出差，行程就是上海到北京一路上的城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务，如图。

在这里插入图片描述

  有一次，你先到南京开会，接下来要对以上的城市走一遍，此时有人对你说，不行，你得从上海开始，因为上海是第一站。你会对这人说什么?神经病。哪有这么傻的，直接回上海根本没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链表，这都是原来的单链表结构解决不了的问题。   事实上，把北京和上海之间连起来，形成一个环就解决了前面所面临的困难。这就是我们现在要讲的循环链表。   将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（ circuar linkedlist)。   从刚才的例子，可以总结出，循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。   其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p-> next 不等于头结点，则循环未结束。

双向链表

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

  我们在单链表中，有了next 指针，这就使得我们要查找下一结点的时间复杂度为0(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是0(n)了，因为我们每次都要从头开始遍历查找。   为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。双向链表( double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继,另一个指向直接前驱。

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

总结回顾

  这两篇文章，我们主要讲的是线性表。   先谈了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型，如它的一些基本操作。 之后我们就线性表的两大结构做了讲述，先讲的是比较容易的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。   后来是我们的重点，由顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式，如单链表、循环链表和双向链表做了讲解。   总的来说，线性表的这两种结构其实是后面其他数据结构的基础，把它们学明白了，对后面的学习有着至关重要的作用。

********************************************************

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

推荐大家读一读

点击下载大话数据结构PDF. 提取码：

y6s5