顺序存储结构就是在内存空间中开辟一片连续的空间,然后把数据按照顺序进行存储的一种方式。
他包含三个属性:1、存储空间的起始位置(也就代表我们定义了一个数组)2、最大的存储容量(数组最大长度)3、线性表的当前长度。
属性2和3的区别是:数组的长度是基本不变的,这是我们在申请内存空间的时候就已经确定好的,而我们的线性表的长度是代表着元素个数,是不确定的长度。则两者的关系为: 线性表的当前长度<=数组长度;
一、顺序存储结构的插入与删除:
1.1、插入思路:
(1)、我们首先需要考虑异常(插入位置异常,插入后的长度异常等)
(2)、从最后一个元素遍历到插入位置,分别将每一个元素向后移动一个位置;
(3)、插入目标元素,表长加1;
1.2、删除思路:
(1)、我们仍然需要首先考虑异常(删除位置错误等)
(2)、查找到需要删除的位置,遍历将其后的每一个元素向前进行移动。
二、总结:
我们可以看出,在插入算法中,顺序存储结构中元素在插入位置的过程中,多数元素都需要进行移动,来给插入的元素腾位置。并且,在删除算法中也是类似的道理。我们计算下他们的时间复杂度:顺序存储结构在读取数据的时候,因为可以按照list[index]进行读取,所以时间复杂度为O(1),但在插入和删除算法的时候,平均的时间复杂度为O(n);
我们可以看出顺序存储结构的优点和缺点:
优点是:不需要为表示元素之间的逻辑关系而增加额外存储空间,可以快速的存取表中的任一位置的元素。
缺点是:插入和删除操作需要移动大量的元素。当线性表变化较大的时候,难以确定存储空间的容量。