XIAOSUO 记录个人学习的足迹

摘要：一、定义 二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉查找树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉查找树。 上述性质简称二叉查找树性质(BST性质)，故二叉查找树实际上是满足BST性质的二叉树。 二、特点 由BST性质可得： （1） 二叉查找树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉查找树中，各结点关键字是惟一的。注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉查找树定义中BST性质(1)里的小于改为大于等于，或将BST性质(2)里的大于改为小于等于，甚至可同时修改这两个性质。 （3） 按中序遍历该树所得到的中序序列是一个递增有序序列。如下图所示的两棵树均是二叉查找树，它们的中序序列均为有序序列：2，3，4，5，7，8。 三、插入运算 在二叉查找树中插入新结点，要保证插入后仍满足BST性质。其插入过程是： (a)若二叉查找树T为空，则为待插入的关键字key申请一个新结点，并令其为根； (b)若二叉查找树T不为空，则将key和根的关键字比较： (i)若二者相等，则说明树中已有此关键字key，无须插入。 (ii)若keyT→key，则将key插入根的左子树中。 (iii)若keyT→key，则将它插入根的右子树中。 子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉查找树中，或者直到发现树中已有此关键字为止。 注意：输入序列决定了二叉查找树的形态。二叉查找树的中序序列是一个有序序列。所以对于一个任意的关键字序列构造一棵二叉查找树，其实质是对此关键字序列进行排序，使其变为有序序列。因此，人们又常常将二叉查找树称为二叉排序树。通常将这种排序称为树排序(Tree Sort)，可以证明这种排序的平均执行时间亦为O(nlgn)。对相同的输入实例，树排序的执行时间约为堆排序的2至3倍。因此在一般情况下，构造二叉排序树的目的并非为了排序，而是用它来加速查找，这是因为在一个有序的集合上查找通常比在无序集合上查找更快，“查找树的名称也由此而来。 四、删除运算…… 阅读全文

摘要：一、先序遍历（DLR） 先序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1） 访问根结点； （2）先序遍历根结点的左子树； （3） 先序遍历根结点的右子树。 算法实现如下： //前序遍历 public void preorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree is empty); return; } if (ptr != null) { Console.Write(ptr.Data + ); preorder(ptr.LChild); preorder(ptr.RChild); } } 二、中序遍历（LDR） 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 算法实现如下： //中序遍历 public void inorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree is empty); return; } if (ptr != null) { inorder(ptr.LChild); Console.Write(ptr.Data + ); inorder(ptr.RChild); } } 三、后序遍历（LRD） 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。 （3）访问根结点； 算法实现如下： //后序列遍历 public void postorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree is empty); return; } if (ptr != null) { postorder(ptr.LChild); postorder(ptr.RChild); Console.Write(ptr.Data + ); } } 四、层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 算法实现如下：…… 阅读全文

