什么是线性表

数据结构中最常用也最简单的应该就是线性表，它是一种线性结构（废话，不是线性结构怎么会叫线性表？当然不是废话，古人公孙龙就说白马非马，现代生物学家也说鲸鱼不是鱼）。

那什么是线性结构？

按数据逻辑结构来划分，数据结构就分为线性结构和非线性结构。

通俗来说就是排成一条线的结构，想象一下你去食堂排队打饭，前面站着一个人，后面也站着一个人，这样的结构就是线性结构。

线性表的定义

线性表就是线性结构的一种（其实其它像栈、队列什么的也可以说是一种特殊的线性表），先看一下线性表的定义：

零个或多个数据元素的有限序列。

零个或多个意味着线性表的数据元素n大于等于0，当n=0时，也就是空表。

有限意味着这个表的数据有限的，计算机中处理的数据都是有限的。

序列也就是说这一组元素是有顺序的，如果没有顺序乱成一团就不是排队而是打架了。



你去食堂打饭，发现来的时间点不对，一个人都没有，这时就是一张空表。于是你在外面转了一圈，回来一看，妈呀，一根烟的时间打饭窗口就站了几十号人，于是你赶快排在最后面，刚站好，你后面又一下站了十几个人。

这时，排在一个的就是第一个元素，排在最后一个的就是最后一个元素，排在你前面的就叫前驱，排你后面叫后继。而排在第一个的人前面已经没人了，所以第一个元素无前驱。同理，排在最后的一个无后继。

你排在中间实在太无聊了，于是数了一下，队伍总共100个人，也就是说线性表当前的长度为100。你又算了一下，从打饭窗口到门口可以排150个人，也就是说理论上队伍最多只能排150个人，150就是线性表的最大存储容量。如果还有人要排进来就要站到门外面了，就会发生数据溢出。

接口定义

后面我们将要介绍到多种实现线性表的方式，但不管哪种方式实现的线性表都是一样的，里面定义方法也是一样的。使用接口可以确保每种方式都实现了相同的操作，方便程序解耦，更利于其它模块调用以及编写单元测试。

下面给出定义的接口：

public interface ILinearList<T>

{

    /// <summary>

    /// 数组长度

    /// </summary>

    int Length

    {

        get;

    }

    /// <summary>

    /// 数组是否为空

    /// </summary>

    /// <returns></returns>

    bool IsEmpty();

    /// <summary>

    ///清空表

    /// </summary>

    void Clear();

    /// <summary>

    ///通过索引获取数据元素

    /// </summary>

    /// <param name="index"></param>

    /// <returns></returns>

    T GetItem(int index);

    /// <summary>

    /// 返回数据元素的索引

    /// </summary>

    /// <param name="t"></param>

    /// <returns></returns>

    int LocateItem(T t);

    /// <summary>

    /// 将数据元素插入到指定位置

    /// </summary>

    /// <param name="item"></param>

    /// <param name="index"></param>

    void Insert(T item, int index);

    /// <summary>

    /// 在数组末尾添加元素

    /// </summary>

    /// <param name="item"></param>

    void Add(T item);

    /// <summary>

    /// 删除指定索引的元素

    /// </summary>

    /// <param name="index"></param>

    void Delete(int index);

}

线性表顺序存储结构

线性表有两种物理结构——顺序存储结构和链式存储结构。我们先来看看顺序存储结构。

顺序存储结构就和前面的排队一样，设计一个排队窗口，定下最多可以排多少人，然后按顺序一个个这么排下去。也就是说在内存中分配一块内存空间，然后把相同数据类型的数据元素依次存放下去。

如何实现

使用一维数组，把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

用C#实现，可以直接使用泛型数组。

初始化

首先我们先定义一些属性及字段：

    private T[] list;

    private int length = 0;

    public int MaxSize

    {

        private set;

        get;

    }

    public int Length

    {

        get { return length; }

    }

