XIAOSUO 记录个人学习的足迹

摘要：在表的组织方式中，线性表是最简单的一种。顺序查找是一种最简单的查找方法。 一、顺序查找的基本思想 基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。 二、基于顺序结构的顺序查找算法 我们先来看顺序查找的算法程序 public int SeqSearch(SeqListint R, int Key) { //顺序表R中顺序查找关键字为Key //成功时返回找到的结点位置，失败时返回0 int i; R.Data[R.GetLength()] = Key; //设置哨兵 for (i = 0; R.Data[i] != Key; i++) ; //若i为n，表示查找失败，否则R[n]是要找的结点 if (i == R.Length) return -1; else return i; } 注意： ① 算法中监视哨R.Data[R.GetLength()]的作用 为了在for循环中省去判定防止下标越界的条件i≥1，从而节省比较的时间。 ②成功时的顺序查找的平均查找长度： 在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为(n+…+2+1)/n=(n+1)/2，即查找成功时的平均比较次数约为表长的一半。 若K值不在表中，则须进行n+1次比较之后才能确定查找失败。 ③表中各结点的查找概率并不相等的ASL 【例】在由全校学生的病历档案组成的线性表中，体弱多病同学的病历的查找概率必然高于健康同学的病历，由于上式的ASLsq在pn≥pn-1≥…≥p2≥p1时达到最小值。 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。 为了提高查找效率，对算法SeqSearch做如下修改：每当查找成功，就将找到的结点和其后继(若存在)结点交换。这样，使得查找概率大的结点在查找过程中不断往后移，便于在以后的查找中减少比较次数。 ④顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结…… 阅读全文

摘要：一、概述 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若u，v ∈E(G)，则u在线性序列中出现在v之前。 通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。 注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。 【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。 　　 ⑤当有向图中存在有向环时，拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示，有向边v3，vl和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。 　　 二、无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为： NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有人度为0的顶点)do{ 从G中选择一个人度为0的顶点v且输出之； 从G中删去v及其所有出边； } if(输出的顶点数目|V(G)|) //若此条件不成立，则表示所有顶点均已输出，排序成功。 Error(G中存在有向环，排序失败！)； } 注意： 无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点： 在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。 三、无后继的顶点优先拓扑排序方法 1、思想方法 ** 　该方法的每一步均是输出当前无后继…… 阅读全文

摘要：一、概述　　 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 这里: TE表示T的边集 w(u，v)表示边(u，v)的权。 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 二、最小生成树的应用 最小生成树有许多重要的应用。 【例】网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。 三、最小生成树性质（MST性质） （1）MST性质 最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。 （2）MST性质的证明 为方便说明，先作以下约定： ①将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边(即权重最轻的边)。于是，MST性质中所述的边(u，v)就可简称为轻边。 用反证法证明MST性质： 假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边(u'，v')连接红点集和蓝点集，否则u和v不连通。当把轻边(u，v)加入树T时，该轻边和P必构成了一个回路。删去紫边(u'，v')后回路亦消除，由此可得另一生成树T'。 T'和T的差别仅在于T'用轻边(u，v)取代了T中权重可能更大的紫边(u'，v')。因为w(u，v)≤w(u'，v')，所以w(T')=w(T)+w(u，v)-w(u'，v')≤w(T)。故T'亦是G的MST，它包含边(u，v)，这与假设矛盾。所以，MST性质成立。 四、求MST的一般算法描述 求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边(u，v)，最终生成一棵含n-1条边的MST。 当一条边(u，v)加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。 用伪代码可将算…… 阅读全文

摘要：问题描述 对每一对顶点vi ≠ vj，求出vi与vj之间的最短路径和最短路径长度 Floyd算法 Floyd(Floyd-Warshall)算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，该算法名称以创始人之一罗伯特·弗洛伊德命名。 Floyd-Warshall算法是动态规划的一个例子，即该算法中的前面的运算都会给予后面结果一些影响，下一步得出的结果可能会依赖于上一步得出的结果，运算的整个过程需要层层迭代，最终得出结果。 核心思路 松弛技术：对在i和j之间的所有其他点进行一次松弛（寻找中间点） 状态转移方程： map[i][j]=min{map[i][k]+map[k][j],map[i][j]} 具体运算过程 ①建立两个辅助数组： a[ i ][ j ]，存储i到j之间的最小路径长度 path[ i ][ j ]，存储i到j所经历的中间顶点 ②辅助数组初始化：使用map[i][j]来进行初始化 若顶点 i能到达顶点 j，使得a[i][j]=map[i][j]，path[i][j] = i 若无法到达，使得a[i][j] = MAX，path[i][j]=-1(作为标记) ③借助状态转移方程对a[][]中所有路径进行松弛 若图有k个顶点，则需遍历k次，使得每个顶点都可用作中间点进行一次松弛判断 核心代码： for(int k=0; ksMap.num; k++) for(int j=0; jsMap.num; j++) for(int i=0; isMap.num; i++) ④在更新完成之后，所得的两个矩阵即为结果 伪代码实现 阅读全文

