线性表的顺序存储结构

1、我们将实现一个顺序存储结构

经典的C语言描述的线性表顺序存储结构通常使用数组来实现的，下面我们也将用数组来实现。我们将实现线性表的增删改查的功能。

顺序存储结构操作的要点和难点其实就是数组的批量移动。因为在数组描述的顺序表中，删除操作，需要将从待删除元素的位置之后的所有元素都往前移动一位；而插入操作，需要将待插入元素的位置，包括原先在该位置的元素及其后面的元素都往前移动一位。而实现删除和插入元素的重点就在于计算出要移动多少元素和从什么位置开始移动。计算要移动多少元素通常用顺序表的长度-要移动的位置。从什么位置开始移动，通常由要插入（或删除）的位置进行一些简单的计算。具体的实现如下所示。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace DataStructure

{

    public class SqList

    {

        const int MAX_LENTH = 100;    //定义线性表的存储空间大小

        public int Lenth;             //线性表的长度,我们将通过线性表的长度判断线性表是否为空，通过Lenth存取线性表

        public int[] data = new int[MAX_LENTH];

 

 

        public int GetLength() //求长度

        {

            return this.Lenth;

        }

        public void Clear()//清空操作

        {

            //长度设置为0

            this.Lenth = 0;

        }

        public bool IsEmpty()//判断线性表是否为空

        {

            //这里通过判断线性表的长度

            return Lenth == 0 ? true : false;

        }

        /// <summary>

        /// 将元素附加到最后一个位置

        /// </summary>

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

        /// <returns></returns>

        public States Append(int item) //

        {

            if (this.Lenth + 1 == MAX_LENTH)

            {

                return States.Fail;

            }

            data[this.Lenth] = item;

            this.Lenth++;

            return States.Success;

        }

        /// <summary>

        /// 插入操作

        /// </summary>

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

        /// <param name="i">位置</param>

        public States Insert(int item, int index)//插入操作

        {

            //异常检查

            if (index < 0 || index > this.Lenth) return States.Fail;//检查插入的位置

            if (this.Lenth + 1 > MAX_LENTH) return States.Fail; //检查数组是否会溢出

 

            //假设线性表中有三个元素0,1,2。当将item=3插入1的位置的时候，1,2各往后移动一位，

            //item=3插入到原来1的位置

            if (index == this.Lenth)

            {

                data[this.Lenth] = item;

                this.Lenth++;

                return States.Success;

 

            }

            int move = this.Lenth - index;

            int NextPosition;

            NextPosition = this.Lenth - 1;

            for (int i = 0; i < move; i++)

            {  //将index之后的元素全部往后移一位

 

                data[NextPosition + 1] = data[NextPosition];

                NextPosition--;

            }

            data[index] = item;

            this.Lenth++;

            //将item插入位置

            return States.Success;

 

        }

        /// <summary>

        /// 删除元素并返回元素的值

        /// </summary>

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

        /// <param name="states"></param>

        /// <returns></returns>

        public int Delete(int index, out States states)//删除操作

        {

            //异常检查

            if (index < 0 || index > this.Lenth)

            {

                states = States.Fail;//检查插入的位置

                return 0;

            }

            if (this.Lenth == 0)//检查是否有值可以被删除

            {

                states = States.Fail;

                return 0;

 

            }

 

            int iDataToDel = data[index];

            if (index == this.Lenth - 1)              //如果正好是最后一个元素，则不需要移动

            {

                this.Lenth--;

                states = States.Success;

                return iDataToDel;

            }

 

            int PositionToMove = index + 1;//要开始往前移动的位置

            //(1)要移动多少元素

            int iMove = this.Lenth - PositionToMove;

            //(2)循环移动元素

            for (int i = 0; i < iMove; i++)

            {

                data[PositionToMove - 1 + i] = data[PositionToMove + i];

            }

            //(3)长度-1

            this.Lenth--;

            //(4)返回要删除的元素

            states = States.Success;

            return iDataToDel;

        }

        public int GetElem(int i)

        {  //取表中的元素

            return this.data[i];

        }

        /// <summary>

        /// 返回查找到的第一个位置

        /// </summary>

        /// <param name="value"></param>

        /// <param name="states"></param>

        /// <returns></returns>

        public int Locate(int value, out States states)

        {   //按值查找

            for (int i = 0; i < this.Lenth; i++)

            {

                if (value == data[i])

                {

                    states = States.Success;

                    return i;

                }

            }

            states = States.Fail;

            return 0;

        }

 

    }

    //定义一个用来指示操作是否成功的枚举量

    public enum States

    {

        Success,

        Fail

    }

 

}

 

 

