1.线性表的基本概念与实现

1.线性表的存储结构

　　存储结构有顺序存储结构和链式存储结构，前者称为顺序表后者称为链表

1. 顺序表

　　顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块存储空间中。

2.链表

　　在链表存储中，每个结点不仅包含所存元素本身的信息，还包含元素之前逻辑关系的信息，及前驱结点包含后继结点的地址信息。

两种存储结构的比较

　　顺序表特性是 随机访问特性和占用连续的存储空间，存储分配只能预先进行，即静态分配，一旦分配好了，在对其操作的过程中始终不变。
　　再看链表，不支持随机访问，链表中每一个结点需要划出一部分空间来指向下一个结点位置的指针，因此链表中结点的存储空间利用率要稍低一些。链表中结点是散落分布在存储器中的，所以链表支持存储空间的动态分配，即在需要新的结点时在进行空间分配，而不需要一次性地划分所有所需空间给链表。
全面的比较
基于空间的比较：
(1)存储分配的方式：
顺序表的存储空间是静态分配的。
链表的存储空间是动态分配的。
(2)存储密度(存储密度=结点值域所占的存储量/结点结构所占的存储总量)
顺序表的存储密度=1，链表的存储密度<1。
基于时间的比较：
(1)存取方式
顺序表可以随机存取，也可以顺序存取。
链表是顺序存取。
(2)插入/删除时移动元素的个数
顺序表平均移动近一半的元素，
链表不需要移动元素，只需要修改指针。