XIAOSUO 记录个人学习的足迹

摘要：希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。 一、基本思想 　　对待排记录序列先作“宏观”调整，再作“微观”调整。 　　所谓“宏观”调整，指的是 “跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。假设将n个记录分成d个子序列，则这d个子序列分别为： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] } 　　其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。 　　下图为希尔排序示意图： 　　　　 二、希尔排序的实现 public class ShellSort { public static Listint Demo(Listint data) { for (int gap =(int) Math.Floor(((decimal)(data.Count / 2))); gap 0; gap = (int)Math.Floor(((decimal)(gap / 2)))) { for (var i = gap; i data.Count; i++) { var j = i; var current = data[i]; while (j - gap = 0 current data[j - gap]) { data[j] = data[j - gap]; j = j - gap; } data[j] = current; } } return data; } } 三、时间复杂度分析 　　大量研究证明，若增量序列的取值比较合…… 阅读全文

摘要：插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的数据序列的适当位置，直到全部记录插入完成为止。 一、基本思想 　　假设待排序的记录存放在数组R[0…n-1]中。初始时，R[0]自成1个有序区，无序区为R[1…n-1]。从i=1起直至i= n-1为止，依次将R[i]插入当前的有序区R[0…i-1]中，生成含n个记录的有序区。 　　通常将一个记录Ri插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i趟插入排序。 　　排序过程的某一中间时刻，R被划分成两个子区间R[0…i-1]（已排好序的有序区）和[i…n-1]（当前未排序的部分，可称无序区）。 　　插入排序的基本操作是将当前无序区的第1个记录R[0]插人到有序区R[0…i-1]中适当的位置上，使 R[0…i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。 　　下图为插入排序是示意图： 　　　　 二、插入排序的实现 public class InsertSort { public static Listint Demo(Listint data) { int preIndex, currentIndex; for (var i = 1; i data.Count; i++) { preIndex = i - 1; currentIndex = data[i]; while (preIndex = 0 data[preIndex] currentIndex) { data[preIndex + 1] = data[preIndex]; preIndex--; } data[preIndex + 1] = currentIndex; } return data; } } 三、时间复杂度分析 　　插入排序算法的时间复杂度分为最好、最坏和随机三种情况： 　　　　（1）最好的情况是关键字在序列中顺序…… 阅读全文

摘要：　　设树T如下图所示，结点R是根，根的子树从左到右依次为T1，T2，…，Tk。 　　　　 一、树的前序遍历 　　若树T非空，则： 　　　　①访问根结点R； 　　　　②依次前序遍历根R的各子树T1，T2，…，Tk。 　　先序遍历树结点算法实现如下： //先序遍历树结点 public void PreOrder(MLNodeT root) { if (root == null) { re... 阅读全文

摘要：　　树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。 一、树转换为二叉树 　　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树： 　　①在所有兄弟结点之间加一连线； 　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。... 阅读全文

摘要：三、 孩子链表表示法 孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 　　下面的(a)图就是用孩子链表表示法来存储图中的树。 　　　　 　　注意： 　　① 孩子结点的数据域仅存放了它们在向量空间的序号。 　　② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 　　③ 将双亲链表表示法和孩子... 阅读全文

摘要：一、多重链表表示法 　　由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法被称为多重链表法。 　　一个树中各结点的度数各异，因此结点的指针域个数有两种设置方法。方法① 每个结点指针域个数等于该结点的度数... 阅读全文

摘要：一、树和森林的定义 　　树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： 　　　　(1)有且仅有一个特定的称为根(Root)的结点； 　　　　(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树。 　　森林(Forest)是m(m≥0)棵互不相交的树的集合。 　　树和森林的概念相近。删去一棵... 阅读全文

摘要：一、怎样从顶部开始逐层打印二叉树结点数据 二、设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。 三、如何不用递归实现二叉树的前序/后序/中序遍历 四、在二叉树中找出和为某一值的所有路径 阅读全文

摘要：一、概念 　　树的路径长度：树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。** **　　结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 　　结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 　　树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和... 阅读全文

摘要：二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉查找树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉查找树。 　　上述性质简称二叉查找树性质(BST性质)，故二叉查找树实际上是满足BST性质的二叉树。 阅读全文