目录
结构特性
长度固定:数组的长度在创建时已经被确定,如果需要动态改变数组的长度,可以考虑使用动态数组。
连续性:数组中的所有元素在内存中是连续存储的。数组可以快速访问任意元素,单插入和删除操作会影响效率。
一致性:数组中的所有元素必须都是相同的类型。
索引:索引从0开始,数组下标上限长度减去1。
内存布局
数组在内存中占据一块连续的内存空间。
数组起始地址是数组首个元素的地址(数组名即为首地址)。
每个元素占据的内存空间是相同的,具体大小取决于与元素的类型。
通过索引可以快速访问数组中的任意元素。
#include <iostream> int main() { int Arr[10] = { 1,3,2,5,4 }; printf("Arr.BaseAddr -> %p \r\n", Arr); printf("Arr.BaseAddr -> %p \r\n", &Arr[0]); for (int Index = 0; Index < sizeof(Arr) / sizeof(Arr[0]); Index++) { printf("Arr[%d] -> %p -> %d \r\n", Index, &Arr[Index], Arr[Index]); } return 0; }
结构样式
静态数组:编译时确定数组长度,无法在运行期间修改其长度。
动态数组:运行时动态分配内存,可以在运行期间修改其长度。(C++STD::VECTOR)
结构拓展
数据初始
#include <iostream>
int main()
{
//stack
int Arr1[5];
int Arr2[5] = { 0 };
int Arr3[] = { 1,2,3,4,5 };
//heap
int* p1 = new int[5];
delete[] p1;
int* p2 = new int[5]{ 1,2,3,4,5 };
delete[] p2;
return 0;
}
元素访问
- 内存图解
- 实例代码
#include <iostream> int main() { int Arr[5] = { 1,3,2,5,4 }; Arr[0] = 1; Arr[1] = 2; Arr[2] = 3; Arr[3] = 4; Arr[4] = 5; return 0; }
- 汇编分析
int Arr[5] = { 1,3,2,5,4 }; 00414635 mov dword ptr [ebp-18h],1 0041463C mov dword ptr [ebp-14h],3 00414643 mov dword ptr [ebp-10h],2 0041464A mov dword ptr [ebp-0Ch],5 00414651 mov dword ptr [ebp-8],4 Arr[0] = 1; 00414658 mov eax,4 0041465D imul ecx,eax,0 00414660 mov dword ptr [ebp+ecx-18h],1 Arr[1] = 2; 00414668 mov eax,4 0041466D shl eax,0 00414670 mov dword ptr [ebp+eax-18h],2 Arr[2] = 3; 00414678 mov eax,4 0041467D shl eax,1 0041467F mov dword ptr [ebp+eax-18h],3 Arr[3] = 4; 00414687 mov eax,4 0041468C imul ecx,eax,3 0041468F mov dword ptr [ebp+ecx-18h],4 Arr[4] = 5; 00414697 mov eax,4 0041469C shl eax,2 0041469F mov dword ptr [ebp+eax-18h],5
ebp-18h == 数组首地址
mov dword ptr [ebp+ecx-18h],1 == ebp-18h + 0 * 4
mov dword ptr [ebp+eax-18h],2 == ebp-18h + 1 * 4
mov dword ptr [ebp+eax-18h],3 == ebp-18h + 2 * 4
mov dword ptr [ebp+ecx-18h],4 == ebp-18h + 3 * 4
mov dword ptr [ebp+eax-18h],5 == ebp-18h + 4 * 4
插入元素
- 插入步骤
- 代码实现
void Insert(int* p, int nLength, int nIndex, int nVar) { for (int i = nLength - 1; i > nIndex; i--) { p[i] = p[i - 1]; } p[nIndex] = nVar; }
删除元素
- 删除步骤
- 代码实现
void Remove(int* p, int nLength, int nIndex) { for (int i = nIndex; i < nLength - 1; i++) { p[i] = p[i + 1]; } }
查找元素
int Find(int* p, int nLength, int nVar) { for (int i = 0; i < nLength; i++) { if (p[i] == nVar) { return i; } } return -1; }
修改元素
int Arr[6] = { 1,2,3,4,5 }; Arr[0] = 11; *(Arr + 1) = 22;
结构设计
成员变量
T* data; //动态数组指针
int size; //数组元素个数
int capacity; //数组容量大小
构造函数
- 默认构造函数
- 有参构造函数
- 拷贝构造函数
- 移动构造函数
- 列表构造函数
功能函数
- 元素个数
- 数组容量
- 是否为空
- 下标访问
- 插入元素
- 删除元素
- 查找元素
示例代码
#include <iostream>
#include <vector>
template <typename T>
class Vector
{
private: //成员变量
T* data; //动态数组指针
int size; //数组元素个数
int capacity; //数组容量大小
public: //构造析构
//默认构造函数
Vector() : data(nullptr), size(0), capacity(0)
{
}
//有参构造函数
Vector(int size, const T& var) : size(size), capacity(size)
{
this->data = new T[capacity];
for (size_t i = 0; i < capacity; i++)
{
data[i] = var;
}
}
//拷贝构造函数
Vector(const Vector& ref) : size(ref.size), capacity(ref.capacity)
{
this->data = new T[capacity];
for (size_t i = 0; i < capacity; i++)
{
this->data[i] = ref.data[i];
}
}
//移动构造函数
Vector(Vector&& other)noexcept : data(other.data), size(other.size), capacity(other.capacity)
{
other.data = nullptr;
other.size = 0;
other.capacity = 0;
}
//列表构造函数
Vector(std::initializer_list<T> initlist) : size(initlist.size()), capacity(initlist.size())
{
this->data = new T[capacity];
int i = 0;
for (const auto& value: initlist)
{
data[i++] = value;
}
}
//默认析构函数
~Vector()
{
if (this->data != NULL)
{
delete[] this->data;
}
}
public: //成员函数
//获取元素个数
int Size() const
{
return this->size;
}
//获取数组容量
int Capacity() const
{
return this->capacity;
}
//数组是否为空
bool Empty()
{
return this->size == 0 ? true : false;
}
//下标获取元素
T& operator[](int nIndex)
{
return this->data[nIndex];
}
//末尾追加元素
void Push_Back(const T& value)
{
//判断容器容量
if (this->size >= this->capacity)
{
//容量大小修正
capacity = (capacity == 0) ? 1 : capacity * 2;
//申请扩容内存
T* tempData = new T[capacity];
//拷贝默认数据
for (int i = 0; i < size; i++)
{
tempData[i] = this->data[i];
}
//释放默认内存
delete[] this->data;
//修正数据指针
this->data = tempData;
}
this->data[size] = value;
- size++;
}
//插入元素数据
void Insert(int nIndex, const T& value)
{
//判断索引序号
if (nIndex < 0 || nIndex > size)
{
throw std::out_of_range("Invalid Index");
}
//判断容器容量
if (this->size >= this->capacity)
{
//容量大小修正
capacity = (capacity == 0) ? 1 : capacity * 2;
//申请扩容内存
T* tempData = new T[capacity];
//拷贝默认数据
for (int i = 0; i < size; i++)
{
tempData[i] = this->data[i];
}
//释放默认内存
delete[] this->data;
//修正数据指针
this->data = tempData;
}
//指定位置插入
for (int i = size; i > nIndex; i--)
{
this->data[i] = this->data[i - 1];
}
this->data[nIndex] = value;
this->size++;
}
//删除元素数据
void erase(int nIndex)
{
//判断索引序号
if (nIndex < 0 || nIndex > size)
{
throw std::out_of_range("Invalid Index");
}
//删除指定元素
for (int i = nIndex; i < this->size -1; i++)
{
this->data[i] = this->data[i + 1];
}
//修正数组个数
//this->data[this->size - 1] = 0;
this->size--;
}
//查找指定元素
int Find(const T& valud) const
{
for (size_t i = 0; i < this->size; i++)
{
if (this->data[i] == valud)
{
return i;
}
}
return -1;
}
};
int main()
{
//默认构造函数
Vector<int> vec1;
//有参构造函数
Vector<int> vec2(3, 0xCC);
//拷贝构造函数
Vector<int> vec3(vec2);
//移动构造函数
Vector<int> vec4(std::move(vec3));
//列表构造函数
Vector<int> vec5 = { 1,2,3,4,5 };
return 0;
}