我們說(shuō)到線性表，可能好多人還不太理解。那么我們舉個(gè)例子來(lái)說(shuō)，在幼兒園中，老師們總會(huì)讓小朋友以同樣的派對(duì)秩序出行，這個(gè)例子的本質(zhì)就是線性表。
10年積累的
網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先
做網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有
夏河免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
那么線性表（List）的表現(xiàn)形式是怎樣的呢？符合以下幾個(gè)特征：1、零個(gè)或多個(gè)數(shù)據(jù)元素組成的集合；2、數(shù)據(jù)元素在位置上是有序排列的；3、數(shù)據(jù)元素的個(gè)數(shù)是有限的；4、數(shù)據(jù)元素的類型必須是相同的。那么線性表的抽象定義是怎么定義的呢？線性表是具有相同類型的 n( ≥ 0 ) 個(gè)數(shù)據(jù)元素的有限序列。如下
下來(lái)我們來(lái)看看 List 的本質(zhì)：1、a0為線性表的第一個(gè)元素，只有一個(gè)后繼；2、an-1為線性表的最后一個(gè)元素，只有一個(gè)前驅(qū)；3、除 a0和 an-1外的其他元素 ai，既有前驅(qū)又有后繼；4、直接支持逐項(xiàng)訪問(wèn)和順序存取。下面我們來(lái)看看線性表一些常用操作：a> 將元素插入線性表；b> 將元素從線性表中刪除；c>獲取目標(biāo)位置處元素的值；d>設(shè)置目標(biāo)位置處元素的值；d> 獲取線性表的長(zhǎng)度；e>清空線性表。
線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型。定義如下
#ifndef LIST_H
#define LIST_H
#include "Object.h"
namespace DTLib
{
template < typename T >
class List : public Object
{
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;
};
}
#endif // LIST_H 下面我們來(lái)看看順序存儲(chǔ)的定義：線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素。如下
那么我們?cè)撊绾卧O(shè)計(jì)呢？可以使用一維數(shù)組來(lái)實(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
{
protected:
T* m_array;
int m_length;
////
}
那么順序存儲(chǔ)結(jié)構(gòu)的元素獲取操作怎樣來(lái)實(shí)現(xiàn)呢？一是判斷目標(biāo)位置是否合法，二是將目標(biāo)位置作為數(shù)組下標(biāo)獲取元素。定義如下
bool SeqList::get(int i, T& e) const
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
e = m_array[i];
}
return ret;
}
順序存儲(chǔ)結(jié)構(gòu)的元素插入示例如下
bool SeqList::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;
}
順序存儲(chǔ)結(jié)構(gòu)的元素刪除操作：1、判斷目標(biāo)位置是否合法；2、將目標(biāo)位置后的所有元素前移一個(gè)位置；3、線性表長(zhǎng)度減一。刪除示例如下
bool SeqList::remove(int i)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
for(int p=i; p 我們完成了以上的幾個(gè)重要操作之后，我們來(lái)看看 SeqList 處于一個(gè)什么樣的位置，如下圖所示
那么這便是一個(gè)順序存儲(chǔ)結(jié)構(gòu)線性表的抽象實(shí)現(xiàn)了。在 SeqList 設(shè)計(jì)時(shí)，我們要只有以下幾點(diǎn)：1、抽象類模板，存儲(chǔ)空間的位置和大小由子類完成；2、實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)線性表的關(guān)鍵操作（增、刪、查等）；3、提供數(shù)組操作符，方便快速獲取元素。那么它的抽象定義如下：
template < typename T >
class SeqList : public List
{
protected:
T* m_array; // 順序存儲(chǔ)空間
int m_length; // 當(dāng)前線性表長(zhǎng)度
public:
bool insert(int i, const T& e);
bool remove(int i);
bool set(int i, const T& e);
bool get(int i, T& e) const;
int length() const;
void clear();
// 順序存儲(chǔ)線性表的數(shù)組訪問(wèn)方式
T& operator[] (int i);
T& operator[] (int i) const;
// 順序存儲(chǔ)空間的容量
virtual int capacity() const = 0;
};
下來(lái)我們來(lái)看看 SeqList 是怎么寫的
SeqList.h 源碼
#ifndef SEQLIST_H
#define SEQLIST_H
#include "List.h"
#include "Exception.h"
namespace DTLib
{
template < typename T >
class SeqList : public List
{
protected:
T* m_array;
int m_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)
{
return insert(m_length, e);
}
bool remove(int i)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
for(int p=i; p&>(*this))[i];
}
virtual int capacity() const = 0;
};
}
#endif // SEQLIST_Hmain.cpp 源碼
#include
#include "Seqlist.h"
using namespace std;
using namespace DTLib;
int main()
{
SeqList* l;
return 0;
}
經(jīng)過(guò)編譯，編譯時(shí)通過(guò)的，說(shuō)明我們已經(jīng)完成了 SeqList 抽象類的實(shí)現(xiàn)了。接下來(lái)我們思考下，在前面的 SeqList 的實(shí)現(xiàn)中，我們?cè)谒南旅孢€有 StaticList 和 DynamicList 的兩個(gè)子類，那么我們?cè)撊绾稳?shí)現(xiàn)它們呢？StaticList 和 DynamicList 的差異在哪里？是否可以將 DynamicList 作為 StaticList 的子類實(shí)現(xiàn)呢？通過(guò)對(duì)線性表的學(xué)習(xí)，總結(jié)如下：1、線性表是數(shù)據(jù)元素的有序并且有限的集合，并且線性表中的數(shù)據(jù)元素必須是類型相同的；2、線性表可用于描述派對(duì)關(guān)系的一系列問(wèn)題；3、線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型；4、線性表在 C++ 中表現(xiàn)為一個(gè)抽象類。
分享文章：線性表的本質(zhì)、操作及順序存儲(chǔ)結(jié)構(gòu)（六）-創(chuàng)新互聯(lián)
瀏覽路徑：http://weahome.cn/article/eohsg.html
重慶分公司
重慶分公司
