@TOC 排序——归并排序与基数排序归并排序 归并排序遵循了分治模式，直观上就是分解：分解带排序的元素的序列成各具n/2个元素的两个子序列；解决：使用归并排序递归的排序两个子序列；合并：合并两个已排序的子序列以产生已排序的答案。 首先看看如何合并已排序的两个数组，为了避免在每一个基本步骤都必须检查数组是否已经到了最末端，在两个数组的最末端都放置了哨兵——将两个数组的最末端的元素设置为最大，这样就 ...

@TOC 排序——内部排序之选择排序简单选择排序选择排序开始的时候，我们扫描整个列表，找到它的最小元素然后和第一个元素交换，将最小元素放到它在有序表的最终位置上。然后我们从第二个元素开始扫描列表，找到最后n-1个元素的最小元素，再和第二个元素交换位置，把第二小的元素放在它最终的位置上。如此循环下去，在n-1遍以后，列表就排好序了。 算法： 123456789101112void SelectSo ...

@TOC 排序——内部排序之插入排序与交换排序排序的一篇优秀博客 插入排序 插入排序 折半插入排序 希尔排序（不稳定）交换排序 冒泡排序 123456789101112131415161718void BubbleSort(ElemType A[], int n) { int temp = 0; // 标记数组是不是有序的； bool flag = false; ...

@TOC 字符串模式匹配简单的字符串模式匹配算法串的模式匹配是求第一个字符串在第二个字符串中的位置1234567891011121314151617int Index(String str, String t) { // 求字符串t在str中的位置。 // str[0]和t[0]存储的是字符串的长度； int i = 1, j = 1; while(i < ...

@TOC 图——存储及遍历图的定义定义：图G是由顶点集V和边集E组成，记为G=(V, E),其中V(G)表示图G的顶点的非空有限集，E(G)表示图中的边的集合。顶点的个数称为图的阶。 基本概念： 有向图 无向图 简单图：如果图满如下条件则图称为简单图：（1）不存在重复边；（2）不存在顶点到自身的边；则称图为简单图。 多重图：若图G中某两个节点之间的边数对于一条，又允许顶点通过同一条边和自己 ...

@TOC 图——应用图广度优先遍历可以判断一个图是否为连通图；广度优先遍历可以求得非带权图的单源最短路径。 最小生成树 Prim算法 Prim算法的时间复杂度为O(|V|^2)，不依赖于|E|，故而适用于求解稠密图的最小生成树。 Kruskal算法 这个算法是按照权值递增的顺序选择合适的边来构造生成树。时间复杂度是O(|E|log|E|) 最短路径 Dijkstra算法求解带权图的单源最短路 ...

@TOC 二叉树——应用二叉排序树（BST） 二叉排序树的定义 或者是一棵空树，或者有如下性质的树： （1）若左子树非空，则左子树上所有节点关键字值均小于根节点的关键字值；（2）若右子树非空，则右子树上所有节点关键字值均大于根节点的关键字值；（3）左右子树也分别是一颗二叉排序树。因此，对二叉排序树的中序遍历得到的就是一个递增的序列。 二叉排序树的查找 从根节点开始，沿一个分支逐层向下进行比较的过 ...

@[TOC]目录 二叉树——概念与操作基本概念二叉树的基本概念与性质 基本概念 二叉树有5种基本形态，特殊的二叉树有满二叉树、完全二叉树、二叉排序树和平衡二叉树。 性质 存储结构 二叉树的存储结构有顺序存储结构和链式存储结构两种。满二叉树和完全二叉树采取顺序存储结构比较合适，树中的节点号可以唯一的反映出节点之间的逻辑关系，可以节省空间也可以利用数组元素的下标确定节点在二叉树中的位置以及节 ...

@TOC 树和森林树的基本概念与性质 基本概念 树的定义是递归的，树是一种逻辑结构，同时也是一种分层结构。 性质 （1）树中的节点数等于所有节点的度数加1； （2）度为m的树中第i层上至多有m^(i-1)个节点； （3）高度为h的m叉树至多有(m^h - 1)/(m-1)个节点； （4）具有n个节点的m叉树的最小高度为[logm(n(m-1)+1)] 树的存储结构 （1）双亲表示法 采用一 ...