线性表（一）：顺序表
2012-03-02 18:12:29一、线性表概念
一个线性表由有限且有序的数据项组成。数据项称为元素。
每个表元素有相同的类型。
空表不含任何元素。
线性表的长度定义为表中所含元素的个数。
表的第一个元素称为表头。
表的最后一个元素称为表尾。
有序表是指表中元素的值按位置顺序递增或递减。
无序表是指表中元素的值与位置没有关系。
表的表示: ( a0, a1, …, an-1)
二、线性表的操作
1.初始化操作
初始条件：线性表不存在。
操作结果：创建一个空的线性表。
2.插入操作：InsertNode(T a, int i)
初始条件：线性表存在，插入位置正确(i<= i <=n+1,n为插入前的表长)。
操作结果：在线性表的第i个位置上插入一个值为 a 的新元素，这样使得原序号为 i,i+1,...,n的数据元素的序号变为 i+1,i+2,...,n+1，插入后表长为 n+1。
3.删除操作：DeleteNode(int i)
初始条件：线性表存在且不为空，删除位置正确(1<= i <=n,n为删除前的表长)。
操作结果：在线性表中删除序号为 i 的数据元素，返回删除后的数据元素。删除后使得原序号为 i+1,i+2,...,n的数据元素的序号变为 i,i+1,...,n-1，插入后表长为 n-1。
4.取表元素：SearchNode(int i)
初始条件：线性表存在，所取数据元素位置正确(1<= i <=n,n为线性表的表长)。
操作结果：返回线性表中第 i 个数据元素。
5.定位元素：SearchNode(T value)
初始条件：线性表存在。
操作结果：在线性表中查找值为value的数据元素，其结果返回在线性表中首次出现的值为value的数据元素的序号，称为查找成功；否则，线性表中未找到值为value的数据元素，返回一个特殊值表示查找失败。
6.求表长：GetLength()
初始条件：线性表存在。
操作结果：返回线性表中所有数据元素的个数。
7.清空操作：Clear()
初始条件：线性表存在且有数据元素。
操作结果：从线性表中清除所有数据元素，线性表为空。
8.判断线性表是否为空：IsEmpty()
初始条件：线性表存在。
操作结果：如果线性表中不包含任何元素则返回true，否则返回false。
三、线性表的顺序表示
线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。顺序表的特点是逻辑结构中相邻的节点在存储结构中任相邻，所以可以进行随机存取。因此，假设已知线性表的第一个数据元素a0的存储位置，且线性表中每个数据元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第 i 个数据元素的存储位置为
LOC(ai) = LOC(a0) + (i - 1) * K （1<= i <=n）
顺序表的存储结构可以用c#语言中的一维数组来表示。数组的元素类型使用泛型，以实现不同数据类型的线性表间代码的重用；因为用数组存储顺序表，需预先为顺序表分配最大存储空间，用字段 maxsize 来表示顺序表的最大长度；由于经常需要在顺序表中插入或删除数据元素，顺序表的实际表长是可变的，用 length 字段表示顺序表的实际长度。
对顺序表进行操作
1.初始化顺序表
步骤：
a.初始化 maxsize 为实际值。
b.为数组申请可以存储 maxsize 个数据元素的存储空间，数据元素的类型由实际应用而定。
c.初始化 length 为0。
2.插入操作
步骤：
a.若没有指定插入位置，则将数据元素插入到顺序表的最末一个位置，指定插入位置 i ，若插入位置 i < 1 或 i > length + 1，则无法插入。
b.将第 length ~ 第 i (共 length - i )个数据元素依次后移，将新的数据元素置于 i 位置上。
c.使顺序表的表长初始化 length + 1。
3.删除操作
步骤：
a.如果列表为空，或者不符合1<= i <= length，则提示没有要删除的元素。
b.将第 i+1 ~ 第 length (共 length - i )个数据元素依次前移。
c.使顺序表的表长初始化 length - 1。
其他操作比较简单，不再分析，实现细节参见下面代码。
四、顺序表的实现
基本运算在顺序表上的实现如下：
public class SeqList<T>
{
private int maxsize; //最大长度
private T[] data; //数据元素
private int length; //实际表长
public SeqList(int size)
{
maxsize = size;
data = new T[maxsize];
length = 0;
}
public int Length
{
get { return this.length; }
}
public int Maxsize
{
get { return this.maxsize; }
set { this.maxsize = value; }
}
//在表尾插入元素
public void InsertNode(T a)
{
if (IsFull())
{
throw new Exception("顺序表达到最大容量。");
}
data[length] = a;
length++;
}
public void InsertNode(T a, int i)
{
if (IsFull())
{
throw new Exception("顺序表达到最大容量。");
}
if (i < 1 || i > length + 1)
{
throw new Exception("要插入的位置错误。");
}
for (int j = length; j >= i; j--)
{
data[j] = data[j - 1];
}
data[i-1] = a;
length++;
}
public void DeleteNode(int i)
{
if (IsEmpty())
{
throw new Exception("顺序表为空，无法再删除了。");
}
if (i < 1 || i > length)
{
throw new Exception("要删除的位置错误。");
}
for (int j = i; j < length; j++)
{
data[j - 1] = data[j];
}
length--;
}
public T SearchNode(int i)
{
if (IsEmpty() || i < 1 || i > length)
{
return default(T);
}
return data[i - 1];
}
public T SearchNode(T value)
{
if (IsEmpty())
{
return default(T);
}
int i = 0;
for (i = 0; i < length; i++)
{
if (data[i].ToString().Contains(value.ToString()))
{
break;
}
}
if (i >= length)
{
return default(T);
}
return data[i];
}
public void Clear()
{
length = 0;
}
public bool IsEmpty()
{
if (length == 0)
return true;
else
return false;
}
private bool IsFull()
{
if (length == maxsize)
return true;
else
return false;
}
}
