线性表
定义
线性表是具有相同数据类型的n（n≥0）个数据元素的有限 序列
特点
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅 有一个直接后继
操作
初始化、增、删、查、改、销毁
元素的下标与位序
下标从0开始，位序从1开始
分类（根据存储结构来划分的）
顺序表
顺序存储
-
定义
用顺序存储的方式实现线性表。顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
-
实现
-
静态分配（数组实现）
扩展容量不方便，缺乏灵活性、但是内存管理简单，不存在内存泄漏的问题（内存泄漏——只申请内存不释放内存）
-
动态分配（malloc）
空间利用灵活，但是内存管理复杂
-
-
特点
-
优点
-
随机访问，即可以在 O(1) 时间内找到第 i 个元素
-
存储密度高
-
-
缺点
-
扩展容量不方便，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高
-
插入、删除操作不方便，需要移动大量的元素
-
-
顺序存储、随机存取
-
-
操作
-
插入：移动元素（n/2）次
-
删除：移动元素（n-1）/ 2次
-
查找：比较次数：（n+1）/ 2
-
查找最多,即(n+1)，记住，删除肯定是要小的，即(n-1)，而插入是增多，即n
-
链表
链式存储
-
单链表
-
定义
用链式存储实现的线性表，链式存储：逻辑上相邻但是物理存储结构上不相邻，每个结点除了存放数据元素外，还要存储指向下一个节点的指针
-
实现
带头结点有什么好处？
-
带头结点
写代码更方便
-
不带头结点
写代码更麻烦，对第一个结点的处理需要使用不同的代码逻辑。比如判空操作
-
-
特点
-
优点
-
扩展容量方便
-
插入、删除操作很方便、不需要移动大量的元素
-
-
缺点：
-
只能顺序访问
-
存储密度低
-
-
随机存储、顺序存取
-
-
操作：插入、删除、查找。三种操作的复杂度都为O(n)
-
建立
-
尾插法
-
头插法：可用于实现单链表逆置
-
-
-
双链表，如下：
-
- 定义
-
由于单链表不能逆向检索，因此出现了双向链表。
-
实现
-
特点
-
存储密度更低，不具备随机存取特性
-
-
操作
-
插入
注意新插入结点、前驱结点、后继结点的指针修改 边界情况∶新插入结点在最后一个位置，需特殊处理
-
删除
注意删除结点的前驱结点、后继结点的指针修改 边界情况︰如果被删除结点是最后一个数据结点，需特殊处理
-
-
-
循环链表
-
循环单链表，如下：
-
表尾结点的next指针指向头结点
-
循环双链表
-
-
表头结点的 prior 指向表尾结点； 表尾结点的 next 指向头结点
-
特点：存储密度服务器托管网低、插入、删除操作方便。相比与普通单链表和普通双向链表，循环链表可以从任意结点出发遍历整个链表，而普通链表只能从头结点开始遍历
-
-
静态链表
-
定义
用数组的方式实现的链表
-
实现：每个结点的next存放下一个结点的下标
-
优点
-
增、删操作不需要大量移动元素
-
-
缺点
-
不能随机存取，容量固定不可变
-
-
适用场景：操作系统文件分配表
-
链表与顺序表的异同
逻辑结构
都是线性表，逻辑上相邻
数据运算
链表：插入、删除很方便，不需要移动大量的元素。查找只能从头开始查找
顺序表：插入、删除元素不方便、需要移动大量的元素。查找可以用折半查找
存储结构
链表：链式存储
顺序表：顺序存储
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