摘要：单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。 一、Dijkstra算法的引入 由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法，其算法的基本思想是：设置两个顶点集合T和S，集合S中存放己经找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到源点v0路径长度最短的顶点w加入集合S，集合S中每加入一个新的顶点w，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来最短路径长度值与顶点w的最短路径长度加上w到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入集合S为止。 【例】在有向网G8中，假定以顶点0为源点，则它则其余各顶点的最短路径按路径递增序排列如下表所示 **　　　　** 二、算法的具体描述 设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。 ①初始化 初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S=，蓝点集为空。 ②重复以下工作，按路径长度递增次序产生各顶点最短路径 在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。 当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。 注意： ①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。 ②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。 在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集 根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是： 源点，红点1，红点2，…，红点n，蓝点k 距离为：源点到红点n最短距离+红点n,蓝点k边长 为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的最短路径长度（简称估计距离）。 若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V-S}，则D[k]…… 阅读全文

摘要：一、深度优先搜索 （1）深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。 （2）深度优先搜索过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 （3）邻接表深度优先算法 //深度优先遍历算法 public NodeT[] DFSAL(NodeT v) { int i = GetIndex(v); int m = 0; NodeT[] nodes = new NodeT[GetNumOfVertex()]; visited[i] = true; Stack st = new Stack(); st.Push(i); while (st.Count 0) { int k = (int)st.Pop(); nodes[m++] = adjList[k].Data; adjListNodeT p = adjList[k].FirstAdj; while (p != …… 阅读全文

