第2章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表 第2章 线性表 2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表 2.7 面向对象的软件设计方法

本章主要知识点： 线性表的定义，顺序存储结构，链式存储结构 顺序表类的设计方法，顺序表插入和删除操作的实现方法，顺序表插入和删除操作的时间复杂度 单链表类的设计方法，单链表插入和删除操作的实现方法，单链表插入和删除操作的时间复杂度，顺序表和单链表的特点对比 循环单链表和循环双向链表的结构和特点

2.1 线性表 2.1.1 线性表的定义 如果一个数据元素序列满足： 2.1 线性表 2.1.1 线性表的定义 如果一个数据元素序列满足： （1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素； （2）第一个数据元素没有前驱数据元素； （3）最后一个数据元素没有后继数据元素。 则称这样的数据结构为线性结构。

线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n（n ≥ 0）个相同类型数据元素a0, a1, a2, 线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n（n ≥ 0）个相同类型数据元素a0, a1, a2, ..., an-1组成的线性结构。 一个有n个数据元素a0, a1, a2, ..., an-1的线性表通常用符号（a0, a1, a2, ..., an-1）表示，其中符号ai（0≤i≤n-1）表示第i个抽象数据元素。空线性表用符号（）表示。

2.1.2 线性表抽象数据类型 数据集合 线性表的数据元素集合可以表示为序列a0, a1, a2, ..., an-1，每个数据元素的数据类型可以是任意的类类型。 操作集合 （1）求当前数据元素个数length() （2）插入数据元素insert(i, obj) （3）删除数据元素delete(i) （4）取数据元素getData(i) （5）线性表是否空isEmpty()

2.2 顺序表 顺序存储结构的线性表称作顺序表。 2.2.1 顺序表存储结构 实现顺序存储结构的方法是使用数组。 对于线性表，数组把线性表的数据元素存储在一块连续地址空间的内存单元中。这样线性表中，逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。

顺序表的存储结构如图所示。 其中，a0,a1,a2等表示顺序表中存储的数据元素，listArray表示存储数据元素的数组，maxSize表示数组的最大允许数据元素个数，size表示数组的当前数据元素个数。

2.2.2 顺序表类 类包含成员变量和成员函数。成员变量用来表示抽象数据类型中定义的数据集合，成员函数用来表示抽象数据类型中定义的操作集合。顺序表类实现接口List。顺序表类的public成员函数主要是接口List中定义的成员函数。

2.2.3 顺序表的效率分析 插入和删除是顺序表中时间复杂度最高的成员函数。 插入时，主要的耗时部分是循环移动数据元素部分。 循环移动数据元素的效率和插入的位置i有关，最坏情况是i = 0，需移动size个数据元素；最好情况是i = size，需移动0个数据元素。平均次数为：

类似地，删除时，平均次数为：

　　顺序表中的其余操作都和数据元素个数n无关，因此在顺序表中插入和删除一个数据元素成员函数的时间复杂度为O（n）。 　　顺序表的主要优点是：支持随机读取，以及内存空间利用效率高。 　　顺序表的主要缺点是：需要预先给出（很难准确）数组的最大数据元素个数，另外，插入和删除操作时需要移动较多的数据元素。

2.3 单链表 指针表示一个数据元素逻辑意义上的存储位置。 链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为一个结点。 2.3 　单链表 　　指针表示一个数据元素逻辑意义上的存储位置。 　　链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为一个结点。 　　链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。 　　链式存储结构的线性表称为链表。 　　根据结点构造链的方法不同，链表主要有单链表、单循环链表和循环双向链表三种。这样，一个数据元素集就可以用链式存储结构来存储。

2.3.1 　单链表的结构 　　　单链表是构成链表的每个结点只有一个指向直接后继结点的指针。 　1 单链表的表示方法 　单链表中每个结点的结构：

　　单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。 （a）空链；　（b）非空链

2　 带头结点单链表和不带头结点单链表的比较 　　　从线性表的定义可知，线性表要求允许在任意位置进行插入和删除。当选用带头结点的单链表时，插入和删除操作的实现方法比不用带头结点单链表的实现方法简单。 　　　设头指针用head表示，在单链表中任意结点（但不是第一个数据元素结点）前插入一个新结点的方法如图2-6所示。算法实现时，首先把插入位置定位在要插入结点的前一个结点位置，然后把s表示的新结点插入单链表中。

