线性表-数组描述（C++）

数组实现的线性表

数组是一种静态的数据结构，在声明时需要指定其大小，之后无法改变。数组中的元素通过索引（通常是整数）进行访问，索引从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;
}