C++ 数据结构 静态顺序表、动态顺序表。

静态顺序表（Static Array List）是一种线性数据结构，通常用数组实现。它具有固定的大小，并在编译时分配内存。以下是静态顺序表的一些基本概念和实现示例。

静态顺序表基本概念

1. 固定大小：静态顺序表的大小在创建时定义，无法动态扩展。
2. 数组实现：使用数组存储数据元素，支持随机访问。
3. 插入和删除操作：需要移动元素以保持顺序，可能会影响性能。
4. 顺序存储：元素在内存中是连续存储的，支持高效的随机访问。

1. 数据结构示意图

假设我们有一个静态顺序表的初始状态如下（数组最大容量为5）：

Index:  0   1   2   3   4+---+---+---+---+---+
Data:   |   |   |   |   |   |+---+---+---+---+---+
Length: 0

2. 尾部插入

操作：将元素10插入到表的末尾。

Index:  0   1   2   3   4+---+---+---+---+---+
Data:   | 10|   |   |   |   |+---+---+---+---+---+
Length: 1

这里因为是一个空表，所以插入之后值就是index是0的位置。

3. 头部插入

操作：将元素5插入到表的头部（索引0）。

Index:  0   1   2   3   4+---+---+---+---+---+
Data:   |  5| 10|   |   |   |+---+---+---+---+---+
Length: 2

4. 中间插入

操作：将元素7插入到索引1的位置。

过程：

1. 移动元素10（从索引1到索引2）以为新元素腾出空间。

结果：

Index:  0   1   2   3   4+---+---+---+---+---+
Data:   |  5|  7| 10|   |   |+---+---+---+---+---+
Length: 3

#include <iostream>
#include <stdexcept> 
#include <string>const int MAX_SIZE = 5; // 最大容量template <typename T>
class StaticArrayList {
public:StaticArrayList() : m_length(0) {} // 构造函数，初始化长度为0~StaticArrayList() {} // 默认析构函数// 插入元素bool insert(int index, const T &value) {if (index < 0 || index > m_length || m_length >= MAX_SIZE) {return false; // 索引越界或已满}// 移动元素以腾出插入位置for (int i = m_length; i > index; --i) {m_data[i] = m_data[i - 1];}m_data[index] = value; // 插入新元素m_length++;return true;}// 删除元素bool remove(int index) {if (index < 0 || index >= m_length) {return false; // 索引越界}// 移动元素以填补删除位置for (int i = index; i < m_length - 1; ++i) {m_data[i] = m_data[i + 1];}m_length--;return true;}// 获取元素T get(int index) const {if (index < 0 || index >= m_length) {throw std::out_of_range("Index out of range"); // 异常处理}return m_data[index]; // 返回元素}// 获取当前长度int size() const {return m_length; // 返回当前元素个数}// 打印所有元素void print() const {for (int i = 0; i < m_length; ++i) {std::cout << m_data[i] << " "; // 输出元素}std::cout << std::endl; // 换行}private:T m_data[MAX_SIZE]; // 存储元素的数组int m_length;       // 当前元素个数
};int main() {StaticArrayList<int> list; list.insert(0, 10);list.insert(1, 20);list.insert(1, 15);list.print(); // 输出: 10 15 20list.remove(1);list.print(); // 输出: 10 20try {std::cout << "Element at index 0: " << list.get(0) << std::endl; }catch (const std::out_of_range &e) {std::cerr << e.what() << std::endl; }return 0;
}

动态顺序表（Dynamic Array List）是一个可以动态调整大小的线性数据结构，通常使用动态分配的数组来实现。与静态顺序表相比，动态顺序表的大小可以根据需要进行扩展和收缩。以下是动态顺序表的基本概念和实现示例。

动态顺序表基本概念

1. 动态大小：可以根据元素数量动态调整大小。
2. 数组实现：使用动态分配的数组存储数据元素，支持随机访问。
3. 插入和删除：在尾部插入操作比较高效，而在中间插入或删除时需要移动元素。

