线性表几种基本操作的思路1、插入算法：
1）插入位置不合理，抛出异常
2）线性表长度超过（>=）数组长度，抛出异常或者是动态增加数组容量(效率会变低)。
3）从最后一个元素向前遍历到第i个位置，分别将它们后移一位。
4）将要插入的元素插入在i处
5）线性表长度要+1
2、 删除算法：
1）删除的位置不合理，抛出异常
2）剔除被删除的元素
3）从被删除的位置往后面遍历，将被遍历的元素前移一位
4）表长要记得 - 1
3.线性表的顺序存储结构
1）线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
理解它物理上的存储方式，先占位一定的内存空间，然后将同一种数据类型的元素依次存放进去
2）顺序存储结构封装的三个属性
a）存储空间的其实位置，数据data的存储位置就是线性表存储空间的存储位置
b）线性表的最大存储容量：数组的长度MaxSize
c）线性表的当前长度：length
4、上述两种操作的时间复杂度分析（在顺序存储结构中）：
在线性表的插入和删除操作上，我们可以知道它们最好的情况是不进行任何移动，直接在最后一个元素后面进行插入或删除操作，这样时间复杂度将是O（1）;最坏的情况是两种操作都在第一个元素位置处进行，需要遍历表中每一个元素，这种情况时间复杂度是0（n）;第三种是折中，操作在中间进行，这样的话它的时间复杂度是0（（n-1）/2）,用之前总结的算法时间复杂度推导方法可以知道简化后还是O（n）。
由此可见，线性表的顺序存储结构其实不适合频繁做插入删除的操作，因为表中相邻元素之间内存地址是紧挨着，没有间隙的，没有办法实现快速插入删除，所以这种办法效率不高（除非它在最后进行操作）。但是做读存操作还是不错的，因为它们的时间复杂度为O（1）。
网友评论