XIAOSUO 记录个人学习的足迹

摘要：虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。 注意： 　 ①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。 　②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找长度。 　③ α的取值 　α越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为O(1)。 　④ 散列法与其他查找方法的区别 除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为"="或"!="两种可能，其平均时间为O(n)；其余的查找均是对有序集合的查找，每次关键字的比较有"="、"<"和">"三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。 阅读全文

摘要：在用线性查找和二分查找的过程中需要依据关键字进行若干次的比较判断，确定数据集合中是否存在关键字等于某个给定关键字的记录以及该记录在数据表中的位置，查找效率与比较的次数密切相关。在查找时需要不断进行比较的原因是建立数据表时，只考虑了各记录的关键字之间的相对大小，记录在表中的位置和其关键字无直接关系。而之前介绍的哈希表就记录了存储位置和其关键字之间的某种直接关系，那么使用哈希表进行查找时，就无须比较或只做很少的比较久能直接由关键字找到相应的记录。实际上哈希表也就是为解决查找问题提出的。具体哈希表的内容请参考之前的“散列表”相关文章。 阅读全文

摘要：　分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。 一、 二分查找表存储结构 　二分查找表由分块有序的线性表和索引表组成。 （1）分块有序的线性表 　表R[1..n]均分为b块，前b-1块中结点个数为 ，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。 （... 阅读全文

摘要：一、二分查找(Binary Search) 　 二分查找又称折半查找，它是一种效率较高的查找方法。 　二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 二、二分查找的基本思想 　二分查找的基本思想是：（设R[low..high]是当前的查找区间） （1）首先确定该区间的中点位置： （2）然后将待查的K值与R[mid].key... 阅读全文

摘要：　　在表的组织方式中，线性表是最简单的一种。顺序查找是一种最简单的查找方法。 一、顺序查找的基本思想 　　基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 　　顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫... 阅读全文

摘要：一、概述 　　对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若u，v ∈E(G)，则u在线性序列中出现在v之前。 　通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。 注意： 　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的... 阅读全文

摘要：一、概述　　 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 　　 这里: 　　TE表示T的边集 　　w(u，v)表示边(u，v)的权。 　　权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 二、最小生成树的应用 　　最小生成树有许多重要的应用。 【例】网络G表示n各城市之间的通信线路网线路... 阅读全文

摘要：问题描述 对每一对顶点vi ≠ vj，求出vi与vj之间的最短路径和最短路径长度 Floyd算法 Floyd(Floyd-Warshall)算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，该算法名称以创始人之一罗伯特·弗洛伊德命名。 Floyd-Warshall算法是动态规划的一个例子，即该算法中的前面的运算都会给予后面结果一些影响，下一步得出的结果可能会... 阅读全文

摘要：　　单源最短路径问题：已知有向带权图(简称有向网)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)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 阅读全文