摘要：一、顺序存储结构表示二叉树 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系。 　　 对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。 二、二叉链表结构表示二叉树 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链表来指示着元素的逻辑关系。 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。下图为一棵二叉树的二叉链表示。 三、三叉链表结构表示二叉树 在三叉链表存储中，每个结点由四个域组成 。parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点。下图为一棵二叉树的三叉链表示。 四、二叉树的实现** 尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还要节省空间。因此二叉链表是最常用的二叉树存储方法。下面将介绍二叉链表存储方法的二叉树实现。 首先我们来看下结点结构的代码： public class NodeT { private T data; //数据域 private NodeT lChild; //左孩子 private NodeT rChild; //右孩子 //构造函数 public Node(T val, NodeT lp, NodeT rp) { data = val; lChild = lp; rChild = rp; } //构造函数 public Node(NodeT lp, NodeT rp) { data = default(T); lChild = lp; rChild = rp; } //构造函数 public Node(T val) { data = val; lChild = null; rChild = null; } /…… 阅读全文

摘要：一、二叉树的定义 二叉树（Binary Tree）是n(n≥0)个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 二叉树的5中形态 二、二叉树的相关术语 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。 （5）路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤ik）,就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。 （6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。 （7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 （8）树的深度。树中所有结点的最大层数称为树的深度。 （9）树的度。树中各结点度的最大值称为该树的度。 （10）满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 （11）完全二叉树。一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 三、二叉树的基本操作 1.Initiate（bt）：建立一棵空二叉树。 2.Create（x，lbt，rbt）：生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。 3.InsertL（bt，x，parent）：将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的…… 阅读全文

摘要：一、稀疏矩阵的定义 对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。 人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。 二、稀疏矩阵的压缩存储 由于稀疏矩阵中非零元素较少，零元素较多，因此可以采用只存储非零元素的方法来进行压缩存储。 由于非零元素分布没有任何规律，所以在进行压缩存储的时侯需要存储非零元素值的同时还要存储非零元素在矩阵中的位置，即非零元素所在的行号和列号，也就是在存储某个元素比如aij的值的同时，还需要存储该元素所在的行号i和它的列号j，这样就构成了一个三元组(i,j,aij)的线性表。 三元组可以采用顺序表示方法，也可以采用链式表示方法，这样就产生了对稀疏矩阵的不同压缩存储方式。 a、稀疏矩阵的顺序实现 若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。 顺序表中除了存储三元组外，还应该存储矩阵行数、列数和总的非零元素数目，这样才能唯一的确定一个矩阵。 顺序存储结构存储三元组线性表的C#代码如下： struct tupletypeT { public int i;//行号 public int j;//列号 public T v; //元素值 public tupletype(int i, int j, T v) { this.i = i; this.j = j; this.v = v; } } class spmatrixT { int MAXNUM;//非零元素的最大个数 int md;//行数值 int nd;//列数值 int td;//非零元素的实际个数 tupletypeT[] data;//存储非零元素的值及一个表示矩阵行数、列数和总的非零元素数目的特殊三元组 } b、稀疏矩阵的十字链表实现 十字链表结点分为三类 : 表结点，它由五个域组成，其中i和j存储的是结点所在的行和列，right和down存储的是指向十字链表中该结点所有行和列的下一个结点的指针，v用于存放元素值。 行头和列头结点，这类结点也有域组成，其中行和列的值均为零，没有实际意义，right和down的域用于在行方向和列方向上指向表结点，next用于指向下一个…… 阅读全文

摘要：一、特殊矩阵的定义 对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，被称之为特殊矩阵。特殊矩阵通常有： 对角矩阵（d i a g o n a l）：M是一个对角矩阵当且仅当i≠j 时有M(i, j) = 0。下图a 所示。 三对角矩阵（ t r i d i a g o n a l）：M是一个三对角矩阵当且仅当| i - j | 1 时有M(i, j ) = 0。下图b 所示。 下三角矩阵（lower triangular）：M是一个下三角矩阵当且仅当i j 时有M (i, j ) = 0。下图c 所示。 上三角矩阵（upper triangular）：M是一个上三角矩阵当且仅当i j 时有M (i, j ) = 0。下图d 所示。 对称矩阵（s y m m e t r i c）：M是一个对称矩阵当且仅当对于所有的i 和j 有M (i, j ) =M (j, i )。下图e 所示。 二、特殊矩阵的压缩存储 由于对称矩阵中的元素关于主对角线对称，为了节省空间，可以为每一对称元素只分配一个存储空间，存储时只存储对称矩阵中的上三角或下三角中的元素 ,这样存储单元的总数是：　 可以以行序为主进行压缩存储，也可以以列序为主进行压缩存储。假设以行序为主进行压缩存储，可以用一个一维数组b(n(n+1)/2)作为n阶对称矩阵a的存储结构，则b[k]和矩阵元素aij之间存在如下一对应关系： 阅读全文

摘要：一、概述 数组的定义： 数组是由n(n≧1)个相同类型的数据元素组成的有限序列，数组中的每一个数据通常为数据元素 。 数组中的元素可以通过下标随机访问，其中下标的个数由组数的维数决定。 数组可以看作是线性表的推广，一维数组为按顺序存储的线性表，二维数组为数据元素类型为一维数组的线性表，三维数组为数据元素类型为二维数组的线性表，依此类推。 数组的特点： 数组中的数据元素数目确定。一旦定义了一个数组，其数据元素的数目不再增减； 数组中的数据元素具有相同的数据类型； 数组中的每个数据元素都和一组唯一的下标值对应； 数组是一种随机存储结构，可随机存取数组中的任意数据元素。 二、数组的操作 1.随机存，给定一组下标，修改相应数据元素中的值：SetValue(Object value,int index)　　 2.随机取，给定一组下标，获取对应数据元素的值：GetValue(int index) 3.获取数组元素的个数：Length{get;} 4.获取数组的秩（维数）Rank { get; } 5.将数组设置为零、false 或null，具体取决于元素类型：Clear(Array array, int index, int length) 6.从第一个元素开始复制数组中的一系列元素到另一数组中：Copy(Array sourceArray, Array destinationArray, int length) 7.将一维数组的所有元素复制到指定的一维数组Array中：CopyTo(Array array, int index) 8.获取数组指定维中的元素数：GetLength(int dimension) 9.对整个一维数组中的元素进行排序：Sort(Array array) 10.反转一维数组：Reverse(Array array) 11.数组指定维度的下限与上限：GetLowerBound(int dimension)和GetUpperBound(int dimension) 三、数组的顺序表示 对于一维数组，可根据数组元素的下标得到它的存储地址，也可根据下标来访问一维数组中的元素 。 对于多维数组，需要把多维的下标表达式转换成一维的下标表达式。这产生了两种存储方式：一种是以行序为主序（先行后列）的顺序存放，另一种是以列序为主序（先列后行）的顺序存放。 二维数组的…… 阅读全文

摘要：\d+$ //非负整数（正整数 + 0） [0-9][1-9][0-9]$ //正整数 ((-\d+)|(0+))$ //非正整数（负整数 + 0） -[0-9][1-9][0-9]$ //负整数 -?\d+$ //整数 \d+(.\d+)?$ //非负浮点数（正浮点数 + 0） (([0-9]+.[0-9][1-9][0-9])|([0-9][1-9][0-9].[0-9]+)|([0-9][1-9][0-9]))$ //正浮点数 ((-\d+(.\d+)?)|(0+(.0+)?))$ //非正浮点数（负浮点数 + 0） (-(([0-9]+.[0-9][1-9][0-9])|([0-9][1-9][0-9].[0-9]+)|([0-9][1-9][0-9])))$ //负浮点数 (-?\d+)(.\d+)?$ //浮点数 [A-Za-z]+$ //由26个英文字母组成的字符串 [A-Z]+$ //由26个英文字母的大写组成的字符串 [a-z]+$ //由26个英文字母的小写组成的字符串 [A-Za-z0-9]+$ //由数字和26个英文字母组成的字符串 \w+$ //由数字、26个英文字母或者下划线组成的字符串 [a-zA-z]+://(\w+(-\w+))(.(\w+(-\w+)))(?\S)?$ //url /(d{2}|d{4})-((0([1-9]{1}))|(1[1|2]))-((0-2)|(3[0|1]))$/ // 年-月-日 /((0([1-9]{1}))|(1[1|2]))/((0-2)|(3[0|1]))/(d{2}|d{4})$/ // 月/日/年 ^([w-.]+)@(([[0-9]{1,3}.[0-9]{1,3}.[0-9]{1,3}.)|(([w-]+.)+))([a-zA-Z]{2,4}|[0-9]{1,3})(]?)$ //Email (d+-)?(d{4}-?d{7}|d{3}-?d{8}|d{7,8})(-d+)? //电话号码 (d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5])$ //IP地址 YYYY-MM-DD基本上把闰年和2月等的情况都考…… 阅读全文

摘要：尽管String类和StringBuilder类提供了一套方法用来处理基于字符串的数据，但是RegEx和它的支持类却为字符串处理任务提供了更强大的功能。字符串的处理主要包括寻找字符串中的模式（模式匹配），以及通过称为正则表达式的特殊语言来执行操作。本问主要介绍正则表达式的方法以及如果利用它们解决普通文本处理任务。 一、正则表达式概述 简单的说，正则表达式是一种可以用于文字模式匹配和替换的强有力的工具。是由一系列普通字符和特殊字符组成的能明确描述文本字符串的文字匹配模式。正则表达式并非一门专用语言，但也可以看作是一种语言，它可以让用户通过使用一系列普通字符和特殊字符构建能明确描述文本字符串的匹配模式。除了简单描述这些模式之外，正则表达式解释引擎通常可用于遍历匹配，并使用模式作为分隔符来将字符串解析为子字符串，或以智能方式替换文本或重新设置文本格式。正则表达式为解决与文本处理有关的许多常见任务提供了有效而简捷的方式。 二、使用正则表达式 为了使用正则表达式需要把RegEx类引入程序。大家可以在System.Text.RegularExpression命名空间中找到这个类。一旦把这个类导入到程序，就需要决定想要用RegEx类来做什么事情了。如果想要进行匹配，就需要使用Match类。如果打算做替换，就需要使用RegEx类的Replace方法。我们先来看一个匹配的操作： Regex reg = new Regex(the); string str = the quick brown fox jumped over the lazy dog; Match matchSet = reg.Match(str); int matchPos; if (matchSet.Success) { matchPos = matchSet.Index; Console.WriteLine(found match at position: + matchPos); } 上面程序中Match类为存储用来与正则表达式进行匹配的数据提供了方法。如果属性Success返回true，那么正则表达式在字符串中至少匹配了一条字串，否则Success返回false。程序还可以有另外一种方法来查看是否匹配成功。通过把正则表达式和目标字符串传递给IsMatch方法可以对正则表达式进行预测试。 如Regex.…… 阅读全文

摘要：一、概述 可变长度的字符串操作类。 以System.String为其数据保存和操作基础。 在字符串操作过程中减少了对象创建次数，但很多情况下仍然会有额外对象创建出来。 二、类的声明 Stringbuilder中有两个非常重要的字段m_currentThread和m_StringValue。前者保存的是Stringbuilder对象拥有者的线程id，用于判断多线程情况下操作Stringbuilder对象是否需要创造副本；后者是以个String类型的对象，用于保存Stringbuilder的实际数据对象，这就说明Stringbuilder是以System.String对象来保存和操作的。 public sealed class StringBuilder : ISerializable { internal IntPtr m_currentThread = Thread.InternalGetCurrentThread(); //对象拥有者的线程id internal volatile String m_StringValue = null; //保存stringbuilder的实际数据的对象 //other code } 三、构造函数 提供7种构造的重载形式用来构建对象，其中有一种是私有重载用于对象的序列化。其他6种重载中主要的代码结构如下 public StringBuilder(String value, int startIndex, int length, int capacity) { if (capacity0) { throw new ArgumentOutOfRangeException(capacity, String.Format(CultureInfo.CurrentCulture, Environment.GetResourceString(ArgumentOutOfRange_MustBePositive), capacity)); } if (length0) { throw new ArgumentOutOfRangeException(length, String.Format(CultureInfo.CurrentCulture, En…… 阅读全文