数据结构1:C++实现变长数组

数组作为线性表的一种，具有内存连续这一特点，可以通过下标访问元素，并且下标访问的时间复杂的是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);
}

输出结果