二零拾肆

从一个点走到另一个点，最短需要走多远的长度？ 这是一个经典的最短路径问题，有很多种方法可以解决它。 而在这其中，有两种算法最为经典：一种名为Dijkstra算法，另一种，名叫Floyd算法。 Dijkstra 算法简介 Dijkstra算法主要是用来计算单源点到其余各点的最短距离，其基本思想和之前的Prim类似，都运用了加点+贪心 的做法，整体的流程也十分类似。 先从最开始确定的起点u开始，其余各点与它的距离即为邻接矩阵中各点到它的距离（也有可能没有邻接关系，距离为无穷）。然后在这些点中找到距离起点u最近的一个，接着通过这个点对所有点进行“ 松弛 ”操作。所谓“松弛”，即对于一段路径<i,j>，找到一个点k，使得<i,k>+<k,j>的长度小于<i,j>的长度。要找到两个点之间的最短路长度，就需要这样不断地松弛。直到将所有点尝试一遍，便能找出起点到其余各点的最短值。 这虽然只是简单的贪心思想，但其正确性已被数学方法所证明，有兴趣的可以自行了解，这里只大概介绍过程。 代码实现 1234567891011121314151617181 ...

XSD指XML Schema Definition ，这是一篇XSD的笔记。 概述 schema的大体作用与DTD相同，但比起DTD，schema更为完备。能够进行对元素更细致地约束，能够实现面向对象的特征，以及拥有良好的扩展性。最主要的是：schema的文档结构利用了XML的基本语法规则，继承了XML的自描述性与可读性。 schema文档的扩展名为 .xsd 。 在XML文档中引用schema文档的基本框架为： 12<根元素 xmlns:xsd="http://www.w3.org/2001/XMLSchema-instance" xsd:noNamespaceSchemaLocation="schema路径"></根元素> 而在一个schema文档中，其基本框架为： 12<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema"></xsd:schema> 语法 简单类型 在讲schema的基本结构之前，我们先聊一 ...

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 换句话说，一棵生成树就是有n-1条边的连通子图。而最小生成树(MST)，就是符合条件的子图中总权值最小的图。 最小生成树在生活中的应用十分广泛，比如说在城市之间搭建通信网络，那最小生成树就能求出电缆长度最短的解法（当然，只是一个举例，现实生活中肯定还要考虑很多因素）。 最小生成树有两种构造方法，分别为“加点法”Prim算法与“加边法”Kruskal算法。 Prim 算法简介 Prim算法的基本思想是“加点”，大体思路就是将顶点们分为两个集合，集合X{}为当前选中的点，集合Y{}为未选中的点。初始情况下X{}为空，而Y{}包含所有顶点。 刚开始先选择一个顶点u作为起点加入X{}。然后从Y{}中寻找距离u最近的点v，将其加入X{}。此时的X{u,v}中就有了两个顶点。接下来从Y{}中继续寻找顶点距离u或v最近的顶点w，将其加入X{}。不断循环以上过程，直到X{}中有所有顶点，而Y{}为空。此时由以上选中的邻接关系组成的子图即为最小生成树。 老规矩，我们来举个例子： ...

DTD即为Document Type Definition，这是一篇DTD的笔记。 概述 文档类型定义（DTD，Document Type Definition）是一种特殊文档，它规定、约束符合标准通用标示语言（SGML）或SGML子集可扩展标示语言（XML）规则的定义和陈述。 反正也没人看这部分，我就随便从百度百科复制一段了 DTD由元素(Elements)、属性(Attribute)、实体(Entities)与注释(Comments)四部分组成。 但由于其限制上的局限性与使用上的不方便，近年来已逐渐被schema代替。 DTD的文件扩展名为 “.dtd” 。 语法 引用 内部引用 在一个XML文档中引用DTD可分为内部引用 与外部引用 ，很显然，内部引用即将DTD编写在XML文档内，外部引用即引用外部编写好的.dtd文件。 内部引用的基本框架为： 123<!DOCTYPE 根元素 [ DTD内容]> 根元素即为要被解释的部分的根元素。或许听起来有点绕，我们可以看个例子： 12345<?xml version="1.0"?> ...

XML是一种用于标记电子文件使其具有结构性的标记语言。这是一篇XML的笔记。 概述 XML(eXtensible Markup Language)是标记语言中的一种，以一种更中立的方式，让用户自行决定要如何理解、呈现从服务端所提供的信息，而着重表示数据以及数据之间的联系。 其特点为可扩展性、灵活性、自描述性与简洁性。 一个完整的XML文档大体分为三个部分：文档数据(XML)、文档结构(DTD/Schema)与文档样式(XSL/CSS)。其结构为树形结构。 语法 声明 位于XML文档的第一行，结构一般为： 1<?xml version="1.0" encoding="UTF-8" standalone="yes"?> 其基本框架为 1<?xml 版本声明 编码声明 独立声明?> 版本声明 ：version属性的取值用于描述当前XML的版本编号，通常情况下为1.0，这是为了将来的新版本能够保持向后的兼容性而设计的。这个属性必须存在，且必须作为第一个属性。 编码声明 ：encoding属性的取值用 ...

