学校网站建设会议讲话稿,软件外包学院大学承认吗,长沙做官网的公司,制作企业网站目录 线索二叉树哈夫曼树并查集最小生成树最短路径拓扑排序二叉排序树平衡二叉树红黑树折半查找散列表堆排序归并排序 线索二叉树
原理#xff1a;利用树节点的n1个左右空指针指向其遍历序列的前驱和后继#xff08;线索#xff09; 优点#xff1a;简化遍历#xff0c;不… 目录 线索二叉树哈夫曼树并查集最小生成树最短路径拓扑排序二叉排序树平衡二叉树红黑树折半查找散列表堆排序归并排序 线索二叉树
原理利用树节点的n1个左右空指针指向其遍历序列的前驱和后继线索 优点简化遍历不需要额外的栈空间快速访问前驱的后继
哈夫曼树
哈夫曼树定义在含有n个带权叶节点的二叉树中其中带权路径WPL最小的二叉树称为哈夫曼树也称最优二叉树 带权路径长度叶子节点×路径长度 的总和 构建方法每次选取根节点最小的集合进行两两组合
并查集
用法判断图中是否有环判断是否在一个集合中 思想使用一个parent[]数组存储集合关系对集合进行并查操作 查找x所属集合返回x所属根节点 并将两个集合合并为一个 为了优化出现最坏的情况在合并集合的时候可以按秩合并
if(rank[x_root]rank[y_root]){//将x作为根节点合并parent[y_root]x_root;
}else{//将y作为根节点合并 rank[x_root]y_root;if(rank[x_root]rank[y_root]){//当秩相等时 rank[y_root];}
} 进一步优化路径压缩查找过程中将一个集合路径下的所有节点都挂到集合根节点下面
int find(int x){//找根节点if(xparent[x])return x;//返回根节点 return parent[x]find(parent[x]);//路径压缩
} 并查集模板代码
#includebits/stdc.h
using namespace std;
int parent[10005],rank[10005];
//找根节点
int find(int x){if(xparent[x])return x;//返回根节点 return parent[x]find(parent[x]);//路径压缩
}
//集合合并
void unionset(int x,int y){int x_rootfind(x);int y_rootfind(y);if(x_rooty_root)return;//在同一个集合中//按秩合并 if(rank[x_root]rank[y_root]){parent[y_root]x_root; }else{parent[x_root]y_root;if(rank[x_root]rank[y_root]){rank[y_root];}}
}
//打印关系函数
void selectdots(){for(int i1;i5;i){printf(%d的根节点%d\n,i,parent[i]);}
}int main(){//初始化 for(int i0;i100;i){parent[i]i;rank[i]0;}//初始化两个集合 A{1 ←2 ←3} B{4 ←5} ;int con[3][2]{{2,1},{3,2},{5,4}};for(int i0;i3;i){unionset(con[i][0],con[i][1]);//建立集合 } printf(A{1 ←2 ←3} B{4 ←5}两个集合没有合并\n); selectdots();printf(2和4点是否有关系);if(find(2)find(4)){couttrueendl;;}else{coutfalseendl;}printf(\n\n增加3 ←5关系\n);unionset(5,3);selectdots();printf(2和4点是否有关系);if(find(2)find(4)){couttrueendl;;}else{coutfalseendl;}printf(\n\n查询一次5的根节点\n);find(5);selectdots(); return 0;
}
最小生成树
生成树包含图中全部顶点的一个极小联通子图 最小生成树边权值之和最小的生成树 普利姆算法选点适合边稠密 克鲁斯卡尔(选边适合边稀疏):
最短路径 Dijkstra算法带权图无权图不适用有负权值的图 时间复杂度O(|V|^2) 思想 1.每次从未标记节点中选择距离出发点最近的节点标记收录到最优路径集合中。 2.计算刚加入节点A的邻近节点B的距离不包含标记的节点若节点A的距离节点A到节点B的边长节点B的距离就进行松弛操作更新节点B的距离
if((dis[A]e[A][B])dis[B]) dis[B] dis[A] e[A][B];Floyd算法(带权图无权图负权图不能解决负权回路的图) 时间复杂度O(|V|^3) 算法思想最开始允许经过1号中转求任意两点最短距离中转接下来只允许经过2号顶点中转…允许经过1~n号顶点中转 一句话概括从i号顶点到j号顶点只经过前k号顶点的最短路径
for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(e[i][k]e[k][j]e[i][j]){e[i][j]e[i][k]e[k][j];}}}}
拓扑排序
思想每次选择入度为0的顶点加入排序序列并删除所有出边 下面拓扑排序为12345
二叉排序树
定义左子树节点值根节点右子树节点值 查找效率最好O(logn) 最坏O(n) 平衡二叉树
定义二叉排序树上任一节点的左子树和右子树的高度之差不超过1 缺点插入/删除 很容易破坏“平衡”特性需要频繁调整树的形态。如插入操作导致不平衡则需要先计算平衡因子找到最小不平衡子树时间开销大再进行LL/RR/LR/RL调整
红黑树 平衡二叉树适用于以查为主很少插入/删除的场景 红黑树:适用于频繁插入、删除的场景实用性更强
折半查找
折半查找时间复杂度O(log2n) 又称二分查找仅适用于有序的顺序表链表不具备随机访问特性不能使用二分查找
大部分情况下折半查找更优但是有的情况顺序查找更优(比如待查找元素在第一个位置) 思想 1.使用双指针low和high分别指向有序表头和尾 2.计算 mid (lowhigh)/2 将有序表一分为二判断mid位置元素和待查找元素temp的大小关系通过移动low和high保留temp可能的区间 3.重复第二步直到lowhigh且此时指针指向的值等于temp查找成功当lowhigh查找失败
散列表
定义一直数据结构特点是数据元素的关键字与其存储地址直接相关通过散列函数(哈希函数):AddrH(key)建立关键字与存储地址的联系 散列查找是一种空间换时间的方法 增删改时间复杂度O(1)
散列函数 处理冲突的方法
堆排序
空间复杂度O(1) 时间复杂度O(nlogn) 物理结构使用顺序存储 逻辑结构大根堆根节点大于左子树和右子树小根堆根节点小于左子树和右子树 1.建立大根堆 **思路**把所有非终端节点都检查一遍是否满足大根堆的要求如果不满足则进行调整 调整方式检查当前节点是否满足 根左、右 若不满足将当前节点与更大的一个孩子互换若元素互换破坏了下一级的堆则采用相同的方法继续向下调整(小元素不断“下坠”)
2.基于大根堆排序 方法每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一个元素交换)并将待排序元素序列再次调整为大根堆(小元素不断下坠)
归并排序
