线性表之数组

数组（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函数进行扩容。