數(shù)據(jù)結(jié)構(gòu)--線性表的順序存儲(chǔ)結(jié)構(gòu)

一 線性表的本質(zhì)和操作

線性表的表現(xiàn)形式主要有以下幾個(gè)方面
1 零個(gè)或多個(gè)數(shù)據(jù)元素組成的集合
2 數(shù)據(jù)元素在位置上是有序排列的
3 數(shù)據(jù)元素的個(gè)數(shù)是有限的
4 數(shù)據(jù)元素的類型必須相同
線性表的抽象定義是具有相同的n(n>=0)個(gè)數(shù)據(jù)元素的優(yōu)先序列(a0,a1......an)

二 線性表的性質(zhì)

a0為線性表的i的一個(gè)元素，只有一個(gè)后繼
an-1為線性表的最后一個(gè)元素，只有一個(gè)前驅(qū)
除去這兩個(gè)元素外的其他元素ai既有前前驅(qū)，又有后繼
直接支持逐項(xiàng)訪問(wèn)和順序存取

三線性表的一些常用操作

1將元素插入線性表
2將元素從線性表中刪除
3獲取目標(biāo)位置處元素的值
4設(shè)置目標(biāo)位置處元素的值
5獲取線性表的長(zhǎng)度
6清空線性表

template <typename T>
class List :public Object
{//Object為頂層父類
  protected:
     List(const List&);
     List& operator=(const List&);//避免賦值操作
    public:
        List(){};
        virtual bool insert(int i,const T&e)=0;//插入
        virtual bool remove(int i)=0;//刪除
        virtual bool set(int i,const T&e)=0//設(shè)置值;
        virtual bool get(int i,const T&e)=0;//獲取值
        virtual int length()const=0;//獲取長(zhǎng)度
        virtual void clear()=0;//清空操作
}

四 線性表的順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)
思路：可以用一維數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)
存儲(chǔ)空間 *T array
當(dāng)前的長(zhǎng)度 int length**

a.順序存儲(chǔ)結(jié)構(gòu)的元素插入操作
1.判斷目位置是否合法
2.將目標(biāo)位置之后的所有元素后移一個(gè)位置
3.將新元素插入目標(biāo)位置
4.線性表的長(zhǎng)度+1
簡(jiǎn)單的圖示

代碼的實(shí)現(xiàn)部分

inset (int i,const T&e)
{
    bool ret=((0<=i)&&(i<length));
    ret=ret&&((length+1)<=capacity());//對(duì)位置進(jìn)行判斷是否合法

    if(ret)
    {
        for(int p=length-1;p>i;p--)
        {
            array[p+1]=arrray[p];//將目標(biāo)位置后的元素后移一位
        }
        array[i]=e;//將元素插入
        length++;//線性表長(zhǎng)度加1
    }
    return ret;
}

b.順序存儲(chǔ)結(jié)構(gòu)的元素刪除操作
1.對(duì)位置進(jìn)行判斷是否合法
2.將目標(biāo)位置后的所有元素前移一個(gè)位置
3.線性表的長(zhǎng)度減1
實(shí)現(xiàn)代碼如下
簡(jiǎn)單的圖示

remove(int i,const T&e)
{
    bool ret=((o<=i)&&(i<=length));
    ret=ret&&((length+1)<=capacity());//對(duì)位置進(jìn)行判斷是否合法

    if(ret)
    {
        for(int p=i;p<length-1;p++)//在刪除處進(jìn)行遍歷
        {
            array[p]=array[p+1];//將元素前移一個(gè)位置
        }
        length--;//線性表的長(zhǎng)度減1
    }
        return ret;
}

c.元素的設(shè)置以及獲取
1判斷目標(biāo)位置是否合法
2.將目標(biāo)位置作為數(shù)組下標(biāo)對(duì)元素進(jìn)行操作
實(shí)現(xiàn)代碼如下

set(int i,const T&e)
{
    bool ret=((0<=i)&&(i<=length))

    if(ret)
    {
        array[i]=e;
    }
    return ret;
}

get(int  i,T&e)const
{
    bool ret=((0<=i)&&(i<=length))

    if(ret)
    {
        e=array[i];
    }
    return ret;
}

d.其他的操作(清除及獲取長(zhǎng)度)
實(shí)現(xiàn)代碼如下

        int length()const
        {
            return length;
        }

        void clear()
        {
            length=0;
        }

完整的代碼如下

include "List"
include "Object"

namespace MyLib
{
    template<typename T>
    class SeqList :public List<T>
    {
        protected:
            T* array;
            int length;
        public:
            bool insert(int i,const T&e)
        {
            bool ret=((0<=i)&&(i<=m_length));

            ret=ret&&(m_length<capacity());
            if(ret)
            {
                for(int p=m_length-1;p>=i;p--)
                {
                    m_array[p+1]=m_array[p];
                }
                m_array[i]=e;
                m_length++;
            }

            return ret;
        }

        bool insert(const T&e)//在尾部插入數(shù)據(jù)
        {
            return insert(m_length,e);
        }

        /*刪除操作
         1.判斷目標(biāo)是否合法
         2.將目標(biāo)位置后的所有元素前移一個(gè)位置
         3.線性表長(zhǎng)度減1
        */
        bool remove(int i)
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                for(int p=i;p<m_length;p++)
                {
                    m_array[p]=m_array[p+1];
                }
                m_length--;
            }
            return ret;
        }

        bool set(int i,const T&e)
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                m_array[i]=e;
            }
            return ret;
        }

        bool get(int i,T&e) const
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                e=m_array[i];
            }
            return ret;
        }

        int find(const T&e)const
        {
            int ret=-1;

            for(int i=0;i<m_length;i++)
            {
                if(m_array[i]=e)
                {
                    ret=i;
                    break;
                }
            }

            return ret;
        }

        int length()const
        {
            return m_length;
        }

        void clear()
        {
            m_length=0;
        }

        //數(shù)組的訪問(wèn)
        T& operator[](int i)//數(shù)組操作符的重載
        {
           if((0<=i)&&(i<=m_length))
           {
               return m_array[i];
           }
           else
           {
               THROW_EXCEPTION(indexOutOfBoundsException,"Parameter i is invaild...");//i不合法，越界操作異常
           }
        }

        T operator [](int i)const
        {
            //去除當(dāng)前對(duì)象的const屬性
            return (const_cast<SeqList<T>&>(*this))[i];
        }

        virtual int capacity()const=0;//純虛h函數(shù)，由子類重寫
    };
}