线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系。 这种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素; (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素。也就是说,数据元素是一个接一个的排列。因此,可以把线性表想象为一种数据元素序列的数据结构。
线性表的接口如下所示。
public interface IListDS<T>//线性表的接口 { int GetLength(); //求长度 void Clear(); //清空操作 bool IsEmpty(); //判断线性表是否为空 bool IsFull(); void Append(T item); //附加操作 void Insert(T item, int i); //插入操作 T Delete(int i); //删除操作 T GetElem(int i); //取表元 int Locate(T value); //按值查找 void Reverse();//倒置 }
在计算机内,保存线性表最简单、最自然的方式,就是把表中的元素一个接一个地放进顺序的存储单元,这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素,用这种方式存储的线性表叫顺序表(Sequence List)。顺序表的特点是表中相邻的数据元素在内存中存储位置也邻。
public class SeqList<T> : IListDS<T> { private int last; private int maxSize; private T[] data; public T this[int index] { get { return data[index]; } set { data[index] = value; } } public SeqList(int size) { maxSize = size; data = new T[size]; last = -; } public int Last { get { return last; } } public int MaxSize { get { return maxSize; } set { maxSize = value; } } public int GetLength() { ; } public void Clear() { last = -; } public bool IsEmpty() { ; } public bool IsFull() { ; } public void Append(T item) { if (IsFull()) { Console.WriteLine("List is full"); return; } data[++last] = item; } public void Insert(T item, int i) { if (IsFull()) { Console.WriteLine("List is full"); return; } || i > last + ) { Console.WriteLine("Position is error!"); return; } ) { data[last + ] = item; } else { ; j <= last; j++) { data[j + ] = data[j]; } data[i - ] = item; } ++last; } public T Delete(int i) { T tmp = default(T); if (IsEmpty()) { Console.WriteLine("List is empty"); return tmp; } || i > last + ) { Console.WriteLine("Position is error!"); return tmp; } ) { tmp = data[last]; } else { tmp = data[i - ]; ; j++) { data[j] = data[j + ]; } } --last; return tmp; } public T GetElem(int i) { || i > last + ) { Console.WriteLine("List is empty or Position is error!"); return default(T); } ]; } public int Locate(T value) { if (IsEmpty()) { Console.WriteLine("List is empty!"); ; } ; ; i <= last; i++) { if (value.Equals(data[i])) break; } if (i > last) ; return i; } public void Reverse() { T tmp = default(T); int len = GetLength(); ; i <= len / ; i++) { tmp = data[i]; data[i] = data[len - i]; data[len - i] = tmp; } } } }