构建线性表只需要给定数组最大容量（MaxSize）然后将list集合初始化就行了，这些我们可以直接放在构造函数里面：

    public SequentialList(int maxSize)

    {

        if (maxSize <= 0)

        {

            throw new Exception("the maxSize can not be less than zero");

        }

        MaxSize = maxSize;

        list = new T[maxSize];

    }

元素获取

元素的获取非常简单，直接通过下标返回就可以了：

    public T GetItem(int index)

    {

        return list[index];

    }

添加元素

添加元素直接将数据元素放在数组的末尾（排队时新来一个人直接站在最后就好），并将length加1就行了：

    public void Add(T item)

    {

        if (isFull())   //判断数组是否已满

        {

            throw new Exception("This linear list is full");

        }

        length++;

        list[length - 1] = item;

    }

将元素插入至指定位置

打饭时，每新来一个人就直接排到队伍的最后面。但是现实却总是不那么美好，总有一些人会来插队。今天你去食堂去晚了，一看队伍已经站了差不多一百个人，所以机智的你看了下队伍的前列，在前面发现了坐在你边上的美女同事，于是赶快和她打个招呼以极其自然的方式插到了她的前面。你的插入对排在美女同事前面的人来说没有任何影响，他们的位置保持不变，但是排在她后面就要相应的全部向后移一个位置：

    public void Insert(T item, int index)

    {

        if (isFull())

        {

            throw new Exception("This linear list is full");

        }

        if (index < 0 || index > length)

        {

            throw new Exception("Location exception");

        }

        length++;

        for (int i = length - 1; i > index; i--)

        {

            list[i] = list[i - 1];

        }

        list[index] = item;

    }

删除

你正在排队打饭，突然发现肚子疼，心想总不能等下一边吃进去一边拉出来吧，于是赶快从队伍里退出来奔向洗手间，这个时候，排在你后面的人自然是满脸欢笑地目送你离开，他们所有人都可以往前面移一个位置：

    public void Delete(int index)

    {

        if (index < 0 || index > length - 1)

        {

            throw new Exception("Location exception");

        }

        length--;

        for (int i = index; i < length; i++)

        {

            list[i] = list[i + 1];

        }

    }

完整代码如下（代码烂，轻拍）：

/// <summary>

/// 线性表顺序结构

/// </summary>

public class SequentialList<T> : ILinearList<T>

{

    private T[] list;

    private int length = 0;

    public int MaxSize

    {

        private set;

        get;

    }

    public int Length

    {

        get { return length; }

    }

    public SequentialList(int maxSize)

    {

        if (maxSize <= 0)

        {

            throw new Exception("the maxSize can not be less than zero");

        }

        MaxSize = maxSize;

        list = new T[maxSize];

    }

    public bool IsEmpty()

    {

        return length == 0;

    }

    public void Clear()

    {

        length = 0;

    }

    public T GetItem(int index)

    {

        return list[index];

    }

    public int LocateItem(T t)

    {

        for (int i = 0; i < list.Length; i++)

        {

            if (list[i].Equals(t))

            {

                return i;

            }

        }

        return -1;

    }

    public void Insert(T item, int index)

    {

        if (isFull())

        {

            throw new Exception("This linear list is full");

        }

        if (index < 0 || index > length)

        {

            throw new Exception("Location exception");

        }

        length++;

        for (int i = length - 1; i > index; i--)

        {

            list[i] = list[i - 1];

        }

        list[index] = item;

    }

    public void Add(T item)

    {

        if (isFull())

        {

            throw new Exception("This linear list is full");

        }

        length++;

        list[length - 1] = item;

    }

    public void Delete(int index)

    {

        if (index < 0 || index > length - 1)

        {

            throw new Exception("Location exception");

        }

        length--;

        for (int i = index; i < length; i++)

        {

            list[i] = list[i + 1];

        }

    }

    bool isFull()

    {

        return length >= MaxSize;

    }

}