C# 数据结构与算法系列(二) 线性表之顺序表

线性表(List)
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，
即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于
实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表是一种常用
的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。
在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线
性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都
是至关重要的。

线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结
点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且
仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是
开始结点，kn是终端结点。n就是线性表的长度，当n=0时的线性表就是一个空表。平时我们都看到很多
线性表的实例，如1-100就是一个线性表，表示为(1,2,3,...,100)，一个数组或一个数据库的表也是一
个线性表。注意：线性表是一个数据元素的有序（次序）集

线性结构的基本特征为:
1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ；
3．除最后一个元素之外，均有唯一的后继(后件)；
4．除第一个元素之外，均有唯一的前驱(前件)。

线性表的接口如下所示：

线性表的基本操作
1、求长度：GetLength()
初始条件：线性表存在；
操作结果：返回线性表中所有数据元素的个数。

2、清空操作：Clear()
初始条件：线性表存在且有数据元素；
操作结果：从线性表中清除所有数据元素，线性表为空。

3、判断线性表是否为空：IsEmpty()
初始条件：线性表存在；
操作结果：如果线性表为空返回true，否则返回false。

4、附加操作：Append(T item)
初始条件：线性表存在且未满；
操作结果：将值为item的新元素添加到表的末尾。

5、插入操作：Insert(T item, int i)
初始条件：线性表存在，插入位置正确()(1≤i≤n+1,n为插入前的表长)。

6 、删除操作: Delete(int i)
初始条件：线性表存在并且线性表不为空。

7、取元素： GetElem(int i)
初始条件：线性表存在并且线性表不为空。

8、按值查找：Locate(T value)
初始条件：线性表存在并且线性表不为空。

线性表具有如下的结构特点：(需要参加这门课程考试的朋友要注意下面二点)
1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数所类长度。
2.有序性：各数据元素在线性表中的位置只取决于它们的序与，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个“的数据
元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前趋和后面均只有一个数据元素（直接后继）。

在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数
组实现线性表数据元素的顺序存储及其应用。另外栈．队列和串也是线性表的特殊情况，又称为受限的线性结构。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。
线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连
续的存储单元中。将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。采用顺序
存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通
过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。

如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。
则有如下的关系:
location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len
存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

构造线性表的类:
  public inte易做图ce 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);
        string Locate(T value);

    }

    public class TList<T> : IListDS<T>
    {
        private T[] _list;
        private int _len;
        private int _lastOne;

        public T this[int length]
        {
            get { return _list[length]; }
            set { _list[length] = value; }
        }

        public

补充：软件开发 , C# ,