[数据结构与算法]数据结构笔记（二）

第二章 线性表

线性结构是最常用、最简单的一种数据结构。
线性表中的数据元素是有序且是有限的。
① 存在一个唯一的被称为“第一个”的数据元素；
② 存在一个唯一的被称为“最后一个”的数据元素；
③ 除第一个元素外，每个元素均有唯一一个直接前驱；
④ 除最后一个元素外，每个元素均有唯一一个直接后继。

顺序表的优点：
（1）无须增加额外的存储空间表示结点间的逻辑关系。
（2）可以方便地随机存取表中任一结点。

顺序表的缺点：
（1）插入和删除运算不方便，通常须移动大量结
点，效率较低。
（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。

线性表顺序存储结构

顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。

存储地址的计算：

LOC(ai+1)=LOC(ai)+c
LOC(ai)=LOC(a1)+(i-1)*c 1<=i<=n，LOC(ai)为结点a1的存储地址（基地址），c为每个结点所占存储单元数。