数据结构与算法 - 线性表

线性表 是具有线性结构特点、最简单且最常用的一种数据结构。         线性表 ( Linear List) 是具有相同特性的数据元素组成的一个有限序列。其元素可以是整数、字符等简单数据，也可以是由多个数据项组成的复合形式，甚至可以是一页书或其他更复杂的信息。         例如，由26个大写英文字母组成的字母表(A，B，C，…，x，Y，Z)就是一个线性表，表中的每个数据元素均是一个大写字母。再如，某高校1990年以来拥有的副教授以上职称的教师个数(48,64,77,93,112,136,167，…,235)也是一个线性表，表中的每个数据元素均是一个正整数。这两个线性表都是包含简单数据元素的例子。         线性表 中的数据元素可以是多种形式的，但是，对于同一个线性表，其数据元素必须具有同一种形式，也就是说，同一线性表中的数据元素必须同属一个数据对象集合，表中相邻的数据元素之间存在某种序偶关系。

线性结构 特点： 在数据元素的非空有限集合中，存在唯一的一个称为“第一个”的数据元素(头结点)；存在唯一的一个“最后一个”的数据元素(末结点)除第一个外，集合中的每个数据元素都只有一个直接前驱；除最后一个外，集合中的每个数据元素都只有一个直接后继。

二、顺序表

顺序表 是指用一组地址连续的存储单元依次存储线性表中的数据元素的线性表 。因为这种方式与高级程序设计语言中一维数组的表示和实现相一致，所以也称为数组表示法。采用顺序表表示的线性表，表中逻辑位置相邻的数据元素将存放到存储器中物理地址相邻的存储单元之中，表中元素的逻辑关系与存储顺序(物理关系)相符，换言之，顺序表中数据元素的逻辑关系是以其在存储结构中的物理(位置)关系来表示的。         因此，在顺序表中，可以根据顺序表中数据元素的位序，随机访问表中的任一元素，即顺序表是一种随机存取的存储结构。

• 2.1、 顺序表的插入

顺序表的插入是指在顺序表的第i-1个元素和第i个元素之间插入一个新的元素，此时顺序表中插入位置前后元素之间的逻辑关系发生变化，因此除非插入位置是当前表中的最后一个元素之后，否则必须通过顺序移动数据元素的存储位置才能实现。插入过程示意图如图所示：

顺序表的插入算法时间耗费主要是元素的移动，移动元素的个数取决于插入位置。 最好情况，插入位置在顺序表表尾，无须移动元素；最坏情况是在第一个位置插入，需要移动n个元素。在长度为n的顺序表i位置前插入一个元素，需要移动n-i+1个元素，可以以有n+1个插入位置，在插入位置等概率条件下，插入一个元素的平均移动次数为1/(n+1)*∑(n-i+1)=n/2，因此算法的时间复杂度为O(n)。 注意：∑(n-i+1)表示下标是i=1，上标是n+1的求和表达式。

• 2.2、顺序表的删除

顺序表的删除和插入的过程类似，需要移动删除元素后面的所有元素存储位置。过程如图所示：

同插入算法一样，删除算法时间主要消耗在元素的移动。最好情况，删除位置在顺序表末尾，无须移动元素；最坏情况，删除位置是第一个元素，需要移动n-1个元素。在长度为n的顺序表的i位置删除元素，需要移动n-i个元素，在删除位置等概率条件下，删除一个元素的平均移动次数为1/n*∑(n-i)=(n-1)/2，因此算法的时间复杂度为O(n)。 注意：∑(n-i)表示下标是i=1，上标是n+1的求和表达式。

• 2.3、顺序表的特点

顺序表的特点是以“存储位置相邻”表示两个元素之间的前驱后继关系。顺序表的优点是可以随机存取表中任意一个元素。其主要缺点一是容易产生存储空间的浪费；二是每做一次插入或删除操作时，平均来说必须移动表中一半元素。因此，顺序表经常主要应用于为查询而很少做插入和删除操作、表长变化不大的线性表。

三、链表

