datetime:2022-04-09 17:46
author:nzb
数据结构与算法
绪论
基本概念
数据
数据元素、数据项
数据对象、数据结构
数据类型、抽象数据类型（ADT）
数据结构三要素
逻辑结构
集合
线性结构
树形结构
图状结构（网状结构）
物理结构（存储结构）
顺序存储
物理内存中是连续的非顺序存储
物理内存中是分散的链式存储
索引存储
散列存储
数据的运算
学习建议
- 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。
线性表
- 定义
逻辑结构
值的注意的特性
数据元素同类型、有限、有序重要术语
表长、空表
表头、表尾
前驱、后继
数据元素的位序（从 1 开始）
类似索引
基本操作
运算创销、增删改查（所有数据结构适用的记忆思路）
判空、判长、打印输出（还可以根据实际需求增加其他基本操作）
其他值的注意的点
理解什么时候要传入参数的引用“&”
值传递还是引用传递函数命名要有可读性
存储/物理结构
顺序表（顺序存储）
存储结构
逻辑上相邻的数据元素物理上也相邻实现方式
静态分配
使用“静态数组”实现
大小一旦确定就无法改变
动态分配
使用“动态数组”实现
顺序表存满时，可再用 malloc 动态扩展顺序表的最大容量
需要将数据元素复制到新的存储区域，并用 free 函数释放原区域
特点
随机访问
能在 O(1) 时间内找到第 i 个元素存储密度高
扩展容量不方便
插入、删除元素不方便
基本操作
插入
插入位置之后的元素都要后移
时间复杂度
最好 O(1)
插入末尾，数据不动最坏 O (n)
插入表头，数据后移平均 O(n)
删除
删除位置之后的元素都要前移
时间复杂度
最好 O(1)
删除末尾，数据不动最坏 O (n)
删除表头，数据前移平均 O(n)
查找
按位查找
获取表 L 中第 i 个位置的元素的值
用数组下标即可得到第 i 个元素 L.data[i - 1]
时间复杂度
最好、最坏、平均时间复杂度都是 O(1)
按值查找
在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序
从第一个元素开始依次往后检索
时间复杂度
最好 O(1)
第一个位置最坏 O(n)
最坏一个位置平均 O(n)
每个位置的概率相同
代码要点
注意位序 i 和数组下标的区别
位序是第几个元素，从 1 开始，下标是从 0 开始判断位序 i 的合法性
链表（链式存储）
单链表
定义
用“链式存储”（存储结构）实现了“线性结构”（逻辑结构）
一个结点存储一个数据元素
各结点间先后关系用一个指针表示
两种实现
不带头结点
空表判断：L == NULL，写代码不方便带头结点
空表判断：L -> next == NULL，写代码方便 头指针 L 加上下一个结点不带数据只带下一个结点的指针域
基本操作
插入
按位序插入
循环遍历找到第 i -1 的节点，然后插入带头结点
当前指针指向，从 0 开始，表示第几个节点不带头结点
当前指针指向，从 1 开始，表示第几个节点
指定结点的后插操作
- 在 p 结点后插入元素 e
- s 为插入的结点
- s -> data = e
- s-> next = p->next
- p->next = s
指定结点的前插操作
知道头指针
依次遍历找到 p 结点，然后插入即可，时间复杂度 O(n)不知道头指针
- 在 p 结点后插入元素 e
- s 为插入的结点
- s -> next = p -> next
- s -> data = p -> data
- p -> data = e
- p -> next = s
删除
按位序删除
和插入操作类似指定结点的删除
- 删除指定结点 p
- 需要改变前驱结点的 next 指针
- 方法1：传入头指针，循环找 p 的前驱结点
- 方法2：类似结点前插入
- p -> data = p -> next -> data
- p -> next = p -> next -> next
- 指定结点是最后一个结点时，需要特殊处理，因为q -> next = NULL，没有 data
查找
注意带头和不带头以及最后一个结点（就是 p 指针为 NULL）按位查找
注意与“顺序表”对比
单链表不具备“随机访问”的特性，只能依次扫描
按值查找
求单链表长度
Key
三种基本操作的时间复杂度都是 O(n)
注意边界条件的处理
建立
尾插法
头插法
链表的逆置
双链表
初始化
头结点的 prior、next 都指向 NULL插入（后插）
注意新插入结点、前驱结点、后继结点的指针修改
边界情况：新插入结点在最后一个位置，需特殊处理
删除（后删）
注意删除结点的前驱结点、后继结点的指针修改
边界情况：如果被删除结点是最后一个数据结点，需特殊处理
遍历
从一个给定结点开始，向后遍历、向前遍历的实现（循环的终止条件）
链表不具备随机存取特性，查找操作只能通过顺序遍历实现
循环链表
循环单链表
- 判断循环单链表是否为空：L -> next == L
- 判断结点 p 是否为循环单链表的表尾结点：p -> next == L，p指针下一个是否指向头指针
循环双链表
- 判断循环双链表是否为空：L -> next == L
- 判断结点 p 是否为循环双链表的表尾结点：p -> next == L，p指针下一个是否指向头指针
静态链表
用数组的方式实现的链表
优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
适用场景
不支持指针的低级语言
数据元素数量固定不变的场景（如操作系统的文件分配表 FAT）
使用
随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。
非随机存取就是顺序存取了，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表。