知识回顾

2.1 线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列

同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。

2.2 案例引入

总结

- 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
- 许多实际应用问题所涉及的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。
- 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现存储结构和基本操作。

2.3 线性表的类型定义

基本操作（一）

1. 初始化
InitList(&L)
- 操作结构：构造一个空的线性表
2. 销毁一个线性表
DestroyList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表
3.线性表的清除
ClearList(&L)
初始条件：线性表L已经存在
操作结果：将线性表L重置为空表

基本操作（二）

- ListEmpty(L)
初始条件：线性表L已经存在。
操作结果：若线性表L为空表（n = 0），则返回TRUE;否则返回FALSE.
- ListLength(L)
初始条件：线性表L已经存在
操作结果：返回线性表L中的数据元素个数

基本操作（三）

- GetElem(L,i,&e);
初始条件：线性表L已经存在，1<=i<=ListLength(L).
操作结果：用e返回线性表L中第i个元素的值。

- LicateElem(查找定位)(L,e,compare())
初始条件：线性表L已经存在，compare()是数据元素判定函数。（判定条件）
操作结果：返回L中第一个与e满足compare()的数据严肃的位序。若这样的元素不存在则返回值为0.

基本操作（四）

- priorElem查当前元素的前驱元素(L,cur_e,&pre_e)
初始条件：线性表L已经存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱否则操作失败：pre_e无意义
- NextElem后继(L,cur_e,&next_e)
初始条件：线性表L已经存在。
操作结果：若cur_e是L的数据元素，且不是最后一个元素，则用next_e返回它的汇集否则则操作失败，next_e无意义。

基本操作（五）

-  ListInsert插入(&L,i,e)
初始条件：线性表L已经存在，1<=i<=ListLength(L)+1.
操作结果：在L的第i个位置之前插入新的数据元素e，L的长度加一.

基本操作(六)

ListDelete(&L,i,&e)
初始条件：线性表L已经存在，1<=i<=ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一

ListTraverse(&L,visited())
初始条件：线性表L已经存在
操作结果：依次对线性表中每个元素调用visited()

2.4 线性表的顺序表示和实现

线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

LOC(a1)为基地址,可以直接获取第n个元素地址复杂度为O(1).

补充类C语言的一些操作

线性表的顺序存储表示

该算法复杂度为常量阶。所以为随机存取。O(1).

顺序表的查找

顺序表的查找
- 在线性表L中查找与指定e相同的数据元素的位置
- 从表的一端开始，逐个进行记录的关键字和给定值的比较。找到返回该元素的位置序号，未找到，返回0.

数量级
O(n)

顺序表插入算法

时间复杂度
O(n)

顺序表的删除算法

顺序表删除算法的平均时间复杂度为O（n）。

小结：

克服这个缺点：链表

2.5 线性表的链式表示和实现

知识回顾

链式存储结构

如何表示空表？

在链表设置头结点的好处？

1. 便于首元节点的处理
首元节点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须经行特殊处理。
2.便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头节点的非空指针，因此空表和非空表表的处理也就统一了。

头节点的数据与内装的是什么？

链表（链式存储结构）的特点

(1)节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理逻辑上不一定相邻。
（2）访问时智能通过头指针进入链表，并通过每个结点的指针域以此向后顺序扫描其余结点，所以寻找第一个节点和最后一个节点所花费的数间不等。
链表->（顺序存取法）->随机存储
顺序表->随机存取->顺序存储

单链表的存储结构

单链表基本操作的实现

单链表的初始化（带头结点的单链表）

判断一个链表是否为空？

单链表的销毁：链表销毁后不存在

清空链表

求单链表L的表长

知识回顾

取值——取单链表中的第i个元素的内容

单链表的查找

单链表的插入

不可以！会丢失ai的地址

单链表删除i个结点

单链表的时间效率

1.查找：

因为线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n).

2.插入和删除

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O（1）。
但是，如果要在单链表前插入或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n).

单链表的建立-头插法

单链表的建立：尾插法