用C#學習數據結構之線性表(上)，

用C#學習數據結構之線性表(上)，

什麼是線性表

 線性表是最簡單、最基本、最常用的數據結構。線性表是線性結構的抽象(Abstract)，線性結構的特點是結構中的數據元素之間存在一對一的線性關系。這種一對一的關系指的是數據元素之間的位置關系，即：（1）除第一個位置的數據元素外，其它數據元素位置的前面都只有一個數據元素；（2）除最後一個位置的數據元素外，其它數據元素位置的後面都只有一個元素。也就是說，數據元素是一個接一個的排列。因此，可以把線性表想象為一種數據元素序列的數據結構。

線性表的接口定義

 1 public interface IListDS<T> {
 2     int GetLength(); //求長度
 3     void Clear(); //清空操作
 4     bool IsEmpty(); //判斷線性表是否為空
 5     void Append(T item); //附加操作
 6     void Insert(T item, int i); //插入操作
 7     T Delete(int i); //刪除操作
 8     T GetElem(int i); //取表元
 9     int Locate(T value); //按值查找
10 }

順序表類SeqList<T>的實現

public class SeqList<T> : IListDS<T>
    {
        private int maxsize; //順序表的容量
        private T[] data; //數組，用於存儲順序表中的數據元素
        private int last; //指示順序表最後一個元素的位置

        //索引器
        public T this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }

        //最後一個數據元素位置屬性
        public int Last
        {
            get
            {
                return last;
            }
        }

        //容量屬性
        public int Maxsize
        {
            get
            {
                return maxsize;
            }
            set
            {
                maxsize = value;
            }
        }

        //構造器
        public SeqList(int size)
        {
            data = new T[size];
            maxsize = size;
            last = -1;
        }
        //求順序表的長度
        public int GetLength()
        {
            return last + 1;
        }

        //清空順序表
        public void Clear()
        {
            last = -1;
        }

        //判斷順序表是否為空
        public bool IsEmpty()
        {
            if (last == -1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //判斷順序表是否為滿
        public bool IsFull()
        {
            if (last == maxsize - 1)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //在順序表的末尾添加新元素
        public void Append(T item)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            data[++last] = item;
        }

        //在順序表的第i個數據元素的位置插入一個數據元素
        public void Insert(T item, int i)
        {
            if (IsFull())
            {
                Console.WriteLine("List is full");
                return;
            }
            if (i < 1 || i > last + 2)
            {
                Console.WriteLine("Position is error!");
                return;
            }
            if (i == last + 2)
            {
                data[last + 1] = item;
            }
            else
            {
                for (int j = last; j >= i - 1; --j)
                {
                    data[j + 1] = data[j];
                }
                data[i - 1] = item;
            }
            ++last;
        }

        //刪除順序表的第i個數據元素
        public T Delete(int i)
        {
            T tmp = default(T);
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return tmp;
            }
            if (i < 1 || i > last + 1)
            {
                Console.WriteLine("Position is error!");
                return tmp;
            }
            if (i == last + 1)
            {
                tmp = data[last--];
            }
            else
            {
                tmp = data[i - 1];
                for (int j = i; j <= last; ++j)
                {
                    data[j] = data[j + 1];
                }
            }
            --last;
            return tmp;
        }

        //獲得順序表的第i個數據元素
        public T GetElem(int i)
        {
            if (IsEmpty() || (i < 1) || (i > last + 1))
            {
                Console.WriteLine("List is empty or Position is error!");
                return default(T);
            }
            return data[i - 1];
        }

        //在順序表中查找值為value的數據元素
        public int Locate(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is Empty!");
                return -1;
            }
            int i = 0;
            for (i = 0; i <= last; ++i)
            {
                if (value.Equals(data[i]))
                {
                    break;
                }
            }
            if (i > last)
            {
                return -1;
            }
            return i;
        }
    }