线性表

本文摘自：

http://blog.csdn.net/congxn/article/details/5333668

http://www.cnblogs.com/ludashi/p/5898704.html

http://www.cnblogs.com/Shoring/p/4762647.html

线性表概述

数据结构整体可以分为物理结构和逻辑结构.

物理结构：数据在磁盘、内存等硬件上的存储结构，主要包括顺序结构和链式结构。

逻辑结构：数据本身所形成的结构，包括集合结构、线性结构、树形结构以及图形结构。

本篇中要说的线性表，即逻辑结构中的线性结构。线性结构的特点就好比一串珠子，其特点是第一个节点只有一个后继，没有前驱，最后一个节点是只有一个前驱，没有后继。而其余的节点只有一个前驱和一个后继。引用Shoring博文中的一段话如下，此比喻很形象。

“你去食堂打饭，发现来的时间点不对，一个人都没有，这时就是一张空表。于是你在外面转了一圈，回来一看，妈呀，一根烟的时间打饭窗口就站了几十号人，于是你赶快排在最后面，刚站好，你后面又一下站了十几个人。
这时，排在一个的就是第一个元素，排在最后一个的就是最后一个元素，排在你前面的就叫前驱，排你后面叫后继。而排在第一个的人前面已经没人了，所以第一个元素无前驱。同理，排在最后的一个无后继。
你排在中间实在太无聊了，于是数了一下，队伍总共100个人，也就是说线性表当前的长度为100。你又算了一下，从打饭窗口到门口可以排150个人，也就是说理论上队伍最多只能排150个人，150就是线性表的最大存储容量。如果还有人要排进来就要站到门外面了，就会发生数据溢出。”

上面说的是线性表的逻辑结构，下面来说线性表的物理结构。

物理存储结构：分为顺序存储结构和链式存储结构。顺序存储结构之所以称之为顺序存储结构因为每个线性表中节点的内存地址是连续的，而链式存储结构中线性表的节点的内存地址可以是不连续的。

下方这个指示图中，上面这个就是链式存储，下方这个就是顺序存储。可见链式存储是有指针域的，也就是前驱和后继的关系有指针来链接。下方这个链式存储就是单向链表，因为只有前驱到后继的指针，而没有后继到前驱的指针。关于双向链表下方会具体给出详细的说明。而下面第二个图就是顺序存储，前驱与后继的关系是由紧挨的内存地址所关联。

顺序存储的内存区块的内存地址是紧挨的，线性关系有相邻的内存地址所保存。当然下方我们是模拟的内存地址，就使用了0x1, 0x2等等来模拟。而链式存储的线性表，在物理存储结构中是不相邻的，仅仅靠内存地址无法去维持这种线性关系。所以就需要一个指针域来指向后继或者前驱节点的内存地址，从而将节点之间进行关联。在单向链式存储中，一个节点不仅仅需要存储数据，而且还要存储该节点下一个节点的内存地址，以便保持这种线性关系。具体请看下图。

线性表的c#实现

顺序存储结构：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Llinear
{
    public interface IListliner<T>
    {
        T GetElement(int i);
        void Insert(T t, int i);
        void Add(T t);
        void Delete(int i);
        //获取线性表长度
        int GetLength();
        bool IsEmpty();
        int LocationElement(T t);
        void Clear();
        void Reverse();
    }
    /// <summary>
    /// 顺序存储结构
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SequenceList<T> : IListliner<T>
    {
        //链表的最大容量
        private int intMaxSize;
        public int MaxSize
        {
            get { return this.intMaxSize; }
            set { this.intMaxSize = value; }
        }
        //使用数组存放元素
        private T[] array;
        public T this[int i]
        {
            get { return this.array[i]; }
        }
        //始终指向最后一个元素的位置
        private int intPointerLast;
        public int PointerLast
        {
            get { return this.intPointerLast; }
        }
        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="size">数组容器的长度</param>
        public SequenceList(int size)
        {
            this.intMaxSize = size;
            this.array = new T[size];
            this.intPointerLast = -1;//初始值为-1，表示当前元素个数为0；
        }
        //判断元素是否溢出
        public bool IsFull()
        {
            return intPointerLast + 1 == this.intMaxSize;
        }
        /// <summary>
        /// 获取某个位置的元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T GetElement(int i)
        {
            if (this.intPointerLast == -1)
            {
                Console.WriteLine("there is no element in the linear!");
                return default(T);//获取默认值
            }
            if (i > intPointerLast || i < 0)
            {
                Console.WriteLine("linear is overflow!");
            }
            return array[i];
        }
        /// <summary>
        /// 在任意位置插入元素
        /// </summary>
        /// <param name="t">需要插叙的元素</param>
        /// <param name="i">从1开始，表示在第i个元素后面插入元素</param>
        public void Insert(T t, int i)
        {
            if (i < 1 || i > intPointerLast + 1)
            {
                Console.WriteLine("insert location is wrong!");
                return;
            }
            if (IsFull())
            {
                Console.WriteLine("linear is overflow!");
            }
            //在i元素后添加元素,其后面的元素都要向后移动一个位置。
            intPointerLast++;
            for (int j = intPointerLast; j > i + 1; j--)
            {
                array[j] = array[j - 1];
            }
            //插入的元素t变为第i个元素
            array[i] = t;
        }
        /// <summary>
        /// 在链表的末位置插入元素
        /// </summary>
        /// <param name="t">添加的元素</param>
        public void Add(T t)
        {
            if (IsFull())
            {
                Console.WriteLine("linear is overflow!");
            }
            else
            {
                intPointerLast++;
                array[intPointerLast] = t;
            }
        }
        /// <summary>
        /// 删除元素
        /// </summary>
        /// <param name="i">删除的元素位置，从0开始</param>
        public void Delete(int i)
        {
            if (intPointerLast == -1)
            {
                Console.WriteLine("there is no element in the linear!");
                return;
            }
            if (i > intPointerLast || i < 0)
            {
                Console.WriteLine("location is wrong!");
                return;
            }
            for (int j = i; j < intPointerLast; j++)
            {
                array[j] = array[j + 1];//i后面的元素向前移动一个位置。
            }
            intPointerLast--;//长度-1；
        }
        /// <summary>
        /// 链表长度（注意此处不能返回数组长度）
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            return this.intPointerLast + 1;
        }

        public bool IsEmpty()
        {
            return intPointerLast == -1;
        }
        /// <summary>
        /// 获取链表某个元素位置
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public int LocationElement(T t)
        {
            if (intPointerLast == -1)
            {
                Console.WriteLine("There is no element in the linear!");
                return -1;
            }
            else
            {
                for (int i = 0; i < intPointerLast; i++)
                {
                    if (array[i].Equals(t))
                    {
                        return i;
                    }
                }
            }
            throw new NotImplementedException();
        }

        public void Clear()
        {
            intPointerLast = -1;
        }
        /// <summary>
        /// 翻转链表
        /// </summary>
        public void Reverse()
        {
            if (intPointerLast == -1)
            {
                Console.WriteLine("There is no items in the list!");
            }
            else
            {
                int i = 0;
                int j = GetLength();
                while (i < j)
                {
                    T tmp = array[i];
                    array[i] = array[intPointerLast - i];
                    array[intPointerLast - i] = tmp;
                    i++;
                }
            }
            throw new NotImplementedException();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

        }
    }

}