一般的应用软件中，通常会提供Redo和Undo的操作，比如Paint.NET中的动作面板，Word中的撤销重做，一般我们按Ctrl-Z即可回退到上次操作。 要实现上面的这一功能，最直观的想法就是，我们需要把执行的命令以及相应的参数记录下来，一个命令或者动作，我们可以想象成一个对象，将这些的命令以对象的方式放到一个Stack里面，然后Undo的时候，Pop出来，然后执行该命令即可返回之前的状态。 将命令或者操作抽象为一个对象，使得可以用不同的请求参数对对象进行初始化，使得可以对命令进行排队处理，记录请求，以及执行Undo和Redo操作，这就是命令模式(Command Pattern)，命令模式最大的优点就是，他将对象方法的调用和实现分离开。 为了说明如何实现Undo和Redo，我们尝试做一个简单的文本格式化的小工具，就是能够进行加粗，倾斜，加下划线，然后支持重做和撤销操作。 首 …
从这篇文章开始介绍图相关的算法，这也是Algorithms在线课程第二部分的第一次课程笔记。 图的应用很广泛，也有很多非常有用的算法，当然也有很多待解决的问题，根据性质，图可以分为无向图和有向图。本文先介绍无向图，后文再介绍有向图。 之所以要研究图，是因为图在生活中应用比较广泛： 无向图 图是若干个顶点(Vertices)和边(Edges)相互连接组成的。边仅由两个顶点连接，并且没有方向的图称为无向图。 在研究图之前，有一些定义需要明确，下图中表示了图的一些基本属性的含义，这里就不多说明。 图的API 表示 在研究图之前，我们需要选用适当的数据结构来表示图，有时候，我们常被我们的直觉欺骗,如下图，这两个其实是一样的，这其实也是一个研究问题，就是如何判断图的形态。 要用计算机处理图，我们可以抽象出以下的表示图的API： Graph的API的实现可以由多 …
数据库分页是老生常谈的问题了。如果使用ORM框架，再使用LINQ的话，一个Skip和Take就可以搞定。但是有时由于限制，需要使用存储过程来实现。在SQLServer中使用存储过程实现分页的已经有很多方法了。之前在面试中遇到过这一问题，问如何高效实现数据库分页。刚好上周在业务中也遇到了这个需求，所以在这里简单记录和分享一下。 一 需求 这里以SQLServer的示例数据库NorthWind为例，里面有一张Product表，现在假设我们的需求是要以UnitPrice降序排列，并且分页，每一页10条记录。要求服务端分页。参数为每页记录数和页码。 二 实现 Top分页 当时采用的最直接做法就是使用两个Top来实现， 最后返回的结果是升序的，在C#代码里再处理一下就可以了。 这里作为演示，语句中使用 * 为了方便，实际开发中要替换为具体的列名。下面的方法简单吧。 SELECT …
在业务开发中，通常会按照业务或者逻辑将项目分成好几个工程文件以方便重用和模块化，有时候我们分开的两个项目可能存在相互引用的情况，举个例子，比如有两个系统，订单系统和产品系统，订单系统需要从产品系统中了解当前产品是否有剩余。产品系统需要从订单系统中了解产品的销售情况，这时候就存在相互引用的情况。 循环引用在Visual Studio中是编译不通过的。出现循环引用很可能是设计上抽象不够导致的，根据设计模式的依赖倒置-高层模块不应该依赖于低层模块。二者都应该依赖于抽象，抽象不应该依赖于细节，细节应该依赖于抽象这一原则，可以来解决循环引用。 在一些项目中，使用一些依赖注入的框架如SPRING.net，CASTLE可以在一定程度上避免循环引用。 Class A中用到了Class B的对象b，一般情况下，需要在A的代码中显式的new一个B的对象。采用依赖注入技术之后，A的代码只需 …
在很多时候，我们在写代码的时候总是会遇到一些相同或者类似的处理流程和步骤，就拿一般的函数编写来说，在处理之前一般会进行参数有效性验证，然后可能会对参数进行预处理，最后在执行业务操作。 这种情况通常会出现在一类业务，比如订单处理系统中，就有订单创建，订单修改等操作，就会出现的这些类似的情况。 如果每个都这样写的话，会发现整个流程比较重复和冗余。比如： class SomeProcessService { ResponseBody SomeProcess (RequestBody request) { ValidateParameter(); PreprocessingParameter(); DoSomething(); } } class …
前面讲解了平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。 维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。” 定义 B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。 根节点至少有两个子节点 每个节点有M-1个key，并且以升序排列 位于M-1和M key的子节点的值位于M-1 和M key对 …
前面一篇文章介绍了2-3查找树，可以看到，2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，本文介绍一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。 正如在博客推荐里所说，本文以及这一系列文章大部分参考或者引用《Algorithms》第四版，国内已经有中文版《算法》第四版，推荐购买原版学习。这里只是我个人的读书笔记。 定义 红黑树的主要是想对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节 …
前面介绍了二叉查找树(Binary Search Tree)，他对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率，要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态，这就是平衡查找树(Balanced Search Tree)。在一棵具有N 个节点的树中，我们希望该树的高度能够维持在lgN左右，这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。所以这里会介绍一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。本文首先介绍2-3查找树(2-3 Search Tree)，后面会在此基础上介绍红黑树和B树。 定义 和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。 …
前文介绍了符号表的两种实现，无序链表和有序数组，无序链表在插入的时候具有较高的灵活性，而有序数组在查找时具有较高的效率，本文介绍的二叉查找树(Binary Search Tree，BST)这一数据结构综合了以上两种数据结构的优点。 二叉查找树具有很高的灵活性，对其优化可以生成平衡二叉树，红黑树等高效的查找和插入数据结构，后文会一一介绍。 一 定义 二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 任意节点的左、右子树也分别为二叉查找树。 4. 没有键值相等的节点（no …
前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。 在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。 一符号表 在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，每一个元素都有一个key和value，我们可以往里面添加key，value键值对，也可以根据key来查找value。在现实的生活中，我们经常会遇到各种需要根据key来查找value的情况，比如DNS根据域名查找IP地址，图书馆根据索引号查找图书等等： 为了实现这一功能，我们定义一个抽象数据结构，然后选用合适的数据结构来实现： …