數(shù)據(jù)結(jié)構(gòu)(03)_順序存儲(chǔ)結(jié)構(gòu)線性表-創(chuàng)新互聯(lián)

基于前面實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類模板基礎(chǔ)，繼續(xù)完成基于順序存儲(chǔ)結(jié)構(gòu)的線性表的實(shí)現(xiàn)，繼承關(guān)系圖如下：
數(shù)據(jù)結(jié)構(gòu)(03)_順序存儲(chǔ)結(jié)構(gòu)線性表

江北網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),江北網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為江北1000多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站建設(shè)要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的江北做網(wǎng)站的公司定做！

1.線性表簡(jiǎn)介

1.1.線性表的表現(xiàn)形式

零個(gè)多多個(gè)數(shù)據(jù)元素組成的集合
數(shù)據(jù)元素在位置上是有序排列的
數(shù)據(jù)元素的個(gè)數(shù)是有限的
數(shù)據(jù)元素的類型必須相同
1.2.線性表的抽象定義、性質(zhì)
線性表是具有相同類型的n(>=)個(gè)數(shù)據(jù)元素的有限序列，(a0, a1, a2... an-1),其中ai是表項(xiàng)，n是表長(zhǎng)度。
性質(zhì)：
a0為線性表的第一個(gè)元素，只有一個(gè)后繼
an-1為線性表的最后一個(gè)元素，只有一個(gè)前驅(qū)
其他數(shù)據(jù)項(xiàng)既有后繼，也有前驅(qū)
支持逐項(xiàng)和順序存儲(chǔ)
1.3.線性表的抽象實(shí)現(xiàn)
插入、刪除數(shù)據(jù)元素
獲取、設(shè)置目標(biāo)位置元素的值
獲取線性表的長(zhǎng)度
清空線性表

template <typename T>
class List:public Object
{
protected:
    List(const List&);
    List& operator ==(const List&);

public:
    List(){}
    virtual bool insert(const T& e) = 0;
    virtual bool insert(int i,const T& e) = 0;
    virtual bool remove(int i) = 0;
    virtual bool set(int i,const T& e) = 0;
    virtual bool get(int i,T& e) const  = 0;
    virtual int length() const = 0;
    virtual void clear() = 0;
};

1.4.總結(jié)：

線性表是數(shù)據(jù)元素的有序并且有限的集合，其中的數(shù)據(jù)元素類型相同，在程序中表現(xiàn)為一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)，可以使用C++中的抽象類來表示，用來描述排隊(duì)關(guān)系的問題。

2.線性表的順序存儲(chǔ)結(jié)構(gòu)

2.1.概念和設(shè)計(jì)思路

定義：
線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素。
數(shù)據(jù)結(jié)構(gòu)(03)_順序存儲(chǔ)結(jié)構(gòu)線性表
設(shè)計(jì)思路：
使用一維數(shù)組來實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)：

// 存儲(chǔ)空間：T* m_array; 當(dāng)前長(zhǎng)度：int m_length；
template <typename T>
class SeqList : public List<T>
{
protected:
    T* m_array;
    int m_length;
};

3.SeqList的設(shè)計(jì)要點(diǎn)

抽象類模板，存儲(chǔ)空間的大小和位置由子類完成；
實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)線性表的關(guān)鍵操作（增、刪、查、等）；
提供數(shù)組操作符重載，方面快速獲取元素；
3.1SeqList實(shí)現(xiàn)

template <typename T>
class SeqList : public List<T>
{
protected:
    T* m_array;      // 順序存儲(chǔ)空間
    int m_length;    // 當(dāng)前線性長(zhǎng)度
public:

    bool insert(int index, const T& e)
    {
        bool ret = ( (index>=0) && (index<=m_length) ); // <= 因?yàn)榭梢圆迦氲狞c(diǎn)，必然比當(dāng)前元素多1

        if(ret && ( m_length < capacity() ))    // 當(dāng)前至少有一個(gè)空間可插入
        {
            for(int p=m_length-1; p>=index; p--)
            {
                m_array[p + 1] = m_array[p];
            }

            m_array[index] = e;
            m_length++;
        }
        return ret;
    }

    bool insert(const T& e)
    {
        return insert(m_length, e);
    }

    bool remove(int index)
    {
        bool ret = ( (index>=0) && (index<m_length) );  // 目標(biāo)位置合法 <m_length

        if(ret)
        {
            for(int p=index; p<m_length-1; p++)        // 注意思考此處的邊界條件
            {
                m_array[p] = m_array[p+1];
            }

             m_length--;
        }

        return ret;
    }

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

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

        return ret;
    }

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

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

        return ret;
    }

    int length() const
    {
        return m_length;
    }

    void clear()
    {
        m_length = 0;
    }

    // 順序存儲(chǔ)表的數(shù)組訪問方式
    T& operator [] (int index)
    {
        if( (index>=0) && (index<m_length) )
        {
            return m_array[index];
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "index out of range...");
        }
    }

    T operator [] (int index) const
    {
        static_cast<SeqList<T>&>(*this)[index];    // 去除const屬性，然后調(diào)用非const版本實(shí)現(xiàn)
    }

    // 順序存儲(chǔ)表的的容量
    virtual int capacity() const = 0;
};

4.StaticList和DynamicList

4.1.StaticList的設(shè)計(jì)要點(diǎn)：

類模板

使用原生數(shù)組做為順序存儲(chǔ)空間

使用模板參數(shù)決定數(shù)組的大小

template < typename T, int N >
class StaticList : public SeqList <T>
{
protected:
T m_space[];        // 順序存儲(chǔ)空間，N為模板參數(shù)
public:
StaticList();       // 指定父類成員的具體值
int capacity() const;
};

