数据结构
2020-09-15 10:03:01 0 举报AI智能生成
408计算机基础，计算机网络，二战123分老学长一年整理出来的资料。
作者其他创作
大纲/内容
图
最短路径算法
Dijkstra算法（不适用于有负值的边）
1.选取与源节点最短的一条边
2.将这条边所连接的节点加入到已加入点集中
3.判断该点所连接的所有的边是否可以修改源点到边的另一点的距离
4.找所有点最短路径中的最短且没有加入点集中的一个（重复234直到所有的边都加入到这个点集中）
Floyd算法（可以有负值，但是带负值的边不能成环）
1.定义数组
2.三重循环，注意最外层是k，其次才是i，j
最小生成树
Prime算法
以顶点为中心逐步加入边，因此适合稠密图
贪心算法，每次选取最小边所连的顶点直至所有的点都加入
Kruskal算法
以边为中心的算法，适合于稀疏图
也是贪心算法，需要特别注意的是，每次选取的边不能使得以构成的图出现环
关键路径算法（有向图）
最长的一条路径
需要特别注意的一个图可能有多条关键路径缩短一条关键路径上的值不一定可以改变最大的长度
拓扑排序（有向图）
有环的有向图必定没有拓扑排序，因此可以用来判断有向图里面有没有环
一个图可能有多个拓扑排序的序列
哈希表
构造方法
1.直接定址法
地址H（key）=a*key+b
2.除留余数法
地址H（key）=key MOD p（p为小于等于表长的最大质数）
3.数据分析法
判断 关键字的那一部分分布的均匀
4.平方取中法
5.折叠法
解决冲突的方法（a为装填因子）
1.开放地址法
线性探索再散列（成功概率1/2乘以（1+1/(1-a)））
平方探索再散列（+-1²+-2²+-3²）
随机探测在散列（双探测再散列）
不可随意删除其中的一个关键字
2.链地址法（成功概率1+(1/2)乘以a）
3.公共溢出区法
4.再散列法（两个散列函数关键字通过第一个散列函数获得地址，通过第二个散列函数获得其增量）
查找等概率下成功失败的平均查找长度
查找成功
计算每个关键字的查找成功的比较次数（注意解决冲突的方法）
用关键字查找成功的比较次数的和除以关键字的个数
查找失败
计算落0-p-1地址内的每一个位置到它之后的第一个空位的比较次数（一般和空位的比较次数也算一次）
若某个地址到散列表的最后（跟散列表的长度有关）也找不带一个空位那么就再重头找，直到找到一个空位位置
将所有的0-p-1的查找失败的比较次数加到一起除以p得到平均查找失败的查找次数
图的基本知识
无向图
连通图（任意两点都有路径的无向图）
联通分量（任意两点都有路径的极大联通子图，不一定包含所有节点）
联通图只有一个连通分量那就是他自己
生成树是极小联通子图（再加一条边就有环的图，且包含所有节点）
有向图
强连通图（任意两点之间都有路径的有向图）
强联通分量（任意两个顶点间都有路径的连通子图）
强连通图只有一个强连通分量
有向图没有极小连通子图这个概念
联通
任意两点之间都有路径称之为联通
联通分为联通和强联通分别对应的是无向图和有向图
简单路径
路径中的点不重复出现的路径称之为简单路径
回路
首尾节点相同的路径称之为回路
表示方法
邻接表
邻接矩阵
十字链表（有向图）
邻接多重表（无向图）
排序
排序算法
内部排序
插入排序
直接插入排序（n²）
2分插入排序（nlog2n）
希尔排序（n的1.3次方）
选择排序
简单选择排序（n²）
堆排序（nlog2n）
交换排序
冒泡排序（n²）
快速排序（nlog2n）
归并排序（nlog2n）
基数排序(r+n)（不基于比较）
外部排序
置换-选择算法
用于生成多个有序段
选出序列中最小的比已经生成的有序段前一个大或者等于的插入到有序段中
有序段的待排序段第一个为最小的一个
所待排序段中所有的值都比有序段中的上一个小则重新创建有序段
最佳归并树（只有度为k或者是0的节点）
用于置换选择算法中生成的多个不等的归并段的合并顺序
k路归并类似于哈夫曼树的创建只不过哈夫曼树是选中最小的两个，最佳归并时选择最小的k个
败者树（完全二叉树）
用于在多个归并段中选取最小的一个（时间复杂度为log2n）
败者树的重构更加方便，每次输出胜者后，新插入的节点放入胜者的位置，败者留在原来的位置，胜者向上
败者树每次重构都是将它的胜者输出，新的节点放入在胜者的地方，这个节点会一路向上（与败者比较胜者替换改节点）知道最后修改最终的胜者
总结
排序算法与初始状态无关的算法（一堆乌龟选基友）
堆排序
选择排序
归并排序
基数排序
稳定的算法
直接插入排序
冒泡排序
归并排序
基数排序
适合情况
基本有序的数列适合直接插入或者是冒泡排序
基本有序的序列不适合快速排序
堆排序在最好和最坏的情况下时间复杂度均为nlog2n
排序趟
快速排序一趟不一定只能确定一个，如中枢元素排在中间第二趟就确定两个
堆排序一趟取出一个放在最后，因此一趟确定一个
简单选择排序每一趟确定一个放在最前面，每趟确定一个
直接进插入排序每趟不一定能确定一个，有可能一个 也确定不了
查找
顺序查找
查找成功的平均查找长度为（1+n）/2
二分查找
画出二分法查找判定树
查找成功的平均查找长度
查找失败的平均查找程度（一般最后的判定树的最后一个为null的节点，这个节点的比较不算入长度里面）
查找节点为（a+b）/2，向下取整
b树和b+树
b树
末行在一行上
非叶节点也是关键字
m阶b树有m/2向上取整到m个连接，相应的连接减一个节点。（根节点1到m-1）
b+树
末行在一行上，有索引
非叶节点是是下一行的最大值
m阶b树有m/2向上取整到m个连接，节点和连接数相同。（根节点一般2到m）
b树操作
新增节点
1.满足节点要求放在最下面一层
2.大于节点要求的个数节点向上分裂，若上层也大于最大要求继续分裂
删除节点
节点为叶子节点
1.节点个数满足要求则直接删除
2.节点个数不满足要求的向兄弟节点借，方法为兄弟节点的值放在父节点（并删除自己），父节点的值放在要删除的位置
3.如果兄弟节点的值也不够借的话就合并节点
节点为非叶子节点
1.找到一个与该节点逻辑相邻（排序后）的叶子节点，与他交换
2.删除交换后的叶子节点
算法
算法的评判标准
时间复杂度
空间复杂度
算法的原则
有穷性
健壮性
可行性
输入输出
线性表
顺序表
链表
创建链表
头插法
尾查法
链表操作
删除节点
新增节点
队列
入队
链队
先判断是否为空
空链队的入队和有不为空的链队的入队是有区别的
表队
queue[rear++]=x
出队
链队
先判断是否为空
空链队的出队和有不为空的链队的出队是有区别的
表队
queue[front++]=x
队空判断
链队
队空rear = front =null
注意若rear = front ！=null表明该链队有一个元素
表队
队空rear = front（循环队列，单独考虑）
栈
入栈
链栈
带头结点的，头插法
不带头节点的，插入节点将改节点插入链表的头部
表栈
stack[++top]=x
出栈
链栈
带头结点的，x=L->next->data,L->next=L->next->next
不带头结点的，x=p->data,p=p->next
表栈
x=stack[top--]
栈空判断（链栈和表栈）
链栈
带头结点的L->next ==null为栈空
不带头节点的p== null为站栈空
表栈
top=-1表示栈空
栈和队列的应用
中缀转前缀表达式
中缀转后缀表达式
只有遇到 ')'才出队''('
操作数不入栈，直接显示
符号都入栈
树
二叉树分类
满二叉树
b树和b+树可以看做满n叉树
完全二叉树
胜者树败者树是完全二叉树
二叉排序树
二叉排序树不一定就是平衡二叉树
二叉排序树的中序遍历是有序的
平衡二叉树
ll型和rr型lr型和rl型
找到从下到上第一个不平衡的树
这课树上下二个节点的左右位置如果分别为左右则为lr型，以此类推
平衡因子是左子树的高度减去右子树的高度，不可颠倒
平衡调整规则
ll型rr型
左旋将上去的节点断掉右子节点连接它的节点成为新的右节点，并将断掉的节点放入合适的位置
右旋将上去的节点断掉左子节点连接它的节点成为新的左节点，并将断掉的节点放入合适的位置
lr型和rl型
先旋转下面的节点使的整个编程rr型的或者是ll型的
根据ll型和rr型由上之下找到第一个不平衡的节点rr或者ll旋转
n个节点有多少种二叉树的形态卡特兰公式
c2n，n/(n+1)
树与二叉树树的转换
树转二叉树
按照左孩子和右兄弟的规则存放
一颗树因此生成二叉树的根节点是没有右孩子的否则这个就不是树而是森林
森林转二叉树
按照左孩子右兄弟的规则
森林可以看做是多个树，多个树生成的二叉树的根节点是有右孩子的，否则就是一个数树
遍历算法
先序，后序，中序的递归算法
先序，后序，中序非递归遍历（栈）
线索化
创建线索化
线索化遍历
哈夫曼树
常见的哈夫曼树是二阶的
k叉树的的哈夫曼树中只有度为k的节点和度为0的节点
k叉树的哈夫曼树的满足公式
向上取整（(n-1)/(k-1)）=m
其中n为叶子节点个数m为非叶子节点的个数
构建k叉树的叶子节点不能构建满足树的度只有k和0时增加权值为0的节点（类似于最佳归并树增加的虚段）
哈夫曼编码和前缀编码的不同在于，前缀编码只要求前缀不重复，哈夫曼编码还要求最短比如00,11可以作为前缀码，但是不能作为哈夫曼编码
树和森林赫尔和二叉树的转换
树和二叉树
树的后根遍历序列与这棵树对应二叉树（孩子兄弟表示法）的中序遍历序列相同
树的先根遍历序列与这棵树对应二叉树（孩子兄弟表示法）的先序遍历序列相同
森林和二叉树
森林的先序遍历和二叉树（孩子兄弟表表示法）的先遍历相同
森林的中序遍历 和二叉树（孩子兄弟表示法）的中序遍历相同
区别
树不存在中序遍历
森林不存在后序遍历
KMP算法
关键求next[]数组
手动求
当i<2时：
next[1]=0
next[2]=1
next[1]=0
next[2]=1
当i>2时：
在字符串s中，s[1]~s[i-1]是长度为i-1的字符子串，这一字符子串的前缀、后缀最长公共元素的数量记为k；
则：
next[i]=1+k
在字符串s中，s[1]~s[i-1]是长度为i-1的字符子串，这一字符子串的前缀、后缀最长公共元素的数量记为k；
则：
next[i]=1+k
getnext函数
求nextval[]数组
手动求
记p = next[i] ;
将 s[i] 与 s[p] 进行比较：
1）二者相同，则，nextval[i] = nextval[p]
2）二者不同，则，nextval[i] = p
将 s[i] 与 s[p] 进行比较：
1）二者相同，则，nextval[i] = nextval[p]
2）二者不同，则，nextval[i] = p
KMP算法的比较次数
在求next若i，j两个指针指向的字符不相等时，i不变j回退到next[j],继续比较
在字符串匹配时若i，j两个指针指向的字符不相等时，i不变j回退到next[j],继续比较
0 条评论
下一页
