导图社区 数据结构
- 41
- 1
- 0
- 举报
数据结构
以王道考研数据结构为基础总结的思维导图 基础阶段复习和强化框架，，全面且系统地涵盖了串、树与二叉树、线性表、栈和队列数组等多个关键数据结构内容。
编辑于2025-08-19 14:10:41- 相似推荐
- 大纲
数据结构
应试技巧
选择题11个，22分
大题23分
应用题(代码比较困难)
八大考点
线性表
数组
2011
栈
队列
2019
树与二叉树
哈夫曼树和哈夫曼编码
并查集
其他
2016
图的基本应用
最小代价生成树
20172018
最短路径
2009 2014 2018
拓扑排序
关键路径
2011
其他
2011 2014 2015 2018
查找算法的分析以及应用
2010 2013 2024 算列表和顺序/折半查找
排序算法的分析以及应用
2012 2023
七大考法
画图
6/16
代码
2/16
文字简答
高
手算分析
数据结构 算法的选择
算法性质分析
文字描述算法过程
数据结构性质推演
算法题(代码比较简单)
线性表
快排
顺序表
如何备考
手写一份快排代码复习
多做题
二路归并排序
两个有序变一个有序
更擅长对有序表，无序不如快排
链表
基本功
tips
树与二叉树
基础
前中后序遍历（递归
层序遍历
可能出题角度
树的属性
特殊树形判断
处理二叉树常用的代码思路
递归遍历时，参数传递
递归遍历时，参数返回值
全局变量，共享信息
顺序存储的二叉树如何处理
图
数据结构定义
图的顺序遍历
基于邻接矩阵
基于邻接表
算法题难度不高
绪论
数据结构
逻辑结构
线性
非线性
存储结构
数据的运算
五个特征
有穷
确定
可行
输入
输出
效率度量
时间复杂度
空间复杂度
线性表
线性表基本概念
线性表是有相同数据类型的n个数据元素的有限序列，一个前驱一个后继
线性表是逻辑结构，顺序表和链表是存储结构
线性表的实现和应用
顺序存储（顺序表）
（数组下标从0开始，线性表下标从1开始）由于位置可以计算，所以是随机存取
定义
静态分配
动态分配
L.data = (int*)malloc(sizeof(int)* InitSize)
基本操作
初始化
静态初始化
动态初始化
插入
在第i(1<=i<=L.lenth+1)个位置插入。
if i的范围有效
if 空间未满
for后移操作（从最后开始往前一个个赋值直到第i个被挪走）
赋值
L.lenth++
删除
在第i(1<=i<=L.lenth)个位置删除
if i的范围有效
赋值
for前移
L.lenth--
按值查找
int i ; for i<lenth;i++(如果相等，return i+1）
优缺点
随机访问，存储密度高
插入删除不方便，存储需要连续空间不方便
链式存储(链表)
定义
typedef struct LNode{ - ElemType data; - struct LNode *next; }LNode, *LinkList;
L
DATA|NEXT
DATA|NEXT
DATA|^
头结点
第一个位置操作无需特殊处理，空表和非空表处理统一
操作
指针p为指向结点的指针，*p是结点本身，p->data或(*p).data 访问数据域
初始化
求表长
维护变量lenth，指针p指向L，while循环:p->next!=Null,p=p->next,Lenth++
按序号查找结点
while(p!=NULL&&j<i){指向next，j++)
按值查找结点
while(p->data!=e){...}
插入结点
后插
新节点指向第i个结点，第i-1个结点指向新结点，需要指针辅助。
前插
可转换为后插
找到前驱
后插后交换DATA
建立单链表
头插法
尾插法
增加尾指针r，r->next =s
删除结点
前驱指向后驱，free(q)
拓展：可以把后继的值赋予自身，然后删除后继，可以不用从头遍历。
原地反转（在本链表内
两个辅助指针
1234
134 2指向1
头结点指2，2134
辅助指针挪到3，1头上指针不动，可以用1指针->Next,来找下一个结点
算法基本功
按位序查找
按关键字查找＋删除某个结点
按关键字查找＋插入某个结点
前后指针
头插法（原地逆置
尾插法（保持原序
其他链表
双链表
有两个指针，prior next ，指向前驱和后继
插入删除复杂度为O(1)
插入：s结点指向i结点，i结点回指s结点。s结点指向i-1结点，i-1结点指向s结点。（有辅助指针p指向i-1结点）（不唯一）
删除：类似单链表
循环链表
循环单链表
最后一个结点指针指向头结点，同时添加尾指针r
表头表尾插入都是O(1)复杂度
任意节点遍历整个链表
循环单链表的头指针不如尾指针好用，尾指针可以循环到头结点，头指针只能遍历寻找尾结点
循环双链表
最后一个结点指向前驱和头结点，头结点指向最后一个结点和后继
注：空的循环链表，L->next->next......就算指n个也可以是空的
静态链表
数组来表示链表，需要分配连续的内存空间
=-1是结束的标志
存储密度低于1
栈 队列 数组
栈和队列
基本概念
栈
栈：只允许在一段进行插入删除
出栈排列个数：卡特兰数 1/(n+1)*C(n,2n)
队列
队列：只允许一端插入另一端删除
顺序存储结构
栈
定义
typedef struct{ - Elemtype data[n]; - int top;}Sqstack;
S.top可以初始化为-1或者0，两种方式操作有所不同
若指向栈顶元素则 S.data[ ++S.top]=x
若指向栈顶元素的下一位则 S.data[S.top++]=x
基本操作
初始化
判空
出入栈
读栈顶元素
共享栈
队列
定义
typedef struct{ - Elemtype data[n] - int front,rear;}SqQuene
初始时两个变量=0；
循环队列
循环队列实现
臆想为一个环，物理上不变，逻辑上视为一个环，解决假上溢问题
初始为0，队首指针进一:Q.front=(Q.front+1)%MAXSIZE,尾指针同理
队列长度=（尾指针＋MAXSIZE-首指针）%MAXSIZE
判空判满
牺牲一个格子
队满(rear+1)%MAXSIZE==front
队空 rear==front
维护一个SIZE
入队+1，出队-1
Q.size==0/Q.size==MAXSIZE
维护一个tag
出队=0，入队=1
若rear==front ,
tag=0,队伍空
tag=1,队伍满
基本操作
初始化
判队空
入队
出队
DeQueue(Q,p)队头出队，且用p接收出队元素的data
链式存储结构
栈
通常用单链表实现链栈，在单链表的表头进行操作
队列
队头在头结点方便删除，队尾结点有指针rear来插入，逆着箭头来比较反人类
双端队列
输入受限，输出受限，不受限
循环队列（循环链表实现）
数组
数组A[10]代表下标为0到9，数组A[0.1.2......10]代表下标为0到10
概念
数组是线性表的推广，一旦被定义，维数和维界不会再改变
多维数组的存储
行优先存储和列优先存储
存储关系式
特殊矩阵的压缩存储（注意下标
对称矩阵
只存上三角或下三角（包含主对角线）
计算方式：画图，根据首项加末项括起来×项数再除2算出前面所有行或者列，再加上本行或列
下三角矩阵
同理推导，常数项存在最后一位，所以与对称矩阵相比需要空间加1
上三角矩阵
n+(n-1)+(n-2)+.....(n-i+2)+(j-i+1)-1=(i-1)(2n-i+2)/2+(j-i)
(j-i+1)是列数减行数，可以理解为要求的那个元素Ai,j中的列数j是本行前面的所有元素个数包括自己，减去i就是减去本行对角线元素的列数（列数等于行数）再加1，这个1是对角线元素，这样就算出了本行存储了多少元素。
j-i是偏移量
按列存储的时候可以把ij互换
注意下标！！！！
三对角矩阵
只有主对角线和上面下面一层，第一行和最后一行只有两个元素
下标k=2i+j-3
稀疏矩阵
三元组（行标列表值）存储
数组存储
十字链表存储
栈队列数组的应用
栈
括号匹配
表达式求值
中缀转后缀
遇到操作数，直接加入后缀表达式
遇到界限符 左括号入栈，右括号弹出栈中的运算符直到遇到左括号
遇到运算符 优先级高于栈顶运算符或者遇到左括号，直接入栈，优先级低于或者等于栈顶运算符则弹出栈中的运算符并且加入后缀表达式，直到遇见一个优先级低于他的运算符或者遇到左括号，之后 将当前运算符入栈
后缀表达式求值
递归中的应用
队列
层次遍历
1根节点入队
2若队空，结束，否则重复3
3，第一个结点出队 左孩子入队，右孩子入队，返回2
计算机系统中的应用
缓冲区=队列
排序
排序基本概念
稳定性
内部外部
插入排序
直接插入排序
从前往后顺序查找Keyi的位置，找到后，把相应位置的后半部分有序序列向后移动，插入
稳定
o(n^2)
顺序和链式存储
链式无序移动元素
折半插入排序
类似于直接插入，但是查找的时候折半查找（前半部分有序）
稳定
o（n^2）
顺序存储
希尔排序
将待排序记录分为i，i+d,i+2d,.....对各个子表进行直接插入排序，当整个表基本有序时，再对全体记录进行一次直接插入排序。
一般增量d每次缩小一半
第一趟一般n/2
不稳定
最好的情况o(n^1.3),最坏o(n^2)
顺序存储
交换排序
冒泡排序
一趟确定一个最大的值或最小的值，下一趟少比较一个值
不稳定
o(n^2)
顺序和链式
快速排序
任取一个基准，一般为首元素，通过一趟排序确定最终位置，左边都小于他右边都大于他，然后再对两边进行同样的快排，
基准元素拿出来，两个指针必定有一个指向空格子，基准元素与非空格子比较，若小于，则放在low空格子里，若大于，则放在high空格子里，若不空则不用动，指向下一个要比较元素
总是在移动非空指针，当low指针和high指针相等，则已经确定基准元素的位置
low和high指向两边的元素，若只剩一个元素，则直接结束
不稳定
复杂度
空间复杂度是调用的递归层数，最好logn,最差n，平均是logn
画的二叉树的层数就是递归调用层数
时间复杂度为O(n*logn)
最坏o（n^2),若原先序列基本有序，是最坏情况
快排的一趟排序在408里要确定多个位置
顺序存储
选择排序
简单选择排序
在无序序列选出最小的元素插入到有序序列的最后一个位置
不吃压力
最好最坏情况都差不多
O(n^2)
不稳定
顺序和链式
堆排序
概念
大根堆
根>左右子树关键值
小根堆
相当于二叉树的顺序存储，逻辑上是个完全二叉树
建立大根堆
从lenth/2开始处理
如果小于孩子，则与最大的孩子交换，
交换后要看孩子结点是否满足大根堆，若不满足，小的关键值继续下坠
下坠一次要对比两次！！！！
基于大根堆进行排序
堆顶元素与加入有序子序列（树的末尾）（与待排序元素末尾进行交换）
swap(A[i],A[1])
将剩下的待排序元素再次调整为大根堆
void headAdjust(A[] ,k,lenth)
复杂度
调整时间与树高有关
关键字的总对比次数不超过4n
建立堆的时间复杂度为O(n)
每一趟排序复杂度不超过O(h)=O(logn)
时间复杂度为
n-1趟，每趟logn
O(n*logn)
不稳定
堆的插入和删除
插入
放到表尾，与父节点对比，若不满足堆，交换
删除
直接删除，用堆底元素代替，然后不断下坠
顺序存储
归并排序
概念
将有序表合成为一个新的有序表
初始把每个元素看为一个有序表，然后n个有序表合成一个有序表为n路合并，在此有序表的基础上，再将n个有序表合成一个有序表
一般n为2，为二路归并
merge（）
先复制到数组B中
A[low....mid]
A[mid+1,...high]
把两个有序数组表头元素进行比较，小的放入A[]中，
low,mid,high
当有一方的下标超出其对应的表长的时候将另一段剩余位置直接复制到A中
复杂度
空间为o(n)
每趟为n，一共logn趟
时间复杂度为O(n*logn）
顺序
基数排序
算盘
适合取值范围小，但是元素个数n多，且关键字方便拆成d组
排序
按照个位进行分配，每个数都到相应的位置，再依次收集（递增或者递减收集顺序不同），此时个位已经排序结束，再按照十位进行分配，再收集....
分配是从前往后分配，收集可以从小到大也可以从大到小，但是一次排序过程中，顺序不表
复杂度
需要的辅助存储空间为r（r个队列，r个队头队尾指针，反复使用）
O（r）
一趟分配为o(n)，一趟收集合并r个队列为o(r)，总共要d趟（d是是位数）
O(d(r+n))
o(r）是因为链式存储可以直接把链子拆下来
稳定
链式和顺序存储
计数排序
原理：统计小于元素x的个数，有n个小于x，x就在第n+1位
step1
创建一个数组B，统计每个元素的出现次数，数组下标对应元素值
step2
在B的基础上创建一个数组C，C[i]的数值是前i+1项和。C[i]表示≤i的元素累计出现了几个
C[i]=C[i-1]+C[i]
step3
实现排序，创建数组D[]，对于要排序的数组A[],从后往前遍历，对C[A[i]]-1，就是该元素在D[]中的位置，每次先减1，确定位置后插入D[],遍历完毕后，排序完毕。
复杂度
空间
O(n+k)
时间
O(n+k)
很快
但是要看k的数量级
（取值范围）
外部排序
文件过大无法读入内存
外部归并排序
内存中输入缓冲区和输出缓冲区来进行归并排序
若要进行k路归并，则需要k个输入缓冲区和1个输出缓冲区
步骤
step1 生成初始归并段（读写各n次，还要内部排序）（对k个记录进行内部排序，组成一个有序段）
step2 第一趟归并（读写各n次，还要内部排序）
step3........
....
当输出缓冲区满，输出到外存，输入缓冲区空，选取下一段
一共进行S趟，S=向上取整logkr
时间开销
开销=读写外存+内部排序+内部归并
读写占大头
优化
k变大
代价1
增加输入缓冲区
代价2
需要k-1次对比，对比次数增加
再优化
败者树
r变小
r依赖于内存工作区大小
再优化
置换选择排序
败者树
可视为完全二叉树，k个叶结点是当前参加比较的元素，非叶结点用来记忆左右子树中的败者，胜者向上继续比较，不同的是，根节点也经过了一次比较，选出了一个胜者在根之上
失败者留在结点，胜者进入下一回合比拼
所以败者树可以减少对比次数，只需要对比完全二叉树的高度-1次，也就是向上取整log2k次
置换选择排序
用一个小工作区产生远远大于自己的归并段
方法
读满内存工作区，输出一个最小的，并且用miniMAX记录已经输出的最小的元素值
此时有一个空缺，读入待排序文件，再次找到一个最小的，
如果最小的比miniMAX还小，那就留着不动，找另一个最小的，大于miniMAX，输出
直到内存工作区全部都比miniMAX小，此时完成了归并段1的输出，开始输出下一个归并段，把内存工作区的元素按顺序输出，维护miniMAX
直到待排序文件全部生成归并段
归并段不等长
最佳归并树
由于归并段不等长，所以归并的先后顺序会导致读写总次数不一致
为了读写磁盘次数更少，引出最佳归并树的概念
归并树的带权路径长度WPL=读磁盘的次数=写磁盘的次数
io次数=归并树的WPL*2
哈夫曼树来优化归并树
优先归并小的归并段
多路归并的最佳归并树
若归并段不够形成严格的k叉树
补充长度为0的虚段，作为最小的归并段，加入哈夫曼树
判断需不需要补充
（初始归并段-1）/（k-1）=0
不需要
若不等于0，需要
排序算法分析以及应用
查找
查找的概念
平均查找长度
ASL=(求和)PiCi
P是查找一个元素的概率1/n,Ci是找到第i个元素需要的比较次数
顺序查找
一般线性表的顺序查找
遍历
哨兵的概念
ST.elem[0]=key;在之后的边界条件可以使用哨兵if(ST.elem[i]!=key;)
有序线性表的查找
遍历
当条件不满足可以直接跳出
查找失败的平均查找长度=1+2+3+...+n+n)/n+1(可以用二叉树来理解，失败结点的层数是查找次数，除以失败结点的个数）
折半查找（顺序索引查找）
仅适用于有序的顺序表
思想
key与中间位置元素进行比较，相等成功
若不相等，key小于中间元素，舍弃后半部分，若大于则相反
重复1,2.
折半查找判定树
元素个数是奇数，是满二叉树，如果不是奇数，最后一层不满
以此可以判断折半查找的最多次数，是完全二叉树的树高，log2(n+1)向上取整
ASL=log2(n+1)-1
分块查找（二分查找）
块内无序，块间有序
索引表含有该块的最大关键字和该块第一个元素的地址
索引表可以顺序查找或者折半查找，块内顺序查找
ASL=L1+L2=(s^2+2s+n)/2s，n=sb,当s取n1/2时，平均查找长度最小为n1/2+1
注意！high=mid-1和low=mid+1;导致每次指针其实多挪了一格，而且low和high不会提前检查
树形查找
二叉搜索树（二叉排序树，二叉查找树)
概念
是动态数表
二叉排序树目的不是排序，而是提高查找删除和插入速度
左<中<右
查找算法
根相等则成功，小于根向左查找，大于根向右查找
是个递归过程
非递归算法
Bst_Search(Bitree T, Key)
while(T!=Null&Key!=T->data)
if
else
跳出while循环，return T；
二叉排序树的插入
动态数表，非一次生成，查找过程中没有找到，则插入
小的往左，大的往右
递归插入
BST_Insert(T,key)
if(T==NULL),执行插入相关操作
else if (k==T->data)存在相关结点，不插入
else if(k<T->data)小于此结点 return BST_Insert(T->lchild,k),调用递归
else 大于此结点 return BST_Insert(T->Rchild,k),调用递归
二叉排序树的删除
叶子直接删
一个孩子直接删，孩子顶上来
两个孩子，用前驱或后继顶上来，删除前驱或者后继，此时删除前驱后继就是第一二种情况
查找算法效率分析
取决于树的高度，有时候会过于偏激，只有右子树
优化：平衡二叉树，树高是logn级别
顺序表的二分查找若有删除插入等操作，维护复杂度为n，二叉排序树维护复杂度低，为logn级别
平衡二叉树（AVL）树
是有序的
定义
左右子树之高度差绝对值不超过1
高度之差为平衡因子，取值-1.0.1
平衡二叉树的插入
LL旋转
RR旋转
LR旋转
RL旋转
对于不平衡因子为2的结点的孩子的孩子，把一侧孩子给父结点，自己成为父节点祖先，再把另一个孩子给此时的父节点，自己再成为父节点祖先。
平衡二叉树删除
类似于排序二叉树
但是删除会导致不平衡，同样按照上面的方式进行旋转
但是如果旋转后导致高度-1，那么往上继续追溯，可能导致上层又不平衡，直到根节点，最后树高-1
查找效率
logn
怎么长得最高？
递推公式
n0=0
n1=1
n2=2
nh=1+(nh-1)+(nh-2)
红黑树
真考就给了兄弟
B树，B+树
B树基本操作
概念
m阶B树就是所有平衡因子均等于零的m路平衡查找树
m阶b树最多又m棵子树，m-1个关键字
若不是叶结点，最少有两棵子树，一个关键字
除了根节点的所有非叶结点，最少有m/2向上取整棵子树，至少有一个关键字
结点前给一格 存储有多少个关键字
高度
最小高度
最大高度
插入
当关键字超出上限，从中间位置分裂，左半边留下，右半边新结点，中间（向上取整m/2）结点插入原结点的父节点
删除
兄弟够借
直接前驱和后继来代替
兄弟不够借
拉下来父节点的关键值，和兄弟合并
B+树基本概念
类似于b树，叶节点用来指向记录，包含所有关键字，并且关键字按大小排列，便于数据库的存储使用
分支结点中包含他的各个子结点的最大关键字和指向该结点的指针
n个关键字有n个子树
叶结点会有链式指针串起来
关键字数量范围是b树＋1
408中将叶结点定义为终端结点
散列表（hash）
概念
根据关键字直接访问地址，有直接映射关系
性质
定义域包含全部关键字
值域取决于散列表的大小
直接定址法
H(key)=key或者H(Key)=a*key+b
适用于关键字分布基本连续
除留余数法
取一个不大于m但是接近m的质数，除以这个质数，取余数，就是address
数字分析法
选取数码分布较为均匀的若干位作为散列地址，例如手机号码后四位
平方取中法
关键字的每位取值都不够均匀，平方后取中间几位数
散列表处理冲突
拉链法
散列表的地址标识着链表，
把关键值用链表连起来，冲突就加到链表的末尾。
查找的时候算出散列值，顺着当前的链表查找。
开放定址法
发生冲突的时候探测地址Hi=(H(key)+di)%m
d的取值
线性探测法
d=1,2,3,4....
平方探测法
1^2,-1^2,2^2,-2^
双散列法
di=第二个散列函数，di=i*hash2(key)
伪随机序列法
人为设置一个伪随机序列
探测到空为查找失败
删除时，产生的空位会导致错误的查找失败，解决方法：逻辑删除
带来的问题，查找效率低
查找及性能分析的应用
查找成功asl
查找次数和/存在元素个数
查找失败asl
查找失败次数和/散列表取值个数（不是整个散列表的长度！而是可能落在的所有地址）
查找失败
从每个可能存在key的地址开始查找，直到查找到空白，删除标记不算失败。
装填因子
表中记录/散列表长度
聚集堆积现象
线性探测法容易堆积
平方探测法可以缓解堆积
查找算法的分析以及应用
图
图的基本概念
有向图无向图，简单图多重图，顶点的度，
路径，路径长度，回路，距离，子图，生成子图
连通，连通图，连通分量（极大）！
极大连通子图称为连通分量（无向图），极大是包含尽可能多的顶点和边，极小连通子图要求包含尽可能少的边。
若是非连通图，边最多的情况：n-1个顶点构成一个完全图，此时再加入一个顶点，变成非连通图
强连通，强连通分量
有向图
n个顶点n条边组成边最少的强连通图
生成树，生成森林
连通图生成树，包含全部顶点极小连通子图，非连通图生成森林，连通分量生成树构成非连通图的生成森林
完全图
任意两个顶点之间都存在边，无向图中(n*(n-1)/2)个边，有向图中乘2
图的存储及基本操作
邻接矩阵法
定义
typedef struct { - VertexType vex[MaxVnum] - EdgeType edge[MaxVnum][MaxVnum] - int Vnum,Arcnum; }MGragh;
行列的含义
邻接表法
顶点域和边表头指针采用顺序存储，称为顶点表（竖着顺序存储）边表存储邻接点和指针域，称为边表，（横着链式存储）类似于孩子表示法。
定义用三个结构定义
一个是边表
typedef struct ArcNode{ - int adjvex; - struct ArcNode *nextarc; - （info）； }Arcnode
一个是顶点表
typedef struct VNode{ int data; ArcNode *firstarc; }VNode,AdjList[MaxVnum]
一个是总的邻接表
typedef struct{ AdjList vertices; int vexnum,arcnum; }ALGraph;
十字链表
有向图
弧结点
五个域，有：弧尾顶点编号，弧头顶点编号，权值，弧头相同的下一条弧，弧尾相同的下一条弧
顶点结点
三个域，数据域，该顶点作为弧头的第一条弧，该顶点作为弧尾的第一条弧
横向来看，就是所有指出去的弧，从顶点结点中间域竖着指出去的是所有指进来的弧
横着能找到所有出边，竖着能找到所有入边
邻接多重表
无向图
边结点
五个域，边的两个顶点，权值，依附于顶点i的下一条边，依附于j的下一条边
顶点结点
数据域和指针指向与该顶点相连的第一条边
图的遍历
广度优先搜索bfs
类似于层序遍历
初始化bool数组visited[MaxVnum]
初始化visited[]为false
初始化辅助队列q
for循环遍历所有顶点（目的是遍历每个分量）
如果visited[i]=false,bfs[i]
bfs
以邻接矩阵为基础
visit(i)
visited[i]=true
入队
while循环如果队不空
队头出队，并且for循环检测队头顶点的所有邻接点，没访问过且有路径，visit(w),visited[w]=ture,入队
以邻接表为基础
visit(i)
visited[i]=ture
入队
while循环如果队不空
队头出队，for循环检测所有邻接顶点，for循环： （p=G.vertices[v].firstace; p ; p=p->nextarc) if(没有访问过）{访问并且入队}}
空间复杂度 o(v)
时间复杂度
邻接表
O(v+e)
邻接矩阵
O(V^2)
由bfs算法求单源最短路径（非带权图）
初始化d[u]=无穷，d[a]=0；bfs遍历时，d[i]=d[a]+1
深度优先搜索dfs
类似于先序遍历（递归
初始化visited[]=false
for循环遍历所有顶点（分量
若没有访问过则
dfs[G，i]
邻接矩阵下的深搜
visit(i)
visited[i]=ture
for循环遍历所有点{
如果没访问过而且有路径
dfs[j]
}
邻接表下的深搜
visit(i)
visited[i]=ture
for循环遍历此顶点邻接表后面所链的所有边表(p=G.Vertices[i].firstarc;p；p=下一个）{j=p->adjvex; if(没访问过j）{dfs[j]} }
空间复杂度O（V）
时间复杂度
邻接表
O(v+e)
邻接矩阵
O(V^2)
基于邻接表的遍历序列可能不相同，边表输入顺序可能不一样，邻接矩阵的序列相同。、
调用Bfs或者Dfs的次数代表有几个连通分量
图的基本应用
最小生成树
性质
权值之和最小的生成树
有权值相等的边时最小生成树不唯一
权值不相等最小生成树唯一
若无向连通图的边数比顶点数少一个，它本身就是最小生成树
基于贪心算法的思想
prim
初始化最小生成树，从某个顶点开始，循环下面操作
选择权值最小的且顶点不在最小生成树里的边，加入最小生成树
生成树顶点==图顶点,停止
kruskal
每个顶点一开始自成连通分量，用并查集实现判断两个顶点是否属于同一个树
选择权值最小的边加入树，用并查集判断是否构成回路，循环
直到有n-1个边 停止
初始化sumS=连通分量数
while(sumS>1){.......；sumS--}
最短路径
Dijkstra求单源最短路径
一个集合，三个辅助数组
集合S记录已经完成的顶点，初始时放入V0
final[]
表示已经找到最短路径
dist[]
记录从源点V0到其他顶点当前的最短路径长度，初始值：若有弧，则是弧的权值，没有弧，为无穷
path[]
从源点到顶点i之间的最短路径的前驱结点
步骤
初始化dist[]=arcs[0][i]
从V-S中选出顶点j，满足距离dist[j]=min边且vj属于V-S，归入S，final[j]=ture;
修改最短路径，dist[j]+arcs[j][k]<dist[k],则更改dist[k]为dist[j]+arcs[j][k];
重复上面两步共n-1次，直到全部并入
时间复杂度
邻接矩阵和邻接表都是O(v^2)，修改dist和选择最小dist。
无法寻找带有负权值的图的最短路径
floyd算法求各个顶点之间的最短路径
两个矩阵
A(n)
path(n)
A初始值为邻接矩阵原矩阵，path初始值为-1
思想
若允许从vn中转，最短路径是多少，更新A(n)path(n)
若A[i][j]>A[i][k]+A[k][j],则赋值下一个A的[i][j]为此和，且path记录k
n轮递推
时间复杂度
o(v^3)
空间复杂度
o(v^2)
允许有负权值，但是回路总权值是负不允许
有向无环图描述表达式(dag)
拓扑排序(aov)(边无权值 只代表因果前后）
算法
初始化栈
统计所有入度为0顶点，同时入栈
维护一个int计数，记录输出顶点
while(栈不空）则
输出栈顶，将栈顶指向的顶点的入度-1，如果减为0，入栈；
if计数不够，说明有回路，否则成功
时间复杂度
邻接矩阵v^2
邻接表v+e
关键路径（AOE）（边有权值）
性质
进入某个顶点的所有有向边活动都已经结束后，该定点所代表的时间才能发生。
顶点的事件发生后，该顶点出发的活动才能开始
顶点表示事件，有向边表示活动，边上的权值表示时间开销
一个开始顶点 一个结束顶点
关键路径
事件的
最早发生时间
源点到此点的最长路径长度
最迟发生时间
知道了结束时间最早发生时间，从后往前推
活动的
最早发生时间
与起点事件最早发生时间相同
最迟发生时间
与终点事件的最迟发生事件减去本活动所需时间
树与二叉树
树的基本概念
有且仅有一个根节点，除了根的其余节点可分为m个互不相交的有限集，每个集合本身又是一棵树，称为根的子树
度
节点的度是盒子个数，树中最大的度数称为树的度
有序树
若各子树从左到右有次序无法交换，称为有序树否则是无序树
性质
结点数与度数的关系
给出结点数加一为度数，仔细读题找条件，错两次
度为m的树第n层最多有（）个结点
高度为h的m叉树最多有（）个结点
度为m，具有n个结点的树的最小高度为（h=（向上取整）logm(n(m-1)+1））
度为m，具有n个结点的树的最大高度为（）
二叉树
定义以及特殊二叉树
只有两科子树，且左右子树次序不能颠倒，左右子树的结点次序不是相对的而是绝对的、
满二叉树
高度为h有（）个结点
完全二叉树
二叉排序树
左子树的所有关键字均小于根节点的关键字，右子树均大于根节点关键字
平衡二叉树
树中任意一个节点的左右子树高度之差绝对值不超过1
正则二叉树
只有度为0或2的结点
二叉树的性质
非空二叉树的叶结点数等于度为2的结点数+1（只有度为2才能增加叶结点个数，度为1只起了传递作用）
非空二叉树的第k层最多有（）个结点
高度为h的二叉树最多有（）个结点
完全二叉树的性质
结点i所在深度为向下取整(log2i)+1或者向上取整(log2(n+1))
二叉树的存储结构
顺序存储
不常用，一般二叉树的空白结点用0填，浪费空间
链式存储
左孩子|DATA|右孩子
typedef struct Bitnode{ int data; struct Bitnode *lchild,*rchild; }Bitnode,*Bittree;
含有n个结点的二叉链表中，含有n+1个空链域（初始结点有两个空链域，一个结点占用一个后提供两个空链域，也就是一个结点能让空链域＋1）
遍历
先序遍历
若为空，则什么也不做，否则：
1）访问根节点
2）访问左子树
3）访问右子树
代码：void preoder(Bittree T){ - if(T!=null){ - visit(T); 在这里可以更换 - preoder(T->lchild); - preoder(T->Rchild); } }
中序遍历
后序遍历
层次遍历
用队列
用遍历构造二叉树
中序+前/后/层序
唯一确定一棵二叉树
中序唯一，前序或者后层序有多少种，就能构造出多少个二叉排序树，给定n个，有卡特兰数（n）个排列
前序＋后序
xy和yx，x是祖先
线索二叉树
tag标识
中序
先序和后序
选择注意事项
叶节点有两层
算法题
求树高
方法一
传入参数，在递归访问孩子的时候＋1
方法二
递归的时候返回高度，左右子树都递归完成，得到左右子树高度后选择更高的return MAX+1
求树宽
维护width[]数组，递归的时候width[level]++
求wpl
if(叶子结点）WPL+=T->weight*n,n是在递归里面传递的层数
如何判定二叉排序树
中序遍历然后判断是否递增序列
temp记录已访问过的最大节点值， if(T->data>=temp)temp=T->data;else{isBST=FALSE})
如何判断二叉树是否平衡
维护isbalance = true
后序遍历，递归传出左右子树高度，相减绝对值大于-1，isbalance=false。不大于一，return更高的子树高度并且加一。
如何判断是否是完全二叉树
维护flag，如果出现叶子结点或者只有左孩子的结点，flag=true，再向后层次遍历的过程中，遇见只有右孩子，或者只有左孩子，或者是叶子结点，iscomplete=false;
树和森林
森林是m课互不相交的树的集合，
树的存储
双亲表示法
连续存储空间，虚拟指针表示双亲
找孩子要遍历整个表
孩子表示法
结点本身采用顺序存储结构，每个结点中都有指针域指向自己的所有孩子，
孩子兄弟表示法
左指针指向自己第一个孩子 右指针指向兄弟
树，森林，二叉树转换
树转二叉树
森林转二叉树
二叉树转森林
树，森林遍历
树的遍历
先根遍历
与相应二叉树的先序遍历相同
后根遍历
与相应二叉树的中序遍历相同
森林的遍历
先序遍历
对应二叉树的先序
中序遍历
对应二叉树的中序
应用
哈夫曼树和哈夫曼编码
wpl值
不是第几层 是与根结点有几个路径
加权平均长度
wpl/频率之和
并查集
双亲表示法
定义 int UFsets[]
-1,初始化值
find查找所在树的根
合并操作 union
合并的优化，小树合并到大树，深度不超过向下取整（log2n)+1
路径压缩，指针t指向x父节点，然后把x挂在根下面
串
字符串模式匹配
kmp匹配算法原理
暴力解
复杂度O（mn）
kmp算法
若在扫描当前子串匹配失败，失败字符前面匹配成功的部分是已知的，依赖于模式串，计算出部分匹配值，某一项失败后按照匹配值，模式串后移相应位置，维护一个数组next[]
主串不回溯，只修改模式串指针，（复杂度O(m+n)
next数组推理过程
捂住失败的字符，看前面的模式串，最大能重合几个，next值就是最大能重合几个＋1
nextval数组求解方法
在next数组基础上，继承，第五个字符next值是3，就看3是否和第五个字符相同，相同的话继承3的next[]值，从前往后一个个更新