所谓 链表 ，就是指采用链式存储结构表示和实现的线性表。         链表的特点是采用一组任意的存储单元来存放线性表中的数据元素，这些存储单元可以是连续的，也可以是不连续的。 在链表中，数据元素之间的逻辑关系并不依赖其对应的存储地址，而是通过设置专门用于指示数据元素之间逻辑关系的指针来描述。         因此，在链表中的每个数据元素是由用于存放代表其本身信息的数据域和用于存放指示数据元素之间逻辑关系的指针域两部分组成的，数据元素的这种特殊存储方式，称为 结点(Node) 。         根据链表结点中包含指针域的指针个数、指针指向和连接方式，可将链表分为 线性链表、循环链表、双向链表、多重链表、十字链表、二叉链表、邻接表、邻接多重表 等，其中线性链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式则用于实现扩展线性结构(数组和广义表等)或非线性结构(树、图等)。

• 3.1、线性链表(单链表)

线性链表也称 单链表 ，在每个结点中只包含一个指针，用于指示该结点的直接后继结点，整个链表通过指针相连，最后一个节点因为没有后集结点，其指针置为空NUll。结构示意图如上图所示。

3.1.1、单链表的插入

线性链表的插入是指在线性链表的第-1个结点和第i个结点之间插入一个新的结点，此时，线性链表中插入位置前后结点之间的逻辑关系发生变化，因此除非插入位置是当前表中的最后一个结点之后，否则必须通过同时修改插入位置之前结点和当前插入结点的指针指向才能实现。         线性链表的插入无须移动元素，插入算法的基本步骤如下图所示：         (1)寻找插入位置，即第i-1个结点的位置。         (2)申请结点存储空间，生成新结点。         (3)修改第-1个结点和新结点指针域，将新结点链接在链表中。

线性链表的插入算法时间主要消耗在寻找插入位置上，需要从链表头指针开始依次访问结点，直到找到插入位置，因此算法的时间复杂度为O(n)。

3.1.2、单链表的删除

线性链表的删除是指删除线性链表的第i个结点，此时，线性链表中删除位置前后结点之间的逻辑关系发生变化，因此必须通过修改删除位置之前结点的指针指向才能实现。删除过程示意图，如上。         同插入结点一样，删除过程首先寻找要删除结点的前一个结点位置，再通过修改结点指针域完成删除操作。 因此算法的时间复杂度为也O(n)。

• 3.2、循环链表(单向)

在线性链表中，最后一个结点的指针指向NULL，表示该线性链表的结束。如果把表尾结点的指针改为指向该链表的第一个结点，则整个线性链表构成一个闭合的回路，称这种头尾相连的线性链表形式为 循环链表 。         整个链表就像一条单向环形的公交线路，人们可以从线路中的任一站点出发到达整个线路的其他站点。插入和删除的时间复杂度也为O(n)，循环链表存储结构示意图如下：

• 3.3、双向链表

如果在线性链表的结点中增加一个指针域，用来指向结点的直接前驱，则从表中的任一结点出发，既可以向后查找结点的后继，也可以向前查找结点的前驱。整个链表包含分别指向前驱和后继的两条链，称为 双向链表 。双向链表的存储结构示意如图：

• 3.4、双向循环链表

使双向链表中的两条链均构成闭合回路，则形成 双向循环链表 。双向循环链表结构示意图以及插入和删除过程示意图如下：

• 3.5、链表的特点

链表的特点是以“指针”指示其后继元素，链表中的元素可以存储在任意一组存储单元中。因此，链表的优点是无须预先估计线性表的大小，节省存储开销，且做插入、删除操作时，无须移动元素；其主要缺点是无论链表做插入、删除还是查找，均需要从链表的起始位置开始，链表不具备随机存取的特性。

四、栈

栈是一种操作受限的线性表，上面提到的顺序表和链表可以在表的两端和表内进行插入删除操作，而 栈仅允许在一端(栈顶)进行插入删除操作 ，也就是进(入)栈和出栈操作，栈顶是栈读取数据的唯一入口，操作遵循“ 先进后出(LIFO) ”的原则。例如Object-C中的导航控制器就是用栈的特性实现的。

根据存储结构的不同，也可以把栈分为 顺序栈 和 链栈 两种存储结构。

• 4.1、顺序栈

栈的顺序存储也称为顺序栈，它利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时附设栈顶标识top来指示栈顶元素在顺序栈中的位置。顺序栈的入栈和出栈操作结构示意图如图所示：

• 4.2、链栈

