下载掌阅APP，畅读海量书库
立即打开
本节主要考查线性表的基本概念，以及线性表的顺序存储方式。
线性表是一种常用的数据结构。
在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。
线性表是一个线性结构，它是一个含有 n （ n ≥0）个节点的有限序列。对于其中的节点，有且仅有一个开始节点，没有前驱但有一个后继节点；有且仅有一个终端节点，没有后继但有一个前驱节点。其他的节点都有且仅有一个前驱和一个后继节点。一般地，一个线性表可以表示成一个线性序列： k 1 ， k 2 ，…， k n ，其中 k 1 是开始节点， k n 是终端节点。
线性结构的基本特征如下：
（1）集合中必存在唯一的一个“第一元素”。
（2）集合中必存在唯一的一个“最后元素”。
（3）除最后一个元素之外，均有唯一的后继（后件）。
（4）除第一个元素之外，均有唯一的前驱（前件）。
由 n （ n ≥0）个数据元素（节点） a 1 ， a 2 ，…， a n 组成的有限序列。
数据元素的个数 n 定义为表的长度。
当 n =0 时称为空表。
常常将非空的线性表（ n >0）记作：( a 1 , a 2 ,…, a n )。
线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储结构具备如下两个基本特征：
（1）线性表中的所有元素所占的存储空间是连续的。
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
假设线性表的每个元素需要占用 k 个存储单元，并以所占的存储位置ADR(a i +1)和第 i 个数据元素的存储位置ADR( a i )之间满足下列关系：ADR(a i +1)=ADR( a i )+ k 。
线性表第 i 个元素 a i 的存储位置为：ADR( a i )=ADR( a 1 )+( i －1)× k 。
公式中ADR( a 1 )是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基址。
在VFP语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
图1-1顺序存储
在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。
在线性表的顺序存储结构下，可以对线性表做以下运算：
（1）在线性表的指定位置处加入一个新的元素（即线性表的插入）。
（2）在线性表中删除指定的元素（即线性表的删除）。
（3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）。
（4）对线性表中的元素进行排序（即线性表的排序）。
（5）将一个线性表分解成多个线性表（即线性表的分解）。
（6）将多个线性表合并成一个线性表（即线性表的合并）。
（7）复制一个线性表（即线性表的复制）。
（8）逆转一个线性表（即线性表的逆转）等。
顺序表的基本操作包括插入运算和删除运算。
1）顺序表的插入运算
线性表的插入运算是指在表的第 i （1≤ i ≤ n +l）个位置上，插入一个新节点 x ，使长度为 n 的线性表：
( a 1 , …, a i －1 , a i , …, a n )
变成长度为 n +1 的线性表：( a 1 , …, a i －1 , x , a , …, a n )
现在分析算法的复杂度。设它的值为 n 。该算法的时间主要花费在循环节点后移语句上，该语句的执行次数（即移动节点的次数）是 n - i +1。由此可看出，所需移动节点的次数不仅依赖于表的长度，而且还与插入位置有关。
当 i=n +1 时，由于循环变量的终值大于初值，节点后移语句将不进行；这是最好情况，其时间复杂度为 O (1)。
当 i =1 时，节点后移语句将循环执行 n 次，需移动表中所有节点，这是最坏情况，其时间复杂度为 O ( n )。
综合以上的情况，得出算法的平均时间复杂度为 O ( n )。
2）顺序表的删除运算
线性表的删除运算是指将表的第 i （1≤ i ≤ n ）个节点删除，使长度为 n 的线性表( a 1 , …, a i －1 , a i , a i +1 , …, a n )变成长度为 n -l的线性表( a 1 , …, a i －1 , a i +1 , …, a n )。
该算法的时间分析与插入算法相似，节点的移动次数也是由表长 n 和位置 i 决定的。
若 i=n ，则由于循环变量的初值大于终值，前移语句将不执行，无须移动节点。
若 i =1，则前移语句将循环执行 n -1次，需移动表中除开始节点外的所有节点。在这两种情况下，算法的时间复杂度分别为 O (1)和 O ( n )。
综合以上的情况得出，在顺序表上进行删除运算，平均要移动表中约一半的节点，平均时间复杂度也是 O ( n )。