顺序表构造,插入,扩容操作

扩容操作函数与功能

函数 功能
insert(loc,value) 将value插入到顺序表中下标为Loc的位置
expand() 扩大顺序表的容量

顺序表插入操作的实现方法如下:

1,判断插入位置是否合法。

2,判断顺序表是否已满。

3,将目标位置及之后的元素后移一位。

4,将待插入的元素值插入到目标位置。

顺序表扩容操作的实现方法:

1,将原来的元素存储到临时存储空间。

2,扩大原来的存储空间。

3,将临时存储空间里的数据元素复制新的存储空间里。

4,释放临时的存储空间。

例子演示顺序表的扩容操作:

我们又向刚刚的顺序表中插入了几个元素,现在顺序表已经被填满了,但是我们还希望在最后继续插入一个元素 7。

程序在扩容时,会将元素存储在临时存储空间,再将原来的空间扩大为  2 倍。

 

之后把所有的元素复制到新的存储的空间,并释放临时存储空间。

 接着就可以继续插入元素了。

 在顺序表的扩容操作中,我们需要把原数组空间里的元素一一复制到新的空间内,因此扩容操作的时间复杂度为O(n)

原文地址:https://www.cnblogs.com/qingjiawen/p/15526504.html