数组特点内存是连续的优点·下标访问随机访问时间复杂度是O(1)不是查找、搜索是arr[0]的访问·末尾位置增删元素的时间复杂度是O(1)不涉及元素的移动·访问元素前后相邻位置的元素很方便缺点·非末尾位置增删元素需要移动大量的数据线性时间复杂度O(n)·搜索的时间复杂度是O(n)无序时线性搜索 O(n)有序时可以二分搜索降低复杂度 O(logn)·数组扩容消耗比较大程序运行时可用内存主要分为三部分数据段 .data存放全局变量的地方系统分配系统释放生命周期是整个程序的生命周期堆 heap通过new/delete来开辟/释放栈 stack随着函数的运行/结束 分配/释放由此可知如果想要手动控制数组内存扩容需要将数组定义在堆上。数组实现下面的代码构建了一个具有末位存储、末位释放、插入、删除、查询功能的数组类。在数组元素增加时通过内部的扩容函数实现数组扩容。在构建类或读类的代码时首先要确定成员变量。之后考虑构造函数的方法和析构函数的处理。释放内存时注意不要产生野指针。然后是成员函数要实现的功能。构建成员函数时要注意数据的安全性。#include iostream #include stdlib.h #include time.h using namespace std; //实现可扩容的数组 class Array { public: //函数构造 Array(int size 10) : mCur(0), mCap(size) //构造函数传递默认值10。在成员列表中给成员变量初始化 { mpArr new int[mCap](); //[]数组大小()表示每个元素初始化为0 } ~Array() //析构在对象销毁前释放掉占用的外部堆内存 { delete[]mpArr; //释放指针指向的堆内存空间 mpArr nullptr; //指针设置为空防止野指针出现 野指针指针非空但是指向的地址内存已经释放 } public: //实现接口 //末尾增加元素 O(1) void push_back(int val) { if (mCur mCap) { expand(2 * mCap); //O(n) } mpArr[mCur] val; } //末尾删除元素 void pop_back() { if (mCur 0) { return; } mCur--; } //按位置增加元素 void insert(int pos, int val) { if (pos 0 || pos mCur) //指定位置可行性判定 { throw pos invalid!; //return } if (mCur mCap) //判断是否需要扩容 { expand(2 * mCap); } //移动元素 for (int i mCur - 1; i pos; i--) { mpArr[i 1] mpArr[i]; } //插入元素 mpArr[pos] val; mCur; } //按位置删除 O(n) void erase(int pos) { //有效性判断 if (pos 0 || pos mCur) { throw pos invalid!; } //移动元素 for (int i pos; i mCur - 1; i) { mpArr[i] mpArr[i 1]; } mCur--; } //元素查询 int find(int val) { for (int i 0; i mCur; i) { if (mpArr[i] val) { return i; } } return -1; } //打印数据 void show()const { for (int i 0; i mCur; i) { cout mpArr[i] ; } cout endl; } private: //内部数组扩容接口 O(n) void expand(int size) { int* p new int[size]; //开辟一片新内存 memcpy(p, mpArr, sizeof(int) * mCap); //复制内存 delete[]mpArr; //释放原有内存 mpArr p; mCap size; } private: //成员变量 int* mpArr; //使用指针指向堆上可扩容的数组内存 int mCap; //记录数组的容量 int mCur; //数组有效元素个数 }; int main() { //用自定义的数组类定义一个对象 Array arr; //用系统时间设置一个随机数种子 srand(time(0)); //随机赋十个值给数组 for (int i 0; i 10; i) { arr.push_back(rand() % 100); } arr.show(); arr.pop_back(); arr.show(); arr.insert(0, 100); arr.show(); arr.insert(10, 200); arr.show(); int pos arr.find(100); if (pos ! -1) { arr.erase(pos); } arr.show(); return 0; }