二零拾肆

归并排序与快速排序都运用了分治(divide-and-conquer)的思想，将一整段序列的排序划分为多段子序列的排序问题。这两个算法的划分法都是二分，最后可以达到 O(nlogn) 的效率（本文中的效率与复杂度取的都是平均值）。 归并排序 归并 首先要了解一下归并算法：给出两个升序序列，将其合并成一个新的升序序列，要怎么做？ 如果将其简单组合再进行排序，未免太低效。我们可以利用其本身就升序的特性，每次先从两个序列头部取出较小的值，置于新序列的头部，并重复该步骤，直到两原序列都为空，算法结束，时间复杂度为 O(n) 。 归并排序 归并排序就是用了归并的思想：将一个序列分成两段，这两段 分别有序 ，那就可以对其进行归并，得到完整的有序数组。那么要怎么保证这两段序列分别有序呢？很简单，对其分别递归执行归并排序就可以了。由于这样分块执行的次数为 logn （即log(2)(n)）次，所以完整的归并排序时间复杂度为 O(nlogn) 。 12345678910111213141516171819//归并排序 O(nlogn)template <class Type>voi ...

实验要求 5.2 构建线程A1、A2… Ak（k>=3）和线程B的程序（k生产者和单消费者）。A1、A2… Ak从磁盘各自读取一个文本文件，写入到内存中的固定的容器（如Pool）。A1、A2… Ak读取每一行时，都会休眠，然后在随机的时间（10–100 ms）醒来继续尝试执行。程序要求按照A1、A2… Ak的顺序写入Pool。B会观察Pool的状态，如果有新数据，则进行读取，否则B处于等待状态。注意，A1、A2… Ak不能互相干扰。当所有的文件被读取完毕，且B读取完毕时，程序结束。 不推荐阅读 以下部分内容表述较不准确；由于我个人对多线程掌握得并不是很优秀，代码也不一定完全正确。但作为应付作业已经足够，谨慎阅读 。 实验环境 Visual Studio 2019 + C#开发环境 算法设计 由于k个读取文件的线程内容基本相同，我们便只介绍一个，其他都相同，不再赘述： 12345678910111213141516171819public void ReadA1(object stateInfo){ Monitor.Enter(this); if ...

XQuery(An XML Query Language) 是一种专门用于XML的半结构化数据查询语言。这是一篇XQuery的笔记。 概述 XQuery的功能与XSLT类似，但是写起来较为直观简便。 语法 一个XQuery文档的基本框架为： 123for $变量名 in doc("xml-location")/xpath ...return ... 其含义即为打开 doc() 中指定的xml文档，并通过xpath路径找到所有结点，绑定到变量上。而执行完一系列操作语句，最后return的语句即为输出的内容。 FLOWR表达式 XQuery有五种最基础的表达式，分别为 for let order by where return ，简称为FLOWR。 for for语句对应于XSLT中的 <xsl:for-each> ，其最基础的用法为 for $x in expr ，其中expr可以是xpath表达式也可以是一串序列，这时for语句会依次读取其中的值： 123for $x in ("cat","dog")re ...

这次来聊聊几个简单的排序算法：插入排序、希尔排序、选择排序、冒泡排序与地精排序。由于我本身不是很想深究这方面的内容，只是应付一下课业，所以就简单介绍一下。反正用处也不是特别大…… 插入排序 1234567891011//插入排序 O(n²)template <class Type>void InsertSort(Type arr[], int n) { int i, j; for (i = 1; i < n; i++) { Type temp = arr[i]; //当前处理数据 //将该数据之前所有大于它的数据都后移一格,找出其正确位置并置入 for (j = i - 1; j >= 0 && arr[j] > temp; j--) arr[j + 1] = arr[j]; arr[j + 1] = temp; }} 对于插入排序，最好的情况是所有数据在表中已为升序排列，此时只需要进行 n-1 次比较， 0 次移动。而 ...

