数据结构与算法 －线性表

线性表是由n（n≥0）个数据元素（结点）组成的有限序列。

线性表中只有一个起始结点，一个终端结点， 起始结点没有直接前驱，有一个直接后继。 终端结点有一个直接前驱，没有直接后继。 除此二结点外，每个结点都有且只有一个直接前驱 和一个直接后继。

线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。

用顺序存储实现的线性表称为顺序表，一般使用数组来表示顺序表。顺序存储线性表时，需要存储单元大小、数据个数、所存放数据的类型。

顺序存储结构的特点：

1. 顺序表是用一维数组实现的线性表，数组下标可以看成是元素的相对地址，所以可以对数据元素实现随机读取。

2. 线性表的逻辑结构与存储结构一致，逻辑上相邻的元素，存储在物理位置也相邻的单元中。

如果线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。

假设表中每个结点占用L个存储单元， 并设表中开始结点a1的存储地址是d，那么结点ai的存储地址LOC（ai）为：

线性表的基本运算：

1. 初始化 Initiate(L)，建立一个空表L=()，L不含数据元素。

2. 求表长度 Length(L)，返回线性表L的长度。

3. 取表元 Get(L,i)，返回线性表第i个数据元素，当i不满足 1≤i≤Length(L)时，返回一特殊值。

4. 插入 Insert(L,x,i)，在线性表L的第i个数据元素之前插入一个值为x的新数据 元素，参数i的合法取值范围是1≤i≤n+1。操作结束后线性表L由（a1，a2，…，ai-1， ai，ai+1，.…，an )变为（a1，a2， …，ai-1，x， ai，ai+1，.…，an )，表长度加 1。

5. 删除 Delete(L,i)，删除线性表L的第i个数据元素ai，i的有效取值范围是1≤i≤n。 删除后线性表L由（a1，a2，…，ai-1， ai，ai+1，.…，an ) 变为 （a1，a2，…，ai-1，ai+1，.…，an )，表长度减1。

6. 定位 Locate(L,x)，查找线性表中数据元素值等于x的结点序号，若有多个数据元素值与x相等，运算结果为这些结点中序号的最小值，若找不到该结点，则运算结果为0。