个人网站的建设方法和过程,珠海网站建设公司,宣威市住房和城乡建设局网站下载中心,cms系统什么意思静态顺序表#xff08;Static Array List#xff09;是一种线性数据结构#xff0c;通常用数组实现。它具有固定的大小#xff0c;并在编译时分配内存。以下是静态顺序表的一些基本概念和实现示例。
静态顺序表基本概念
固定大小#xff1a;静态顺序表的大小在创建时定义…静态顺序表Static Array List是一种线性数据结构通常用数组实现。它具有固定的大小并在编译时分配内存。以下是静态顺序表的一些基本概念和实现示例。
静态顺序表基本概念
固定大小静态顺序表的大小在创建时定义无法动态扩展。数组实现使用数组存储数据元素支持随机访问。插入和删除操作需要移动元素以保持顺序可能会影响性能。顺序存储元素在内存中是连续存储的支持高效的随机访问。
1. 数据结构示意图
假设我们有一个静态顺序表的初始状态如下数组最大容量为5
Index: 0 1 2 3 4---------------
Data: | | | | | |---------------
Length: 02. 尾部插入
操作将元素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: 24. 中间插入
操作将元素7插入到索引1的位置。
过程
移动元素10从索引1到索引2以为新元素腾出空间。
结果
Index: 0 1 2 3 4---------------
Data: | 5| 7| 10| | |---------------
Length: 3#include iostream
#include stdexcept
#include stringconst 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() {StaticArrayListint 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是一个可以动态调整大小的线性数据结构通常使用动态分配的数组来实现。与静态顺序表相比动态顺序表的大小可以根据需要进行扩展和收缩。以下是动态顺序表的基本概念和实现示例。
动态顺序表基本概念
动态大小可以根据元素数量动态调整大小。数组实现使用动态分配的数组存储数据元素支持随机访问。插入和删除在尾部插入操作比较高效而在中间插入或删除时需要移动元素。
#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 {DynamicArrayListint 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 stdexcepttemplate 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;
}
