XIAOSUO 记录个人学习的足迹

摘要：选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的最后，直到全部记录排序完毕。 一、基本思想 选择排序是一种简单且直观的排序方法。选择排序的做法是：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。 在选择排序中，每次排序完成一个记录的排序，也就是找到了当前剩余记录中关键字最小的记录的位置，n-1次排序就对n-1个记录进行了排序，此时剩下的一个记录必定是原始序列中关键码最大的，应排在所有记录的后面，因此具有n个记录的序列要做n-1次排序。 下图为选择排序的示意图： 从上图中我们可以看出，在初始关键字序列中，10是当前最小的关键字，因此在第一趟排序过程中，10和70互换；在第二趟排序时，20是从第二个记录30开始的最小关键字，互换20与30；依此类推……。 二、选择排序的实现 public class SelectSort { public static Listint Demo(Listint data) { int minIndex, temp; for (var i = 0; i data.Count - 1; i++) { minIndex = i; for (var j = i + 1; j data.Count; j++) { if (data[j] data[minIndex]) { minIndex = j; } } temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } return data; } } 三、时…… 阅读全文

摘要：希尔排序(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）最好的情况是关键字在序列中顺序有序。这时外层循环的比较次数为n-1，i…… 阅读全文

摘要：设树T如下图所示，结点R是根，根的子树从左到右依次为T1，T2，…，Tk。 一、树的前序遍历 若树T非空，则： ①访问根结点R； ②依次前序遍历根R的各子树T1，T2，…，Tk。 先序遍历树结点算法实现如下： //先序遍历树结点 public void PreOrder(MLNodeT root) { if (root == null) { return; } //访问根结点 Console.Write(root.Data + ); //按先序访问子树结点 for (int i = 0; i root.Childs.Length; i++) { PreOrder(root.Childs[i]); } } 二、树的后序遍历 若树T非空，则： ①依次后序遍历根T的各子树Tl，T2，…，Tk； ②访问根结点R。 后序遍历树结点算法实现如下： //后序遍历树结点 public void PostOrder(MLNodeT root) { if (root == null) { return; } //按先序访问子树结点 for (int i = 0; i root.Childs.Length; i++) { if (root.Childs[i] != null) { PostOrder(root.Childs[i]); } } //访问根结点 Console.Write(root.Data + ); } 三、树的层序遍历 按照树的结构从上到下、从左到右的顺序访问树的结点。 层序遍历树结点算法实现如下： //层序遍历 public void BroadOrder(MLNodeT root) { Console.WriteLine(遍历开始:); if (root == null) { Console.WriteLine(没有结点！); return; } MLNodeT tmp = root; Queue que = new Queue(); //根结点入队列 que.Enqueue(tmp); while (que.Count 0) { //结点出队列并访问 tmp = (ML…… 阅读全文

摘要：树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。 一、树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树： ①在所有兄弟结点之间加一连线； ②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。 下面(a)图所示的树可转换为(c)图所示的二叉树。 　　 注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 二、森林转换为二叉树 具体方法是： ① 将森林中的每棵树变为二叉树 ② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。 下图中，左边包含三棵树的森林可转换为右边的二叉树。 **　　** 三、二叉树转换为树或森林 把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。 阅读全文

摘要：三、 孩子链表表示法 孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 下面的(a)图就是用孩子链表表示法来存储图中的树。 注意： ① 孩子结点的数据域仅存放了它们在向量空间的序号。 ② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 ③ 将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。 孩子链表实现树形结构的代码如下： public class ChildNode { private int pos; private ChildNode nextChild; public ChildNode() { pos = -1; nextChild = null; } public ChildNode(int p, ChildNode nc) { pos = p; nextChild = nc; } //孩子结点在一维数组中的位置序号 public int Pos { get { return pos; } set { pos = value; } } //下一个孩子结点的地址信息 public ChildNode NextChild { get { return nextChild; } set { nextChild = value; } } } public class CLNodeT { private T data; private ChildNode firstChild; public CLNode(){ data = default(T); firstChild = null; } public CLNode(T d, ChildNode c) { data = d; firstChild = c; } //孩子结点的数据信息 public T Data { get { return data; } set { data = value; } } //第一个孩子结点的信息 public ChildNode FirstChild { get { return firstChild; } set { fi…… 阅读全文

摘要：一、多重链表表示法 由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法被称为多重链表法。 一个树中各结点的度数各异，因此结点的指针域个数有两种设置方法。方法① 每个结点指针域个数等于该结点的度数；方法② 每个结点指针域个数等于该树的度数。对于方法①它虽然在一定程度上节约了存储空间，但由于树中各个结点的度数是不相同的，各种操作不容易实现，所以一般采用方法②来实现多重链表法。显然，该方法适用于各个结点的度相差不大的情况。 下图为多重链表表示存储结构示意图 双重链表实现树形结构的代码如下： public class MLNodeT { //存储结点的数据 private T data; //存储子结点的位置 private MLNodeT[] childs; //初始化结点 public MLNode(int max) { childs = new MLNodeT[max]; for (int i = 0; i childs.Length; i++) { childs[i] = null; } } public T Data { get { return data; } set { data = value; } } public MLNodeT[] Childs{ get { return childs; } set { childs = value; } } } public class MLTreeT { private MLNodeT head; public MLNodeT Head { get { return head; } set { head = value; } } public MLTree() { head = null; } public MLTree(MLNodeT node) { head = node; } //求树的根结点，如果树非空，返回根结点，否则返回空 public MLNodeT Root() { retur…… 阅读全文

摘要：一、树和森林的定义 树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树。 森林(Forest)是m(m≥0)棵互不相交的树的集合。 树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。 二、树的相关术语 1. 一个结点的子树的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 2. 树中度为零的结点称为叶结点或终端结点。 3. 树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 4. 结点的子树的根成为该结点的孩子，相应地，该结点称为孩子的双亲。 5. 如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。 6. 如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙或后裔。 7. 我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。 8. 树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。 9. 从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。 10. 树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称…… 阅读全文

摘要：首先写一个二叉树的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，…，…… 阅读全文