这次来聊一聊哈希表(Hash Table)。哈希表本身不难理解，所以我就做点简单的介绍。 哈希表 哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表。 看这些概念或许有点凌乱，但我们举个例子就能很快明白了：假设有一组数据 15, 24, 16, 32, 40 要进行存储，此时我们就可以开放一个数组 int HashTable[7] ，并设计哈希函数 index = key % 10 ，就容易算出 index(15) = 5 ，index(24) = 4 ，index(16) = 6 ，index(32) = 2 ，index(40) = 0 ，并按照这些角标进行存储，得到 HashTable = [40, 0, 32, 0, 24, 15, 16] 。 接下来我来介绍两个比较典型的哈希函数构造方法。 哈希函数 直接定址法 直接定址法的哈希函数为 index = key * a + b ，其中a与b都是自由取的变量。一般用于 地址数组长度& ...

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。 二叉排序树，顾名思义，是一种能将数据进行排序的二叉树。其 中序遍历 所得出的序列为有序序列。以下我们统一以 升序序列 进行讨论，降序序列原理相同。 要实现一棵这样的树，只要遵循一条规则： 每个结点的左子结点的值小于当前结点，右子结点的值大于当前节点 。具体为什么要这样？假设一个结点 A (A->left=B; A->right=C) ，中序遍历得到的序列为 BAC ，要符合升序排列，必定是 B<A<C。 二叉树的基本结构之前聊过多次，这里就不多赘述了 12345678class BinaryTree { typedef struct Node { int val; //数据域 Node* left; //左指针域 Node* right; //右指针域 } Node, *BTLink; ...

实验要求 目的：熟悉图形化界面程序，开发有趣应用。 2.2 参考分形的概念，绘制分形树或者其他分形图形。要求可以对图形进行保存和打开等操作。 需求分析 抛开分形树不看，这次的实验就是简单的图片浏览器，并且无需编辑功能，只需实现读写即可。这部分内容我们其实已经在实验#2实现过，本质上就是调用C#的自带控件。所以本次实验的重点即为 分形树 的绘制。 分形树 分形(Fractal)，具有以非整数维形式充填空间的形态特征。通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。 而分形树，其基本单元就是一棵“Y”型的“树”，再将这棵树的两个分叉分别作为另外两棵树的根，以此不断扩张。换句话说，类似于一棵上下颠倒的 满二叉树 。 结合与其结构类似的满二叉树，可以想到，我们应该用 递归 来实现分形树。 代码实现 定义变量 1234567Graphics graphics; //画板Bitmap paintImg; //绘画图像int pWidth; //图像宽度int pHeight; ...

前面几个算法基本是以无向图为基础的，这次我们就来聊一聊有向图。 我们这次来解决两种问题：事件序列的执行顺序以及判断有向图中是否存在环。 以上两种问题都可以通过 拓扑排序(Topological Sort) 来解决。 引入 假设上图是你起床到出门的过程需要完成的事件序列，那么要如何给出一个符合约束的执行顺序呢？ 作为人类，肯定很容易就能看出来 A->B->C->D->E->F 或者 A->C->B->E->D->F 都是可行的执行顺序，但计算机没办法一眼看出来。我们便可以用拓扑排序计算出这样的一个拓扑序列。 拓扑排序 算法简介 其实上方的这种图我们一般称为 AOV网 （Activity On Vertex network），即将每个顶点都记为一个活动，与之对应的为 AOE网（Activity On Edge network），这两种网都是建立在 DAG图 （有向无环图Directed Acyclic Graph）之上的。 对于这种图，我们可以计算出一条符合事件发生次序的序列，名为 拓扑序列 ，这其中的过程则称为 拓扑排 ...

XSLT 指 XSL 转换(XSL Transformations)，这是一篇XSLT的教程， 概述 XSLT 用于将一种 XML 文档转换为另外一种 XML 文档，或者可被浏览器识别的其他类型的文档，比如 HTML 和 XHTML。通常，XSLT 是通过把每个 XML 元素转换为 (X)HTML 元素来完成这项工作的。 把文档声明为 XSL 样式表的根元素是 <xsl:stylesheet> 或 <xsl:transform>。这两个是同义的，均可使用。 正确的样式表声明如下： 123<?xml version="1.0" encoding="UTF-8"?><xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"></xsl:stylesheet> 123<?xml version="1.0" encoding=& ...

XPath即为XML路径语言(XML Path Language)，这是一篇XPath的笔记。 概述 XPath的主要功能是定位XML文档中的某部分内容，换句话说，就是确定一条路，使得电脑能够顺着这条路找到你想要的节点。 语法 节点 节点是XPath中的基本单位，以下几种都属于节点： 123<bookstore> <!-- 文档节点 --><author>J K. Rowling</author> <!-- 元素节点 -->lang="en" <!-- 属性节点 --> 而节点中的数据被称为原子值 ，比如上述例子中，J K. Rowling与“en”都属于原子值。 而节点之间的关系 分为父（Parent）、子（Children）、兄弟（Sibling）、先辈（Ancestor）与后代（Descendant）。举个例子，在如下文档中： 12345678<bookstore> <book> <title>Harry Potter< ...