【王道数据结构】第二章 线性表_数据结构王道第二章

22.1 线性表的定义和基本操作

• 线性表(Linear List)的定义

• 线性表的基本操作

什么时候要传入参数的引用 **“&” **—— 对参数的修改结果需要 “带回来”

---

2.2 线性表的顺序表示

2.2.1 顺序表的定义

• 顺序表的实现——静态分布

• 顺序表的实现——动态分配

顺序表特点

---

2.2.2 顺序表上基本操作的实现

顺序表的插入和删除

• 顺序表的插入

静态分配方法（动态类似）：

插入操作的时间复杂度：

• 顺序表的删除

删除操作：

删除操作的时间复杂度：

---

顺序表的查找

• 按位查找

GetElem(L,i)：按位查找操作。获取表L中 第i个位置 的元素的值。

1）静态分配：

2）动态分配：

其中：

时间复杂度：

• 按值查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

数组下标 为i的元素值等于e，返回其 位序i+1

关于结构体的比较：

Tips：
《数据结构》考研初试中，手写代码可以直接用“==”，无论 ElemType 是基本数据类型还是结构类型。手写代码主要考察学生是否能理解算法思想，不会严格要求代码完全可运行。

时间复杂度：

---

2.3 线性表的链式表示

2.3.1 单链表的定义

• 什么是单链表

• 用代码定义一个单链表