Iterfun's Blog

2021-08-27（22号学长分享的一道题，今天才来记录。） 我自己的DFS解法（有漏洞）： 12345678910111213141516171819202122232425262728293031323334353637383940 1 #include <bits/stdc++.h> 2 using namespace std; 3 int matrix[30][30]; 4 void dfs(int i, int j) { 5 if (matrix[i][j] == 1 || matrix[i][j] == 2) // 是墙，或者走过了，就走人 6 return; 7 if (matrix[i][j] == 0) // 没走过就标记为2 8 matrix[i][j] = 2; 9 10 // 上下左右继续11 dfs(i, j+1);12 dfs(i+1, j);13 dfs(i, j-1);14 dfs(i-1, j);15 return;16  ...

　　　我们把构造连通网的最小代价生成树称为**最小生成树(Minimum Cost Spanning Tree)**。　　　找连通网的最小生成树，有两种经典的算法，普里姆算法和克鲁斯卡尔算法。 普利姆（Prim）算法 123456789101112131415161718192021222324252627282930313233 1 // Prim算法生成最小生成树 2 void MiniSpanTree_Prim(MGraph G) { 3 int min, i, j, k; 4 int adjvex[MAXVEX]; // 保存相关顶点下标 5 int lowcost[MAXVEX]; // 保存相关顶点间边的权值 6 lowcost[0] = 0; // 初始化第一个权值为0，即v₀加入生成树 7 // lowcost的值为0，在这里就是此下标的顶点已经加入生成树 8 adjvex[0] = 0; // 初始化第一个顶点下标为0 9 for (i = 1; i < G.nu ...

迪杰斯特拉（Dijkstra）算法 1234567891011121314151617181920212223242526272829303132333435 1 #define MAXVEX 9 2 #define INFINITY 65535 3 typedef int Pathmatrix[MAXVEX]; // 用于存储最短路径下标的数组 4 typedef int ShortPathTable[MAXVEX]; // 用于存储到各点最短路径的权值和 5 // Dijkstra算法，求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v] 6 // P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和 7 void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatrix *P, ShortPathTable *D) { 8 int v, w, k, min; 9 int final[MAXVEX]; // final[w]=1表示求的顶点v0至vw的最短路径10 for (v ...

　　　从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。 深度优先遍历（Depth_First_Search） 从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这是连通图的情况，如果是非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 如果我们用的是邻接矩阵的方式，则代码如下： 123456789101112131415161718 1 typedef bool Boolean; // Boolean是布尔类型，其值是TRUE或FALSE 2 Boolean visited[MAX]; // 访问标志的数组 3 // 邻接矩阵的深度优先递归算法 4 void DFS(MGraph G, int i) { 5 visited[i] = TRUE; 6 printf ...

各种图定义 图(Graph)是由顶点的有穷非空**集合和顶点之间边的集合组成，通常表示为：G(VE),其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 顶点（Vertex）：图中的数据元素 若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（vi,vj）来表示。 如果图中任意两个顶点之间的边都是无向边，则称该图为**无向图(Undirected graphs)**。 若从顶点v到v的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶对<vi,vj>来表示，v1称为弧尾（Tail），v2称为弧头（Head）。 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有nx(n-1)/2条边。 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n×(n-1)条边。 有很少条边或弧的图称为稀疏图，反之称为稠密图。（相对概 ...

树的抽象数据结构 123456789101112131415161718192021ADT 树（tree）DataOperation InitTree(*T): 构造空树T DestroyTree(*T): 销毁树T CreateTree(*T, definition): 按definition中给出树的定义来构造树 ClearTree(*T): 若树T存在，则将树T清为空树 TreeEmpty(T): 若T为空树，返回true，否则返回false TreeDepth(T): 返回T的深度 Root(T): 返回T的根结点 Value(T, cur_e): cur_e是树T中一个结点，返回此结点的值 Assign(T, cur_e, value): 给树T的结点cur_e赋值为value Parent(T, cur_e): 若cur_e是树T的非根结点，则返回它的双亲，否则返回空 LeftChild(T, cur_e): 若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空 RightSibling(T, ...

串的抽象数据类型 1234567891011121314151617181920212223ADT 串（string）DataOperation StrAssign(T, *chars): 生成一个其值等于字符串常量chars的串T StrCopy(T, S): 串S存在，由串S复制得串T ClearString(S): 串S存在，将串清空 StringEmpty(S): 若串S为空，返回true，否则返回false StrLength(S): 返回串S的元素个数，即串的长度 StrCompare(S, T): 若S>T，返回值>0，若S=T，返回0，若S<T，返回值<0 Concat(T, S1, S2): 用T返回由S1和S2联接而成的新串 SubString(Sub, S, pos, len): 串S存在，1≤pos≤StrLength(S)， 且0≤len≤StrLength(S)-pos+1，用sub ...

队列的抽象数据类型 123456789101112ADT 队列（queue）DataOperation InitQueue(*Q): 初始化操作，建立一个空队列Q DestroyQueue(*Q): 若队列Q存在，则销毁它 ClearQueue(*Q): 将队列Q清空 QueueEmpty(Q): 若队列Q为空，返回true，否则返回false GetHead(Q, *e): 若队列Q存在且非空，用e返回队列Q的队头元素 EnQueue(*Q, e): 若队列Q存在，插入新元素e到队列Q中并成为队尾元素 DeQueue(*Q, *e): 删除队列Q中队头元素，并用e返回其值 QueueLength(Q): 返回队列Q的元素个数endADT 循环队列 循环队列的结构 1234561 typedef int QElemType; // QElemType类型根据实际情况而定，这里假设为int2 typedef struct {3 QElemType data[MAXSIZE];4 int front; // ...

栈的抽象数据类型 123456789101112ADT 栈（stack）Dataoperation InitStack(*S): 初始化操作，建立一个空栈S DestroyStack(*S): 若栈存在，则销毁它 ClearStack(*S): 将栈清空 StackEmpty(S): 若栈为空，返回true，否则返回false GetTop(S, *e): 若栈存在且非空，用e返回S的栈顶元素 Push(*S, e): 若栈S存在，插入新元素e到栈S中并成为栈顶元素 Pop(*S, e): 删除栈S中栈顶元素，并用e返回其值 StackLength(S): 返回栈S的元素个数endADT 栈的顺序存储结构 栈的结构 123451 typedef int SElemType; // SElemType类型根据实际情况而定，这里假设为int2 typedef struct {3 SElemType data[MAXSIZE];4 int top; // 用于栈顶指针5 } SqStack; 进栈 ...

线性表的抽象数据类型 123456789101112ADT 线性表(List)DataOperation InitList(*L); 初始化操作，建立一个空的线性表L ListEmpty(L); 若线性表为空，返回true，否则返回false ClearList(*L); 将线性表清空 GetElem(L, i, *e) 将线性表L中的第i个位置元素值返回给e LocateElem(L, e); 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败 ListInsert(*L, i, e); 在线性表L中的第i个位置插入新元素e ListDelete(*L, i, *e); 删除线性表L中第i个位置元素，并用e返回其值 ListLength(L); 返回线性表L的元素个数endADT 线性表的顺序存储结构 将所有的在线性表Lb中但不在La中的数据元素插入到La中 1234567891011 1 void unionL(SqList *La, SqList Lb) { 2 ...