XIAOSUO 记录个人学习的足迹

摘要：一、二分查找(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)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 阅读全文

摘要：一、用邻接矩阵表示图 　　邻接矩阵(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的空间开销却通常很大，以空间换取时间；适用于读取操作频繁，写入操作很少的操作类型。 阅读全文