在单链表非第一个结点前插入结点过程 　　要在第一个数据元素结点前插入一个新结点，若采用不带头结点的单链表结构，则结点插入后，头指针head就要等于新插入结点s，这和在非第一个数据元素结点前插入结点时的情况不同。另外，还有一些不同情况需要考虑。因此，算法对这两种情况就要分别设计实现方法。

图在带头结点单链表第一个结点前插入结点过程 　　而如果采用带头结点的单链表结构，算法实现时，p指向头结点，改变的是p指针的next指针的值，而头指针head的值不变。因此，算法实现方法比较简单。在带头结点单链表中第一个数据元素结点前插入一个新结点的过程如图所示。 图在带头结点单链表第一个结点前插入结点过程

2.3.2 结点类 　　　单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。 2.3.3 单链表类 　　　单链表类的成员变量至少要有两个：一个是头指针，另一个是单链表中的数据元素个数。但是，如果再增加一个表示单链表当前结点位置的成员变量，则有些成员函数的设计将更加方便。

2.3.4 单链表的效率分析 　　在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：

删除单链表的一个数据元素时比较数据元素的平均次数为： 　　删除单链表的一个数据元素时比较数据元素的平均次数为： 因此，单链表插入和删除操作的时间复杂度均为O（n）。另外，单链表取数据元素操作的时间复杂度也为O（n）。

2.3.5 　顺序表和单链表的比较 　顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。 　和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。 　单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为O（1）。

2.4 　循环单链表 　　循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。

　　和单链表相同，循环单链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作时，算法实现较为方便。 带头结点的循环单链表结构如下： （a）空链表；（b）非空链表

　　带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于： 　　（1）在构造函数中，要加一条head.next = head 语句，把初始时的带头结点的循环单链表设计成图2-11 （a）所示的状态。 　　（2）在index(i)成员函数中，把循环结束判断条件current != null改为current != head。

2.5 　双向链表 　　双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用。

　在双向链表中，每个结点包括三个域，分别是element域、next域和prior域，其中element域为数据元素域，next域为指向后继结点的对象引用，prior域为指向前驱结点的对象引用。图2-12为双向链表结点的图示结构。 　双向链表结点的图示结构

　图2-13是带头结点的循环双向链表的图示结构。从图2-13可见，循环双向链表的next和prior各自构成自己的循环单链表。 （a）空链表；（b）非空链表

在双向链表中，有如下关系：设对象引用p表示双向链表中的第i个结点，则p. next表示第i+1个结点，p. next 　　　在双向链表中，有如下关系：设对象引用p表示双向链表中的第i个结点，则p.next表示第i+1个结点，p.next.prior仍表示第i个结点，即p.next.prior == p；同样地，p.prior表示第i-1个结点，p.prior.next仍表示第i个结点，即p.prior.next == p。图2-14是双向链表上述关系的图示。 图2-14　双向链表的关系

　　循环双向链表的插入过程如图2-15所示。图中的指针p表示要插入结点的位置，s表示要插入的结点，①、②、③、④表示实现插入过程的步骤。 图2-15 　循环双向链表的插入过程

　循环双向链表的删除过程如图2-16所示。图中的指针p表示要插入结点的位置，①、②表示实现删除过程的步骤。 　 循环双向链表的删除过程

2.6　仿真链表 　　　在链式存储结构中，我们实现数据元素之间的次序关系依靠指针。我们也可以用数组来构造仿真链表。方法是在数组中增加一个（或两个）int类型的变量域，这些变量用来表示后一个（或前一个）数据元素在数组中的下标。我们把这些int类型变量构造的指针称为仿真指针。这样，就可以用仿真指针构造仿真的单链表（或仿真的双向链表）。

（a）常规单链表；（b）仿真单链表一；（c）仿真单链表二

2.7　 面向对象的软件设计方法 面向对象软件设计方法是一种和人类认识事物、分析事物方法一致的软件设计方法。不仅如此，面向对象设计方法的模块化软件、数据封装、信息隐藏等特点，还可以使软件设计可以像其他工业产品一样，可以大规模协作开发。 模块化软件设计的基本思想是：把基础软件设计成可重复使用的模块，这些模块提供外部调用的接口，其他程序通过接口使用这些基础软件模块。这样，软件工业将摆脱了小作坊工作方式，像现代的其他工业一样，可以进行大规模的协作生产或开发。