对比静态顺序表与动态顺序表
| 特性 | 静态顺序表 | 动态顺序表 |
|---|---|---|
| 大小 | 固定 | 动态 |
| 内存管理 | 简单 | 复杂 |
| 随机访问 | 快速 | 快速 |
| 插入/删除效率 | 较低 | 较低（需移动元素） |
| 扩展能力 | 不可扩展 | 可扩展 |
C++ 静态顺序表概述
定义：静态顺序表是一种线性表的实现方式，采用一段连续的内存空间存储数据元素，具有固定的大小。在编译时确定长度，无法动态扩展。
主要特性
- 固定大小：在创建时指定大小，无法在运行时改变。
- 连续存储：元素在内存中是连续存放的，支持随机访问。
- 效率：访问元素速度快，但插入和删除效率较低。
设计静态顺序表时，可以从以下思路入手：
设计思路
- 数据结构：使用动态数组（指针）存储元素，需管理数组的容量和当前大小。
- 基本操作：
- 插入：在指定位置插入元素，需移动后面的元素。
- 删除：删除指定位置的元素，需移动后面的元素。
- 访问：通过索引直接访问元素，利用数组的随机访问特性。
图示理解
[0] [1] [2] [3] [4] // 初始静态顺序表，容量为5
- - - - - // 初始元素为空
插入10、20、30后：
[10] [20] [30] [ ] [ ] // 当前大小为3
删除20后：
[10] [30] [ ] [ ] [ ] // 当前大小为2
访问第0个元素：
返回10
实现
以下是静态顺序表的简单实现示例：
#include <iostream>
template <typename T>
class StaticArray {
private:
T* arr; // 存储元素的数组
int capacity; // 数组的最大容量
int size; // 当前元素数量
public:
// 构造函数
StaticArray(int cap) : capacity(cap), size(0) {
arr = new T[capacity];
}
// 析构函数
~StaticArray() {
delete[] arr;
}
// 插入元素
bool insert(int index, const T& value) {
if (index < 0 || index > size || size >= capacity) {
return false; // 索引无效或已满
}
for (int i = size; i > index; --i) {
arr[i] = arr[i - 1]; // 移动元素
}
arr[index] = value; // 插入新元素
++size;
return true;
}
// 删除元素
bool remove(int index) {
if (index < 0 || index >= size) {
return false; // 索引无效
}
for (int i = index; i < size - 1; ++i) {
arr[i] = arr[i + 1]; // 移动元素
}
--size;
return true;
}
// 获取元素
T get(int index) const {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
return arr[index];
}
// 获取当前大小
int getSize() const {
return size;
}
// 获取容量
int getCapacity() const {
return capacity;
}
// 打印数组
void print() const {
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
};
int main() {
StaticArray<int> array(5);
// 插入元素
array.insert(0, 10);
array.insert(1, 20);
array.insert(2, 30);
array.print(); // 输出: 10 20 30
// 删除元素
array.remove(1);
array.print(); // 输出: 10 30
// 获取元素
std::cout << "Element at index 0: " << array.get(0) << std::endl; // 输出: 10
// 当前大小和容量
std::cout << "Size: " << array.getSize() << ", Capacity: " << array.getCapacity() << std::endl;
return 0;
}
主要操作
- 插入（Insert）：在指定位置插入新元素，需移动后面的元素。
- 删除（Remove）：删除指定位置的元素，需移动后面的元素。
- 获取（Get）：通过索引访问元素，需注意索引范围。
- 容量管理：通过
capacity和size管理数组的最大容量和当前元素数量。
应用场景
- 简单数据存储：适合存储固定数量的数据，如学生成绩、产品列表等。
- 需要快速访问的场景：适合需要频繁访问元素的情况。
优缺点
-
优点：
- 随机访问速度快。
- 实现简单。
-
缺点：
- 固定大小，无法动态扩展。
- 插入和删除操作效率低。
C++ 动态顺序表概述
定义：动态顺序表是一种线性表的实现，能够在运行时动态调整大小，适应数据量的变化。通常使用动态数组实现。
主要特性
- 动态大小：可以根据需要扩展或缩减大小。
- 随机访问：支持高效的随机访问。
- 内存管理：需要处理内存的分配与释放。
设计思路
- 动态内存管理：使用动态数组，初始时给定一个容量，达到上限后进行扩展。
- 操作管理：支持插入、删除、访问操作，需处理元素移动。
- 扩展策略：一般采用容量翻倍的策略，避免频繁的内存分配。
图示理解
-
初始状态（容量为2）：
-
[0] [1] // 初始动态顺序表
- - // 空元素 -
插入元素10、20后：
-
[0] [1]
[10] [20] // 当前大小为2 -
插入元素30（触发扩展）：
-
[0] [1] [2] [3]
[10] [20] [30] [ ] // 扩展后容量变为4 -
删除元素20后：
-
[0] [1] [2] [3]
[10] [30] [ ] [ ] // 当前大小为2
实现
以下是动态顺序表的简单实现示例：
#include <iostream>
template <typename T>
class DynamicArray {
private:
T* arr; // 存储元素的数组
int capacity; // 数组的最大容量
int size; // 当前元素数量
// 扩展数组的容量
void resize() {
capacity *= 2; // 容量翻倍
T* newArr = new T[capacity];
for (int i = 0; i < size; ++i) {
newArr[i] = arr[i]; // 复制旧数组的元素
}
delete[] arr; // 释放旧数组
arr = newArr; // 更新指针
}
public:
// 构造函数
DynamicArray(int cap = 2) : capacity(cap), size(0) {
arr = new T[capacity];
}
// 析构函数
~DynamicArray() {
delete[] arr;
}
// 插入元素
void insert(int index, const T& value) {
if (index < 0 || index > size) {
throw std::out_of_range("Index out of range");
}
if (size >= capacity) {
resize(); // 扩展数组
}
for (int i = size; i > index; --i) {
arr[i] = arr[i - 1]; // 移动元素
}
arr[index] = value; // 插入新元素
++size;
}
// 删除元素
void remove(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
for (int i = index; i < size - 1; ++i) {
arr[i] = arr[i + 1]; // 移动元素
}
--size;
}
// 获取元素
T get(int index) const {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
return arr[index];
}
// 获取当前大小
int getSize() const {
return size;
}
// 打印数组
void print() const {
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
};
int main() {
DynamicArray<int> array;
// 插入元素
array.insert(0, 10);
array.insert(1, 20);
array.insert(2, 30);
array.print(); // 输出: 10 20 30
// 删除元素
array.remove(1);
array.print(); // 输出: 10 30
// 获取元素
std::cout << "Element at index 0: " << array.get(0) << std::endl; // 输出: 10
// 当前大小
std::cout << "Size: " << array.getSize() << std::endl; // 输出: 2
return 0;
}
主要操作
- 插入（Insert）：在指定位置插入元素，自动扩展数组。
- 删除（Remove）：删除指定位置的元素，需移动后面的元素。
- 访问（Get）：通过索引访问元素，需注意索引范围。
- 动态调整：当元素数量超过容量时，自动扩展数组。
应用场景
- 数据量不确定：适合存储数据量不确定的情况，如动态用户输入、动态任务列表等。
- 频繁插入和删除：适合需要频繁修改数据的场景。
优缺点
-
优点：
- 能够动态扩展，适应变化的数据量。
- 随机访问速度快。
-
缺点：
- 需要管理内存，可能导致内存碎片。
- 扩展时需要复制数组，效率较低。
常见坑
- 越界访问：对索引的检查不充分，导致访问越界。
- 内存泄漏：未正确释放动态分配的内存，导致内存泄漏。
- 频繁扩展：如果扩展策略不当，频繁扩展可能导致性能下降。
- 元素移动：插入和删除时未注意到元素的移动，可能导致数据错位。