栈的链式存储也称为链栈，它和链表的存储原理一样，都可以利用闲散空间来存储元素，用指针来建立各结点之间的逻辑关系。链栈也会设置一个栈顶元素的标识符top，称为栈顶指针。链栈的入栈和出栈操作结构示意图如图所示

五、队列

队列是也一种操作受限的线性表，但队列和栈不同， 队列只允许在一端(队尾)进行插入(入队)操作 ，在另一端(队头)进行删除(出队)操作，操作遵循的是“ 先进先出(FIFO) ”原则。         队列中会有一个指针指向队头，这个指针称为 队头指针front 。当有元素出队时，队头指针向后移动,指向下一个元素，下一个元素成为新的队头元素(类似于栈的栈顶指针)；队列中也会有一个指针指向队尾，称为 队尾指针rear ，队尾指针是指向最后一个元素之后的一个空指针。当有元素需要入队时，就插入到队尾指针所指位置处，插入之后，队尾指针向后移动，指向下一个空位。当队列已满时，元素不能再入队；同理，当队列为空，无法执行出队操作。

根据存储结构的不同，也可以把队列分为 顺序队列 和 链式队列 两种存储结构。

• 5.1、顺序队列

使用顺序表实现的队列称作 顺序队列 。顺序队列的实现和顺序表的实现相似，只是在顺序队列中只允许在一端进行插入，在另一端进行删除。定义两个变量 front与rear分别标识队头与队尾，当删除队头元素时， front后移到下一个位置；当插入新元素时，在rear指示的位置插入，插入后，rear向后移动指向下一个存储位置。顺序队列的出入队操作示意图如下：

• 注意 ：队列的“假溢出”

在顺序队列的存储过程中，可能出现“溢出”现象，队列的“溢出”有两种情况，一种真“溢出”，另一种为假“溢出“。         所谓 真“溢出” 是指当队列分配的空间已满，此时再往里存储元素则会出现“溢出”，这种“溢出”是真的再无空间来存储元素，是真“溢出”；而 假“溢出” 是指队列尚有空间而出现的“溢出”情况。当 front端有元素出队时， front向后移动；当rear端有元素入队时，rear向后移动，若rear已指到队列中下标最大的位置，此时虽然 front前面有空间，但再有元素入队也会出现“溢出”，这种“溢出”叫作“假溢出”，示意图如下。         解决“假溢出”有两种方法。一是采用“移动队列”的方法，即每当执行一次出队操作，则依次将队头和队尾指针向数组的起始位置移动，始终保持队头在数组的起始位置，这种方法的代价是产生大量的元素移动，显然不是一个好方法；另一种方法就更合理高效了，就是采用5.2循环队列。

• 5.2、循环队列

为了解决顺序队列中的假“溢出”现象，充分利用数组的存储空间，可以将顺序队列的头尾相连，构成一个 循环队列 ，循环队列一般都是用数组来实现的。将循环队列假想为一个环状的空间，如下图所示。         在循环队列中， front与rear都是可以循环移动的，当队空时， front=rear成立；当队满时， front=rear也成立。因此显然不能只凭 front=rear来判断队空还是队满。         为了解决这个问题，在循环队列中有一个约定：少用一个元素空间，当队尾标识的rear在队头标识front的上一个位置时，队列为满。此时，判断队空和队满的条件分别如下：         队空时： front==rear为真。         队满时：(rear+1)% MAXSIZE== front为真 ( MAXSIZE是队列容量的大小）。         循环队列中ront和rear的移动不再是简单的加1，因为是循环的，可能原本指在末尾，前进一个单位就是又一个循环的开始，所以每次移动都要对队列容量 MAXSIZE取模：front = (front +1)% MAXSIZE，rear = (rear+1)% MAXSIZE。         在循环队列中，求队列的长度也不仅仅是rear与ront相减这么简单，因为，rear的值有可能比front小，这样的相减结果是负值，显然不对。在求循环队列的长度时，都是用rear加上队列容量，减去 front的值后，再对容量取模：(rear+ MAXSIZE- front)% MAXSIZE。

• 5.3、链式队列

用链表来实现的队列也称为 链式队列 ，在链式队列中也用指针 front与rear分别指示队头与队尾，在队头 front处删除元素，在队尾rear处插入元素。与顺序队列不同，链式队列的rear指针指向最后一个元素。链式队列的结构和出入队操作示意图如下：

注：文中的图片均转摘自网络