C++实现动态数组功能

2023-09-05 11:48:05 155

数组

数组是一种线性表数据结构。它用一组连续内存空间，来存储一组具有相同数据类型数据。

1.线性表：数据存储像一条线一样的结构，每个线性表上的数据最多只有前和后的两个方向，如数组、链表、队列、栈等都是这种结构，所以实现的数组的动态操作，其他结构也可轻易的类似实现。更重要的是，在这之后看源码就可大大降低难度。（博主自己看的是STL源码剖析）
2.非线性表：如二叉树、堆、图等。
3连续内存空间和相同数据类型：当数组作插入、删除操作时，为了保证数据的连续性，往往需要做大量的数据搬移工作，效率很低。

动态数组功能实现

1.数组初始化

考虑到扩容时数据搬移可能会发生的内存泄露，博主这里采用两只手的原则，即设定一个内存标志位ItemsFlag。当ItemsFlag=0，usingpreitems；当ItemsFlag=1，usingitems。下文扩容部分有具体实现。默认数组容量10。

enum{MAX=10};
explicitGenericArray(intss=MAX);
template
GenericArray::GenericArray(intss):capacity(ss),counts(0)
{
itemsFlag=0;
preitems=newT[capacity];
items=nullptr;
}

2.析构函数

释放内存。

template
GenericArray::~GenericArray()
{
if(preitems!=nullptr)
delete[]preitems;
if(items!=nullptr)
delete[]items;
}

3.检查下标

检查要操作的下标是否在数组容量范围内。

template
boolGenericArray::checkIndex(intindex)
{
if(index<0||index>=capacity)
{
intcap=capacity-1;
cout<<"Outoftherange!Pleaseensuretheindexbe
in0~"<
4.获取元素数目和容量、判断数组空和满


intcount()const{returncounts;}
intgetCapacity()const{returncapacity;}
boolisEmpty()const{returncounts==0;}
boolisFull()const{returncounts>=capacity;}
5.取索引对应值、按索引修改值、打印输出、是否包含某值


template
TGenericArray::get(intindex)
{
if(!itemsFlag)
returnpreitems[index];
else
returnitems[index];
}
voidGenericArray::set(intindex,Telem)
{
if(checkIndex(index))
{
if(!itemsFlag)
preitems[index]=elem;
else
items[index]=elem;
return;
}
}
template
voidGenericArray::printArray()const
{
for(inti=0;i
boolGenericArray::contains(Tarr)
{
for(inti=counts-1;i>=0;i--)
if(!itemsFlag)
{
if(arr==preitems[i])
returntrue;
}
else
{
if(arr==items[i])
returntrue;
}
returnfalse;
}
6.查找某值下标、删除某值
查找某值的下标时，要考虑到该值在数组中是否重复，所以博主用了一个结构体findArrIndex来存储该值重复的次数和对应的下标。


structfindArrIndex
{
intnumIndex;
int*findIndex;
};
template
voidGenericArray::find(Tarr,findArrIndex*ps)
{
ps->findIndex=newint[counts];
ps->numIndex=0;
for(inti=0,j=0;ifindIndex)[j]=i;
(*ps).numIndex++;
cout<findIndex)[j]=i;
(*ps).numIndex++;
cout<
voidGenericArray::removeElement(findArrIndex*ps)
{
for(inti=ps->numIndex;i>0;i--)
remove((ps->findIndex)[i-1]);
delete[](ps->findIndex);
}
template
voidGenericArray::set(intindex,Telem)
{
if(checkIndex(index))
{
if(!itemsFlag)
preitems[index]=elem;
else
items[index]=elem;
return;
}
}
7.扩容


添加数据操作时需判断数组容量是否足够，若不够需考虑扩容。


template
voidGenericArray::renewCapacity()
{
cout<<"Thearray'scapacityissmall!Renewcapacity.\n";
if(capacity<1000)
capacity=capacity<<1;
else
capacity=capacity>>1+capacity;
if(!itemsFlag)
{
itemsFlag=1;
items=newT[capacity];
for(inti=0;i
8.添加数据：数组添加数据包括按索引下标插值、数组头插值、数组尾插值。实质上后两种都可以通过调用按索引下标插值函数实现。前文也提到过，数组添加操作中复杂的是大量的数据搬移工作：将某个元素按索引下标插入到数组第k个位置，需要将k~n部分的元素向后搬移一位，然后插入元素，更新元素数目。若插入到数组尾，时间复杂度O(1)；插入到数组头，时间复杂度O(n)；插入的平均时间复杂度为（1+2+…+n）/n=O(n)。

另外，还有一个优化问题：若数组是无序数组，则插入时不需要搬移数据：若将某个元素插入到数组第k个位置，首先将该位置的元素移动到数组末尾，然后将待插入元素插入到第k个位置，时间复杂度O(1)。


template
voidGenericArray::add(intindex,Telem)
{
if(isFull())
{
cout<<"Arrayisfull!"<<'\n';
renewCapacity();
}
if(checkIndex(index))
if(!itemsFlag)
{
for(inti=counts;i>index;i--)
preitems[i]=preitems[i-1];
preitems[index]=elem;
}
else
{
for(inti=counts;i>index;i--)
items[i]=items[i-1];
items[index]=elem;
}
counts++;
return;
}

template
voidGenericArray::addFirst(Telem)
{
add(0,elem);
}

template
voidGenericArray::addLast(Telem)
{
add(counts,elem);
}
9.删除数据：数组删除数据包括按索引下标删除、数组头删除、数组尾删除。实质上后两种都可以通过调用按索引下标删除函数实现。与前文类似，数组删除操作中复杂的也是大量的数据搬移工作：按索引下标将某个元素删除，需要将k+1~n部分的元素向前搬移一位，更新元素数目。若删除数组尾，直接元素数目减一即可，时间复杂度O(1)；删除数组头，时间复杂度O(n)；删除的平均时间复杂度（1+2+…+n）/n=O(n)。

另外，有一个优化问题：如果想多次删除数组中的值，可以先对要删除的值做好标记，做完标记后一次删除，这样就大大减少了搬移的次数。


template
TGenericArray::remove(intindex)
{
if(!isEmpty())
{
if(checkIndex(index))
{
if(!itemsFlag)
{
Ttemp=preitems[index];
for(inti=index+1;i
TGenericArray::removeFirst()
{
returnremove(0);
}
template
TGenericArray::removeLast()
{
returnremove(counts-1);
}


好啦，基本上就这么多了。


最后总结一下，多看源码还是很重要的。


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

C++实现动态数组功能

热门推荐

随机推荐