数组
起因
今天开始写一个新的系列文章--数据结构与算法,这一系列的文章是学习数据结构和算法的心得体会。由于博主之前没有写过C++代码,对C++的语言语法不是特别了解,但是博主会在学习数据结构和算法的同时更新自己C++相关的语言知识。如若代码中有错误的写法,请您不吝赐教在评论里帮博主更正。先行谢过各位看官。
数组的基本概念
数组是有着连续存储空间的一种数据结构,它支持快速的查询、更新、新增操作,这些操作的时间复杂度为O(1),而删除操作的时间复杂度为O(N)。
数组的结构定义
参照博主的主要开发语言(C#)中关于数组的定义,博主为数组定义的数据结构如下:
private: int* ArrayHead; int count; int capacity;
ArrayHead指向该数组的首元素指针
count记录数组成员当前的个数
capacity记录数组的当前容量
数组定义的操作算法
在C#语言中数组的主要操作方法有新增、删除、插入、初始化,因此博主定义了该数组的操作方法如下:
public: ~GoodeyArray(); int Count(); int Capacity(); GoodeyArray(int initialCapacity); bool Add(int item); bool InsertBefore(unsigned int index, int item); bool Delete(unsigned int index); void PrintArray();//打印输入元素、容量、大小信息
数组初始化
GoodeyArray(Int initialCapacity)构造函数,要求使用者输入数组的初始化容量,在构造函数的实现中,我们New了该容量的连续空间,并将ArrayHead指向该连续空间的首地址,之后再初始化count和capacity,代码如下:
GoodeyArray::GoodeyArray(int initialCapacity) { ArrayHead = new int [sizeof(int) * initialCapacity]; capacity = initialCapacity; count = 0; } //数组打印函数 void GoodeyArray::PrintArray() { for (int i = 0; i < count; i++) { printf("%u ",ArrayHead[i]); } printf("\n"); printf("容量:%u 长度:%u \n", Capacity(), Count()); }
此时,我们来测试一下初始化方法,看命令行输入是否正确(初始化后,容量为5,长度为0):
数组新增
在介绍数组新增功能之前,我们先考虑一个数组动态扩容的问题,当我们向数组添加的元素数量大于此时数组的容量时,我们就需要动态的申请更多的空间(原来容量的1.5倍),并将原有ArrayHead指针指向新空间的首地址,之后再删除临时指针,动态扩展代码如下:
void GoodeyArray::changedCapacity() { //扩容为原来的1.5倍 capacity = (capacity * 3 / 2); int* temp = new int[sizeof(int) * capacity]; int addr; if (temp != NULL) { memset(temp, 0, sizeof(int) * capacity); memcpy(temp, ArrayHead, sizeof(int) * count); addr = *temp; *temp = *ArrayHead; *ArrayHead = addr; delete[] temp; } }
新增元素代码如下:
bool GoodeyArray::Add(int item) { if (count == capacity) { changedCapacity(); } ArrayHead[count] = item; count++; return true; }
此时,我们来测试一下新增方法,测试方法以及结果如下:
GoodeyArray gArray = GoodeyArray(5); gArray.Add(1); gArray.Add(2); gArray.Add(3); gArray.Add(4); gArray.PrintArray(); gArray.Add(5); gArray.Add(6); gArray.Add(7); gArray.Add(8); gArray.PrintArray();
数组插入
数组的插入操作逻辑是将插入位置以及之后的元素往后移动一位,此时描述的插入操作为通常意义的插入,即为前插入;移动元素时要从后往前变量,一直遍历到待插入的位置索引;插入操作要主要数组的容量扩容问题。数组插入代码如下:
bool GoodeyArray::InsertBefore(unsigned int index, int item) { if (index > count) { printf("插入位置错误"); return false; } if (count == capacity) { changedCapacity(); } for (int i = count; i > index; i--) { ArrayHead[i] = ArrayHead[i - 1]; } ArrayHead[index] = item; count++; return true; }
此时,我们来测试一下插入方法,测试用例包含数组首位、中间、末尾:
GoodeyArray gArray = GoodeyArray(5); gArray.Add(1); gArray.Add(2); gArray.Add(3); gArray.Add(4); gArray.Add(5); gArray.InsertBefore(0,12); gArray.PrintArray(); gArray.InsertBefore(3, 15); gArray.PrintArray(); gArray.InsertBefore(7, 19); gArray.PrintArray();
数组删除
数组的删除操作逻辑是将删除索引位置后的元素迁移一位,移动元素时要从删除索引位置往后,直至数组结尾,删除代码如下:
bool GoodeyArray::Delete(unsigned int index) { if (index >= count) { printf("删除位置错误"); return false; } for (int i = index; i < count-1; i++) { ArrayHead[i] = ArrayHead[i+1]; } count--; return true; }
此时,我们测试一下数组的删除操作,测试用例和结果如下:
GoodeyArray gArray = GoodeyArray(5); gArray.Add(1); gArray.Add(2); gArray.Add(3); gArray.Add(4); gArray.Add(5); gArray.InsertBefore(0,12); gArray.InsertBefore(3, 15); gArray.InsertBefore(7, 19); gArray.Delete(0); gArray.PrintArray(); gArray.Delete(4); gArray.PrintArray(); gArray.Delete(5); gArray.PrintArray();