一、线性表概述
1.1 线性表的定义
- 线性表是具有相同数据类型的 n (n>=0) 个数据元素的有限序列。其中 n 表示表长，当 n = 0 时表示该线性表是一个空表。
- 除第一个元素外，每个元素有且仅有一个直接前驱。
- 除最后一个元素外，每个元素有且仅有一个直接后驱。
1.2 线性表的特性
- 表中元素的个数有限。
- 表中元素具有逻辑上的顺序性，在序列各元素排序有其先后次序。
- 表中元素都是数据元素，每个元素都是单元素。
- 表中元素的数据类型都相同，这意味着每一个元素占有相同大小的存储空间。
- 表中元素具有抽样性，即仅讨论元素之间的逻辑关系，不考虑元素究竟表示什么内容。
1.3 线性表的基本操作
- InitList(&L)：初始化表，构造一个空的线性表。
- Length(L)：求表厂，返回线性表L的长度，即L中数据元素的个数。
- LocateElem(L, e)：按值查找，在表 L 中查找具有给定关键字值的元素。
- GetElem(L, i)：按位查找，获取表中第 i 个位置的元素的值。
- ListInsert(&L, i, e)：插入操作，在表 L 中第 i 个位置插入指定元素 e 。
- ListDelete(&L, i, &e)：删除操作，表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
- PrintList(L)：输出操作，按前后顺序输出线性表 L 的所有元素值。
- Empty(L)：判空操作，若 L 为空表，则返回 true ，否则返回 false 。
- DestoryList(&L)：销毁操作，销毁线性表，并释放线性表 L 所占用的内存空间。
二、线性表的顺序表示
2.1 顺序表的定义
- 线性表的顺序存储又称顺序表。
- 它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
- 一维数组可以是静态分配，也可以是动态分配。
- 静态分配需事先固定数组的大小和空间，空间占满时，再加入新的数据将产生溢出，导致程序崩溃。
- 动态分配时，在程序执行过程中通过动态存储分配语句分配存储数组的空间，空间占满时，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而扩充数组空间，而不是一次性地划分所有所需空间。
2.2 顺序表的特点
- 顺序表的最主要特点是随机访问，即通过首地址和元素序号可以在 O(1) 的时间内找到指定的元素。
- 顺序表的存储密度高，每个节点只存储数据元素。
- 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
2.3 顺序表基本操作
- 插入、删除、按值查找（顺序查找）
三、线性表的链式表示
- 链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻。
- 它是通过链建立数据元素之间的逻辑关系。
- 对线性表的插入、删除不需要移动元素，而只需要移动指针。
3.1 单链表的定义
- 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。
- 由于单链表的元素是离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接查找表中某个特定的节点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
- 通常用头指针来标识一个单链表，如单链表 L ，头指针为 NULL 时表示一个空表，
- 为了操作上的方便，在单链表的第一个结点之前附加一个结点，称为头节点。
3.2 单链表基本操作
- 采用头插法建立单链表、通过尾插法建立单链表、按序号查找结点值、按值查找结点值、插入节点操作（分为前插操作、后插操作，常用后插操作），删除节点操作、求表厂操作。
3.3 双链表
- 双链表结点中有两个指针 prior 和 next ，分别指向其前驱结点和后驱节点
- 主要操作：双链表的插入操作、双链表的删除操作。
3.4 循环链表
- 循环单链表：循环单链表与单链表的区别在于，表中的最后一个指针不是 NULL，而改为指向头节点，从而使整个链表形成一个环。可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。
- 循环双链表：与循环单链表类似，但头节点的 prior 指针还要指向尾节点。
四、静态链表
- 静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，这里的指针时结点的相对地址（数组下标），又称为游标。
- 和顺序表一样，静态链表也要预先分配一块连续的内存空间。
- 静态链表以 next = -1 作为其结束的标志。
- 静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。
五、顺序表和链表的比较
5.1 存取方式
- 顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。
5.2 逻辑结构与物理结构
- 采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相似。
- 链式存储时，逻辑上相邻的元素，其物理位置不一定相邻，其对应的逻辑关系时通过指针链接来表示的。
5.3 查找、插入和删除操作
- 对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为 O(n)，而当顺序表有序时，可采用折半查找，此时时间复杂度为 O(log n)。
- 对于按序号查找，顺序表支持随机访问，时间复杂度为 O(1)，而链表的平均时间复杂度为 O(n)。
- 顺序表的插入、删除操作，平均需要移动半个表厂的元素；链表的插入、删除操作，只需要修改相关结点的指针域即可。
- 由于链表每个结点带有指针域，因而在存储空间上的存储密度较小。
5.4 空间分配
- 顺序存储在静态分配情况下，需要预先分配较大的内存空间。预先分配过大，可能会导致顺序表后面大量闲置；预先分配过小，会造成溢出。
- 顺序表在动态分配情况下，虽然可以扩充存储空间，但需要移动大量元素，操作效率较低，而且内存中没有更大块的连续存储空间将导致分配失败。
- 链式存储的结点空间只需要的时候申请分配，只要内存有空间就可以分配，操作灵活、高效。
六、在实际中怎样选取存储结构
- 通常较稳定的线性表选择顺序存储，而频繁做插入、删除操作的线性表（即动态性较强）宜选择链式存储。
6.1 基于存储的考虑
- 对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度小于1。
6.2 基于运算的考虑
- 经常做按序号访问数据元素时，顺序表优于链表。
- 做插入和删除操作，当数据元素的信息量较大且表较长时，由于顺序表平均移动表中一般的元素，而在链表中主要是比较操作，从这个角度考虑，后者由于前者。
6.3 基于环境的考虑
- 顺序表易于实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单。
易错点
- 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。
- 顺序表和链表是指存储结构，两者属于不同层次的概念，莫要将其混淆。
- 线性表的顺序存储结构是一种随机存取的存储结构。
