线性表之数组

        数组（Array）是 C/C++ 中最基础和重要的数据结构之一，它提供了一种有效存储和访问固定大小元素集合的方式。关于数组的定义和使用相信大家都已经熟练掌握，本文将着重为大家剖析数组的物理结构和逻辑结构。

1. 数组的物理结构

        数组的物理结构是指数组元素在内存中的实际存储方式。在内存中，数组元素是连续存储的，这意味着相邻元素的地址是连续的，且每个元素占用固定大小的内存空间。

        例如，对于一个整型数组 int numbers[5]，如果数组的起始地址为 0x1000，每个整型元素占据4个字节，那么数组中的元素在内存中的存储情况可能如下：

0x1000: numbers[0]
0x1004: numbers[1]
0x1008: numbers[2]
0x100C: numbers[3]
0x1010: numbers[4]

        这样的存储方式保证了对数组元素的快速访问和遍历，因为可以通过计算地址偏移来访问数组中的任意元素。

2. 数组的逻辑结构

2.1 线性表

        数组是一种线性数据结构，它由相同类型的元素组成，并以连续的内存地址存储。所谓的线性表就是由一个或多个元素组成的有序序列。在一个线性表中头部节点只有一个后继节点，尾部节点只有一个前驱节点，头部和尾部中间的节点分别有一个前驱节点，一个后继节点，如下图：

        根据从前到后的顺序，我们就可以将A1记作头结点，A5记作尾节点，A2~A4记作中间节点。拿A3举例，它的前驱节点是A2，后继节点是A4。

        在逻辑上，数组是一个有序集合，每个元素可以通过唯一的下标（索引）来访问。

        例如，数组 int numbers[5] 中的元素可以用 numbers[0]、numbers[1]、numbers[2]、numbers[3] 和 numbers[4] 这些下标来访问。这种抽象方式隐藏了数组元素在内存中的实际存储方式，使程序员只需关注元素的逻辑位置而无需担心其物理存储。

2.2 数组的优缺点

关于数组的使用，它的优缺点总结如下：

优点

• 通过下标访问数组中的任意元素速度非常快，时间复杂度是 O(1)
• 末尾位置增加、删除元素速度非常快，时间复杂度是O(1)
• 访问当前元素前、后相邻位置的元素非常方便

缺点

• 非末尾位置增加、删除元素需要进行大量的数据移动，时间复杂度为 O(n)
• 数组扩容的时候资源开销比较大

2.3 动态数组

        在C语言中是没有动态数组的概念的，只有静态数组。想要使用动态数组只能由程序员自己实现，其核心思想有以下几点：

• 记录下数组的容量和数组中存储的数据的个数
• 当数组的容量 == 存储的数据个数的时候重新申请一块新内存或者扩容

        与此同时，如果要求这个动态数组可以在不同场景下存储不同类型的数据，我们就需要使用泛型编程，因此可以这样定义这个类:

#include <iostream>
using namespace std;

template <typename T>
class Array
{
public:
    Array(int size = 64);
    ~Array();

    // 在尾部添加元素
    void append(T val);
    // 尾部删除元素
    void popBack();
    // 插入元素
    void insert(int pos, T val);
    // 删除元素
    void remove(int pos);
    // 查询元素-> 返回位置
    int find(T val);
    // 得到指定位置的元素的值
    int value(int pos);
    // 获取数组元素数量
    int size();
    // 打印数据
    void show();
private:
    void expand(int size);
private:
    T* m_arry;           // 数组的起始地址
    int m_capacity;      // 数组容量
    int m_count;         // 数组中的元素数量
};

        在编写模板类的时候需要注意一个问题：类的声明和定义要写到同一个文件中，如果分开写到 .h 和 .cpp 中，编译的时候就会出现链接错误。因此在实现上边这个的类的时候可以将代码写到一个 .h 或者 .cpp 文件中。

array.cpp 文件

#include <iostream>
#include <cassert>
using namespace std;

template <typename T>
class Array
{
public:
    Array(int size = 64);
    ~Array();

    // 在尾部添加元素
    void append(T val);
    // 尾部删除元素
    void popBack();
    // 插入元素
    void insert(int pos, T val);
    // 删除元素
    void remove(int pos);
    // 查询元素-> 返回位置
    int find(T val);
    // 得到指定位置的元素的值
    int value(int pos);
    // 获取数组元素数量
    int size();
    // 打印数据
    void show();

private:
    void expand(int size);

private:
    T* m_arry;           // 数组的起始地址
    int m_capacity;      // 数组容量
    int m_count;         // 数组中的元素数量
};

template <typename T>
Array<T>::Array(int size) :
    m_capacity(size),
    m_count(0),
    m_arry(new T[size]()) 
{
}

template <typename T>
Array<T>::~Array()
{
    // 释放资源
    delete[]m_arry;
    m_arry = nullptr;
}

template <typename T>
void Array<T>::append(T val)
{
    // 满了, 扩容
    if (m_count == m_capacity)
    {
        expand(m_capacity * 2);
    }
    m_arry[m_count++] = val;
}

template <typename T>
void Array<T>::popBack()
{
    if (m_count == 0)
    {
        return;
    }
    m_count--;  // 把尾部元素变成了无效元素
}

template <typename T>
void Array<T>::insert(int pos, T val)
{
    if (pos < 0 || pos > m_count) 
    {
        cout << "插入数据失败: 无效的pos位置" << endl;
        return;
    }
    if (m_count == m_capacity)
    {
        expand(2 * m_capacity);
    }
    // 移动元素
    for (int i = m_count - 1; i >= pos; --i)
    {
        m_arry[i + 1] = m_arry[i];
    }
    m_arry[pos] = val;
    m_count++;
}

template <typename T>
void Array<T>::remove(int pos)
{
    if (pos < 0 || pos >= m_count)  
    {
        return;
    }
    int value = m_arry[pos];
    for (int i = pos + 1; i < m_count; ++i)
    {
        m_arry[i - 1] = m_arry[i];
    }
    m_count--;
}

template <typename T>
int Array<T>::find(T val)
{
    for (int i = 0; i < m_count; ++i)
    {
        if (m_arry[i] == val)
        {
            return i;
        }
    }
    return -1;
}

template<typename T>
int Array<T>::value(int pos)
{
    assert(pos >= 0 && pos < m_count);
    return m_arry[pos];
}

template<typename T>
int Array<T>::size()
{
    return m_count;
}

template <typename T>
void Array<T>::show()
{
    for (int i = 0; i < m_count; ++i)
    {
        cout << m_arry[i] << " ";
        cout << (int)m_arry[i] << " ";
    }
    cout << endl;
}

template <typename T>
void Array<T>::expand(int size)
{
    // 申请一块新的内存
    T* ptr = new T[size]();
    // 旧数据拷贝到新内存
    memcpy(ptr, m_arry, sizeof(T) * m_capacity);
    delete[]m_arry;
    // 数据更新
    m_arry = ptr;
    m_capacity = size;
}

        上面的代码是通过append或者insert函数往数组中添加数据的时候，判断了数组中已存储的元素数量，如果数组已满便调用expand函数进行扩容。

• 使用relloc函数扩容比重新分配内存的方式要简单一些，如果它在其它位置开辟了新的存储空间而不是在尾部扩容，会自动释放旧的内存块。
• 对数组进行动态扩容之后，要对数组的容量进行更新。
• 对数组进行动态扩容之后，要更新数组指针指向的起始地址。

        另外，通过阅读上述代码也可以证明在数组的中间位置添加、删除数据都会涉及到元素的大量移动（后移或者前移），操作相率相对较低。