第二章：线性表

2.1线性表的定义

定义

基本操作

&参数引用

为什么要实现对数据结构的基本操作？
①团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）
②将常用的操作/运算封装成函数，避免重复工作，降低出错风险

总结

2.2顺序表的定义

2.2.1静态分配:

2.2.2动态分配

总结

2.2顺序表的基本操作

2.2.1 插入操作 ：平均时间复杂度O(n)

时间复杂度

2.2.2 删除操作：平均时间复杂度O(n)

时间复杂度

总结

2.2.3 按位查找(获取L表中第i个位置的值)：平均时间复杂度O(1)

时间复杂度

2.2.4 按值查找：平均时间复杂度O（n）

结构类型struct的比较

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

时间复杂度

总结

2.3线性表的链式表示

2.3.1 单链表的定义

不带头节点的单链表

带头结点的单链表

总结

2.3.2单链表上基本操作的实现

按位序插入（带头结点）

按位序插入（不带头结点）

指定结点的后插操作

指定结点的前插操作

按位序删除（带头结点）

指定结点的删除

总结

2.3.3单链表的查找

按位查找

按值查找

求表的长度

总结

2.3.4单链表的创建操作

尾插法建立单链表

头插法建立单链表

总结

2.3.5双链表

初始化

插入？

删除

遍历

总结

2.3.6循环链表

循环单链表

循环双链表

初始化

插入

删除

总结

2.3.7静态链表

定义

代码实现

总结

2.3.8顺序表和链表的比较

逻辑结构

都属于线性表，都是线性结构

存储结构

基本操作

选择

总结