数据结构知识点(含算法)

第一章概论数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系可以用一组数据(结点集合K)以及这些数据之间的一组二元关系(关系集合R)来表示：(K,R)结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系r(r£R)都是KXK上的二元关系数据类型基本数据类型整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型(char)、指针类型(pointer)复合数据类型复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型数据结构的分类：线性结构(一对一)、树型结构(一对多)、图结构(多对多)四种基本存储映射方法：顺序、链接、索引、散列算法的特性：通用性、有效性、确定性、有穷性算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化渐进算法分析大0分析法：上限，表明最坏情况Q分析法：下限，表明最好情况0分析法：当上限和下限相同时，表明平均情况第二章线性表线性结构的基本特征集合中必存在唯一的一个“第一元素”集合中必存在唯一的一个“最后元素”除最后元素之外，均有唯一的后继除第一元素之外，均有唯一的前驱线性结构的基本特点:均匀性、有序性顺序表主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度线性表中任意元素的存储位置：Loc(ki)=Loc(kO)+i*L(设每个元素需占用L个存储单元)线性表的优缺点：优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样缺点：空间难以扩充检索：ASL=【0(1)】插入：插入前检查是否满了，插入时插入处后的表需要复制【0(n)】删除：删除前检查是否是空的，删除时直接覆盖就行了【0(n)】链表单链表特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等带头结点的怎么判定空表：head和tail指向单链表的头结点链表的插入(q->next=p->next;p->next=q;)【0(n)】链表的删除(q=p->next;p->next=q->next;deleteq;)【0(n)】不足：next仅指向后继，不能有效找到前驱双链表增加前驱指针，弥补单链表的不足带头结点的怎么判定空表:head和tail指向单链表的头结点插入：(q->next=p->next;q->prev=p;p->next=q;q->next->prev=q)删除：(p->prev->next=p->next;p->next->prev=p->prev;p->prev=p->next=NULL;deletep;)顺序表和链表的比较主要优点顺序表的主要优点没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利链表的主要优点无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况应用场合的选择不宜使用顺序表的场合经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素不宜使用链表的场合当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择第三章栈与队列栈栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈(压栈)；删除：出栈(退栈)；插入、删除一端被称为栈顶(浮动)，另一端称为栈底(固定)；实现分为顺序栈和链式栈两种应用：数制转换while(N){N%8入栈；N=N/8;}while（栈非空）{出栈；输出；}2）括号匹配检验不匹配情况：各类括号数量不同；嵌套关系不正确算法：逐一处理表达式中的每个字符ch：小=非括号：不做任何处理ch=左括号：入栈ch=右括号：if（栈空）returnfalseelse{出栈，检查匹配情况，if（不匹配）returnfalse}如果结束后，栈非空，返回false3）表达式求值3.1中缀表达式：计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右3.2后缀表达式：＜表达式＞::=＜项＞＜项＞+|＜项＞＜项＞－|＜项＞＜项＞::=＜因子＞＜因子＞*|＜因子＞＜因子＞/|＜因子＞＜因子＞::=＜常数＞•＜常数＞::=＜数字＞|＜数字＞＜常数＞＜数字〉：上0|1|2|3|4|5|6|7|8|9中缀表达式转换为后缀表达式InfixExp为中缀表达式，PostfixExp为后缀表达式初始化操作数栈0P,运算符栈OPND；OPND.push（'#'）;读取InfixExp表达式的一项操作数：直接输出到PostfixExp中；操作符：{当'（'入OPND;当'）'OPND此时若空，则出错；OPND若非空，栈中元素依次弹出，输入PostfixExpz中，直到遇到'（‘为止；若为'（'弹出即可当'四则运算符'循环（当栈非空且栈顶不是'（‘&&当前运算符优先级〉栈顶运算符优先级），反复弹出栈顶运算符并输入到PostfixExp中，再将当前运算符压入栈3.4后缀表达式求值初始化操作数栈OP；while（表达式没有处理完）{item=读取表达式一项;操作数：入栈OP；运算符：退出两个操作数，计算，并将结果入栈｝C.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的队列若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列循环队列判断队满对空：队空：front==rear；队满：（rear+1）%n==front第五章二叉树概念一个结点的子树的个数称为度数二叉树的高度定义为二叉树中层数最大的叶结点的层数加1二叉树的深度定义为二叉树中层数最大的叶结点的层数如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，贝y此二叉树称作满二叉树如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树外部路径长度E：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和内部路径长度I：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和性质二叉树的第i层（根为第0层，i±0）最多有29个结点深度为k的二叉树至多有2k+1-1个结点任何一颗二叉树，度为0的结点比度为2的结点多一个。n0=n2+1满二叉树定理：非空满二叉树树叶数等于其分支结点数加1满二叉树定理推论：一个非空二叉树的空子树（指针）数目等于其结点数加1有n个结点（n>0）的完全二叉树的高度为Hog2（n+1）］,深度为Hog2（n+1）］对于具有n个结点的完全二叉树，结点按层次由左到右编号，则有：1） 如果i=0为根结点；如果i>0，其父结点编号是（i-1）/22） 当2i+1<n，i结点的左子结点是2i+1；否则i结点没有左子结点3） 当2i+2<n，i结点的右子结点是2i+2；否则i结点没有右子结点周游（重点为由前序中序/中序后序求得二叉树）深度优先周游二叉树，可以有下列三种周游顺序：（实现：栈）1） 前序周游（tLR次序）：访问根结点；前序周游左子树；前序周游右子树2） 中序周游（LtR次序）：中序周游左子树；访问根结点；中序周游右子树3） 后序周游（LRt次序）：后序周游左子树；后序周游右子树；访问根结点广度周游二叉树：从二叉树的顶层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问（实现：队列）存储链式存储结构，顺序存储结构（仅限完全二叉树：因为完全二叉树排列紧凑）二叉搜索树（BST）判定：是一颗空树；或者是具有下列性质的二叉树：对于任何一个结点，设其值为K,则该结点的左子树（若不空）的所有结点的值都小于K；右子树（若不空）的所有结点的值都大于K；它的左右子树也分别为二叉搜索树性质：按照中序周游将各结点打印出来，得到的排列按照由小到大有序C.检索：从根结点开始，在二叉搜索树中检索值K如果根结点储存的值为K,则检索结束如果K小于根结点的值，则只需检索左子树如果K大于根结点的值，则只检索右子树该过程一直持续到找到K或者遇上叶子结点如果遇上叶子结点仍没有发现K,则查找失败**查找关键码：把查找时所经过的点一次写出d插入用待插入结点与树根比较，若待插入的关键值小于树根的关键值，就进入左子树，否则进入右子树；在子树中，按照同样的方式沿检索路径直到叶结点，将新结点插入到二叉搜索树的叶子结点位置创建：从空的BST开始，将关键码按BST定义一次插入f删除：与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性，删除过程分为如下情况：1） 被删除的结点是叶子：直接将其删除即可2） 被删除的结点只有左子树或只有右子树：直接将要删除的点删除后，将该点的左（右）孩子和上面结点相连3） 被删除结点有左、右子树：若p有左右子树，则在左子树里找中序周游的最后一个结点r,将r的右指针置成指向p的右子树的根，用结点p的左子树的根去代替被删除的结点p堆最小/大堆定义：最小堆：是个关键码序列｛kO,kl・・4l｝，具有如下特性（i=0,1,••订n/2」-1）kiWk2i+1（左孩子）kiWk2i+2（右孩子） （即父W2个孩子）类似可以定义最大堆ki三k2i+1ki三k2i+2 （即父三2个孩子）建“初堆：按序列建立完全二叉树，从其中最后一个有孩子的结点开始按堆的定义调整插入：插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义删除：用最后结点替换被删结点，自上至下调整成堆移出最小/大值：可以将堆中最后一个位置上的元素（数组中实际的最后一个元素）移到根的位置上，利用从左开始向下筛选对堆重新调整7.Huffman树a.概念路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径结点路径长度：从根结点到该结点的路径上分支的数目树的路径长度：树中每个结点的路径长度之和带权的路径长度树中所有叶子结点的带权路径长度之和=其中：wfc：权值-：结点到根的路径长度编码：左0右1如何构建：选取序列中最小的相加生成树如此反复第六章树概念若＜k,k、WN,则称k是k'的父结点，k'是k的子结点若有序对＜k,k'＞及＜k,k〃＞WN,则称k'和k〃互为兄弟若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙树/森林与二叉树的相互转换树转换成二叉树加线:在树中所有兄弟结点之间加一连线抹线:对每个结点,除了其最左孩子外,去除其与其余孩子之间的连线旋转:以树的根结点为轴心,将整树顺时针转45°二叉树转化成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树周游先根（次序）周游若树不空，则先访问根结点，然后依次先根周游各棵子树后根（次序）周游若树不空，则先依次后根周游各棵子树，然后访问根结点按层次周游若树不空，则自上而下自左至右访问树中每个结点存储结构“左子/右兄”二叉链表表示法：结点左指针指向孩子，右结点指向右兄弟，按树结构存储，无孩子或无右兄弟则置空“UNION/FIND算法”（等价类）判断两个结点是否在同一个集合中，查找一个给定结点的根结点的过程称为FIND归并两个集合，这个归并过程常常被称为UNION“UNION/FIND”算法用一棵树代表一个集合，如果两个结点在同一棵树中，则认为它们在同一个集合中；树中的每个结点(除根结点以外)有仅且有一个父结点；结点中仅需保存父指针信息，树本身可以存储为一个以其结点为元素的数组6.树的顺序存储结构a.带右链的先根次序表示法在带右链的先根次序表示中，结点按先根次序顺序存储在一片连续的存储单元中每个结点除包括结点本身数据外，还附加两个表示结构的信息字段，结点的形式为:info是结点的数据；rlink是右指针，指向结点的下一个兄弟；Itag是一个左标记，当结点没有子结点(即对应二叉树中结点没有左子结点时)，Itag为1,否则为0带双标记位的先根次序表示法规定当结点没有下一个兄弟(即对应的二叉树中结点没有右子结点时)rtag为1,否则为0带双标记位的层次次序表示法结点按层次次序顺序存储在一片连续的存储单元中第七章图定义假设图中有n个顶点，e条边：含有e=n(n-1)/2条边的无向图称作完全图含有e=n(n-1)条弧的有向图称作有向完全图若边或弧的个数e<nlogn，则称作稀疏图，否则称作稠密图顶点的度(TD)=出度(OD)+入度(ID)顶点的出度：以顶点v为弧尾的弧的数目顶点的入度：以顶点v为弧头的弧的数目C.连通图、连通分量若图G中任意两个顶点之间都有路径相通，则称此图为连通图若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量强连通图、强连通分量对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图否则，其各个极大强连通子图称作它的强连通分量生成树、生成森林假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树对非连通图，则将由各个连通分量构成的生成树集合称做此非连通图的生成森林存储结构a.相邻矩阵表示法表示顶点间相邻关系的矩阵若G是一个具有n个顶点的图，则G的相邻矩阵是如下定义的nXn矩阵：A[i,j]=1，若(Vi,Vj)(或<Vi,Vj>)是图G的边A[i,j]=O，若（Vi,Vj）（或＜Vi,Vj＞）不是图G的边b.邻接表表示法为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）（建立单链表时按结点顺序建立）周游a.深度优先周游：从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发，深度优先搜索遍历图中的其余顶点，直至图中所有与V0有路径相通的顶点都被访问到为止b.广度优先周游：从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止拓扑排序拓扑排序的方法是：1）选择一个入度为0的顶点且输出之2） 从图中删掉此顶点及所有的出边3） 回到第1步继续执行，直至图空或者图不空但找不到无前驱（入度为0）的顶点为止单源最短路径（Dijkstra算法）每对顶点间的最短路径（Floyd算法）最小生成树Prim算法Kruskal算法两种算法比较：Prim算法适合稠密图，Kruskal算法适合稀疏图第八章内排序算法最大时间平均时间最小时间S(n)稳定性直接插入排序0（少）0(n2)0(n)0(1)稳定冒泡排序0(n2)0(n2)0(n)0(1)稳定直接选择排序0(n2)0(n2)0(n2)0(1)不稳定盘匕-TTTh1_10(n3/2)0(n3/2)0(n3/2)0(1)不稳定快速排序0(n2)0(nlogn)0(nlogn)0(logn)不稳定归并排序0(nlogn)0(nlogn)0(nlogn)0(n)稳定堆排序0(nlogn)0(nlogn)0(nlogn)0(1)不稳定桶式排序0(n+m)0(n+m)0(n+m)0(n+m)稳定基数0(d•(n+r))0(d•(n+r))0(d•(n+r))0(n+r)稳定排序第十章检索1•平均检索长度（ASL）是待检索记录集合中元素规模n的函数，其定义为：ASL=Pi为检索第i个元素的概率;Ci为找到第i个元素所需的比较次数2•散列除余法用关键码key除以M（取散列表长度），并取余数作为散列地址散列函数为：hash（key）=keymodM解决冲突的方法开散列方法：把发生冲突的关键码存储在散列表主表之外（在主表外拉出单链表）闭散列方法：把发生冲突的关键码存储在表中另一个位置上线性探查基本思想：如果记录的基位置存储位置被占用，就在表中下移，直到找到一个空存储位置依次探查下述地址单元：dO+1,dO+2,…，m-1,0, 1,...,dO-1；用于简单线性探查的探查函数是:p（K,i）=i散列表的检索1•假设给定的值为K,根据所设定的散列函数h,计算出散列地址h（K）如果表中该地址对应的空间未被占用，则检索失败，否则将该地址中的值与K比较若相等则检索成功；否则,按建表时设定的处理冲突方法查找探查序列的下一个地址,如此反复下去,直到某个地址空间未被占用（可以插入）,或者关键码比较相等（有重复记录,不需插入）为止散列表的删除：删除后在删除地点应加上墓碑（被删除标记）散列表的插入：遇到墓碑不停止，知道找到真正的空位置第十一章索引技术概念：主码：数据库中的每条记录的唯一标识辅码：数据库中可以出现重复值的码B树a.定义：B树定义：一个m阶B树满足下列条件：（1） 每个结点至多有m个子结点；（2） 除根和叶外其它每个结点至少有个子结点；（3）根结点至少有两个子结点例外（空树，or独根）⑷所有的叶在同一层,可以有丨1-1到m-1个关键码⑸有k个子结点的非根结点恰好包含k-1个关键码b.查找在根结点所包含的关键码K1,…，Kj中查找给定的关键码值（用顺序检索（key少）/二分检索（key多））；找到：则检索成功否则，确定要查的关键码值是在某个Ki和Ki+1之间，于是取pi所指结点继续查找;如果pi指向外部结点，表示检索失败.c插入找到的叶是插入位置，若插入后该叶中关键码个a<m,插入完成；否则分裂,中间为分界码（插入到父结点）,若父结点上溢则继续向上分裂d删除删除的关键码不在叶结点层：先把此关键码与它在B树里的后继对换位置，然后再删除该关键码（叶中删）删除的关键码在叶结点层：删除后关键码个数不小于」1-1――直接删除关键码个数小于丨1-1,如果兄弟结点关键码个数不等于-1――从兄弟结点移若干个关键码到该结点中来（父结点中的一个关键码要做相应变化）如果兄弟结点关键码个数等于丨1-1――合并3.B+树m阶B+树的结构定义如下：⑴每个结点至多有m个子结点；（2） 每个结点（除根外）至少有□个子结点；（3） 根结点至少有两个子结点；⑷叶在同一层，有」1..m个key，叶包含全部key，B+树的叶结点链接成一个双链表⑸有k个子结点的结点必有k个关键码。第十二章高级数据结构1.广义表а. 广义表的结构特点：广义表中的数据元素有相对次序广义表的长度定义为最外层包含元素个数广义表的深度定义为所含括弧的重数：“原子”的深度为0;“空表”的深度为1广义表可以共享广义表可以是一个递归的表：递归表的深度是无穷值，长度是有限值б. 任何一个非空广义表LS=（a1,a2,…，an）均可分解为：表头Head（LS）=a1和表尾Tail（LS）=（a2,…，an）两部分b.广义表的各种类型纯表(purelist)：从根结点到任何叶结点只有一条路径；也就是说任何一个元素(原子、子表)只能在广义表中出现一次可重入表(reentrantlist)：图示对应于一个DAG；其元素(包括原子和子表)可能会在表中多次出现，但不会出现回路循环表(cycliclist，递归表)：有向图中可能包含回路；循环表的深度为无穷大2•平衡的二叉搜索树(AVL)平衡因子用bf(x)来表示结点x的平衡因子，它被定义为：bf(x)=x的右子树的高度-X的左子树的高度AVL的插入：按BST建立，发现不满足AVL定义即调整，插入时出现的情况：LL/RR:中间元素成为双亲，左右各位孩子(满足BST定义)LR/RL:最后元素成为双亲，前两个为孩子(满足BST定义)附录：二叉树前序周游template<classT>voidBinaryTree<T>::PreOrderWithoutRecusion(BinaryTreeNode<T>*root){usingstd::stack; 〃使用STL(StandardTemplateLibrary中的stackstack<BinaryTreeNode<T>*>aStack;BinaryTreeNode<T>*p=root;while(p){Visit(p->value()); //先访问当前结点if(p->rc!=NULL)aStack.push(p->rc());//右子非空入栈if(p->lc!=NULL)p=p->lc();//继续向左下周游else{p=aStack.top();//向左下至空：出栈aStack.pop();}}}二叉树中序周游template<classT>voidBinaryTree<T>::InOrderWithoutRecusion(BinaryTreeNode<T>*root){usingstd::stack; 〃使用STL(StandardTemplateLibrary)中的stackstack<BinaryTreeNode<T>*>aStack;//栈aStackBinaryTreeNode<T>*p=root;while(!aStack.empty()||p){if(p){ //向左下走到底，不访问只入栈aStack.push(p); //当前结点地址入栈p=p->leftchild();} //指向左孩子else{p=aStack.top(); //取栈顶aStack.pop(); //出栈Visit(p->value());//访问当前结点p=p->rightchild();}//右跨一步(指向右子)重复}二叉树后序周游enumTags{Left,Right};//枚举类型标志位template<classT>classStackElement{ //栈元素的类型定义public:BinaryTreeNode<T>*pointer;//指向二叉树结点的指针Tagstag;}; //标志位template<classT>voidBinaryTree<T>::PostOrderWithoutRecusion(BinaryTreeNode<T>*root){usingstd::stack;〃使用STL栈部分StackElement<T>element;stack<StackElement<T>>aStack;//栈声明BinaryTreeNode<T>*p;if(root==NULL)return;//空树即返回elsep=root;while(!aStack.empty()||p){while(p!=NULL){element.pointer=p;element.tag=Left;aStack.push(element);p=p->leftchild();//进入左子树//准备栈元素//标志置位//入栈} //沿左子树向下周游element=aStack.top();//取栈顶元素aStack.pop(); //出栈p=element.pointer;if(element.tag==Left){//从左子树回来element.tag=Right;aStack.push(element);p=p->rightchild();}else{ Visit(p->value()); //访问当前结点p=NULL; } //清空为了继续出栈}}图的深度周游voidDFS(Graph&G,intV){ //深度优先搜索算法实现G.Mark[V]=VISITED;〃访问顶点V并标记其标志位Visit(G,V); //访问Vfor(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))〃递归周游与V邻接未访问过的顶点if(G.Mark[G.ToVertices(e)]==UNVISITED)DFS(G,G.ToVertices(e));}图的广度周游voidBFS(Graph&G,intV){usingstd::queue;queue<int>Q;////初始化队列G.Mark[V]=VISITED;Visit(G,V); //先访问Q.push(V); //再入队while(!Q.empty()) //如果队列仍然有元素{intV=Q.front();Q.pop(); //出队//将与该点相邻的每一个未访问点都访问完入队for(Edgee=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e)){if(G.Mark[G.ToVertex(e)]==UNVISITED){G.Mark[G.ToVertex(e)]=VISITED;Visit(G,G.ToVertex(e));Q.push(G.ToVertex(e));}}}}Floyd算法voidFloyd(Graph&G,Dist**&D){inti,j,v;//i,j,v作为计数器D=newDist*[G.VerticesNum()];//创建D[][]for(i=0;;i<G.VerticesNum();i++){D[i]=newDist[G.VerticesNum()];}for(i=0;i<G.VerticesNum();i++)//初始化D数组for(j=0;j<G.VerticesNum();j++)if(i==j){D[i][j].length=0;D[i][j].pre=i; }//对角线0else{D[i][j].lengthINFINITY;D[i][j].pre=-1;}//无路for(v=0;v<G.VerticesNum();v++)for(Edgee=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e)){ //按权值初始DD[v][G.ToVertex(e)].length=G.Weight(e);D[v][G.ToVertex(