1.1.2 线性表

本节主要考查线性表的基本概念，以及线性表的顺序存储方式。

1.线性表概述

线性表是一种常用的数据结构。

在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。

线性表是一个线性结构，它是一个含有n（n≥0）个节点的有限序列，对于其中的节点，有且仅有一个开始节点没有前驱（前件）节点但有一个后继（后件）节点，有且仅有一个终端节点没有后继节点但有一个前驱节点，其他的节点都有且仅有一个前驱节点和一个后继节点。一般来说，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始节点，kn是终端节点。

线性结构的基本特征如下：

1）集合中必存在唯一的一个“第一元素”。

2）集合中必存在唯一的一个“最后元素”。

3）除最后一个元素之外，每个元素均有唯一的后继。

4）除第一个元素之外，每个元素均有唯一的前驱。

由n（n≥0）个数据元素（节点）a1,a2,…,an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表。常常将非空的线性表（n>0）记作：（a1,a2,…,an）。

2.线性表的顺序存储

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储又叫作顺序表。

（1）线性表的顺序存储基本概念

线性表的顺序存储结构具备以下两个基本特征：

1）线性表中的所有元素所占的存储空间是连续的。

2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设线性表的每个元素需要占用k个存储单元，并且所占的存储位置ADR（ai+1）和第i个数据元素的存储位置ADR（ai）之间满足下列关系：

ADR（ai+1）=ADR（ai）+k

线性表第i个元素ai的存储位置为：

ADR（ai）=ADR（a1）+（i-1）×k

公式中ADR（a1）是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基址。

在C语言中，通常定义一个一维数组来表示线性表的顺序存储空间，如图1-1所示。

在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。

在线性表的顺序存储结构下，可以对线性表做以下运算：

1）在线性表的指定位置处加入一个新的元素（即线性表的插入）。

2）在线性表中删除指定的元素（即线性表的删除）。

3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）。

4）对线性表中的元素进行排序（即线性表的排序）。

5）将一个线性表分解成多个线性表（即线性表的分解）。

6）将多个线性表合并成一个线性表（即线性表的合并）。

7）复制一个线性表（即线性表的复制）。

8）逆转一个线性表（即线性表的逆转）。

（2）顺序表的基本操作

顺序表的基本操作包括插入运算和删除运算。

1）顺序表的插入运算：线性表的插入运算是指在表的第i（1≤i≤n+l）个位置上，插入一个新节点x，使长度为n的线性表（a1,…,ai-1,ai,…,an）变成长度为n+1的线性表（a1,…,ai-1,x,ai,…,an+1）。

现在分析算法的复杂度。设它的值为n。该算法的时间主要花费在循环节点后移语句上，该语句的执行次数（即移动节点的次数）是n-i+1。由此可看出，所需移动节点的次数不仅依赖于表的长度，而且还与插入位置有关。

当i=n+1时，由于循环变量的终值大于初值，节点后移语句将不执行。这是最好的情况，其时间复杂度为O（1）。

当i=1时，节点后移语句将循环执行n次，需移动表中所有节点。这是最坏的情况，其时间复杂度为O（n）。

综合以上的情况，得出算法的平均时间复杂度为O（n）。

2）顺序表的删除运算：线性表的删除运算是指将表的第i（1≤i≤n）个节点删除，使长度为n的线性表（a1,…,ai-1,ai,ai+1,…,an）变成长度为n-l的线性表（a1,…,ai-1,ai+1,…,an-1）。

该算法的时间分析与插入算法相似，节点的移动次数也是由表长n和位置i决定的。

若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动节点。

若i=1，则前移语句将循环执行n-1次，需移动表中除开始节点外的所有节点。这两种情况下算法的时间复杂度分别为O（1）和O（n）。

综合以上的情况得出，在顺序表上做删除运算，平均要移动表中约一半的节点，平均时间复杂度也是O（n）。