设计一份包含网站建设范,网站设计常识,微网站免,阜创汇网站建设名额数组作为线性表的一种#xff0c;具有内存连续这一特点#xff0c;可以通过下标访问元素#xff0c;并且下标访问的时间复杂的是O(1)#xff0c;在数组的末尾插入和删除元素的时间复杂度同样是O(1)#xff0c;我们使用C实现一个简单的边长数组。
数据结构定义
class Arr…数组作为线性表的一种具有内存连续这一特点可以通过下标访问元素并且下标访问的时间复杂的是O(1)在数组的末尾插入和删除元素的时间复杂度同样是O(1)我们使用C实现一个简单的边长数组。
数据结构定义
class Array
{
int cur;
int cap;
int *tail;
};
cur是当前元素的个数cap是数组的总容量tail是数组最后一个元素的下一个空间地址。
数组接口定义
#includeiostream
#includestdlib.h
#includetime.h
class Array
{
private:
int cur;
int cap;
int *tail;
void expand(int size);
public:
Array(int size15);
~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自身使用。
函数实现
#includeiostream
#includestdlib.h
#includetime.h
class Array
{
private:
int cur;
int cap;
int *tail;
void expand(int size)
{int *pnew int[size*sizeof(int)];memcpy(p,tail,size);delete tail;tailp;capsize;
}
public:
Array(int size15):cap(size),cur(0)
{tailnew int[size];
}
~Array()
{delete []tail;tailnullptr;//防止产生野指针
}// 末尾增加元素void push_back(int val){if(curcap){expand(2*cap);}tail[cur]val;}// 末尾删除元素void pop_back(){if(cur0)return;cur--;}// 按位置增加元素void insert(int pos, int val){if(pos0||poscur)return;if(curcap)expand(2*cap);for(int icur-1;ipos;i--){tail[i1]tail[i];}tail[pos]val;cur;}// 按位置删除void erase(int pos){if(pos0||poscur||cur0)return;for(int ipos1;icur;i){tail[i-1]tail[i];}cur--;}// 元素查询int find(int val){for(int i0;icur;i){if(tail[i]val)return i;}return -1;}// 打印数据void show()const{for(int i0;icur;i){std::couttail[i] ;}std::coutstd::endl;}
};接口测试
int main()
{Array array;srand(time(0));for(int i0;i10;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::coutarray.find(100);
}
输出结果