2、使用C#特有的语法来实现经典顺序存储结构

下面，我们将对以上实现的顺序存储线性表用C#特有的语法进行改造。主要的改造如下：

1、使用模板template抽象线性表元素的类型；

2、使用索引器简化元素的访问；

3、使用属性代替特定的方法。

为了保持两边方法签名的一致性，我们利用vs2010中提取接口的功能将相关的方法提取为接口

                                                        图1 提取接口

提取后的接口，如下所示

using System;

namespace DataStructure

{

    interface ISqList

    {

        States Append(int item);

        void Clear();

        int Delete(int index, out States states);

        int GetElem(int i);

        int GetLength();

        States Insert(int item, int index);

        bool IsEmpty();

        int Locate(int value, out States states);

    }

}

为了让我们的线性表能够适应不同的元素类型，我们稍微改变一下接口的声明。我们所需要做的只是将具体的元素类型使用模板进行填充，如下所示。有变化的部分都用灰色背景进行标识。

using System;

namespace DataStructure

{

    interface ISqList<T>

    {

       States Append(T item);

        void Clear();

        T Delete(int index, out States states);

       T GetElem(int i);

        int GetLength();

        States Insert(T item, int index);

        bool IsEmpty();

        int Locate(T value, out States states);

    }

}

我们遵循着前面提到的3个改造将经典的顺序表改造得更C#，详见以下代码

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace DataStructure

{

    class AD_Sqlist<T> : ISqList<T>

    {

        const int MAX_LENTH = 100;//定义线性表的存储空间大小

        public T[] data = new T[MAX_LENTH];

 

        private int lenth;

        /// <summary>

        /// 线性表的长度

        /// </summary>

        public int Lenth

        {

            get { return lenth; }

            set { lenth = value; }

        }

        /// <summary>

        /// 判断线性表是否已满

        /// </summary>

        public bool IsFull

        {

            get

            {

                if (Lenth + 1 > MAX_LENTH)

                {

                    return true;

                }

                else

                {

                    return false;

                }

            }

        }

 

        public States Append(T item)

        {

            if (IsFull == true)

            {

                return States.Fail;

            }

            data[this.Lenth] = item;

            return States.Success;

        }

 

        public void Clear()

        {

            this.Lenth = 0;

        }

 

        public T Delete(int index, out States states)

        {

            if (Lenth == 0)

            {

                states = States.Fail;

                return default(T);

            }

            if (index >= this.Lenth)

            {

                states = States.Fail;

                return default(T);

            }

            //(1)要移动多少位

            int move = this.Lenth - 1 - index;

 

            //(2)从哪一位开始移动

            int position = index + 1;

            T dataToDel = data[index];//将要被删除的元素

 

            //(3)将所有元素都批量往前移动

            for (int i = 0; i < move; i++)

            {

                data[position - 1] = data[position];

                position++;

            }

            Lenth--;

            //(4)返回被删除的元素

            states = States.Success;

            return dataToDel;

        }

 

        public T GetElem(int i)

        {

            if (i < 0 || i >= this.Lenth)

            {

                return default(T);

            }

            return this.data[i];

        }

        public T this[int i]

        {

            get

            {

 

                if (i < 0 || i >= this.Lenth)

                {

                    return default(T);

                }

                return this.data[i];

            }

 

        }

        public int GetLength()

        {

            return this.Lenth;

        }

 

        public States Insert(T item, int index)

        {

            //(1)线性表是否已满

            if (IsFull == true)

            {

                return States.Fail;

            }

 

            //(2)插入的位置是否正确

            if (index < 0 || index > this.Lenth)

            {

                return States.Fail;

            }

            if (index == this.Lenth)

            {

                data[index] = item;

                this.Lenth++;

                return States.Success;

            }

            //(3)将要移动的个数

            int move = this.Lenth - 1 - index;

            //（4）准备移动的位置

            int position = this.Lenth - 1;

            //(5)批量移动

            for (int i = 0; i <= move; i++)

            {

                this.data[position + 1] = this.data[position];

                position--;

            }

            this.data[index] = item;

            //(6)返回

            this.Lenth++;

            return States.Success;

        }

 

        public bool IsEmpty()

        {

            if (this.Lenth == 0)

            {

                return true;

            }

            else

            {

                return false;

            }

        }

 

        public int Locate(T value, out States states)

        {

            if (IsEmpty() == true)

            {

                states = States.Fail;

                return 0;

            }

            else

            {

                for (int i = 0; i < this.Lenth; i++)

                {

                    if (this.data[i].Equals(value))

                    {

                        states = States.Success;

                        return i;

                    }

                }

            }

            states = States.Fail;

            return 0;

        }

    }

}