导图社区 数据结构(2)
- 22
- 0
- 0
- 举报
数据结构(2)
数据结构(的三要素是：逻辑结构、物理结构（存储结构）、数据的运算，欢迎一起来看数据结构知识。
编辑于2023-05-28 15:46:20 安徽- 相似推荐
- 大纲
数据结构
1.1数据结构的基本概念
数据结构
基本概念
数据
数据元素、数据项
数据对象、数据结构
数据类型、抽象数据类型（ADT）
三要素
逻辑结构
物理结构（存储结构）
数据的运算
1.2.1算法的基本概念
算法的基本概念
什么是算法
程序=数据结构+算法
数据结构是要处理的信息
算法是处理信息的步骤
算法的五个特征
算法必须要具备的特性
有穷性
有穷时间内能执行完
算法是有穷的
程序可以是无穷的
确定性
相同输入只会产生相同输出
可行性
可以用已有的基本操作实现算法
输入
丢给算法处理的数据
输出
算法处理的结果
“好”算法的特质
设计算法时要尽量追求的目标
正确性
能正确解决问题
可读性
对算法的描述要让其他人看的懂
健壮性
算法能处理一些异常状况
高效率与低存储量需求
即算法执行省时、省内存
时间复杂度低、空间复杂度低
1.2.2算法的时间复杂度
时间复杂度
如何计算
①找到一个基本操作（最深层循环）
②分析该基本操作的执行次数X和问题规模n的关系x=f（n）
③x的数量级O（x）就是算法复杂度
常用技巧
加法规则
乘法规则
书上p6常对幂指阶
三种复杂度
最坏时间复杂度：考虑输入数据“最坏”的情况
平均时间复杂度：考虑所有输入数据都等概率出现的情况
最好时间复杂度：考虑输入数据“最好”的情况
空间复杂度
如何计算
普通程序
①找到所占空间大小与问题规模相关的变量
②分析所占空间x与问题规模n的关系x=f（n）
③x数量级O（x）就是算法空间复杂度S（n）
递归程序
①找到递归调用的深度x与问题规模n的关系x=f（n）
②x 数量级O（x）就是算法空间复杂度S（n）
注：有的算法各层函数所需存储空间不同，分析方法略有不同
常用技巧
加法规则
乘法规则
同时间复杂度
2.1线性表的定义和基本操作
线性表
定义
值的注意的特性
数据元素同类型、有限、有序
重要术语
表长、空表
表头、表尾
前驱、后继
数据元素的位序（从1开始）
基本操作
创销、增删改查（所有数据结构适用的记忆思路）
判空、判长、打印输出
其他值得注意的点
理解什么时候要传入参数的引用“&”
函数命名要有可读性
存储/物理结构
顺序表（顺序存储）
定义（如何用代码实现）
基本操作的实现
链表（链式存储）
单链表
定义（如何用代码实现）
基本操作的实现
双链表
循环链表
静态链表
2.2.1顺序表的定义
顺序表
存储结构
逻辑上相邻的数据元素物理上也相邻
实现方式
静态分配
使用“静态数组”实现
大小一旦确定就无法改变
动态分配
使用“动态数组”实现
L.data=(ElemType*)malloc(sizeof(ElemType)*size);
顺序表存满时，可再用malloc动态拓展顺序表的最大容量
需要将数据元素复制到新的存储区域，并用free函数释放原区域
特点
随机访问
能在O（1）时间内找到第i个元素
存储密度高
拓展容量不方便
插入删除数据元素不方便
2.2.2.1顺序表的插入删除
顺序表的基本操作
插入
Listinsert(&L,i,e)
将元素e插入到L的第i个位置
插入位置之后的元素都要后移
时间复杂度
最好O（1）、最坏O（n）、平均O（n）
删除
ListDelete(&L,i,&e)
将L的第i个元素删除，并用e返回
删除位置之后的元素要前移
时间复杂度
最好O（1）、最坏O（n）、平均O（n）
代码要点
代码中注意位序i和数组下标的区别
算法要有健壮性，注意判断i的合法性
移动元素时，从靠前的元素开始？还是从表尾元素开始？
分析代码，理解为什么有的参数需要加“&”引用
2.2.2.2顺序表的查找
顺序表的基本操作
按位查找
GetElem（L，i）
获取表L中第i个位置的元素的值
用数组下标即可得到第i个元素L.data【i—1】
时间复杂度
最好/最坏/平均时间复杂度都是O（1）
按值查找
LocativeElem（L，e）
在顺序表L中查找第一个元素值等于e的元素，并返回其位序
从第一个元素开始依次往后检索
时间复杂度
最好O（1）：目标元素在第一个位置
最好O（n）：目标元素在最后一个位置
最好O（n）：目标元素在每个位置的概率相同
2.3.1单链表的定义
单链表
用“链式存储”（存储结构）实现了“线性结构”（逻辑结构）
一个结点存储一个数据元素
各结点间的先后关系用一个指针表示
用代码定义一个单链表
两种实现
不带头结点
空表判断：L==NULL。写代码不方便
带头结点
空表判断：L→next==NULL。写代码更方便
其他注意的点
typedef关键字的用法
LinkList等价于LNode* 前者强调这是链表，后者强调这是结点 合适的地方用合适的名字，代码可读性高
2.3.2.1单链表的插入删除
插入
按位序插入
带头结点
不带头结点
指定结点的后插操作
指定结点的前插操作
删除
按位序删除
指定结点的删除
2.3.2.2单链表的查找
按位查找
注意与“顺序表”对比
单链表不具备“随机访问”的特性，只能依次扫描
按值查找
求单链表长度
key
三种基本操作的时间复杂度都是O（n）
如何写循环扫描各个结点的代码逻辑
注意边界条件的处理
2.3.2.3单链表的建立
采用头插法建立单链表
采用尾插法建立单链表
2.3.3双链表
初始化
头结点的prior.next 都指向NULL
插入（后插）
注意新插入结点、前驱结点、后继结点的指针修改
⚠️边界情况：新插入结点在最后一个位置，需特殊处理
删除（后插）
注意删除结点的前驱结点、后继结点的指针修改
⚠️边界情况：如果被删除结点是最后一个数据结点，需特殊处理
遍历
从一个给定结点开始，后向遍历、前向遍历的实现（循环的终止条件）
链表不具备随机存取特性，查找操作只能通过顺序遍历实现
2.3.4循环链表
循环单链表
空表f
非空表
循环双链表
空表
非空表
代码问题
2.3.5静态链表
2.3.6顺序表和链表的比较
3.1.1栈的基本概念
栈
定义
一种操作受限的线性表，只能在栈顶插入、删除
特性：后进先出（LIFO）
术语：栈顶、栈底、空栈
基本操作
创、销
增、删（元素 进栈、出栈，只能在栈顶操作
查（获得栈顶元素，但不删除）
判空
3.1.2栈的顺序存储实现
顺序栈
顺序存储，用静态数组实现，并需要记录栈顶指针
基本操作
创删改查
都是O（1）时间复杂度
两种实现
初始化时top=1
入栈
S.data［++S.top］=x;
出栈
x=S.data［S.top--］;
获得栈顶元素
x=S.data［S.top］;
栈空/栈满条件是？
初始化时top=0
入栈
S.data［S.top++］=x;
出栈
x=S.data［--S.top］;
获得栈顶元素
x=S.data［S.top-1］;
栈空/栈满条件是？
共享栈
两个栈共享同一片内存空间，两个栈从两边往中间增长
初始化
0号栈栈顶指针初始时top0=-1;1号栈栈顶指针初始时TOP1=MaxSize;
栈满条件
top0+1==top1
3.1.3栈的链式存储实现
链栈
用链式存储方式实现的栈
两种实现方式
带头结点
不带头结点（推荐）
重要基本操作
创（初始化）
增（进栈）
删（出栈）
查（获取栈顶元素）
如何判空、判满
3.2.1队列的基本概念
定义
一种操作受限的线性表，只能在队尾插入，在队头删除
特性：先进先出
术语：队头、队尾、空队列、队头元素、队尾元素
基本操作
创、销
增、删（入队、出队，只能在规定的一端进行）
查（获得队头元素，但不删除）
判空
3.2.2队列的顺序实现
实现思想
用静态数组存放数据元素，设置队头队尾（front/rear）指针
循环队列：用模运算（取余）将存储空间在逻辑上变为“环状”
Q.rear=(Q.rear+1)%MaxSize
重要考点
如何初始化、入队、出队
如何判空、判满
如何计算队列的长度
分析思路
确定front、rear指针的指向
①rear指向队尾元素后一个位置
②rear指向队尾元素
确定判空判满的方法
a.牺牲一个存储单元
b.增加size变量记录队列长度
c.增加tag=0/1用于标记最近一次操作是出队/入队
……
3.2.3队列的链式实现
队列
用链式存储实现队列
带头节点
不带头结点
基本操作
创（初始化）
增（入队）
注意第一个元素入队
删（出队）
注意最后一个元素出队
查（获取队头元素）
判空
判满？不存在的
3.2.4双端队列
队列的变种
双端队列
允许两段插入，两端删除的队列
输入受限的双端队列
允许从两端删除、从一端插入的队列
输出受限的双端队列
允许从两端插入、从另一端删除的队列
考点：对输出序列合法性的判断
在栈中合法的输出序列，在双端队列必定合法
3.3.1栈在括号匹配中的应用
用栈实现括号匹配
依次扫描所有字符，遇到左括号入栈， 遇到右括号则弹出栈顶元素检查是否匹配
匹配失败情况
1左括号单身
2右括号单身
3左右括号不匹配
3.3.2.1栈在表达式求值中的应用（上）
表达式求值问题
概念
运算符、操作数、界限符（DIY概念：左操作数、右操作数）
三种表达式
中缀表达式
运算符在操作数中间
后缀表达式（逆波兰式）
运算符在操作数后面
前缀表达式（波兰式）
运算符在操作数前面
⚠️后缀表达式考点
中缀转后缀
①按照“左优先”原则确定运算符的运算次序
②按照①中确定的次序，依次将各个运算符和与之相邻的两个操作数 按〈左操作数 右操作数 运算符〉的规则合体
后缀转中缀
从左往右扫描，每遇到一个运算符，就将〈左操作数 右操作数 运算符〉 变为（左操作数 运算符 右操作数）的形式
计算
从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈 （注意：先弹出的是“右操作数”）
前缀表达式
中缀转前缀
①按照“右优先”原则确定运算符的运算次序
②按照①中确定的次序，依次将各个运算符和与之相邻的两个操作数 按〈 运算符 左操作数 右操作数 〉的规则合体
计算
从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈 （注意：先弹出的是“左操作数”）
3.3.2.2栈在表达式求值中的应用
用栈实现中缀转后缀表达式
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符
从左到右处理各个元素，直到末尾。可能会遇到三种情况
①遇到操作数。直接加入后缀表达式
②遇到界限符。遇到“（”直接入栈；遇到“）”则依次弹出栈内运算符并加入 后缀表达式，直到弹出“（”为止。注意：“（”不加入后缀表达式
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符， 并加入后缀表达式，若碰到“（”或栈空则停止。之后再把当前运算符入栈
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式
用栈实现后缀表达式的计算
①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①；否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
用栈实现中缀表达式的计算
初始化两个栈，操作数栈和运算符栈
若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈 （期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应 运算，运算结果再压回到操作数栈）
3.3.3栈在递归中的应用
函数调用的特点：最后被调用的函数最先被执行结束（LIFO）
函数调用时，需要用一个“函数调用栈”存储
调用返回地址
实参
局部变量
递归调用时，函数调用栈可称为“递归工作栈” 每进入一次递归，就将递归调用所需信息压入栈顶 每退出一层递归，就从栈顶弹出相应信息
3.4特殊矩阵的压缩存储
对称矩阵
特点：对方阵中的任意一个元素，有a（i，j）=a（i，j）
压缩：只存储主对角线+下三角区（或主对角线+上三角区）
三角矩阵
特点：上三角区全为常量（下三角矩阵）；或下三角区全为常量（上三角矩阵）
压缩：按行优先/列优先规则依次存储非常量区域，并在最后一个位置存放常量c
三对角矩阵（带状矩阵）
特点：当|i-j|>1时，有a（i，j）=0（1≤i，j≤n）
压缩：按行优先/列优先规则依次存储带状区域
稀疏矩阵
非零元素个数小于零元素个数
压缩：只存储非零元素
顺序存储：顺序存储三元组<行，列，值>
链式存储：十字链表法
4.1.1串的定义和基本操作
串
定义
串，即字符串（String）是由零个或多个字符组成的有限序列
术语：串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置
串vs线性表
串的数据对象限定为字符集
串的基本操作大多以“子串”为操作对象
基本操作
index（S，T），定位操作，找到串T在主串S中的位置
StrCompare（S，T）：比较操作。若S>T，则返回值>0；若S=T，则返回值=0； 若S<T，则返回值<0；
其他…
字符集编码
每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小
4.1.2串的存储结构
顺序存储
静态数组
动态数组
malloc free
链式存储
可让每个结点存多个字符，没有字符的位置用"#"或'/0' 补足
王道教材采用 —静态数组
基本操作的实现
求子串：bool SubString（SString&Sub，SString S，int pos，int len）
串的比较：int StringCompare（SString S，SString T）
求串在主串中的位置：int index（SString S，SString T）
4.2.1朴素模式匹配算法
算法思想
主串长度n，模式串长度m
将主串中所有长度为m的子串与模式串对比
找到第一个与模式串匹配的子串，并返回子串起始位置
若所有子串都不匹配，则返回为零
最坏时间复杂度=O（nm）
4.2.2KMP算法
5.1.1和5.1.2树的定义和基本术语
基本概念
结点，边，根节点，叶子节点，分支结点，子树
基本术语
节点之间的关系
父节点（双亲节点）、孩子结点
祖先结点，子孙结点
兄弟结点，堂兄弟结点
结点之间的路径—只能从上往下
路径长度—路径上经过多少条边
结点，树的属性
结点的层次（深度），结点的高度
树的深度（高度）
结点的度
结点的分支数
树的度
树中各结点的度的最大值
有序树vs无序树
逻辑上看，各子树是否有序，位置是否可互换
森林
由M个（M>0）个互不相交的树组成森林
5.1.3树的性质
考点一
结点数=总度数+1
考点二
度为m的树
至少有一个结点度=m
一定是非空树
m叉树
允许所有结点的度都<m
可以是空树
考点三
度为m的树第i层至多有几个结点？
考点四
高度为h的m二叉树至多有几个结点？
考点五
高度为h的m叉树至少有多少个结点
高度为h，度为m的树至少有多少个结点？
考点六
具有n个结点的m叉树的最小高度为？
5.2.1.1二叉树的定义和基本术语
二叉树
基本概念
可为空二叉树
任意结点的度≤2
是有序树，左子树、右子树不可颠倒
思考：二叉树vs度为2的有序树
特殊二叉树
满二叉树
高度为h，含有2×h-1个结点的二叉树
完全二叉树
在满二叉树的基础上可去掉若干个编号更大的结点
二叉排序树
左子树关键字＜根节点关键字＜右子树关键字
平衡二叉树
左右子树深度差不超过1
5.2.1.2二叉树的性质
5.2.2二叉树的存储结构
5.3.1.1二叉树的先中后序遍历
二叉树的遍历
三种方法
先序遍历
根，左右
中序遍历
左，右，根
后序遍历
左，右，根
遍历算法表达树
先序遍历得前缀表达式
中序遍历得中缀表达式（没有括号）
后序遍历得后缀表达式
考点：求遍历序列
分支结点逐层展开法
从你的全世界路过法
先序—第一次访问时路过
中序—第二次访问时路过
后序—第三次访问时路过
5.3.1.2二叉树的层次遍历
树的层次遍历思想
①初始化一个辅助队列
②根节点入队
③若队列非空，则队头结点入队，访问该节点，并将其左右孩子插入队列
④重复③直至队列为空
5.3.1.3由遍历序列构造二叉树
前序+中序遍历序列
后序+中序遍历序列
层序+中序遍历序列
一定要有中序序列
5.3.2.1线索二叉树的概念
线索二叉树
作用：方便从一个指定结点出发，找到其前驱、后继；方便遍历
存储结构
在普通二叉树结点的基础上，增加两个标志位itag和rtag
itag==1时，表示ichild指向前驱；itag==0时，表示ichild指向左孩子
rtag==1时，表示rchild指向后继；rtag==0时，表示ichild指向右孩子
三种线索二叉树
中序线索二叉树
以中序遍历序列为依据进行“线索化”
先序线索二叉树
以先序遍历序列为依据进行“线索化”
后序线索二叉树
以后序遍历序列为依据进行“线索化”
几个概念
线索
指向前驱/后继的指针称为线索
中序前驱/中序后继；先序前驱/先序后继；后续前驱/后续后继
手刷画出线索二叉树
①确定线索二叉树类型—中序、先序、or后序？
②按照对应遍历规则，确定各个结点的访问顺序，并写上编号
③将n+1个空链域连上前驱、后继
5.3.2.2二叉树的线索化
中序线索化
得到中序线索二叉树
先序线索化
得到先序线索二叉树
后续线索化
得到后序线索二叉树
核心
中序/先序/后序遍历算法的改造，当访问一个结点时，连接该结点 与前驱结点的线索信息
用一个指针pre记录当前访问结点的前驱结点
易错点
最后一个结点的rchild、rtag的处理
先序线索化中，注意处理转圈问题，当itag==0时，才能对左子树先序线索化
5.3.2.3在线索二叉树中找前驱后继
若itag/rtag==0
自己可以推出来
5.4.1树的存储结构
树、森林的存储结构
双亲表示法
顺序存储结点数据，结点中保存父节点在数组中的下标
优点：找父节点方便；缺点；找孩子不方便
孩子表示法
顺序存储结点数据，结点中保存孩子链表头指针（顺序+链式存储）
优点：找孩子方便；缺点：找父节点不方便
孩子兄弟表示法
用二叉链表存储结点—左孩子右兄弟
用于存储森林时，将森林中每棵树的根节点视为平级的兄弟关系
从存储视角来看形态上和二叉树类似
5.4.2树、森林与二叉树的转换
key
本质：用孩子兄弟表示法存储树或森林，在形态上与二叉树类似
用孩子兄弟表示法存储森林时，将森林每棵树的根节点视为平级的兄弟关系
树、森林转二叉树
按“层序”依次处理每个结点
处理一个节点的方法是：如果当前处理的结点有孩子，就把所有孩子 结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点 的左指针下方
二叉树转树、森林
按“层序”恢复每个结点的孩子
如何恢复一个结点的孩子：在二叉树中，如果当前处理的结点有左孩子 ，就把左孩子和“一整串右指针糖葫芦”拆下来，按顺序挂在当前结点的下方
5.4.3树和森林的遍历
树
先根遍历
后根遍历
森林
先序遍历
中序遍历
二叉树
先序遍历
中序遍历
第六章图
6.1图的基本概念
6.1.1图的基本概念
定义：G=（V，E），顶点集V，边集E
无向图（无向边/边）、有向图（有向边/弧）
顶点的度、出度、入度（无向图？有向图？）
边的权、带权图/网
点到点的关系
路径、回路、简单路径、简单回路
路径长度
点到点的距离（最短路径）
无向图顶点的连通性、联通图
有向图顶点的连通性、连通图
图的局部
子图
连通分量—极大连通子图
强连通分量—极大强连通子图
连通无向图的生成树—包含全部顶点的极小连通子图
非连通无向图的生成森林—各连通分量的生成树
几种特殊形态的图
完全图
稠密图、稀疏图
树、森林、有向树
常见考点
对于n个顶点的无向图G
所有顶点的度之和=2｜E｜
若G是连通图，则至少有n-1条边（树），若 ｜E｜>n-1，则一定有回路
若G是非连通图，则最多可能有条边
无向完全图共有条边
对于n个顶点的有向图G
所有顶点的度之和=2｜E｜
若G是连通图，则至少有n条边（树），形成回路
所有顶点的出度之和=入度之和=｜E｜
有向完全图共有条边
6.2图的存储及基本操作
邻接矩阵
数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
邻接表
十字链表
存储有向图
邻接多重表
存储无向图
6.3图的遍历
6.3.1图的广度优先遍历（BFS）
类似于树的层序遍历（广度优先遍历）
算法要点
需要一个辅助队列
如何从一个结点找到与之邻接的其他顶点
visited数组防止重复访问
如何处理非连通图
复杂度
空间复杂度：O（｜V｜）—辅助队列
时间复杂度
访问结点的时间➕访问所有边的时间
邻接矩阵：O（｜V｜^2）
邻接表：（｜V｜+｜E｜）
广度优先生成树
由广度优先遍历确定的树
邻接表存储的图表示方式不唯一，遍历序列，生成树也不唯一
遍历非联通图可得广度优先生成森林
图的深度优先遍历（DFS）
算法要点
递归地深入探索未被访问过的邻接点（类似于树的先根遍历的实现）
如何从一个节点找到与之邻接的其他顶点
visited数组防止重复访问
如何处理非连通图
复杂度分析
空间复杂度：O｜V｜—来自递归工作栈
时间复杂度
访问结点的时间➕访问所有边的时间
邻接矩阵：O（｜V｜^2）
邻接表：O（｜V｜+｜E｜）
深度优先生成树
由深度优先遍历确定的树
邻接表存储的图表示方式不唯一，深度优先遍历序列，生成数也不唯一
深度优先遍历非连通图可得深度优先生成森林
图的遍历和图的连通性
无向图
DFS/BFS函数调用次数=连通分量数
有向图
若从起始顶点到其他顶点都有路径，则只需调用一次DFS/BFS函数
对于强连通图，从任一顶点出发都只需调用一次DFS/BFS函数
6.4图的应用
6.4.1最小生成树
Prim算法（普里姆）
从某一个顶点开始构建生成树； 每一次都将代价最小的新顶点纳入生成树 直到所有顶点都纳入为止
Kruskal算法（克鲁斯卡尔）
每次选择一条权值最小的边，使这条边的 两头连通（原本已经连通的就不选） 直到所有结点都连通
6.4.2最短路径问题
单源最短路径
BFS算法（无权图）
Dijkstra算法（带权图，无权图）
不适用于有负权值的带权图
各顶点间的最短路径
Floyd算法（带权图、无权图）
不能解决带有“负权回路”的图，这种图可能没有最短路径