13518219792
基于前面實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類模板基礎(chǔ)，繼續(xù)完成基于順序存儲結(jié)構(gòu)的線性表的實現(xiàn)，繼承關(guān)系圖如下：
線性表是具有相同類型的n(>=)個數(shù)據(jù)元素的有限序列，(a0, a1, a2... an-1),其中ai是表項，n是表長度。
性質(zhì)：
template
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;
}; 線性表是數(shù)據(jù)元素的有序并且有限的集合，其中的數(shù)據(jù)元素類型相同，在程序中表現(xiàn)為一個特殊的數(shù)據(jù)結(jié)構(gòu)，可以使用C++中的抽象類來表示，用來描述排隊關(guān)系的問題。
定義：
線性表的順序存儲結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素。
設(shè)計思路：
使用一維數(shù)組來實現(xiàn)存儲結(jié)構(gòu)：
// 存儲空間：T* m_array; 當前長度：int m_length；
template
class SeqList : public List
{
protected:
T* m_array;
int m_length;
}; template
class SeqList : public List
{
protected:
T* m_array; // 順序存儲空間
int m_length; // 當前線性長度
public:
bool insert(int index, const T& e)
{
bool ret = ( (index>=0) && (index<=m_length) ); // <= 因為可以插入的點，必然比當前元素多1
if(ret && ( m_length < capacity() )) // 當前至少有一個空間可插入
{
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=0) && (index=0) && (index=0) && (index&>(*this)[index]; // 去除const屬性，然后調(diào)用非const版本實現(xiàn)
}
// 順序存儲表的的容量
virtual int capacity() const = 0;
};
類模板
template < typename T, int N >
class StaticList : public SeqList
{
protected:
T m_space[]; // 順序存儲空間，N為模板參數(shù)
public:
StaticList(); // 指定父類成員的具體值
int capacity() const;
}; template < typename T, int N >
class StaticList : public SeqList
{
protected:
T m_space[N]; // 順序存儲空間，N為模板參數(shù)
public:
StaticList() // 指定父類成員的具體值
{
this->m_array = m_space;
this->m_length = 0;
}
int capacity() const
{
return N;
}
};
類模板
template < typename T>
class DynamicList : public SeqList
{
protected:
int capacity; // 順序存儲空間的大小
public:
DynamicList(int capacity); // 申請空間
int capacity(void) const // 返回capacity的值
// 重置存儲空間的大小
void reset(int capacity);
~DynamicList(); // 歸還空間
}; template
class DynamicList : public SeqList
{
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;im_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;
}
};
順序存儲結(jié)構(gòu)線性表的效率為O(n)，主要受其插入和刪除操作的影響（譬如插入操作時，要插入位置之后的數(shù)據(jù)要向后挪動） 。
兩個長度相同的順序存儲結(jié)構(gòu)線性表，插入、刪除操作的耗時是否相同？
拷貝構(gòu)造和賦值操作會導(dǎo)致兩個指針指向同一個地址，導(dǎo)致內(nèi)存重復(fù)釋放。對于容器類型的類，可以考慮禁用拷貝構(gòu)造和賦值操作。
原因： 1、對于生活中容器類的東西，我們無法對其進行賦值（譬如生活中我們不可能將杯子中的水進行復(fù)制，只能使用另一個杯子重新去獲取等量的水）。
實現(xiàn)：將拷貝構(gòu)造和賦值操作函數(shù)定義為proteced成員，在類的外部，不能使用。
protected:
List(const List&){}
List& operator = (const List&){}線性表不能直接當做數(shù)組來使用
順序存儲結(jié)構(gòu)線性表提供了數(shù)組操作符的重載，可以直接像數(shù)組一樣，同過下標直接獲取目標位置的元素，在具體的使用上類似數(shù)組，但是本質(zhì)上不同，不能代替數(shù)組使用：
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
