数组实现的线性表
数组是一种静态的数据结构,在声明时需要指定其大小,之后无法改变。数组中的元素通过索引(通常是整数)进行访问,索引从0开始。
优点:
- 访问速度快,因为通过索引可以直接访问元素。
- 内存连续,便于遍历。
缺点:
- 大小固定,不能动态扩展。
- 插入和删除操作效率较低,特别是当操作位置靠近数组中间时,需要移动大量元素。
抽象类linearList
template<typename T>
class linearList
{
public:
virtual ~linearList(){};
virtual bool empty() const = 0;
virtual int size() const = 0;
virtual T& get(const int& theIndex) const = 0;
virtual int indexOf(const T& theElement) const = 0;
virtual void erase(const int& theIndex) const = 0;
virtual void insert(const int& theIndex,const T& theElement) = 0;
virtual void optput(std::ostream& out) const = 0;
};
改变一维数组长度:
注:
1.第一个参数的类型为指针的引用,能够改变调用者传入指针指向的内存地址。如果单纯的为指针类型,就不能改变调用者传入指针指向的内存地址,只能改变内存地址中的数据。这一点要区分。
2.assert一般是在调试阶段使用,这里只是为了练习用的。断言是否生效取决于是否定义了NDEBUG宏。
template<typename T>
void changeLength1D(T*& a,const int& oldLength,const int& newLength)
{
assert(newLength >= 0);
T* temp = new T[newLength];
int number = min(oldLength,newLength);
copy(a, a + number,temp);
delete [] a;
a = temp;
}
派生类arrayList:
template<typename T>
class arrayList : public linearList<T>
{
public:
arrayList(int initialCapacity = 10);
arrayList(const arrayList<T>&);
bool empty() const;
int size() const;
T& get(const int& theIndex) const;
int indexOf(const T& theElement) const;
void erase(const int& theIndex);
void insert(const int& theIndex,const T& theElement);
void optput(ostream& out) const;
int capacity() const;
private:
void checkIndex(const int& theIndex) const;
private:
T* m_pElement;
int m_iArrayLength;
int m_iListSize;
template<typename T>
arrayList<T>::arrayList(int initialCapacity)
{
assert(initialCapacity > 0);
m_iArrayLength = initialCapacity;
m_pElement = new T[m_iArrayLength];
m_iListSize = 0;
}
template<typename T>
arrayList<T>::arrayList(const arrayList<T> & theList)
{
m_iArrayLength = theList.m_iArrayLength;
m_iListSize = theList.m_iListSize;
m_pElement = new T[m_iArrayLength];
copy(theList.m_pElement,theList.m_pElement+m_iListSize,m_pElement);
}
template<typename T>
arrayList<T>::~arrayList()
{
delete [] m_pElement;
}
template<typename T>
bool arrayList<T>::empty() const
{
return m_iListSize == 0;
}
template<typename T>
int arrayList<T>::size() const
{
return m_iListSize;
}
template<typename T>
T &arrayList<T>::get(const int &theIndex) const
{
checkIndex(theIndex);
return m_pElement[theIndex];
}
template<typename T>
int arrayList<T>::indexOf(const T &theElement) const
{
auto theIndex = (int)(find(m_pElement,m_pElement+m_iListSize,theElement) - m_pElement);
if(theIndex == m_iListSize)
{
return -1;
}
return theIndex;
}
template<typename T>
void arrayList<T>::erase(const int &theIndex)
{
checkIndex(theIndex);
copy(m_pElement + theIndex + 1, m_pElement + m_iListSize, m_pElement + theIndex);
m_pElement[--m_iListSize].~T();
}
template<typename T>
void arrayList<T>::insert(const int &theIndex, const T &theElement)
{
assert(theIndex >= 0 && theIndex <= m_iListSize);
if(m_iArrayLength == m_iListSize)
{
changeLength1D(m_pElement,m_iArrayLength,m_iArrayLength*2);
m_iArrayLength *= 2;
}
copy_backward(m_pElement + theIndex,m_pElement + m_iListSize,m_pElement + m_iListSize + 1);
m_pElement[theIndex] = theElement;
m_iListSize++;
}
template<typename T>
void arrayList<T>::optput(ostream &out) const
{
copy(m_pElement,m_pElement + m_iListSize, ostream_iterator<T>(out," "));
}
template<typename T>
int arrayList<T>::capacity() const
{
return m_iArrayLength;
}
template<typename T>
void arrayList<T>::checkIndex(const int &theIndex) const
{
assert(theIndex >= 0 && theIndex < m_iListSize);
}
template<typename T>
ostream& operator<<(ostream& out,const arrayList<T>& theArrayList)
{
theArrayList.optput(out);
return out;
}