數據結構 C#語言版 第2章 線性表(1)

2.2 順序表

2.2.1 順序表的定義www.2cto.com

在計算機內，保存線性表最簡單、最自然的方式，就是把表中的元素一個接一個地放進順序的存儲單元，這就是線性表的順序存儲(Sequence Storage)。線性表的順序存儲是指在內存中用一塊地址連續的空間依次存放線性表的數據元素，用這種方式存儲的線性表叫順序表(Sequence List)。順序表的特點是表中相鄰的數據元素在內存中位置也相鄰。

C#語言中的數組在內存中占用的存儲空間就是一組連續的存儲空間，因此，數據具有隨機存取的特點，所以，數組天生具有表示順序表的數據存儲區域的特點。

隨機存取（有時亦稱直接存取）代表同等時間存取一組序列中的一個隨意元件。反之則稱循序存取，即是需要更多時間去存取一個遠端元件。

C# 實現順序表:

[csharp] class SeqList<T>:ConsoleApplication3.ISeqList<T> 
{ 
    public int Maxsize{get;set;} 
    private T[] data; 
    public int Last { get; private set; } 
 
    //索引器  
    public T this[int index] 
    { 
        get 
        { 
            return data[index]; 
        } 
        set 
        { 
            data[index] = 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"); 
        else 
            data[++Last] = item; 
    } 
 
    public void Insert(T item, int i) 
    { 
        if (IsFull()) 
            Console.WriteLine("List is full"); 
        else if (i < 0 || i > Last + 1) 
            Console.WriteLine("Position is error!"); 
        else if (i == Last + 1) 
            data[++Last] = item; 
        else 
        { 
            for (int j = ++Last; j >i; --j) 
            { 
                data[j] = data[j - 1]; 
            } 
            data[i] = item; 
        } 
    } 
 
    public T Delete(int i) 
    { 
        T tmp = default(T); 
        if (IsEmpty()) 
        { 
            Console.WriteLine("List is empty"); 
            return tmp; 
        } 
        else if (i > Last || i < 0) 
        { 
            Console.WriteLine("Position is error!"); 
            return tmp; 
        } 
        else 
        { 
            tmp = data[i]; 
            for (int j = i; j < Last; j++) 
            { 
                data[j] = data[j + 1]; 
            } 
            --Last; 
            return tmp; 
        } 
    } 
 
    public T GetItem(int i) 
    { 
        if (IsEmpty() || i < 0 || i > Last + 1) 
        { 
            Console.WriteLine("List is empty or Position is error!"); 
            return default(T); 
        } 
        else 
            return data[i]; 
    } 
 
    public int Locate(T value) 
    { 
        if (IsEmpty()) 
        { 
            Console.WriteLine("List is empty!"); 
            return -1; 
        } 
 
        for (int i = 0; i <= Last; ++i) 
        { 
            if (value.Equals(data[i])) 
                return i; 
        } 
 
        return -1; 
    } 
} 
    class SeqList<T>:ConsoleApplication3.ISeqList<T>
    {
        public int Maxsize{get;set;}
        private T[] data;
        public int Last { get; private set; }

        //索引器
        public T this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = 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");
            else
                data[++Last] = item;
        }

        public void Insert(T item, int i)
        {
            if (IsFull())
                Console.WriteLine("List is full");
            else if (i < 0 || i > Last + 1)
                Console.WriteLine("Position is error!");
            else if (i == Last + 1)
                data[++Last] = item;
            else
            {
                for (int j = ++Last; j >i; --j)
                {
                    data[j] = data[j - 1];
                }
                data[i] = item;
            }
        }

        public T Delete(int i)
        {
            T tmp = default(T);
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return tmp;
            }
            else if (i > Last || i < 0)
            {
                Console.WriteLine("Position is error!");
                return tmp;
            }
            else
            {
                tmp = data[i];
                for (int j = i; j < Last; j++)
                {
                    data[j] = data[j + 1];
                }
                --Last;
                return tmp;
            }
        }

        public T GetItem(int i)
        {
            if (IsEmpty() || i < 0 || i > Last + 1)
            {
                Console.WriteLine("List is empty or Position is error!");
                return default(T);
            }
            else
                return data[i];
        }

        public int Locate(T value)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty!");
                return -1;
            }

            for (int i = 0; i <= Last; ++i)
            {
                if (value.Equals(data[i]))
                    return i;
            }

            return -1;
        }
    }[csharp] view plaincopyprint?//ISeqList.cs  
using System; 
namespace ConsoleApplication3 
{ 
    interface ISeqList<T> 
    { 
        void Append(T item); 
        void Clear(); 
        T Delete(int i); 
        T GetItem(int i); 
        int GetLength(); 
        void Insert(T item, int i); 
        bool IsEmpty(); 
        bool IsFull(); 
        int Locate(T value); 
    } 
} 

 摘自 xufei96的專欄