C++实现动态数组

实现一个动态数组，要求对于随机访问可以在常数时间完成，可以通过push_back向数据的尾部追加元素，可以通过pop_back删除尾部元素，能够满足常见的数组操作。 LINE 2016年春招笔试

这里说的动态数组是可以根据需要动态增长占用内存的数组，比如程序初始分配了100个元素，可是运行了一段时间后区区100个空间不能满足了，现在需要400个，怎么办呢；那肯定需要再额外分配300个。

C语言有realloc()函数来解决空间扩充的问题，但是不要忘了realloc可能会迁移内存，会发现数据要复制

C++中的vector和这个题的要求很像，但是vector在扩展内存的时候，也是要复制数据

一次分配足够的空间是可以解决这个问题，很明显这会造成内存的浪费，这个做法不算明智。

不使用数组呢？使用list能解决一部分问题，但是list不能支持随机访问啊，鉴于效率上的硬伤，显然不能随便用list替换数组。

怎么解决这个问题呢？动态数组

动态数组的特征

动态数组是一个很简单易用的数据结构，但是简单不代表优点小，它的特征如下：

1 根据需要动态批量增长内存；

2 一经分配，元素地址不会再次变化；

3 实现简单，效率高，事实上它和普通数组相比基本没有效率损失；

4 最大个数固定；

其实最重要的就是特征2了，不然直接使用realloc多方便呢，当然动态数组的实现也很方便

#include<iostream>

using namespace std;

//动态数组，最多200个单位，空间不够的时候，一次自动增长10个单位，所以capacity是size的最接近10的数

class DArray

{

public:

int* section[20];

int size;//动态数组的实际大小

int capacity;//动态数组最多能容纳多少

DArray(int sizep)//指定动态数组大小，并初始化成0

{

if(sizep<=200)

{

int time=0;

if(size%10==0)//如果size是30的话，最大的数保存到29，就是0 1 2 三个数组

{

time=sizep/10-1;

capacity=size;

}

else

{

time=sizep/10;

capacity=(time+1)*10;

}

for(int i=0; i<=time; i++)//多初始化一些也没有关系

{

section[i]=new int[10];

for(int j=0;j<10;j++)

section[i][j]=0;

}

size=sizep;

}

else

cout<<"无法分配超过200的空间！"<<endl;

}

int& operator[](int index)//重载方括号

{

int sec=index/10;

int offset=index%10;

return section[sec][offset];

} //A reference shall be initialized to refer to a valid object or function.

int resize(int newSize)//重新分配数组大小，如果newSize>size,则用0填充

{

if(newSize<=200)

{

if(newSize<=capacity)//现在还是装的下的

{

if(size<newSize)//从小到大是 size newSize capacity

for(int i=size;i<newSize;i++)

section[size/10][i%10]=0;

}

else

{//这样的话从小到大就是 size capacity newSize

for(int i=size;i<capacity;i++)

section[size/10][i%10]=0;

while(capacity<newSize)//多初始化一些，没有关系

{

section[capacity/10]=new int[10];

for(int i=0;i<10;i++)

section[capacity/10][i]=0;

capacity+=10;

}

size=newSize;

}

else

return 0;

}

void push_back(int ele)

{

if(size<=199)

{

if(size==capacity)//需要扩容

{

section[capacity/10]=new int[10];

capacity+=10;

}

section[size/10][size%10]=ele;

size++;

}

else

cout<<"已满！"<<endl;

}

void pop_back()

{

size--;

}

~DArray()

{

while(capacity>0)

{

delete [] section[capacity/10-1];

capacity-=10;

}

cout<<"已经析构！"<<endl;

}

};

int main()//测试动态数组

{

DArray array(2);

for(int i=0; i<24; i++)

{

array.push_back(i);

}

for(int i=0;i<array.size;i++)

{

cout<<array[i]<<" ";

}

cout<<endl;

cout<<"size: "<<array.size<<" capacity: "<<array.capacity<<endl;

array.resize(35);

for(int i=0;i<array.size;i++)

{

cout<<array[i]<<" ";

}

cout<<endl;

cout<<"size: "<<array.size<<" capacity: "<<array.capacity<<endl;

// array

}

动态数组结构如下：

	0	1	2	3	4	9	capacity
0						9	10
1						19	20
2						29	30
3						39	40
4						49	50

思路来自 http://blog.csdn.net/sparkliang/article/details/5359634

巴特西

C++实现动态数组

最新文章

热门文章