数据结构的C/C++描述01:数组·动态数组 木灵的炼金工作室

写在前边:读本文您至少得能写一点C语言。

数组

数组是一个有序的元素序列,它是最基础的数据结构,是线性表的最自然的描述方式。它通过将相同大小的数据单元一个接着一个地排放来存储数据。由它的这种存放方式,我们可以以非常快的速度找出它其中的某一个位置上的元素:我们可以直接算出第n个数据的位置,从而实现直接寻址。

一般的计算机程序使用一个连续的空间来存放数组。由于高速缓存的应用,读取连续的数据往往更加高效

数组定义了两个基本操作:随机读取——对一个指定的下标,读取它的值和随机写入——对于一个指定的下标,修改它的值。

数组的实现

在C和C++语言中,我们通常使用数组首个元素的地址来代表一个数组。符号表中数组标识符的类型是一个指针。执行如下的代码:

    int test[20];
    cout << test << "----" << &test[0] << endl;

我们得到了如下的输出:0x61fdd0----0x61fdd0 可以看到:数组的标识符即为数组首元素的指针。这就说明,我们可以使用指针的操作来遍历一个数组。

方括号是什么?

对一个指针A进行[x]的操作,实际上相当于*(A + x) 运行如下的代码:

    int testInt;
    int* intPointer = &testInt;
    cout << intPointer + 5 << "----" << &intPointer[5] << endl;

我们得到了如下的输出:0x61fe18----0x61fe18

在多数的语言中,数组的大小一经声明便无法更改。因此我们需要:

动态数组

所谓动态数组,就是封装之后的标准数组,同样没有办法跳出C/C++内存管理的限制,所谓动态只是我们在需要时重新申请一块大小不同的内存空间而已。对于动态数组,我们一般维护它目前的最大容量、目前已经占用的空间和一个指针(标准数组)。它一般支持:随机读写、随机插入、随机删除。 我们来简单写一下它的架构。

template<class elementType>
class array {
protected:
    elementType* ptl; //存放数据的标准数组
    int maxLength; //标准数组申请的长度
    int usedLength = 0; //标准数组中已占用的长度

    void increaseSize();//放大数组大小
    void decreaseSize();//缩小数组大小
public:
    array(int initSize = 10);//标准构造函数
    array(const array<elementType> &theArray);//复制构造函数
    ~array() { delete[] ptl; }//析构函数
    
    int size() const { return usedLength; }//返回大小
    bool empty() const { return usedLength == 0; }//判空
    bool vaildIndex(int index) const { return index >= 0 && index < usedLength; }//判断索引是否有效 此函数可以声明为protected
    array<elementType>& operator=(const array<elementType> &A);//重载赋值运算符

    elementType& operator[](unsigned int const index);//读写
    void pop();//弹出元素
    void pop(unsigned int const index);//按索引弹出元素
    void push(elementType val);//压入元素
    void push(elementType val, unsigned int const index);//按索引压入元素
};

接下来我们来实现它: 首先来写构造函数:一般构造函数非常直观,对最大长度变量赋值,然后申请空间。 复制构造函数使用了重载赋值运算符。

template<class elementType>
array<elementType>::array(int initSize) : maxLength(initSize) {
    ptl = new elementType[initSize];
}

template<class elementType>
array<elementType>::array(const array<elementType> &theArray) {
    ptl = new elementType[theArray.maxLength];
    *this = theArray;
}

再实现两个private方法: 两个方法的实现非常相似且直观

template<class elementType>
void array<elementType>::increaseSize(){
    elementType* tempPtl = new elementType[maxLength * 2];
    for (int i = 0; i < usedLength; i++){
        tempPtl[i] = ptl[i];
    }
    maxLength *= 2;
    delete[] ptl;
    ptl = tempPtl;
}

template<class elementType>
void array<elementType>::decreaseSize(){
    elementType* tempPtl = new elementType[maxLength / 2];
    for (int i = 0; i < usedLength; i++){
        tempPtl[i] = ptl[i];
    }
    maxLength /= 2;
    delete[] ptl;
    ptl = tempPtl;
}

重载两个运算符: 此处注意:C++要求赋值运算符返回左值的引用。

template<class elementType>
array<elementType>& array<elementType>::operator=(const array<elementType> &A) {
    maxLength = A.maxLength;
    usedLength = A.usedLength;
    for (int i = 0; i < A.usedLength; i++){
        ptl[i] = A.ptl[i];
    }
    return *this;
}

template<class elementType>
elementType& array<elementType>::operator[](unsigned int const index) {
    if (vaildIndex(index))
        return ptl[index];
    else
        throw("invaild index");
}

最后完成两个操作的四个重载方法:

template<class elementType>
void array<elementType>::pop() {
    usedLength--;
    if (usedLength <= maxLength / 4)
        decreaseSize();
}

template<class elementType>
void array<elementType>::pop(unsigned int const index) {
    if (vaildIndex(index)) {
        for (int i = index; i < usedLength - 1; i++)
            ptl[i] = ptl[i + 1];
        usedLength--;
        if (usedLength <= maxLength / 4)
            decreaseSize();
    }else 
        throw("invaild index");
}

template<class elementType>
void array<elementType>::push(elementType val) {
    usedLength++;
    if (usedLength >= maxLength)
        increaseSize();
    ptl[usedLength - 1] = val;
}

template<class elementType>
void array<elementType>::push(elementType val, unsigned int const index) {
    usedLength++;
    if (vaildIndex(index)) {
        if (usedLength >= maxLength)
            increaseSize();
        for (int i = usedLength; i > index; i--)
            ptl[i] = ptl[i - 1];
        ptl[index] = val;
    }else {
        usedLength--;
        throw("invaild index");
    }
}

一个简单的动态数组类就完成了。 实际上如果#include<vector>,你可以使用C++标准库中的动态数组STLstd::vector,它与上述动态数组有类似的功能并且附加了很多实用的方法。

一点练习

请你在上述例程的基础上,重载操作符==!=,判断两个array类的引用是否完全相同。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn