XIAOSUO 记录个人学习的足迹

摘要：一、顺序存储结构表示二叉树 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系。 　　 对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。 二、二叉链表结构表示二叉树 二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链表来指示着元素的逻辑关系。 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。下图为一棵二叉树的二叉链表示。 三、三叉链表结构表示二叉树 在三叉链表存储中，每个结点由四个域组成 。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…… 阅读全文

摘要：一、SubString方法的实现 如果理解了上一篇文章中介绍的FastAllocateString方法与wstrcpy方法，理解SubString方法的实现就会比较容易。此方法的两个重载都会先调用一个参数的校验函数InternalSubStringWithChecks。如果没有发生异常就会继续调用内部实现的核心方法InternalSubString，该方法在内部实现获取[startIndex, startIndex + length]之间的字串。具体代码如下 //返回从startIndex开始到结束的字符串 public String Substring (int startIndex) { return this.Substring (startIndex, Length-startIndex); } public String Substring (int startIndex, int length) { return InternalSubStringWithChecks(startIndex, length, false); } //采用手术室清洁策略来对参数进行检验 internal String InternalSubStringWithChecks (int startIndex, int length, bool fAlwaysCopy) { int thisLength = Length; if (startIndex0) { throw new ArgumentOutOfRangeException(startIndex, Environment.GetResourceString(ArgumentOutOfRange_StartIndex)); } if (startIndex thisLength) { throw new ArgumentOutOfRangeException(startIndex, Environment.GetResourceString(ArgumentOutOfRange_StartIndexLargerThanLength)); } if (length0) { throw new ArgumentOutOfRangeException(length, Envi…… 阅读全文

摘要：一、字符串类的概述 String类继承了IComparable、ICloneable、IConvertible、IEnumerable接口，以便调用者枚举、拷贝、转换容器中的字符。同时还继承了IComparable, IEnumerable, IEquatable，这表示源代码的编写者考虑到了对泛型的支持。如果使用C# 2.0以上标准的编译器编译代码，那么String类还需要继承这三个泛型接口。 String类是.NET Framework中最为重要的类型之一。 不可变对象，提供了多种字符串操作函数。 为StringBuilder类提供基础方法。 为了保证执行效率，String类的性能关键部分采用非托管C++代码编写： - 数据寻址：例如：get_Chars等； - 内存分配：例如：FastAllocateString等； - 内存复制，移动。 二、System.String源代码的组成 String.cs实现主要源代码，其他多个源代码文件实现辅助和基础操作功能。 托管代码部分： – unsafecharbuffer.cs / buffer.cs提供辅助数据操作； – CultureInfo.cs/CompareInfo.cs为字符串比较，大小写处理提供和文化区域相关的代码实现； – Normalization提供规格化处理。 非托管代码部分： – Ecall.cpp / ecall.h实现托管代码到非托管代码映射，FCFuncStart(gStringFuncs)部分； – Object.h实现String类的非托管结构映射和基本取值操作的功能； – Comstring.cpp实现复杂字符串操作； – Comnlsinfo.cpp/.h提供与文化区域相关的复杂字符串操作。 三、类的声明 在String类一开始定义了3个非常重要的私有变量m_arrayLength、m_stringLength和m_firstChar，这3个私有变量在非托管代码中也会拥有同样的声明。以保证托管代码到非托管代码的映射。 public sealed class String : IComparable, ICloneable, IConvertible, IEnumerable, IComparableString, IEnumerablechar, IEquatableString…… 阅读全文