数据结构与算法中的顺序表
顺序表的定义
在计算机内，保存线性表最简单、最自然的方式，就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表(Sequence List)，如图2.1所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻。
图2.1 顺序表的存储结构示意图
假设顺序表中的每个数据元素占w个存储单元，设第i个数据元素的存储地址为Loc(ai)，则有：
Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n
式中的Loc(a1)表示第一个数据元素a1的存储地址，也是顺序表的起始存储地址，称为顺序表的基地址(Base Address)。也就是说，只要知道顺序表的基地址和每个数据元素所占的存储单元的个数就可以求出顺序表中任何一个数据元素的存储地址。并且，由于计算顺序表中每个数据元素存储地址的时间相同，所以顺序表具有随机存取的特点。
C#语言中的数组在内存中占用的存储空间就是一组连续的存储区域，因此，数组具有随机存取的特点。所以，数组天生具有表示顺序表的数据存储区域的特性。
把顺序表看作是一个泛型类，类名叫SeqList。”Seq”是英文单词”Sequence”的前三个字母。SeqList类实现了接口IListDS。用数组来存储顺序表中的元素，在SeqList类中用字段data来表示。由于经常需要在顺序表中插入或删除数据元素，所以要求顺序表的表长是可变的。因此，数组的容量需要设计得特别大，可以用System.Array的Length属性来表示。但为了说明顺序表的最大长度（顺序表的容量），在SeqList类中用字段maxsize来表示。maxsize的值可以根据实际需要修改，这通过SeqList类中构造器的参数size来实现。顺序表中的元素由data[0]开始依次顺序存放，由于顺序表中的实际元素个数一般达不到maxsize，因此，在SeqList类中需要一个字段last表示顺序表中最后一个数据元素在数组中的位置。如果顺序表中有数据元素时，last的变化范围是0到maxsize-1，如果顺序表为空，last=-1。具体表示见图2.1所示。由于顺序表空间的限制，当往顺序表中插入数据元素需要判断顺序表是否已满，顺序表已满不能插入元素。所以，SeqList类除了要实现接口IListDS中的方法外，还需要实现判断顺序表是否已满等成员方法。
顺序表类SeqList的实现说明如下所示。
public class SeqList : IListDS {
private int maxsize; //顺序表的容量
private T[] data; //数组，用于存储顺序表中的数据元素
private int last; //指示顺序表最后一个元素的位置
//索引器
public T this[int index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}
//最后一个数据元素位置属性
public int Last
{
get
{
return last;
}
}
//容量属性
public int Maxsize
{
get
{
return maxsize;
}
set
{
maxsize = value;
}
}
//构造器
public SeqList(int size)
{
data = new T[size];
maxsize = size;
last = -1;
}
//求顺序表的长度
public int GetLength()
{
return last+1;
}
//清空顺序表
public void Clear()
{
last = -1;
}
//判断顺序表是否为空
public bool IsEmpty()
{
if (last == -1)
{
return true;
}
else
{
return false;
}
}
//判断顺序表是否为满
public bool IsFull()
{
if (last == maxsize-1)
{
return true;
}
else
{
return false;
}
}
//在顺序表的末尾添加新元素
public void Append(T item)
{
if(IsFull())
{
Console.WriteLine("List is full");
return;
}
data[++last] = item;
}
//在顺序表的第i个数据元素的位置插入一个数据元素
public void Insert(T item, int i)
{
if (IsFull())
{
Console.WriteLine("List is full");
return;
}
if(i<1 || i>last+2)
{
Console.WriteLine("Position is error!");
return;
}
if (i == last + 2)
{
data[last+1] = item;
}
else
{
for (int j = last; j>= i-1; --j)
{
data[j + 1] = data[j];
}
data[i-1] = item;
}
++last;
}
//删除顺序表的第i个数据元素
public T Delete(int i)
{
T tmp = default(T);
if (IsEmpty())
{
Console.WriteLine("List is empty");
return tmp;
}
if (i < 1 || i > last+1)
{
Console.WriteLine("Position is error!");
return tmp;
}
if (i == last+1)
{
tmp = data[last--];
}
else
{
tmp = data[i-1];
for (int j = i; j <= last; ++j)
{
data[j] = data[j + 1];
}
}
--last;
}
//获得顺序表的第i个数据元素
public T GetElem(int i)
{
if (IsEmpty() || (i<1) || (i>last+1))
{
Console.WriteLine("List is empty or Position is error!");
return default(T);
}
return data[i-1];
}
//在顺序表中查找值为value的数据元素
public int Locate(T value)
{
if(IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}
int i = 0;
for (i = 0; i <= last; ++i)
{
if (value.Equals(data[i]))
{
break;
}
}
if (i > last)
{
return -1;
}
return i;
}
}
数据结构与算法中的顺序表
