《之于数据结构简析》可灼

2、第二章

　　1.线性表是n个元素构成的有限序列、相同特性的数据元素构成。线性表是一种逻辑结构---线性结构。
　　n=0 为空表
　　n为表的长度
　　下标从1开始（物理位序从1开始，逻辑位序从0开始）线性表(a1,a2,a3……an)
　　2.线性表逻辑特征：每个元素仅有一个直接前驱和直接后继，仅有一个起始节点。

　　3.线性表的存储结构研究：

　　3.1线性表的顺序存储表示：【重点基础】
　　1.线性表的顺序存储表示又可以称为顺序存储结构or顺序映像。
　　2.顺序存储的含义是：逻辑上相邻的数据元素存储在物理上相邻的存储单元。逻辑上相邻，物理上也相邻。
　　3.起始位置（基地址）的含义：线性表的第1个数据元素a1的存储位置。
　　4.线性表顺序存储结构特点：占用一片连续的存储空间，中间不能空出存储单元。因此从基地址开始，可以表示所有任意一个元素的存储地址。任意元素随机存取。
　　5.小结：顺序表（元素）:地址连续、依次存放、随机存取、类型相同。所以恰好和c的一维数组对应，但顺序表长可变，数组不可动态定义，所以需要使用数组存元素，但增加一个变量表示表长，构成一个结构体来表示顺序表。
　　6.考点：
　　①定义顺序表时数组分配空间：静态分配、动态分配。

　　②初始化顺序表时开辟存储空间：静态分配、动态分配。

　　③顺序表的基本操作函数：初始化、销毁、清空、插入、删除元素、判空、返回表长、查找元素、获取元素。(要反复敲代码）
　　④顺序表的查找算法分析：查找（按值查）、插入、删除算法的平均时间复杂度为O(n) 。插入和删除算法不仅包括找位置、还包括主要的是移动元素位置时间消耗。 空间复杂度为O(1)，没有辅助空间。
　　⑤顺序表优缺点：优点存储密度大，随机存取任一元素；缺点：插入删除元素要移动大量元素O(n) 浪费存储空间，静态存储形式数据元素个数不能自由扩充。