线性表

线性表定义：

线性表（Linear List）是由n（n≥0）个数据元素（结点）a₁，a₂，…，a_n组成的有限序列。
① 数据元素的个数n定义为表的长度（n=0时称为空表）。
② 将非空的线性表（n＞0）记作：（a₁，a₂，…，a_n）
③ 数据元素a_i（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。

         【例1】英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点）

【例2】一副扑克牌的点数（2，3，…，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数
线性表的特征：

1. 有且只有一个“首元素”。
2. 有且只有一个“末元素”。
3. 除末元素外，其余元素均有唯一的后继元素。
4. 除首元素外，其余元素均有唯一的前驱元素。

常见线性表的基本操作：

1  InitList（L）

构造一个空的线性表L，即表的初始化。

2 ListLength（L）

求线性表L中的结点个数，即求表长。

3 GetNode（L，i）

取线性表L中的第i个结点，这里要求1≤i≤ListLength（L）

4 LocateNode（L，x）

在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则 返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。

5 InsertList（L，x，i）

在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。这里1≤i≤n+1，而n是原表L的长度。插入后，表L的长度加1。

6 DeleteList（L，i）

删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。这里1≤i≤n，而n是原表L的长度。删除后表L的长度减1。

转自 http://itjoy.org/?p=137