摘要：一、用邻接矩阵表示图 邻接矩阵(Adjacentcy Matrix)是用两个数组来表示图，一个数组是一维数组，存储图中的顶点信息，一个数组是二维数组，即矩阵，存储顶点之间相邻的信息，也就是边（或弧）的信息。如果图中有n个顶点，你需要大小为n×n的二维数组来表示图。如下图所示 对邻接矩阵进行操作的代码如下： public class NodeT { private T data; //数据域 //构造器 public Node(T v) { data = v; } //数据域属性 public T Data { get { return data; } set { data = value; } } } public class GraphAdjMatrixT { private NodeT[] nodes; //顶点数组 private int[,] matrix; //邻接矩阵数组 private int numEdges; //边的数目 //初始化邻接矩阵 public GraphAdjMatrix(int n) { nodes = new NodeT[n]; matrix = new int[n, n]; } //设置索引为index的顶点的信息 public void SetNode(int index, NodeT v) { nodes[index] = v; } //获取索引为index的顶点的信息 public NodeT GetNode(int index) { return nodes[index]; } //在顶点v1和v2之间添加权值为v的边 public void SetEdge(NodeT v1, NodeT v2, int v) { //v1或v2不是图的顶点 if (!IsNode(v1) || !IsNode(v2)) { Console.WriteLine(Node is not belong to Graph!); return; } //矩阵是对称矩阵 matrix[GetIndex(v1), GetIndex(v2)] = v; matrix[GetIndex(v2…… 阅读全文

摘要：一、图的定义 图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成。图是数据元素的集合，这些数据元素被相互连接以形成网络。其形式化定义为： G=（V，E） V={Vi|Vi∈某个数据元素集合} E={(Vi,Vj)|Vi,Vj∈V∧P(Vi,Vj)} 其中，G表示图，V是顶点的集合，E是边或弧的集合。在集合E中，P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连。 二、图的术语 顶点集：图中具有相同特性的数据元素的集合称为顶点集。 边（弧）：边是一对顶点间的路径，通常带箭头的边称为弧。 弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个。 弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。 度：在无向图中的顶点的度是指连那个顶点的边的数量。在有向图中，每个顶点有两种类的的度：出度和入度。 入度：顶点的入度是指向那个顶点的边的数量。 出度：顶点的出度是由那个顶点出发的边的数量。 权：有些图的边（或弧）附带有一些数据信息，这些数据信息称为边（或弧）的权（weigh）。 三、图的分类 有向图：在一个图中，如果任意两顶点构成的偶对（Vi,Vj）是有序的，那么称该图为有向图。这里Vi是弧尾，Vj是弧头。这表示有一个从顶点Vi到顶点 Vj的路径。但是从Vj到Vi是不可能的。 无向图：在一个图中，如果有任意两顶点构成的边（Vi,Vj），（Vi,Vj）和（Vj ，Vi）是相同的。 在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。无向完全图又称完全图。 在一个有向图，如果任意两个顶点之间都是弧相连，则称该图为有向完全图。 有很少条边或弧的图称为稀疏图，反之称为稠密图。 四、图的基本操作 1.SetNode()：在图中增加一个新的顶点 2.GetNode()：获取图中指定顶点 3.SetEdge()：在两个顶点之间添加指定权值的边或弧 4.GetEdge()：获取两个顶点之间的边 5.DelEdge()：删除两个顶点之间的边或弧 6.GetNumOfVertex()：获取邻接矩阵顶点数 7.GetNumOfEdge()：获取邻接矩阵边或弧的数目 8.GetIndex()：获取指定顶点在数组中的索引 9.IsEdge()：判断两个顶点之间是否存在边或弧 10.IsNode()：判断指定结点是否是图的顶点 阅读全文

摘要：Hash是各种数据结构中最为重要的数据结构之一；Hash具有O(1)的数据检索效率；Hash的空间开销却通常很大，以空间换取时间；适用于读取操作频繁，写入操作很少的操作类型。 一、存储结构 .NET中hash以数组的方式保存，数组的大小为素数，当数组中存在的数据项个数大于数组容量的扩张因子倍数时，数组进行扩张。 我们先看一下Hashtable类中的构造函数和一些重要数据项，如以下代码： public class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable { //其他部分 private struct bucket { public Object key; //实际保存的键对象，如果key==buckets或者null，认为该项数据已经被清除 public Object val; //实际保存的值对象 public int hash_coll; //hash值最高位（31bit）表示在该位上是否发生过冲突 //即按照hash算法，在插入数据时如果计算到该位置发现hash_coll(31bit)==1，那么认为该位置曾经发生过冲突， //从当前位置使用hash算法计算后可能会继续发现可用的数据 } private bucket[] buckets; //保存数据的hash桶 private int count; //hash表中实际包含数据项个数 private int occupancy; //在hashtable中标记的冲突位个数 private int loadsize; private float loadFactor; //装载因子，如果 当前hash表中的实际数据项个数*装载因子hash表中保存数据项的桶的大小 //那么当前保存数据项桶需要扩容至少当前容量2倍的素数大小 //其他部分 //capacity为hash表中可以保存的数据项的期望值，注意：这个值并不等于保存数据项的hash桶的实际大小 public Hashtable(int capacity, float loadFactor) { if (capa…… 阅读全文

摘要：通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。 一、开放定址法 （1）开放地址法解决冲突的方法 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。 注意： ①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。 ②空单元的表示与具体的应用相关。 【例】关键字均为非负数时，可用-1来表示空单元，而关键字为字符串时，空单元应是空串。 总之：应该用一个不会出现的关键字来表示空单元。 （2）开放地址法的一般形式 开放定址法的一般形式为： hi=(h(key)+di)％m 1≤i≤m-1 其中： ①h(key)为散列函数，di为增量序列，m为表长。 ②h(key)是初始的探查位置，后续的探查位置依次是hl，h2，…，hm-1，即h(key)，hl，h2，…，hm-1形成了一个探查序列。 ③若令开放地址一般形式的i从0开始，并令d0=0，则h0=h(key)，则有： hi=(h(key)+di)％m 0≤i≤m-1 探查序列可简记为hi(0≤i≤m-1)。 （3）开放地址法堆装填因子的要求 开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。 （4）形成探测序列的方法 按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。 ①线性探查法(Linear Probing) 该方法的基本思想是： 将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：d，d+l，d+2，…，m-1，0，1，…，d-1 即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。 探查…… 阅读全文