#include <iostream>
#include <stdexcept> // 用于异常处理template <typename T>
class DynamicArrayList {
public:DynamicArrayList() : m_size(0), m_capacity(2) {try {m_data = new T[m_capacity]; // 动态分配数组}catch (const std::bad_alloc &e) {std::cerr << "Memory allocation failed: " << e.what() << std::endl;throw; // 重新抛出异常以便上层处理}}~DynamicArrayList() {delete[] m_data; // 释放动态分配的数组}// 插入元素void insert(const T &value) {if (m_size >= m_capacity) {resize(); // 扩展容量}m_data[m_size++] = value; // 添加新元素}// 删除元素bool remove(int index) {if (index < 0 || index >= m_size) {return false; // 索引越界}for (int i = index; i < m_size - 1; ++i) {m_data[i] = m_data[i + 1]; // 移动元素}m_size--;return true;}// 获取元素T get(int index) const {if (index < 0 || index >= m_size) {throw std::out_of_range("Index out of range"); // 异常处理}return m_data[index]; // 返回元素}// 获取当前长度int size() const {return m_size; // 返回当前元素个数}// 打印所有元素void print() const {for (int i = 0; i < m_size; ++i) {std::cout << m_data[i] << " "; // 输出元素}std::cout << std::endl; // 换行}private:T *m_data;        // 动态分配的数组int m_size;       // 当前元素个数int m_capacity;   // 当前容量// 扩展容量void resize() {m_capacity *= 2; // 容量翻倍T *newData = nullptr;try {newData = new T[m_capacity]; // 创建新数组}catch (const std::bad_alloc &e) {std::cerr << "Memory allocation failed during resize: " << e.what() << std::endl;throw; // 重新抛出异常}for (int i = 0; i < m_size; ++i) {newData[i] = m_data[i]; // 复制元素}delete[] m_data; // 释放旧数组m_data = newData; // 更新指针}
};int main() {try {DynamicArrayList<int> list; // 创建动态顺序表实例list.insert(10);list.insert(20);list.insert(30);list.print(); // 输出: 10 20 30list.remove(1);list.print(); // 输出: 10 30std::cout << "Element at index 0: " << list.get(0) << std::endl; // 输出: 10}catch (const std::bad_alloc &e) {std::cerr << "Failed to allocate memory: " << e.what() << std::endl;}catch (const std::out_of_range &e) {std::cerr << e.what() << std::endl; // 捕获越界异常}return 0;
}

1. 动态数组的优缺点

• 优点：

  • 动态调整大小：可以根据需要增加或减少数组的大小，灵活性较高。
  • 随机访问：支持O(1)时间复杂度的随机访问。

• 缺点：

  • 插入和删除效率：在数组中间插入或删除元素时，需要移动元素，时间复杂度为O(n)。
  • 内存分配：每次扩展容量时，需要分配新内存并复制数据，可能会导致性能下降。

2. 扩展策略

• 容量翻倍：在数组满时将容量翻倍是一种常见的扩展策略，能有效减少频繁的内存分配操作。
• 减少容量：可以考虑在删除元素后，如果数组的使用率低于某个阈值（如25%），则缩小数组的容量，以节省内存。

3. 迭代器支持

为了使动态顺序表更加灵活，可以实现迭代器支持，允许用户使用范围for循环遍历元素。这需要定义一个迭代器类，并在动态数组类中实现相关方法。

4. 拷贝构造和赋值运算符

• 拷贝构造函数：在类中添加拷贝构造函数，以支持深拷贝。
• 赋值运算符重载：实现赋值运算符重载以支持正确的赋值操作，避免浅拷贝引起的问题。

5. 线程安全

在多线程环境中，如果多个线程同时访问动态数组，可能会导致数据不一致或崩溃。可以通过加锁机制或使用原子操作来实现线程安全。

6. 性能优化

• 预分配内存：如果预知元素数量，可以在初始化时分配足够的内存，避免频繁扩展。
• 内存池：使用内存池技术，减少频繁的动态内存分配操作，提高性能。

代码（包含拷贝构造和赋值运算符）

下面是改进后的动态顺序表示例，添加了拷贝构造函数和赋值运算符重载：

#include <iostream>
#include <stdexcept>template <typename T>
class DynamicArrayList {
public:DynamicArrayList() : m_size(0), m_capacity(2) {m_data = new T[m_capacity];}~DynamicArrayList() {delete[] m_data;}// 拷贝构造函数DynamicArrayList(const DynamicArrayList& other) {m_size = other.m_size;m_capacity = other.m_capacity;m_data = new T[m_capacity];for (int i = 0; i < m_size; ++i) {m_data[i] = other.m_data[i];}}// 赋值运算符重载DynamicArrayList& operator=(const DynamicArrayList& other) {if (this != &other) {delete[] m_data; // 释放旧内存m_size = other.m_size;m_capacity = other.m_capacity;m_data = new T[m_capacity]; // 分配新内存for (int i = 0; i < m_size; ++i) {m_data[i] = other.m_data[i];}}return *this;}// 插入、删除、获取等方法保持不变...private:T* m_data;int m_size;int m_capacity;void resize() {// resize 实现...}
};int main() {// 示例操作...return 0;
}