XIAOSUO 记录个人学习的足迹

摘要：　　单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。 一、Dijkstra算法的引入 　　由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法，其算法的基本思想是：设置两个顶点集合T和S，集合S中存放己经找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中... 阅读全文

摘要：假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 　图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 阅读全文

摘要：一、用邻接矩阵表示图 　　邻接矩阵(Adjacentcy Matrix)是用两个数组来表示图，一个数组是一维数组，存储图中的顶点信息，一个数组是二维数组，即矩阵，存储顶点之间相邻的信息，也就是边（或弧）的信息。如果图中有n个顶点，你需要大小为n×n的二维数组来表示图。如下图所示 　　　　 　　对邻接矩阵进行操作的代码如下： public class NodeT { private T dat... 阅读全文

摘要：一、图的定义 　　图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成。图是数据元素的集合，这些数据元素被相互连接以形成网络。其形式化定义为： 　　G=（V，E） 　　V={Vi|Vi∈某个数据元素集合} 　　E={(Vi,Vj)|Vi,Vj∈V∧P(Vi,Vj)} 　　其中，G表示图，V是顶点的集合，E是边或弧的集合。在集合E中，P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连。 　... 阅读全文

摘要：Hash是各种数据结构中最为重要的数据结构之一；Hash具有O(1)的数据检索效率；Hash的空间开销却通常很大，以空间换取时间；适用于读取操作频繁，写入操作很少的操作类型。 阅读全文

摘要：　　通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。 一、开放定址法 （1）开放地址法解决冲突的方法 　用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(... 阅读全文

摘要：一、散列函数的选择有两条标准：简单和均匀。 　简单指散列函数的计算简单快速； 　均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。 二、常用散列函数 　为简单起见，假定关键字是定义在自然数集合上。 （1）平方取中法 　具体方法：先通过求关键字的平方值扩大相近数的... 阅读全文

摘要：一、散列表 　设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。 　散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 其中： 　 ① h：U→{0，1，2，…，m-1} ，通常称h为散列函... 阅读全文

摘要：(1)若n较小(如n≤50)，可采用插入或选择排序。 　当记录规模较小时，插入排序较好；否则因为选择移动的记录数少于插人，应选选择排序为宜。 (2)若文件初始状态基本有序(指正序)，则应选用插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和插入排序结合在一起使用。先利用插入排序求得较长的有序子文件，然后再两两归并之。因为插入排序是稳定的，所以改进后的归并排序仍是稳定的。 (4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。 　当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。 (5)如果编程语言没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。 (6)这些排序算法中，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系： R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key 　　若要求最终结果是： R[0].key≤R[1].key≤…≤R[n-1].key 则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。 阅读全文

摘要：分配排序的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。 一、两种多关键码排序方法 　　最高位优先法（MSD法）。先按k1排序，将序列分成若干子序列，每个子序列中的记录具有相同的k1值；再按k2排序，将每个子序列分成更小的子序列；然后，对后面的关键码继续同样的排序分成更小的子序列，直到按kd排序分组分成最小的子序列后，最后将各个子序列连接起来，便可得到一个有序的序列。前面介绍的扑克牌先按花色再按面值进行排序的方法就是MSD法 　　最次位优先法（LSD法）。先按kd排序，将序列分成若干子序列，每个子序列中的记录具有相同的kd值；再按kd-1排序，将每个子序列分成更小的子序列；然后，对后面的关键码继续同样的排序分成更小的子序列，直到按k1排序分组分成最小的子序列后，最后将各个子序列连接起来，便可得到一个有序的序列。前面介绍的扑克牌先按面值再按花色进行排序的方法就是LSD法。 二、基于LSD方法的链式基数排序的基本思想 　　“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。 　　　　　　 三、基数排序的实现 public class RadixNodeT { private T data; //数据域 private RadixNodeT next; //引用域 public RadixNode(T val, RadixNodeT p) { data = val; next = p; } public RadixNode(RadixNodeT p) { …… 阅读全文