- 博客(281)
- 收藏
- 关注
RSS订阅原创 线性方程组的迭代法(Jacobi 迭代法和Gauss-Seidel 迭代法) C++代码
线性方程组的迭代法(Jacobi 迭代法和Gauss-Seidel 迭代法)
2023-11-30 16:12:35
471
原创 数据结构--关键路径
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹AOE⽹具有以下两个性质：① 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。另外，有些活动是可以并⾏进⾏的在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个。
2023-08-17 16:17:10
583
原创 数据结构--拓扑排序
AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边ViVj表示活动Vi必须先于活动Vj进⾏注：如果图中存在环路就不是AOV网DAG图是指有向无环图（Directed Acyclic Graph），是一种有向图的特殊形式。它由一些有向边连接的节点组成，并且不存在任何形式的环。换句话说，从任何一个节点出发，沿着有向边的方向无法经过一系列的节点再回到原始节点。
2023-08-17 11:37:12
1736
原创 数据结构--最短路径 Floyd算法
Floyd算法：求出每⼀对顶点之间的最短路径使⽤动态规划思想，将问题的求解分为多个阶段对于n个顶点的图G，求任意⼀对顶点Vi→Vj之间的最短路径可分为如下⼏个阶段：#初始：不允许在其他顶点中转，最短路径是？#0：若允许在 V0 中转，最短路径是？#1：若允许在 V0、V1 中转，最短路径是？#2：若允许在 V0、V1、V2 中转，最短路径是？#n-1：若允许在 V0、V1、V2 …… Vn-1 中转，最短路径是？以上就是Floyd算法的基本步骤。
2023-08-15 16:58:02
319
原创 数据结构--最短路径 Dijkstra算法
计算begin点到各个点的最短路如果是无向图，可以先把无向图转化成有向图我们需要2个数组final[] （标记各顶点是否已找到最短路径）与 dis[] （最短路径⻓度）数组begin→以上就是Dijkstra算法的基本步骤。在实际应用中，可以使用优先队列来选取最短路径最小的节点，以提高算法的效率 (堆Dijkstra)。V0到V2 的最短(带权)路径⻓度为：dist[2] = 9v0→v4→v1→v2。
2023-08-15 16:06:18
595
3
原创 数据结构--最小生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
2023-08-08 17:03:41
454
原创 数据结构--图的遍历 DFS
同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀。同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀。查找每个顶点的邻接点都需要O(|V|)的时间，⽽总共有|V|个顶点。查找各个顶点的邻接点共需要O(|E|)的时间，，从任⼀结点出发都只需调⽤1次 BFS/DFS。访问 |V| 个顶点需要O(|V|)的时间。访问 |V| 个顶点需要O(|V|)的时间。调⽤BFS/DFS函数的次数=连通分量数。，只需调⽤1次 BFS/DFS。进⾏BFS/DFS遍历。
2023-08-01 16:06:30
517
2
原创 数据结构--图的基本操作
使用的存储模式：图的基本操作：• Adjacent(G,x,y)：判断图G是否存在边或(x, y)。• Neighbors(G,x)：列出图G中与结点x邻接的边。• InsertVertex(G,x)：在图G中插入顶点x。• DeleteVertex(G,x)：从图G中删除顶点x。• AddEdge(G,x,y)：若无向边(x, y)或有向边不存在，则向图G中添加该边。
2023-07-18 16:33:58
1449
原创 数据结构--图的存储 十字链表、邻接多重表
空间复杂度：O(|V|+|E|)如何找到指定顶点的所有出边？——顺着绿色线路找如何找到指定顶点的所有入边？——顺着橙色线路找注意：十字链表只用于存储有向图。
2023-07-18 15:57:18
778
原创 数据结构--图的存储邻接矩阵法
无向图：100无向图：第i个结点的度第i行（或第i列）有向图的非零元素个数有向图：第i个结点的出度第i行的非零元素个数第i个结点的入度第i列的非零元素个数第i个结点的度第i行、第i列的非零元素个数之和邻接矩阵法求顶点的度出度入度的时间复杂度为O∣V∣。
2023-07-17 11:13:32
150
原创 数据结构--图定义与基本术语
图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若Vv1v2vn，则用|V|表示图G中顶点的个数，也称图G的阶，E{(uv∣u∈Vv∈V，用|E|表示图G中边的条数。线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集。
2023-07-17 10:32:20
206
原创 数据结构--并查集的进一步优化
压缩路径−−Find操作，先找到根节点，再将查找路径上所有结点都挂到根结点下每次Find操作，先找根，再“压缩路径”，可使树的高度不超过Oαn))。αn是一个增长很缓慢的函数，对于常见的n值，通常αn≤4，因此优化后并查集的Find、Union操作时间开销都很低。
2023-07-11 15:35:04
475
原创 数据结构--哈夫曼树
以上都是哈夫曼树在含有n个带权叶结点的二叉树中，其中带权路径长度WPL最小的二叉树\color{red}带权路径长度(WPL)最小的二叉树带权路径长度WPL最小的二叉树称为哈夫曼树\color{red}哈夫曼树哈夫曼树，也称最优二叉树\color{red}最优二叉树最优二叉树。
2023-07-11 10:39:16
731
原创 数据结构--树的存储结构
树是nn≥0个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足:1）有且仅有一个特定的称为根的结点。2）当n >1时，其余结点可分为m (m>0）个互不相交的有限集合T1T2Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。树是一种递归定义的数据结构二叉树:一个分支结点最多只能有两棵子树树:一个分支结点可以有多棵子树。
2023-07-10 10:11:30
650
原创 数据结构--线索二叉树找前驱后继
在中序线索二叉树中找到指定结点*p的中序后继next①若p->rtag == 1，则next = p->rchild②若p->rtag== 0中序遍历――左根右左根(左根右)左根((左根右)根右)next = p的右子树中最左下结点。
2023-07-07 17:30:52
1155
原创 数据结构--线索二叉树的概念
中序遍历序列:D G B E A F C①如何找到指定结点p在中序遍历序列中的前驱?②如何找到p的中序后继?思路:从根节点出发，重新进行一次中序遍历，指针q记录当前访问的结点,指针pre记录上一个被访问的结点①当qp时，q为后继缺点找前驱、后继很不方便;遍历操作必须从根开始。
2023-07-07 11:17:17
625
原创 数据结构--由遍历序列构造二叉树
中序遍历:中序遍历左子树、根结点、中序遍历右子树中序遍历序列:BDCAE结论一个中序遍历序列可能对应多种二叉树形态。
2023-07-07 10:28:26
893
原创 数据结构--二叉树的层遍历
算法思想:①初始化一个辅助队列②根结点入队③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话)④重复③直至队列为空。
2023-07-07 09:46:19
619
原创 数据结构--二叉树的先中后序遍历
层次遍历:基于树的层次特性确定的次序规则二叉树的递归特性:①要么是个空二叉树②要么就是由“根节点+左子树+右子树”组成的二叉树先\color{red}先先序遍历：根\color{red}根根左右（N\color{red}NNLR）中\color{red}中中序遍历：左根\color{red}根根右（LN\color{red}NNR）后\color{red}后后序遍历：左右根\color{red}根根（LRN\color{red}NN）序遍历:A B D G E C F中序遍历:D G B E
2023-07-06 11:31:13
539
原创 数据结构--二叉树的性质
设非空二叉树中度为0、1和2的结点个数分别为n0n1和n2，则n0n21n0n21(叶子结点比二分支结点多一个)假设树中结点总数为n，则nn0n1n2nn12n21树的结点数总度数1n0n21二叉树第i层至多有2i−1个结点（ i≥1)m叉树第i层至多有mi−1个结点（ i≥1)高度为h的二叉树至多有2h−1个结点（满二叉树)
2023-07-05 17:25:40
369
原创 数据结构--二叉树的定义和基本术语
二叉树是nn≥0个结点的有限集合:①或者为空二叉树，即n = 0。②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。特点:①每个结点至多只有两棵子树②左右子树不能颠倒（二叉树是有序树注意区别: 度为2的有序树度为2的有序树是二叉树，二叉树不一定是度为2的有序树二叉树是递归定义的数据结构。
2023-07-05 16:36:14
621
原创 数据结构--树的性质
常见考点1结点数总度数1结点的度 ―― 结点有几个孩子(分支)树的度 ―― 各结点的度的最大值m叉树 ―― 每个结点最多只能有m个孩子的树常见考点2度为m的树、m叉树的区别常见考点3度为m的树第i层至多有mi−1个结点（i≥1m叉树第i层至多有mi−1个结点（i≥1常见考点4高度为h的m叉树至多有m−1mh−1个结点。
2023-07-05 15:54:35
695
原创 数据结构--KMP算法进一步优化(nextval)
在KMP算法中，nextval数组是对应于next数组的一个优化。nextval数组的作用是在匹配失败时，可以跳过一些不必要的字符比较，从而提高匹配的效率。nextval数组的计算方式和next数组类似，但是在计算过程中引入了一个新的指针k。k指向的是当前位置的前缀的末尾位置，即pattern[k]是当前位置的前缀的最后一个字符。k的初始值为0。与next数组不同的是，在计算nextval[i]时，如果pattern[i]与pattern[j]不相等，则需要根据next[j]的值来更新j和k的值。
2023-07-04 11:48:53
1040
原创 数据结构--KMP之求next数组
next数组的作用:当模式串的第j个字符失配时，从模式串的第 next[j]的继续往后匹配任何模式串都一样，第一个字符不匹配时，只能匹配下一个子串，因此，往后余生next1都无脑写0。
2023-07-04 11:02:36
622
原创 数据结构--字符串的KMP算法
朴素模式匹配算法：一旦发现当前这个子串中某个字符不匹配，就只能转而匹配下一个子串(从头开始)不匹配的字符之前，一定是和模式串一致的我们可以利用这个信息进行优化查找，我们知道一定无法匹配的就无需再进行匹配操作了我们可以发现：对于模式串T = ‘abaabc’当第6个元素匹配失败时，可令主串指针i不变，模式串指针j3当第5个元素匹配失败时，可令主串指针i不变，模式串指针j2当第4个元素匹配失败时，可令主串指针i不变，模式串指针j2当第3个。
2023-07-04 10:20:35
598
原创 数据结构--串的定义和基本操作
串\color{red}串串，即字符串String\color{red}字符串 (String）字符串String是由零个或多个字符\color{red}字符字符组成的有限序列。一般记为s =‘a1a2……a,’ (n ≥0)其中，S是串名\color{red}串名串名，单引号括起来的字符序列是串的值;a;可以是字母、数字或其他字符;串中字符的个数n称为串的长度\color{red}串的长度串的长度。n =0时的串称为空串（用∅\empty∅表示）。注。
2023-07-02 16:25:19
408
原创 数据结构--特殊矩阵的压缩存储
各数组元素大小相同，且物理上连续存放。数组元素a[i]的存放地址= LOC + i * sizeof(ElemType)0≤i10注:除非题目特别说明，否则数组下标默认从0开始注意审题!易错!
2023-07-02 11:40:32
1089
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人