线性表-数组描述(C++)

发布于:2024-10-18 ⋅ 阅读:(31) ⋅ 点赞:(0)

数组实现的线性表

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


网站公告

今日签到

点亮在社区的每一天
去签到