之前實現了java的動態數組，試著寫了個C++版的，同樣對時間復雜度振蕩進行了處理。純手打，代碼如下 ：
//
// Created by PC-Saw on 2018/12/19.
//#ifndef DATA_STRUCTURE_MYARRAY_H
#define DATA_STRUCTURE_MYARRAY_H#include <iostream>using namespace std;template <typename T>
class MyArray {
private:int mSize;int mCapacity;T* data;
public:MyArray(); // 無參構造函數explicit MyArray(int Capacity); // 構造函數，傳入容量CapacityMyArray(const MyArray& arr); // 拷貝構造MyArray &operator= (MyArray arr); // 重載賦值操作符T &operator[](int index); // 重載[]操作賦~MyArray(); // 析構函數//友元函數實現 重載輸出 << 操作符friend ostream & operator << (ostream &out, MyArray<T> &obj){out << "MyArray size = " << obj.mSize << ", Capacity = " << obj.mCapacity << endl;out << "MyArray: [";for (int i = 0; i < obj.mSize; ++i){out << obj.data[i];if (i != obj.mSize - 1)out << ", ";}out << "] ";return out;}//友元函數實現 輸入 >> 操作符friend istream & operator >> (istream &in, MyArray<T> &obj){for (int i = 0; i < obj.mSize; ++i) {in << obj.data[i];}if (!in){obj = new MyArray();}return in;}bool isEmpty(); // 判斷數組是否為空bool isFull(); // 判斷數組是否已滿int find(T t); // 查找元素 t 的下標bool contain(T t); // 判斷是否包含元素 tint getSize(); // 獲取數組元素個數int getCapacity(); // 獲取數組容量void pushFront(T t); // 頭部添加元素void pushBack(T t); // 尾部添加元素void insert(int index, T t); // 在指定位置插入元素 tT remove(int index); // 刪除指定位元素T removeFront(); // 刪除第一個元素T removeBack(); // 刪除最后一個元素void removeElement(T t); // 刪除元素 tvoid set(int index, T t); // 將指定位置元素設為 tT get(int index); // 查看 index 位置的元素T getBack(); // 返回最后一個元素void resize(int newCapacity); // 重新分配空間
};// 構造函數
template <typename T>
MyArray<T>::MyArray(int Capacity)
{cout << "調用 MyArray(int) 構造 " << endl;if (Capacity <= 0)throw "傳入容量有誤！";mSize = 0;mCapacity = Capacity;data = new T[Capacity];
};// 無參構造函數
template <typename T>
MyArray<T>::MyArray()
{cout << "調用 MyArray() 構造 " << endl;mSize = 0;mCapacity = 10;data = new T[10];
};// 拷貝構造
template <typename T>
MyArray<T>::MyArray(const MyArray<T>& arr)
{cout << "調用拷貝構造 " << endl;this->mSize = arr.mSize;this->mCapacity = arr.mCapacity;this->data = new T[arr.mCapacity];// 拷貝數據for (int i = 0; i < arr.mSize; ++i) {this->data[i] = arr.data[i];}
}// 重載賦值操作符
template <typename T>
MyArray<T> &MyArray<T>::operator= (const MyArray<T> arr)
{cout << "調用 = 賦值操作 " << endl;if (this->data != NULL){delete[] this->data;this->data = NULL;}//分配內存this->mSize = arr.mSize;this->mCapacity = arr.mCapacity;this->data = new T[arr.mCapacity];//拷貝數據for(int i = 0; i < this->mSize; i++){//如果是自定義的復雜數據類型，必須對 = 運算賦進行重載, operator=this->data[i] = arr.data[i];}return *this;
}// 重載[]操作賦
template <typename T>
T &MyArray<T>::operator[](int index)
{if (index < 0 || index > this->mSize - 1)throw "索引非法！";return this->data[index];
}// 析構函數
template <typename T>
MyArray<T>::~MyArray()
{cout << "調用析構函數 " << endl;if (this->data != NULL){delete[] this->data;this->data = NULL;}this->mSize = 0;this->mCapacity = 0;
}// 判斷數組是否為空
template <typename T>
bool MyArray<T>::isEmpty()
{return mSize == 0;
};// 判斷數組是否已滿
template <typename T>
bool MyArray<T>::isFull()
{return mSize == mCapacity;
};// 查找元素 t 的下標
template <typename T>
int MyArray<T>::find(T t)
{for (int i = 0; i < mSize; ++i){if (data[i] == t)return i;}return -1;
}// 查找是否包含元素 t
template <typename T>
bool MyArray<T>::contain(T t)
{return (find(t) != -1);
}// 獲取數組元素個數
template <typename T>
int MyArray<T>::getSize()
{return mSize;
}// 獲取數組容量
template <typename T>
int MyArray<T>::getCapacity()
{return mCapacity;
}// 頭部添加元素
template <typename T>
void MyArray<T>::pushFront(T t)
{insert(0, t);
}// 尾部添加元素
template <typename T>
void MyArray<T>::pushBack(T t)
{insert(mSize, t);
}// 在指定位置插入元素 t
template <typename T>
void MyArray<T>::insert(int index, T t)
{if (index < 0 || index > mSize) // 判斷下標是否有誤throw 0;if (isFull()) // 數組已滿則重新分配空間resize(2 * mCapacity);for (int i = mSize; i > index ; --i){data[i] = data[i - 1];}data[index] = t;mSize++;
}// 刪除指定位元素
template <typename T>
T MyArray<T>::remove(int index)
{if (index < 0 || index >= mSize) // 判斷下標是否合法throw 0;// 刪除 index 位置的元素并返回T ret = data[index];for (int i = index; i < mSize - 1; ++i) {data[i] = data[i + 1];}mSize--;if (mSize == mCapacity / 4 && mCapacity / 2 != 0) // 空閑空間太大，重新分配空間resize(mCapacity / 2);return ret;
}// 刪除第一個元素
template <typename T>
T MyArray<T>::removeFront()
{return remove(0);
}// 刪除最后一個元素
template <typename T>
T MyArray<T>::removeBack()
{return remove(mSize - 1);
}// 刪除元素 e
template <typename T>
void MyArray<T>::removeElement(T t)
{int index = find(t);index != -1 && remove(index);
}// 將制定位置元素設為 t
template <typename T>
void MyArray<T>::set(int index, T t)
{if (index < 0 || index >= mSize)throw 0;data[index] = t;
}// 返回 index 位置的元素
template <typename T>
T MyArray<T>::get(int index)
{if (index < 0 || index >= mSize)throw "index is illegal!";return data[index];
}// 返回最后一個元素
template <typename T>
T MyArray<T>::getBack()
{return get(mSize - 1);
}// 重新分配空間
template <typename T>
void MyArray<T>::resize(int newCapacity)
{if (newCapacity <= 0)throw 0;T* tmp = new T[newCapacity];for (int i = 0; i < mSize; ++i){tmp[i] = data[i];}delete[] data;data = tmp;mCapacity = newCapacity;
}#endif //DATA_STRUCTURE_MYARRAY_H
測試代碼：
#include <iostream>
#include "MyArray.h"using namespace std;int main()
{//cout << boolalpha; // 將bool值正常顯示MyArray<int> arr; for(int i = 0; i < 10; ++i) arr.pushBack(i);cout << arr << endl;arr.pushFront(100);cout << arr << endl;arr.pushFront(-1);cout << arr << endl;arr.remove(2);cout << arr << endl;arr.removeElement(4);cout << arr << endl;arr.removeFront();cout << arr << endl;for(int i = 0; i < 5; ++i){arr.removeBack();cout << arr << endl;}return 0;
}?
之后還會有其他數據結構的 java 和 C++ 實現。
