線性表的順序表示（順序連結清單）

C#實作線性表的順序表示（順序連結清單）

順序連結清單：指的是用一組位址連續的存儲單元依次㽾線性表的資料元素；

優點：

1.存取速度快，通過索引進行存取；

2.空間使用率高；
           

缺點：

1.插入和删除較慢，操作繁瑣；

2.需要連續的空間進行資料存儲；
           

順序連結清單的實作：

1.接口類：

/// <summary>
    /// 該類為連結清單接口定義類，順序連結清單和單連結清單都使用該接口
    /// </summary>
    /// <typeparam name="T"></typeparam>
    interface IListDS<T>
    {
        /// <summary>
        /// 擷取連結清單長度
        /// </summary>
        /// <returns></returns>
        int GetLength();

        /// <summary>
        /// 清空連結清單
        /// </summary>
        void Clear();

        /// <summary>
        /// 判斷連結清單是否為空
        /// </summary>
        /// <returns></returns>
        bool IsEmpty(); 

        /// <summary>
        /// 向連結清單中添加元素
        /// </summary>
        /// <param name="item"></param>
        void Add(T item);

        /// <summary>
        /// 根據索引向連結清單中插入元素
        /// </summary>
        /// <param name="item"></param>
        /// <param name="index"></param>
        void Insert(T item, int index);

        /// <summary>
        /// 根據索引删除連結清單中的元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        T Delete(int index);

        /// <summary>
        ///根據索引擷取元素值
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        T GetEle(int index);

        /// <summary>
        /// 更具元素值，擷取元素在連結清單中的位置
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        int Locate(T value);

        /// <summary>
        /// 格局索引擷取元素值
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        T this[int index] { get; }
    }
    
           

2.實作類：

/// <summary>
    /// 順序表實作方式，該順序連結清單長度不會自增連結清單
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// 
    class SeqList<T> : IListDS<T>                   //數組類型位置，是以SeqList使用T來傳入參數類型，該類實作接口類IListDS類
    {

        private T[] data;                           //定義一個數組data，用來存放資料
        private int count = 0;                      //定義一個變量，用來表示順序連結清單元素個數

        public SeqList(int size)                    //構造函數初始化，size指定數組data長度,數組初始，元素個數為零
        {                                           //這裡定義的數組長度不會變化，即順序連結清單長度不會變化
            data = new T[size];
            count = 0;
        }
        public SeqList() : this(10) { }             //這裡指定數組長度為10，即順序連結清單長度為10

        #region 根據索引擷取值
        public T this[int index]                    //根據索引index擷取元素值
        {
            get { return GetEle(index); }           //調用目前類的GetEle方法擷取元素值
        }
        #endregion

        #region 向順序連結清單中添加元素
        public void Add(T item)                     //向順序連結清單中添加一個元素
        {
            if (count == data.Length)               //判斷順序連結清單中元素個數是否與數組大小相等，如果相等，說明數組（連結清單）存滿了
            {
                Console.WriteLine("連結清單已存滿，不允許在存入"); 
            }
            else
            {
                data[count] = item;
                count++;
            }
        }
        #endregion

        #region 清空順序連結清單
        public void Clear()                          //清空順序連結清單，将元素個數設定為0即可
        {
            count = 0;
        }
        #endregion

        #region 根據索引删除元素
        public T Delete(int index)                   //根據索引删除元素,并将删除的元素傳回，需要将索引之後的元素向前移動一個位置
        {
            T temp = data[index];                    //建立一個臨時變量，用來存放要删除的元素
            for(int i = index; i < count; i++)
            {
                data[i] = data[i + 1];               //循環周遊，将要删除的元素後面的資料向前移動一個位置

            }
            count--;                                 //将元素個數減一
            return temp;
        }
        #endregion


        #region 根據索引擷取值
        public T GetEle(int index)                   //根據索引擷取元素
        {
            if (index >= 0 && index <= count - 1)    //判斷元素索引index是否小于元素個數count，小于則存在該元素，大于則索引越界
            {
                return data[index];
            }
            else
            {
                Console.WriteLine("索引越界");
                return default;
            }
        }
        #endregion

        #region 擷取順序連結清單中元素個數
        public int GetLength()                       //擷取順序連結清單長度，即元素個數
        {
            return count;
        }
        #endregion

        #region 向順序連結清單中插入元素
        public void Insert(T item, int index)        //向順序連結清單中插入一個元素
        {
            if (count + 1 < data.Length)             //判斷如果插入後，元素個數是否大于數組長度，如果大于，則連結清單存滿，不能插入
            {
                for (int i = count; index <= i; i--) //循環周遊，将插入位置及其之後的元素向後移動一個位置
                {
                    data[i] = data[i - 1];
                }
                data[index] = item;                  //根據索引将元素插入到數組中
                count++;
            }
            else
            {
                Console.WriteLine("連結清單已滿，不能再插入資料");
            }
            
        }
        #endregion

        #region 判斷順序連結清單是否為空
        public bool IsEmpty()                         //判斷順序連結清單是否為空，即元素個數是否為零
        {
            return count == 0;
        }
        #endregion

        #region 根據值擷取元素在連結清單中的位置
        public int Locate(T value)                    //根據元素值，擷取元素在順序連結清單中的位置
        {
            for(int i = 0; i < count; i++)
            {
                if (data[i].Equals(value))            //循環周遊數組，根據元素值，擷取該元素在連結清單（數組）中的位置
                {
                    return i;
                }
            }
            return -1;                                 //如果該元素不在連結清單（數組）中，傳回-1
        }
        #endregion
    }
           

3.測試類;

static void Main(string[] args)
{
            IListDS<string> list = new SeqList<string>();
            list.Add("1");
            list.Add("2");
            list.Add("3");
            list.Add("4");
            list.Add("5");
            list.Add("6");
            list.Add("7");
            list.Add("8");
            list.Add("9");
            list.Add("10");
            list.Insert("&", 3);
            Console.WriteLine(list.GetLength());
            Console.WriteLine("--------------");
            for (int i = 0; i < list.GetLength() - 1; i++)
            {
                Console.Write(list.GetEle(i) + " ");
            }
}