C/C++数据结构之动态数组

概述

        与前一篇文章中介绍的静态数组不同，动态数组允许我们在运行时根据需要调整其大小。这意味着，数组元素的个数不是在编译时就固定的，而是可以在运行时指定。另外，我们还可以在程序执行过程中动态地添加或删除元素，而无需预先确定数组的最大容量。这种灵活性，使得动态数组非常适合用于那些数据量不确定或会随时间变化的场景。

        当我们在网上购物时，购物车就是运用动态数组的一个典型例子。我们可以不断地向购物车中添加商品，直到结账为止。即使不小心多加了某件商品，也可以轻松地从购物车中移除它。

声明与初始化

        声明一个动态数组，需要明确指定数组的类型，实际上是声明一个该类型的指针。声明格式通常如下：

        type *arrayName;

        其中，type代表数组中元素的数据类型（比如：int、float等）。

        在声明数组的同时，还可以对数组进行初始化。初始化时，需要使用new操作符来分配内存，形式如下：

        type *arrayName = new type[size];

        其中，size可以是任何有效的常量、变量和表达式。需要特别注意的是：使用完动态数组后，我们应该记得使用delete[]来释放所分配的内存，以防止内存泄漏。可参考下面的示例代码。

int nSize = 66;
int *paNumber = new int[nSize];
delete [] paNumber;

基本操作

        对动态数组进行访问、修改、遍历等基本操作，与静态数组基本类似，这里就不再赘述了。

        接下来，我们重点介绍下动态数组如何根据需要自动调整大小。在下面的示例代码中，我们定义了一个名为CDynamicArray的类，它包含了添加元素的方法AddItem。当数组达到其容量限制时，该方法会自动扩展数组容量，通常是将容量翻倍。

class CDynamicArray
{
public:
    CDynamicArray() : m_pData(NULL), m_nCapacity(0), m_nSize(0) {}
    
    ~CDynamicArray()
    {
        delete[] m_pData;
    }
    
    void AddItem(int nValue)
    {
        if(m_nSize == m_nCapacity)
        {
            // 如果数组已满，则扩展容量
            int nCapacityNew = (m_nCapacity == 0) ? 6 : m_nCapacity * 2;
            int* pData = new int[nCapacityNew];
            
            // 将旧数组的值复制到新数组
            for(int i = 0; i < m_nSize; ++i)
            {
                pData[i] = m_pData[i];
            }
            
            // 释放旧数组并更新指针和容量
            delete[] m_pData;
            m_pData = pData;
            m_nCapacity = nCapacityNew;
        }
        
        // 添加新元素
        m_pData[m_nSize++] = nValue;
    }

private:
    int* m_pData;      // 指向动态数组的指针
    int m_nCapacity;   // 数组的当前容量
    int m_nSize;       // 当前数组中的元素数量
};

总结

        使用动态数组的主要好处是：能够有效地管理内存。由于其大小可以根据实际需求进行调整，因此可以避免浪费过多的内存空间。比如：在处理用户输入的数据时，我们无法事先知道用户会输入多少条记录，这时候动态数组就能派上用场了。另外，通过动态分配和释放内存，还可以优化程序的性能，提高资源的利用率。

        然而，动态数组也有其局限性。最明显的就是效率问题：每次调整大小时，都可能涉及到内存的重新分配，这是一项相对耗时的操作。另外，频繁地增减元素，还可能导致内存碎片的问题。