线性表

#

线性表的定义

#

线性表是同一类型数据的有序序列，数据之间存在逻辑上的线性关系。线性结构是最常用，最简单的一种数据结构，而其特点是线性表中的数据元素是有序且有限的。

线性表可以为空

定义： (A1,A2,A3,… An-1,An)

顺序表

#

存储结构

#

线性表的顺序又表示为顺序存储结构或者顺序映像

顺序存储： 线性表的结构按照逻辑顺序一次存放在椅子地址连续的存储单元里面，这样吨出的线性表成为顺序表。

顺序存储的线性表的特点：

• 线性表的存储顺序和物理顺序一致。

• 数据元素之间的关系是以元素在计算机内的 “物理位置相邻’‘来实现

元素地址计算公式：

算法

#

遍历输出

#

顺序表中插入元素

#

在长度位N的顺序表中的第I位插入元素。

算法步骤：

• 判断插入位置I是否合适
• 判断顺序表中的存储空间是否已满
• 将第N至第I位元素一次后移一个位置，空出第I个位置
• 将元素插入第I位

顺序表中删除元素

#

在长度为N的顺序表中删除第I位元素。

算法步骤：

• 判断插入位置I是否合法
• 判断顺序表中的存储空间是否已满
• 将第N至第I位元素一次后移一个位置，空出第I个位置
• 将元素插入第I位

顺序表的浅拷贝和深拷贝

#

浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。

顺序表小结

#

顺序表静态特性很好，动态特定很差，具体说明如下：

• 顺序表元素的物理存储顺序直接反应线性表元素的逻辑顺序。顺序表是一种随机存取结构，get() ，set()方法的时间复杂度是O(1)。
• 插入和删除操作效率很低，如果在各位置