XIAOSUO 记录个人学习的足迹

摘要：首先写一个二叉树的C#实现，这是我们的基石： public class BinNode { public int Element; public BinNode Left; public BinNode Right; public BinNode(int element, BinNode left, BinNode right) { this.Element = element; this.Left = left; this.Right = right; } public bool IsLeaf() { return this.Left == null this.Right == null; } } 一、怎样从顶部开始逐层打印二叉树结点数据 有2种算法： 算法1：基于Queue来实现，也就是广度优先搜索（BFS）的思想 static void PrintTree1(BinNode root) { if (root == null) return; BinNode tmp = null; Queue queue = new Queue(); queue.Enqueue(root); while (queue.Count 0) { tmp = (BinNode)queue.Dequeue(); Console.WriteLine(tmp.Element); if (tmp.Left != null) queue.Enqueue(tmp.Left); if (tmp.Right != null) queue.Enqueue(tmp.Right); } } 话说，BFS和DFS思想本来是用于图的，但我们不能被传统的思维方式所束缚。 算法2：基于单链表实现 如果没有Queue给我们用，我们只好使用单链表，把每个节点存在单链表的Data中，实现如下： public class Link { public Link Next; public B…… 阅读全文

摘要：一、概念 树的路径长度：树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。** **　　结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和，通常记为： 其中： n表示叶子结点的数目 wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。 树的带权路径长度亦称为树的代价。 哈夫曼树或最优二叉树：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为哈夫曼树或最优二叉树。 【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为： (a)WPL=72+52+22+42=36 (b)WPL=73+53+21+42=46 (c)WPL=71+52+23+43=35 其中(c)树的WPL最小，可以验证，它就是哈夫曼树。 注意： ① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 ② 最优二叉树中，权越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，WPL最小。 二、构造最优二叉树 **　　**哈夫曼算法经常用来解决编码方面的问题，运用这种方式的编码我们称做哈夫曼编码，它是一种变长编码，其优点是可以根据字符出现的不同频率来节省空间。假设给定8个叶子结点Z、K、F、C、U、D、L、E，分别带权2、7、24、32、37、42、42、120，我们来看看这组数的哈夫曼编码过程。 最终的哈夫曼树，我们加入编码后的效果如下图： 前缀特性：一组编码中，其他任何字符的编码都不是某个字符编码的前缀。 DEED的编码: 10100101 1011001110111101的解码: DUCK 每个字符的平均编码位数：Σ(ci*fi) / fT= 785 / 306 = 2.56536 三、哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。其基本思想是： (1)根据给定的n个权值wl，w2，…，wn构成n棵二叉树的森林F={T1，T2，…，…… 阅读全文

摘要：一、定义 二叉查找(搜索)树(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月等的情况都考…… 阅读全文