文的盲

排序可以说是相当常用的一类数据处理方式，而进行排序的方法也是多种多样的，此文主要记录经典的排序算法，并阐明基本原理 开始之前 所有的排序算法以函数形式展现，采用C语言编写 函数风格统一，命名规则同ASort，A为排序方法名称，首字母大写，传参均仅传入数组及其大小，函数类型为void，即直接将原数组进行排序 所有排序的终点，也就时排序后的结果，为从大到小排序 为了让排序更好的进行，首先编写交换函数，即Swap()函数 代码： 123456789#include <stdio.h>#define ELEMENT_TYPE intvoid Swap(ELEMENT_TYPE *x, ELEMENT_TYPE *y) { ELEMENT_TYPE temp = *x; *x = *y; *y = temp;} 冒泡排序 冒泡排序可谓是相当经典的一个排序算法，记得自己大一面试学校社团之时，学长让第一个去了解的排序算法就是冒泡算法 实现思路 冒泡，顾名思义，就是将需排序的元素，看作大小不同的泡泡进行处理 首先 ...

拓扑序：如果图中从v到w有一条有向路径，则v一定排在w之前。满足此条件的顶点序列称为一个拓扑序 拓扑排序：获得一个拓扑序的过程就是拓扑排序 AOV如果有合理的拓扑序，则必定是有向无环图 算法原理： 将图中入度为0的顶点输出，或者储存在一数组中 输出之后，将这些结点以及其所在边一同抹掉，即将其连接的下个结点的入度设为0 继续输出新的入度为0的顶点 算法优化： 问题：进行寻找入度为0的结点之时，每次都扫描一次，这时很多都是无用功 优化：用一个容器将所有入度为0的结点装入，每次输出之时只需取出即可 12345678910111213141516171819202122232425262728bool TopSort(LGraph graph, Vertex topOrder[]){ // 拓扑排序 int indegree[MAXSIZE], cnt; Vertex v; PtrToAdjVNode w; Queue Q = CreateQueue(graph->nv); for (v = 0; v &l ...

是一棵树 无回路 v 个顶点一定有 v-1 条边 是生成树 包含全部顶点 v-1 条边都在图里 向生成树中加入一条边都一定构成回路 边权重和最小 最小生成树问题的相关算法都基本按照贪心算法来实现 Prim算法 形象地来说，此算法就是让一棵小树长大——在图中任意选取一结点作为树根，然后继续在图中选取结点让这棵树长大 代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960Vertex FindMinDist (MGraph graph, WeightType dist[]){ /* 返回未收录顶点之中dist的最小者 */ Vertex minV, v; WeightType minDist = INFINITY; for (v = 0; v < graph->nv; ++v) { if (dis ...

此系列博文记录自己的刷题过程，一些有意思或者精妙的解答将会被我整理成一篇博文 No.3 无重复字符的最长子串 给定一个字符串，找出不含有重复字符的最长子串的长度。 示例 1: 123输入: "abcabcbb"输出: 3 解释: 无重复字符的最长子串是 "abc"，其长度为 3。 示例 2: 123输入: "bbbbb"输出: 1解释: 无重复字符的最长子串是 "b"，其长度为 1。 示例 3: 1234输入: "pwwkew"输出: 3解释: 无重复字符的最长子串是 "wke"，其长度为 3。 请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。 说明：在看到此题之后，菜鸡的我开始思考如何通过设置一临时字符指针对未重复数字进行复制求长，有了大致思路之后开始胡乱操作，写的代码涂涂改改愣是半天没有结果，我随手百度一手，看到了一个简洁与智慧并存的解决方案，让人五体投地，特来膜拜 算法来源：XDmonkey ...

知道了单源最短路的算法之后，我们可以更进一步，学习多源最短路问题，因为我们的需求是多样的，我们在知道某点到某点最短距离之后还想知道其他两点间的最短距离，那么我们需要再求解一次吗？显然，那样过于麻烦，显然，我们需要一种算法来一次性求解所有的两两间距，用的时候只需要取出即可 弗洛伊德（Floyd）算法 弗洛伊德算法是比较经典的求解多元路径的算法，代码极为简洁 代码： 123456789101112131415161718typedef int Pathmatirx[MAXSIZE][MAXSIZE];typedef int ShortPathTable[MAXSIZE][MAXSIZE];void ShortestPathFloyd(MGraph graph, Pathmatirx *P, ShortPathTable *D){ int v, w, k; for (v = 0; v < graph->nv; ++v) for (w = 0; w < graph->nv; ++w) { // 初始化数组 ...

说明 在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的一条路径 这条路径就是两点之间的最短路径（Shortest Path） 第一个顶点为源点（Source） 最后一个顶点为终点（Destination） 分类： 单源最短路径：从某固定源点出发，求其到其他顶点的最短路径 无权图 有权图 无权图的单源最短路 实现方法：从源点开始，按照非递减的顺序，找出各个顶点的最短路，此类查找类似于图的BFS遍历，但有细微的不同 代码： 1234567891011121314151617void UnWeighted (LGraph graph, int dist[], int path[], Vertex s){ /* dist[] 存距源点的距离 path[] 存通过结点找到此结点的结点 */ Queue Q = CreateQueue(); Vertex v; PtrToAdjVNode w; dist[s] = 0; // 初始化源节点 AddQ(Q, s); while (!IsEmp ...

定义：从图中某一顶点出发，访遍图中其余结点，且使每一个顶点仅被访问一次，此过程称之为图的遍历 此文主要介绍两种遍历方法：DFS和BFS 深度优先遍历（DFS -- Depth First Search） 深度优先遍历也称之为深度优先搜索，是一种常用的图遍历算法 深度优先遍历实现总的来说就是两句话： 从一顶点开始，在图中进行 ”深入“ —— 即从这个顶点开始，顺着某条边进行遍历 无法 ”深入“ 时，进行 ”回溯“ —— 即若遍历到这条边的终点，则原路返回上一个结点，在此结点进行查询通过此结点所有可以到达的所有结点是否还有未遍历过的结点，再次进行 ”深入“ 可见，此遍历的实现过程描述是一种递归描述，所以首先考虑通过递归的方法进行实现 代码： 12345678void DFS(MGraph graph, int i) { int j; visited[i] = TRUE; printf("%5d", graph->data[i]); for (j = 0; j < graph->nv; j+ ...

算法竞赛入门经典（第二版）—— 第二章习题 此为练手简单习题，觉得挺有意思，并且第一次处理之时想的过于简单或者处理有误，故贴出来作为提醒，并分享处理方案，仅供参考！ 习题 2-5：分数化小数 输入正整数a,b,c，输出a/b的小数形式，精确到小数点后c位。a,b ≤ \(10 ^6\) ，c ≤ 100。输入包含多组数据, 结束标记为a=b=c=0。 样例输入： 1 6 4 0 0 0 样例输出： Case 1: 0.1667 该题以普通想法来说，是直接进行输出，但是存在着两个问题： 输出的小数位数为c，不好直接进行输出 c ≤ 100 ，由于C语言小数位数的限定，就算 double 类型，其小数位数也不可能达到100位，具体位数可自己进行试验，所以直接进行输出时会有严重的精度损失 由以上，我们可以针对C语言整数除法的特点，间接计算小数的值 代码： 12345678910111213void Decimal(int a, int b, int c){ int i = 1; printf("%d.", a/ ...

定义：串是由零个或多个字符组成的有限序列，又叫做 字符串 一般记为 S = "\(a_1a_2......a_n\)"(n ≥ 0) S : 串的名称 \(a_1a_2......a_n\)：串的值 概念解释： 空格串：只包含空格的串，空格串不是空串，其有内容有长度，可不止一个空格 子串与主串：串中任意个数的连续字符组成的子序列称之为该串的子串，包含子串的串称之为主串 子串位置：子串第一个字符在主串中的位置 串的比较 定义： 给定两个串：s= "\(a_1a_2......a_n\)", t = "\(b_1b_2......b_n\)"，当满足以下条件之时，s < t： n < m，且 \(a_i = b_i\) ( i = 1，2，...，n) 存在某个k ≤ min(m, n) ，使得\(a_i = b_i\)（i = 1，2，...，k-1），\(a_k < b_k\) 其原理就如同英文字典一样，字典前面的单词总是小于后面的 串的抽象数据类型 ...

什么是图（Graph）？ 表示“多对多”的关系 包含： 一组顶点：通常用V（Vertex） 表示顶点集合 一组边：通常用E（Edge）表示边的集合 边是顶点对：（v,w）属于 E ，其中 v,w 属于 V 有向边 <v,w> 表示从v指向w的边（单行线） 不考虑重边和自回路 抽象数据类型定义 类型名称：图（Graph） 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。 操作集：对于任意图 G 属于（\(/in\)） Graph，以及 v 属于 V, e 属于 E Graph Create()： 建立并返回空图； Graph InsertVertex(Graph G, Vertex v)： 将v插入G； Graph InsertEdge(Graph G, Edge e)： 将e插入G； void DFS(Graph G, Vertex v)： 从顶点v出发深度优先遍历图G； void BFS(Graph G, Vertex v)： 从顶点v出发宽度优先遍历图G； void ShortestPath ...