1.数组实现
数组的特点:内存是连续的,即物理地址是连续的。
优点:
- 随机访问的时间复杂度为 O(1);
- 末尾位置增加元素的时间复杂度为 O(1);
- 访问元素前后相邻位置的元素非常方便;
缺点:
- 非末尾位置增加元素需要进行大量的数据移动,时间复杂度为 O(n);
- 搜索的时间复杂度:
- 无序数组采用线性搜索,时间复杂度为 O(n);
- 有序数组采用二分搜索,时间复杂度为 O(logn);
- 数组扩容时的消耗比较大;
如下为动态数组的实现:
class Array {
public:
Array(int size = 10);
~Array();
public:
// 返回第i个位置的值
int at(int idx) const { return mpArr_[idx]; }
// 返回数组大小
int size() const { return mCur_; }
// 在末尾增加元素
void push_back(int val);
// 删除末尾元素
void pop_back();
// 按位置增加元素
void insert(int pos, int val);
// 按位置删除
void erase(int pos);
// 元素查询
int find(int val);
// 数组扩容
void expand(int size);
private:
int* mpArr_; // 指向可扩容数组的内存
int mCap_; // 数组的容量
int mCur_; // 数组有效元素的个数
};
Array::Array(int size)
: mCur_(0)
, mCap_(size) {
mpArr_ = new int[mCap_];
}
Array::~Array() {
delete[] mpArr_;
mpArr_ = nullptr;
}
void Array::push_back(int val) {
if (mCur_ == mCap_) {
expand(2 * mCap_);
}
mpArr_[mCur_++] = val;
}
void Array::pop_back() {
if (mCur_ != 0)
mCur_--;
}
void Array::insert(int pos, int val) {
if (pos < 0 || pos >= mCap_)
return;
if (mCur_ == mCap_) {
expand(2 * mCap_);
}
for (int i = mCur_ - 1; i >= pos; i--) {
mpArr_[i + 1] = mpArr_[i];
}
mpArr_[pos] = val;
mCur_++;
}
void Array::erase(int pos) {
if (pos < 0 || pos >= mCap_)
return;
for (int i = pos + 1; i < mCur_; i++) {
mpArr_[i - 1] = mpArr_[i];
}
mCur_--;
}
int Array::find(int val) {
for (int i = 0; i < mCur_; i++) {
if (mpArr_[i] == val)
return i;
}
return -1;
}
void Array::expand(int size) {
int* ptr = new int[size];
memcpy(ptr, mpArr_, sizeof(int) * mCap_);
delete[] mpArr_;
mpArr_ = ptr;
mCap_ = size;
}
2.常见的算法问题
2.1 双指针
应用场景:数组逆序
算法过程:定义两个指针,分别指向数组头部和数组尾部,每次交换两个指针所指向的内容,然后左指针往左走,右指针往右走,直到左指针跨过右指针。
void reverse(int arr[], int size) {
int* left = arr;
int* right = arr + size - 1;
while (left < right) {
int tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
3.STL实现
在 STL 标准库中,数组数据结构的对应实现是 vector
,即动态数组。
vector 采用的数据结构为:线性连续空间。它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已经被使用的范围,并以迭代器 end_of_storage 指向整块连续空间的尾端。
当增加新元素时,如果超过当前的容量,则容量会扩充到 2倍。如果两倍容量仍不足,就扩张至足够大的容量。所谓动态增加大小,并不是在原空间之后接续新空间,而是以原大小的两倍另外配置一块较大空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此,对vector的任何操作,一旦引起空间重新配置,指向原 vector 的所有迭代器就都失效了。
vector的大小为 3 个指针的大小,且它以普通指针作为迭代器,如下:
template<class T, class Alloc = alloc>
class vector {
typedef T value_type;
typedef T* iterator;
iterator start;
iterator finish;
iterator end_of_storage;
};
标签:int,void,mpArr,数组,Array,数据结构,mCur
From: https://www.cnblogs.com/tuilk/p/16977330.html