數組作為線性表的一種，具有內存連續這一特點，可以通過下標訪問元素，并且下標訪問的時間復雜的是O(1)，在數組的末尾插入和刪除元素的時間復雜度同樣是O(1)，我們使用C++實現一個簡單的邊長數組。

數據結構定義

class Array
{
int cur;
int cap;
int *tail;
};

cur是當前元素的個數，cap是數組的總容量，tail是數組最后一個元素的下一個空間地址。

數組接口定義

#include<iostream>
#include<stdlib.h>
#include<time.h>
class Array
{
private:
int cur;
int cap;
int *tail;
void expand(int size);
public:
Array(int size=15);
~Array();// 末尾增加元素void push_back(int val);// 末尾刪除元素void pop_back();// 按位置增加元素void insert(int pos, int val);// 按位置刪除void erase(int pos);// 元素查詢int find(int val);// 打印數據void show()const;
};

這里的expand函數用于給數組擴容，由于擴容操作是由C++標準庫的函數實現的(參考vector)，因此我們將expand函數使用private關鍵字修飾，代表這個函數只能被Array自身使用。

函數實現

#include<iostream>
#include<stdlib.h>
#include<time.h>
class Array
{
private:
int cur;
int cap;
int *tail;
void expand(int size)
{int *p=new int[size*sizeof(int)];memcpy(p,tail,size);delete tail;tail=p;cap=size;
}
public:
Array(int size=15):cap(size),cur(0)
{tail=new int[size];
}
~Array()
{delete []tail;tail=nullptr;//防止產生野指針
}// 末尾增加元素void push_back(int val){if(cur>=cap){expand(2*cap);}tail[cur++]=val;}// 末尾刪除元素void pop_back(){if(cur==0)return;cur--;}// 按位置增加元素void insert(int pos, int val){if(pos<0||pos>cur)return;if(cur>=cap)expand(2*cap);for(int i=cur-1;i>=pos;i--){tail[i+1]=tail[i];}tail[pos]=val;cur++;}// 按位置刪除void erase(int pos){if(pos<0||pos>cur||cur==0)return;for(int i=pos+1;i<cur;i++){tail[i-1]=tail[i];}cur--;}// 元素查詢int find(int val){for(int i=0;i<cur;i++){if(tail[i]==val)return i;}return -1;}// 打印數據void show()const{for(int i=0;i<cur;i++){std::cout<<tail[i]<<" ";}std::cout<<std::endl;}
};

接口測試

int main()
{Array array;srand(time(0));for(int i=0;i<10;i++){array.push_back(rand()%100);}array.show();array.insert(1,100);array.show();array.pop_back();array.show();array.erase(2);array.show();std::cout<<array.find(100);
}

輸出結果