MH's Blog

基本概念

将个元素按关键字的递增或递减排列

说明一下数组长度为n，是从1-n，0的位置拿来做哨兵

查找表

概念

• 同一类型的数据元素构成的集合
• 含有的操作有
  1. 查询某个特定的元素是否在表中
  2. 检索某个特定元素的各种属性
  3. 插入或删除某个元素

将含有插入删除操作的查找表称为动态查找表，只有1,2的称为静态查找表

有向无环图

• 定义:一个有向图中不存在环(DAG)
• 应用:
  1. 描述运算表达式
  2. 拓扑排序(AOV)
  3. 关键路径(AOE)

graph TD;
A(有向无环图)
B(描述运算表达式)
C(拓扑排序)
D(关键路径)
A==>B;A==>C;A==>D;
C1(AOV网);C2(拓扑排序);C3(逆拓扑排序);C-->C1;C-->C2;C-->C3;
D1(AOE);D2(求解);D3(特性);D-->D1;D-->D2;D-->D3;

最短路径

BFS算法

解决单源无权图最短路径问题
从修改BFS算法开始

最小生成树

graph TD;
A[最小生成树]==>B1[最小生成树概念]
A==>B2[Prim算法]
A==>B3[Kruskal算法]

问题解决

• 查看输出
  The name org.freedesktop.secrets was not provided by any .service files

• 解决方案
  按这个网址所说
  sudo apt install gnome-keyring
  重启vscode 再次登录账户后会要求创建一个密码环 可以直接留空

图的基本操作

• Adjacent(G, x, y) 判断图G是否存在边
• Neighbors(G, x) x的全部边
• InsertVertex(G, x) 在图G中插入顶点x
• DeleteVertex(G, x) 从图G中删除顶点x
• AddEdge(G, x, y) 若无向边(x, y)或有向边不存在，则向图G中添加该边。
• RemoveEdge(G, x, y) 若无向边(x, y)或有向边存在，则从图G中删除该边。
• FirstNeighbor(G, x) 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点 或图中不存在x，则返回-1。
• NextNeighbor(G, x, y) 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
• Get_edge_value(G, x, y) 获取图G中边(x, y)或对应的权值。以及Set_edge_value(G, x, y, v)

在输出中，终端窗口的Task下拉列表切换成C/C++

/home/pi/.vscode/extensions/ms-vscode.cpptools-1.1.2/bin/../LLVM/bin/clang-format: error while loading shared libraries: libtinfo.so.5: cannot open shared object file: No such file or directory

解决方法

把libtinfo.so.5这包装上就好老
sudo apt-get install libncurses5
百度来的方法sudo ln -s /usr/lib/libtinfo.so.6 /usr/lib/libtinfo.so.5

graph TD;
A(图的存储);;
A-->B1(邻接矩阵)==>C1[数组实现,空间复杂度高];
A-->B2(邻接表)==>C2[顺序存储+链表实现];
A-->B3(十字链表)==>C3[存储有向图];
A-->B4(邻接多重表)==>C4[存储无向图];
C3-->D1(代码复杂考研很少考);
C4-->D1;

1.图的基础

i.图的定义

图是由顶点的有穷非空集合和顶点之间边的集合组成，表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。其中G为有穷非空。
图有分有向图和无向图。