这次实验是单纯的对C#反射特性的学习，没什么特别的。 前期准备 实验要求 3.2 构建一个components.txt文件，每行代表一个类（比如形状类Shape）的名字（这些类可以来自系统库，或者自己构造）；程序逐行扫描该文件，构建对应的类的对象。要求： 1）并把这些对象放到数组中； 列出每个类的字段、方法； 3）让用户选择，使得用户可以调用所需要的方法（操作） 4）系统随机选择对象（比如形状），随机的执行其操作。从而看系统演化。可能的话，进行界面展示 前置知识 实验要求中需要我们通过类名字实例化对象，且列出其字段与方法，并尝试调用方法。以上这些操作都指向了C#中很重要的一个知识点——反射。 反射提供描述程序集、模块和类型的对象（Type 类型）。 可以使用反射动态地创建类型的实例，将类型绑定到现有对象，或从现有对象中获取类型，然后调用其方法或访问器字段和属性。 如果代码中使用了特性，可以利用反射来访问它们。 如果对反射还不太理解，建议参阅C#官方文档。 而从文件中读取的操作则需要System.IO中File类的操作。 对于调用形状库，则需要使用System.Ref ...

介绍完了图的基础知识，我们终于迎来图中最重要的一个知识点，也是许多算法都会用到的著名思想——DFS与BFS。 DFS即为深度优先搜索，BFS为广度优先搜索，他们就如同亲兄弟一般，处处相照应，前者需用到栈，而后者，则会用到队列。 它们都是图的遍历方法，执行一轮后即可以不同顺序遍历过图的所有顶点。 DFS(Depth-First-Search) DFS的基本思想即为一条路走到黑 ，先顺着一条路搜索到底，然后再开始回溯 ，对之前没搜索过的岔路分别执行DFS。在这其中，已搜索过的顶点不会被重复搜索 。若DFS一轮后还有剩余顶点，则再对其进行DFS，当然，这种情况只出现于非连通图。 但看概念可能较为晦涩，我们来举个例子： 对于这张图，我们先从A开始DFS，先心无旁骛沿着一条路走到底：A->B->C->D->E 。当然，A->B->F->G也可以，在没有其他限定的情况下，遍历结果不具有唯一性 。我们假设使用的是前者，那么走到E后无路可走了，就进行回退。回退到D，但是与D相邻的C和E都已经搜索过，所以也无路可走，只好再次回退到B。这时发现有一个邻接点 ...

结束了树的部分，我们终于迎来了图。 不论是在算法或是在离散数学中，图都是一种很重要的结构：后续的DFS、BFS以及最小生成树等重要算法都需要建立在图的基础上。 这是图的第一篇笔记，我们就先从图的概念以及邻接矩阵与邻接表入手。 一起走进图论的大坑（ 基本概念 图，是一种邻接关系较为复杂的数据结构。不同于表的有规律，树的层级性，图看起来较为零散。 最基本的元素为顶点(Vertex) 与边(Edge) 。顶点，顾名思义，就是一个个存储数据的独立结点；而边，自然就是两个顶点之间的邻接关系。根据边的有向性，又可以将图分为无向图与有向图 。 👆无向图 👆有向图 为了加以区分，一般将有向图的边称为弧(Arc) ，并将弧的起点终点分别称为"弧头"与"弧尾"。不过这些不太重要，平时大家还是都习惯称之为边。 对于每条边都有权值的图，也被称为网，或是带权图。但是为了方便，一般情况还是默认称为图，而对于不带权值的图，则默认将权值都视为1。 其他还有一些零星的概念，稍作了解，以后遇到的时候自然会明白： 度（Degree） ：一个顶点的度是指与该顶点相关联的边 ...

已知a和b是亲戚， b和c是亲戚，b和d也是亲戚。那c和d是不是亲戚呢…… 要解决这种问题，看起来不是那么的容易。 没事，这次我们来聊一聊并查集，学完之后这种问题就能迎刃而解！ 在介绍并查集之前，我要先介绍一种树的表示方法——树的双亲表示法。 双亲表示法 双亲表示法，实际上就是利用了树的每个结点只有一个父结点的特性来表示树。为了不引起歧义，我更喜欢称之为父亲表示法。 比如对于这样一棵二叉树： 我们可以将其转化成线性结构，数组中的每一位代表一个结点，而其数据则代表其父结点的序号： 比如对于结点5，在数组tree中，tree[5]=2，则说明其父结点为2号结点。 用这种表示方式，很容易找到某个结点的父结点；然而缺点也很显然，如果要找结点的子结点，则需要遍历整个数组。 并查集 回到我们开头讲的那个问题，要判断两个人是不是亲戚，直接判断或许难度较高，但我们可以将他们的亲戚关系建立一棵树，在判断的时候只需要判断他们是否拥有同一个根结点即可，这样就大大简化了问题的难度。 我们建立起来的这种用双亲表示法表示的树形结构，由于只需实现合并与查找的功能，所以被称为并查集(union-find s ...

想象一下，让你对一串字符串进行编码，使其成为只由0和1构成的序列，你会设计怎样的编码算法？ 70年前，在MIT攻读博士学位的哈夫曼构建了一棵二叉树实现了最有效的编码算法。 这棵树名为最优二叉树，也被称为Huffman树。 编码 看到0和1，我们自然就很容易想到二进制数，想到将每一个字母对应一个二进制数。 比如：对于序列"ABCD"，可以将A编为0，B编为1，C编为10，D编为11。这样一来，编码后的序列就可以写作"011011"。看起来好像没什么不对。但是…解码的时候呢？前三位"011"是应该被理解成"ABB"还是"AD"呢…？ 可以发现，用简单的二进制不等长编码并不能解决我们的问题，究其原因，主要是因为"B"的编码与"D"的编码拥有相同的前缀 （都为"1"）。这时，就需要我们引入一个可以避免这种情况的编码方法——前缀编码。 前缀编码 前缀编码是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。 ...