漫画算法笔记

数组实现

#include <iostream> #include <stdlib.h> using namespace std; //C/C++代码实现 template<typename T> class MyArray { public: MyArray(int capacity) :_capacity(capacity) ,_size(0) { _data = new T[capacity](); } ~MyArray() { delete[] _data; } T& operator[](int index) { return _data[index]; } void toString() { for (int i = 0; i < _size; ++i) { cout << _data[i] << " "; } cout << endl; } /* 数组插入元素 @param element 插入的元素 @param index 插入的位置 */ void insert(const int &element, const int &index) { //判断访问下标是否超出范围 if ( index < 0 || index > _size ) { throw out_of_range("超出数组实际元素范围!"); } //如果实际元素达到数组容量上限,则对数组进行扩容 if (_size >= _capacity) resize(); //将元素右移 for ( int i = _size - 1; i >= index; --i ) { _data[i + 1] = _data[i]; } //放置元素 _data[index] = element; ++_size; } /* 数组删除元素 @param index 删除的位置 */ T remove(int index) { //判断访问下标是否超出范围 if (index < 0 || index > _size) { throw out_of_range("超出数组实际元素范围!"); } T delElement = _data[index]; //元素左移 for ( int i = index; i < _size - 1; ++i ) { _data[i] = _data[i + 1]; } --_size; return delElement; } private: /* 数组扩容 */ void resize() { int newCapacity = _capacity * 2; T *newData = new T[newCapacity](); memcpy(newData, _data, sizeof(T) * _capacity); delete[] _data; _data = newData; _capacity = newCapacity; } T* _data; int _capacity; int _size; }; int main(int argc, char** argv) { auto *arr = new MyArray<int>(4); arr->insert(3, 0); arr->insert(7, 1); arr->insert(9, 2); arr->insert(5, 3); arr->toString(); //3 7 9 5 arr->insert(6, 1); arr->toString(); //3 6 7 9 5 arr->remove(1); arr->toString(); //3 7 9 5 system("pause"); return 0; }