4.2. StaticList實(shí)現(xiàn)

template < typename T, int N >
class StaticList : public SeqList <T>
{
protected:
    T m_space[N];       // 順序存儲(chǔ)空間，N為模板參數(shù)
public:
    StaticList()        // 指定父類成員的具體值
    {
        this->m_array = m_space;
        this->m_length = 0;
    }
    int capacity() const
    {
        return N;
    }
};

4.3.DynamicList的設(shè)計(jì)要點(diǎn)：

類模板

申請(qǐng)連續(xù)堆空間做為順序存儲(chǔ)空間
保證重置順序存儲(chǔ)空間的異常安全性
函數(shù)異常安全的概念：
不允許任何內(nèi)存泄露，不允許破壞數(shù)據(jù)
函數(shù)異常安全的基本保證：

如果有異常拋出，對(duì)象內(nèi)的任何成員任然能保持有效狀態(tài)，沒有數(shù)據(jù)破話或者資源泄露。

template < typename T>
class DynamicList : public SeqList <T>
{
protected:
int capacity;       // 順序存儲(chǔ)空間的大小
public:
DynamicList(int capacity);   // 申請(qǐng)空間
int capacity(void) const         // 返回capacity的值 
// 重置存儲(chǔ)空間的大小
void reset(int capacity);
~DynamicList();             // 歸還空間
};

4.4. DynamicList實(shí)現(xiàn)

template <typename T>
class DynamicList : public SeqList<T>
{

protected:
    int m_capacity;
public:
    DynamicList(int capacity)
    {
        this->m_array = new T[capacity];
        if(this->m_array != NULL)
        {
            this->m_length = 0;
            this->m_capacity = capacity;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ...");
        }
    }

    int capacity()const
    {
        return m_capacity;
    }

    void resize(int capacity)
    {
        if(capacity != m_capacity)
        {
            T* array = new T[capacity];
            if(array != NULL)
            {
                int length = (this->m_length < capacity ? this->m_length : capacity);
                for(int i=0;i<length;i++)
                {
                    array[i] = this->m_array[i];
                }

                T* temp = this->m_array;
                this->m_array = array;
                this->m_length = length;
                this->m_capacity = capacity;
                delete[] temp;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ...");
            }
        }
    }

    ~DynamicList()
    {
        delete[] this->m_array;
    }
};

5.順序存儲(chǔ)結(jié)構(gòu)線性表分析

5.1.時(shí)間復(fù)雜度

順序存儲(chǔ)結(jié)構(gòu)線性表的效率為O(n)，主要受其插入和刪除操作的影響（譬如插入操作時(shí)，要插入位置之后的數(shù)據(jù)要向后挪動(dòng)）。

5.2.問題

兩個(gè)長(zhǎng)度相同的順序存儲(chǔ)結(jié)構(gòu)線性表，插入、刪除操作的耗時(shí)是否相同？

不相同，對(duì)順序存儲(chǔ)結(jié)構(gòu)線性表，其插入、刪除操作的復(fù)雜度還取決于存儲(chǔ)的數(shù)據(jù)類型，譬如一個(gè)普通類型和一個(gè)字符串類型/類類型就完全不同（對(duì)于復(fù)雜數(shù)據(jù)類型，元素之間移動(dòng)時(shí)必然耗時(shí)很多）。從這個(gè)角度考慮，線性表的效率存在隱患。
花費(fèi)多少
5.3.禁用拷貝構(gòu)造和賦值操作。
拷貝構(gòu)造和賦值操作會(huì)導(dǎo)致兩個(gè)指針指向同一個(gè)地址，導(dǎo)致內(nèi)存重復(fù)釋放。對(duì)于容器類型的類，可以考慮禁用拷貝構(gòu)造和賦值操作。
原因： 1、對(duì)于生活中容器類的東西，我們無法對(duì)其進(jìn)行賦值（譬如生活中我們不可能將杯子中的水進(jìn)行復(fù)制，只能使用另一個(gè)杯子重新去獲取等量的水）。
實(shí)現(xiàn)：將拷貝構(gòu)造和賦值操作函數(shù)定義為proteced成員，在類的外部，不能使用。
```
protected:
List(const List&){}
List& operator = (const List&){}
```
5.4.注意事項(xiàng)
線性表不能直接當(dāng)做數(shù)組來使用
順序存儲(chǔ)結(jié)構(gòu)線性表提供了數(shù)組操作符的重載，可以直接像數(shù)組一樣，同過下標(biāo)直接獲取目標(biāo)位置的元素，在具體的使用上類似數(shù)組，但是本質(zhì)上不同，不能代替數(shù)組使用：
必須先進(jìn)行插入操作，才能對(duì)其內(nèi)部的數(shù)據(jù)進(jìn)行操作。
原生數(shù)組是自帶空間的，可以直接操作。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站欄目：數(shù)據(jù)結(jié)構(gòu)(03)_順序存儲(chǔ)結(jié)構(gòu)線性表-創(chuàng)新互聯(lián)
文章路徑：http://jinyejixie.com/article38/dsicsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、網(wǎng)站導(dǎo)航、品牌網(wǎng)站設(shè)計(jì)、搜索引擎優(yōu)化、定制開發(fā)、定制網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

數(shù)據(jù)結(jié)構(gòu)(03)_順序存儲(chǔ)結(jié)構(gòu)線性表-創(chuàng)新互聯(lián)

1.線性表簡(jiǎn)介

1.1.線性表的表現(xiàn)形式

1.2.線性表的抽象定義、性質(zhì)

1.3.線性表的抽象實(shí)現(xiàn)