XIAOSUO 记录个人学习的足迹

摘要：一、采用数组保存数据 部分私有成员如下： public class ListT : IListT, System.Collections.IList { private const int _defaultCapacity = 4; //初始list大小 private T[] _items; //list数据项保存的数组 private int _size; //数据项的实际个数 private int _version; //数据项被修改过的次数,主要用户枚举过程中对于数据的修改 static T[] _emptyArray = new T[0]; //................其他部分 ｝ 数据项查找复杂度为O(n)； public int IndexOf(T item) { return Array.IndexOf(_items, item, 0, _size); } 下标查找复杂度为O(1)； 二、当数据空间不够时，扩大1倍空间 带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费（可以使用TrimExcess来缩紧）。 //获取与设置保存数据项数组的长度，注意在设置长度时所带来的开销 public int Capacity { get { return _items.Length; } set { if (value != _items.Length) { if (value _size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); } if (value 0) { //注意_size个元素复制开销,与原有对象丢弃后可引起cc启动的开销 T[] newItems = new T[value]; if (_size 0) { …… 阅读全文

摘要：这篇文章是一些与线性表相关的算法 1.如果顺序表中每个元素都是整数，设计用最少时间把所有值为负数的元素放在全部正数值元素的前面。 2.如果顺序表为非递减有序排列，试删除顺序表中多余的值相同的元素。 3.编写一个单链表逆置算法。 4.找出单链表的中间元素。 1.如果顺序表中每个元素都是整数，设计用最少时间把所有值为负数的元素放在全部正数值元素的前面。 分析：从左向右找到正数，从右到左找到负，将两者交换。循环直到 i 大于 j 为止。 public void Move(int[] list) { int i = 0, j = list.Length; int temp; while (i = j) { while (list[i] = 0) i++; while (list[j] = 0) j--; if (i j) { temp = list[i]; list[i] = list[j]; list[j] = temp; } } } 注意：①“用最少的时间”一词，②只要求将负数的元素移动到全部正数的前面。 2.如果顺序表为非递减有序排列，试删除顺序表中多余的值相同的元素。 分析：由于顺序表是非递减有序排序，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等则删除其中一个，否则继续向后查找。 public void Delete(int[] list) { int i = 0, j, len = list.Length; while (i len - 1) { if (list[i] != list[i + 1]) { i++; } else { for (j = i; j len; j++) { list[j] = list[j + 1]; } } } } 注意：顺序表删除一个元素的实现方法。 3.编写一个单链表逆置算法。 分析：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext； public static Link Reverse(NodeT head) { NodeT curr = head.Next; NodeT next = null; NodeT nextnext = nu…… 阅读全文

摘要：一、双向链表的表示 双链表是结点有两个引用域的链表：一个指向直接后继结点，一个指向直接前驱结点。这种类型定义如下： public class DNodeT { private T data; private DNodeT prev; private DNodeT next; public DNode(T data, DNodeT next) { this.data = data; this.next = next; } public DNode(T data) { this.data = data; this.next = null; } public DNode(DNodeT next) { this.next = next; } public DNode() { this.data = default(T); this.next = null; } public T Data { get { return this.data; } set { this.data = value; } } public DNodeT Next { get { return this.next; } set { this.next = value; } } public DNodeT Prev { get { return this.prev; } set { this.prev = value; } } } 二、双向链表的实现 在双链表中，有些操作(如取元素、定位等)算法中仅涉及后继结点，此时双向链表的算法和单链表的算法均相同，但对插入、删除操作，双向链表需同时修改后继和前驱两个引用，比单链表要复杂一些，其操作如下： public class DLinkListT { private DNodeT start; private int length; public DLinkList() { start = null; } public int Length { get { return this.length; } } public void InsertNode(T data) { if (start == null) …… 阅读全文

摘要：一、链表概述 线性表的链式表示就是采用链表实现存储，即表中数据元素是用一组任意的存储单元存储，它不要求逻辑上相邻的元素在物理位置上也相邻。这种数据结构有以下优点：其一，在进行插入和删除操作时，无需移动大量元素；其二，给长度变化较大的线性表无需预先分配最大空间；其三，表容量容易扩充。链表的特点是用一组任意的存储单元存储线性表的数据元素。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。 二、线性表的链式表示之单链表 由n个结点链接起来，且每个节点只包含一个引用域的链表称为单链表。 对单链表进行操作 1.初始化单链表 步骤： a.声明一个为结点类型的start变量，用来指向单链表的第一个结点。 b.在单链表的构造函数中将start变量的值赋为null。 2.插入操作 步骤： ①在单链表开头插入新的结点 a.为新结点分配内存并为数据字段分配值。 b.使新结点的next字段指向列表中的第一个结点。 c.是start指向新结点。 ②在单链表两个结点之间插入结点 a.为新结点分配内存并为数据字段分配值。 b.确定要在那两个结点之间插入新结点。将它们标记为前结点previous和当前结点current。找到前一个和当前结点，请执行步骤： ⑴.使previous指向null； ⑵使current指向第一个结点； ⑶如果新结点的序号大于当前结点的值，重复步骤⑷、⑸； ⑷使previous指向current； ⑸使current指向序列中的下一个结点。 c.使新结点的next字段指向当前结点。 d.使前一个结点的next字段指向新结点。 ③在单链表末尾插入一个新结点 a.为新结点分配内存并为数据字段分配值。 b.找到列表中的最后一个结点，将它标记为current。 c.是current的next字段指向新结点。 d.使新结点的next字段指向null，释放current空间。 3.删除操作 步骤： ①在单链表开头删除结点 a.将列表中的一个结点标记为当前结点。 b.使start指向单链表中的下一个结点。 c.释放标记为当前结点的内存。 ②在单链表两个结点之间删除结点 a.定位要删除的结点，请执行步骤： ⑴.将previ…… 阅读全文

摘要：一、线性表概念 一个线性表由有限且有序的数据项组成。数据项称为元素。 每个表元素有相同的类型。 空表不含任何元素。 线性表的长度定义为表中所含元素的个数。 表的第一个元素称为表头。 表的最后一个元素称为表尾。 有序表是指表中元素的值按位置顺序递增或递减。 无序表是指表中元素的值与位置没有关系。 表的表示: ( a0, a1, …, an-1) 二、线性表的操作 1.初始化操作 初始条件：线性表不存在。 操作结果：创建一个空的线性表。 2.插入操作：InsertNode(T a, int i) 初始条件：线性表存在，插入位置正确(i= i =n+1,n为插入前的表长)。 操作结果：在线性表的第i个位置上插入一个值为 a 的新元素，这样使得原序号为 i,i+1,...,n的数据元素的序号变为 i+1,i+2,...,n+1，插入后表长为 n+1。 3.删除操作：DeleteNode(int i) 初始条件：线性表存在且不为空，删除位置正确(1= i =n,n为删除前的表长)。 操作结果：在线性表中删除序号为 i 的数据元素，返回删除后的数据元素。删除后使得原序号为 i+1,i+2,...,n的数据元素的序号变为 i,i+1,...,n-1，插入后表长为 n-1。 4.取表元素：SearchNode(int i) 初始条件：线性表存在，所取数据元素位置正确(1= i =n,n为线性表的表长)。 操作结果：返回线性表中第 i 个数据元素。 5.定位元素：SearchNode(T value) 初始条件：线性表存在。 操作结果：在线性表中查找值为value的数据元素，其结果返回在线性表中首次出现的值为value的数据元素的序号，称为查找成功；否则，线性表中未找到值为value的数据元素，返回一个特殊值表示查找失败。 6.求表长：GetLength() 初始条件：线性表存在。 操作结果：返回线性表中所有数据元素的个数。 7.清空操作：Clear() 初始条件：线性表存在且有数据元素。 操作结果：从线性表中清除所有数据元素，线性表为空。 8.判断线性表是否为空：IsEmpty() 初始条件：线性表存在。 操作结果：如果线性表中不包含任何元素则返回true，否则返回false。 三、线性表的顺序表示 线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。顺序表的…… 阅读全文

摘要：创建型模式 FACTORY—追MM少不了请吃饭了，麦当劳的鸡翅和肯德基的鸡翅都是MM爱吃的东西，虽然口味有所不同，但不管你带MM去麦当劳或肯德基，只管向服务员说“来四个鸡翅”就行了。麦当劳和肯德基就是生产鸡翅的Factory1 工厂模式：客户类和工厂类分开。消费者任何时候需要某种产品，只需向工厂请求即可。消费者无须修改就可以接纳新产品。缺点是当产品修改时，工厂类也要做相应的修改。如：如何创建及如何向客户端提供。 BUILDER—MM最爱听的就是“我爱你”这句话了，见到不同地方的MM,要能够用她们的方言跟她说这句话哦，我有一个多种语言翻译机，上面每种语言都有一个按键，见到MM我只要按对应的键，它就能够用相应的语言说出“我爱你”这句话了，国外的MM也可以轻松搞掂，这就是我的“我爱你”builder。（这一定比美军在伊拉克用的翻译机好卖） 建造模式：将产品的内部表象和产品的生成过程分割开来，从而使一个建造过程生成具有不同的内部表象的产品对象。建造模式使得产品内部表象可以独立的变化，客户不必知道产品内部组成的细节。建造模式可以强制实行一种分步骤进行的建造过程。 FACTORY METHOD—请MM去麦当劳吃汉堡，不同的MM有不同的口味，要每个都记住是一件烦人的事情，我一般采用Factory Method模式，带着MM到服务员那儿，说“要一个汉堡”，具体要什么样的汉堡呢，让MM直接跟服务员说就行了。 工厂方法模式：核心工厂类不再负责所有产品的创建，而是将具体创建的工作交给子类去做，成为一个抽象工厂角色，仅负责给出具体工厂类必须实现的接口，而不接触哪一个产品类应当被实例化这种细节。 PROTOTYPE—跟MM用QQ聊天，一定要说些深情的话语了，我搜集了好多肉麻的情话，需要时只要copy出来放到QQ里面就行了，这就是我的情话prototype了。（100块钱一份，你要不要） 原始模型模式：通过给出一个原型对象来指明所要创建的对象的类型，然后用复制这个原型对象的方法创建出更多同类型的对象。原始模型模式允许动态的增加或减少产品类，产品类不需要非得有任何事先确定的等级结构，原始模型模式适用于任何的等级结构。缺点是每一个类都必须配备一个克隆方法。 SINGLETON—俺有6个漂亮的老婆，她们的老公都是我，我就是我们家里的老公Sigleton，她们只要说道“老…… 阅读全文

摘要：设计的初衷是提高代码质量 创业时，我们经常会讲到一个词：初心。这词说的其实就是，你到底是为什么干这件事。不管走多远、产品经过多少迭代、转变多少次方向，“初心”一般都不会随便改。当我们在为产品该不该转型、该不该做某个功能而拿捏不定的时候，想想它符不符合我们创业的初心，有时候就自然有答案了。 实际上，应用设计模式也是如此。应用设计模式只是方法，最终的目的，也就是初心，是提高代码的质量。具体点说就是，提高代码的可读性、可扩展性、可维护性等。所有的设计都是围绕着这个初心来做的。 所以，在做代码设计的时候，你一定要先问下自己，为什么要这样设计，为什么要应用这种设计模式，这样做是否能真正地提高代码质量，能提高代码质量的哪些方面。如果自己很难讲清楚，或者给出的理由都比较牵强，没有压倒性的优势，那基本上就可以断定这是一种过度设计，是为了设计而设计。 实际上，设计原则和思想是心法，设计模式只是招式。掌握心法，以不变应万变，无招胜有招。所以，设计原则和思想比设计模式更加普适、重要。掌握了设计原则和思想，我们能更清楚地了解为什么要用某种设计模式，就能更恰到好处地应用设计模式，甚至我们还可以自己创造出来新的设计模式。 设计的过程是先有问题后有方案 如果我们把写出的代码看作产品，那做产品的时候，我们先要思考痛点在哪里，用户的真正需求在哪里，然后再看要开发哪些功能去满足，而不是先拍脑袋想出一个花哨的功能，再去东搬西凑硬编出一个需求来。 代码设计也是类似的。我们先要去分析代码存在的痛点，比如可读性不好、可扩展性不好等等，然后再针对性地利用设计模式去改善，而不是看到某个场景之后，觉得跟之前在某本书中看到的某个设计模式的应用场景很相似，就套用上去，也不考虑到底合不合适，最后如果有人问起了，就再找几个不痛不痒、很不具体的伪需求来搪塞，比如提高了代码的扩展性、满足了开闭原则等等。 实际上，很多没有太多开发经验的新手，往往在学完设计模式之后会非常“学生气”，拿原理当真理，不懂得具体问题具体分析，手里拿着锤子看哪都是钉子，不分青红皂白，上来就是套用某个设计模式。写完之后，看着自己写的很复杂的代码，还沾沾自喜，甚至到处炫耀。这完全是无知地炫技，半瓶子不满大抵就是这个样子的。等你慢慢成长之后，回过头来再看自己当年的代码。 学习设计模式最重要的是培养分析问题、解决问题的能力。这样，看到某段代码之后，你就能够自…… 阅读全文

摘要：访问者模式：表示一个作用于某对象结构中的各元素的操作，它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。 大部分设计模式的原理和实现都很简单，不过也有例外，比如今天要讲的访问者模式。它可以算是 23 种经典设计模式中最难理解的几个之一。因为它难理解、难实现，应用它会导致代码的可读性、可维护性变差，所以，访问者模式在实际的软件开发中很少被用到，在没有特别必要的情况下，建议不要使用访问者模式。 访问者模式诞生的思维过程 假设我们从网站上爬取了很多资源文件，它们的格式有三种：PDF、PPT、Word。我们现在要开发一个工具来处理这批资源文件。这个工具的其中一个功能是，把这些资源文件中的文本内容抽取出来放到 txt 文件中。 实现这个功能并不难，不同的人有不同的写法，我将其中一种代码实现方式贴在这里。其中，ResourceFile 是一个抽象类，包含一个抽象方法 Extract2txt()。PdfFile、PPTFile、WordFile 都继承 ResourceFile 类，并且重写了 Extract2txt() 方法。在 ToolApplication 中，我们可以利用多态特性，根据对象的实际类型，来决定执行哪个方法。 public abstract class ResourceFile { protected string filePath; public ResourceFile(string filePath) { this.filePath = filePath; } public abstract void Extract2txt(); } public class PPTFile : ResourceFile { public PPTFile(string filePath):base(filePath) { } public override void Extract2txt() { //...省略一大坨从PPT中抽取文本的代码... //...将抽取出来的文本保存在跟filePath同名的.txt文件中... Console.WriteLine(Extract PPT.); } …… 阅读全文

摘要：解释器模式：为某个语言定义它的语法（或者叫文法）表示，并定义一个解释器用来处理这个语法。 解释器模式为某个语言定义它的语法（或者叫文法）表示，并定义一个解释器用来处理这个语法。实际上，这里的“语言”不仅仅指我们平时说的中、英、日、法等各种语言。从广义上来讲，只要是能承载信息的载体，我们都可以称之为“语言”，比如，古代的结绳记事、盲文、哑语、摩斯密码等。 要想了解“语言”要表达的信息，我们就必须定义相应的语法规则。这样，书写者就可以根据语法规则来书写“句子”（专业点的叫法应该是“表达式”），阅读者根据语法规则来阅读“句子”，这样才能做到信息的正确传递。而我们要讲的解释器模式，其实就是用来实现根据语法规则解读“句子”的解释器。 解释器模式的代码实现比较灵活，没有固定的模板。应用设计模式主要是应对代码的复杂性，解释器模式也不例外。它的代码实现的核心思想，就是将语法解析的工作拆分到各个小类中，以此来避免大而全的解析类。一般的做法是，将语法规则拆分一些小的独立的单元，然后对每个单元进行解析，最终合并为对整个语法规则的解析。 实战 接下来我们用解释起模式来实现一个自定义的接口告警规则： 在我们平时的项目开发中，监控系统非常重要，它可以时刻监控业务系统的运行情况，及时将异常报告给开发者。比如，如果每分钟接口出错数超过 100，监控系统就通过短信、微信、邮件等方式发送告警给开发者。 一般来讲，监控系统支持开发者自定义告警规则，比如我们可以用下面这样一个表达式，来表示一个告警规则，它表达的意思是：每分钟 API 总出错数超过 100 或者每分钟 API 总调用数超过 10000 就触发告警。 api_error_per_minute 100 || api_count_per_minute 10000 在监控系统中，告警模块只负责根据统计数据和告警规则，判断是否触发告警。至于每分钟 API 接口出错数、每分钟接口调用数等统计数据的计算，是由其他模块来负责的。其他模块将统计数据放到一个字典中（数据的格式如下所示），发送给告警模块。接下来，我们只关注告警模块。 为了简化讲解和代码实现，我们假设自定义的告警规则只包含“||、、、、”这五个运算符，其中，“、、”运算符的优先级高于“||、”运算符，“”运算符优先级高于“||”。在表达式中，任意元素之间需要通过空格来分隔。除此之外，用…… 阅读全文

摘要：备忘录模式：在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态。这样以后就可以将该对象恢复到原先保持的状态 备忘录模式也叫快照模式，这个模式的定义表达了两部分内容：一部分是存储副本以便后期恢复；另一部分是要在不违背封装原则的前提下，进行对象的备份和恢复。 备忘录模式的应用场景也比较明确和有限，主要是用来防丢失、撤销、恢复等。它跟平时我们常说的“备份”很相似。两者的主要区别在于，备忘录模式更侧重于代码的设计和实现，备份更侧重架构设计或产品设计。 对于大对象的备份来说，备份占用的存储空间会比较大，备份和恢复的耗时会比较长。针对这个问题，不同的业务场景有不同的处理方式。比如，只备份必要的恢复信息，结合最新的数据来恢复；再比如，全量备份和增量备份相结合，低频全量备份，高频增量备份，两者结合来做恢复。 下面用保存游戏进度的示例来看一下备忘录模式的实现： class GameRole { public int Vitality { get; set; } public int Attack { get; set; } public int Defense { get; set; } public void StateDisplay() { Console.WriteLine(角色当前状态:); Console.WriteLine($生命力：{Vitality}); Console.WriteLine($攻击力：{Attack}); Console.WriteLine($防御力：{Defense}); Console.WriteLine(); } public void GetInitState() { Vitality = 100; Attack = 100; Defense = 100; } public void Fight() { Vitality = 0; Attack = 0; Defense = 0; //与大Boss战斗后死亡 } //…… 阅读全文