include.docx_第1页
include.docx_第2页
include.docx_第3页
include.docx_第4页
include.docx_第5页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

节点i称为外节点(externalnode)，当且仅当节点i的左子树或右子树为空( left(i) = NULL或right(i) = NULL )；节点i的距离(dist(i)是节点i到它的后代中，最近的外节点所经过的边数。特别的，如果节点i本身是外节点，则它的距离为0；而空节点的距离规定为-1 (dist(NULL) =-1)。在本文中，有时也提到一棵左偏树的距离，这指的是该树根节点的距离。一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数，也就是说，我们有 性质3 节点的距离等于它的右子节点的距离加1。性质2 节点的左子节点的距离不小于右子节点的距离性质1 节点的键值小于或等于它的左右子节点的键值。即dist( i ) = dist( right( i ) ) + 1 外节点的距离为0，由于性质2，它的右子节点必为空节点。为了满足性质3，故前面规定空节点的距离为-1。它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质有时也提到一棵左偏树的距离，这指的是该树根节点的距离。图一 图二图1是我给出的二分图中的一个匹配：1，5和2，6。图2就是在这个匹配的基础上找到的一条增广路径：3-6-2-5-1-4。我们借由它来描述一下二分图中的增广路径的性质：7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。（如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。）我们平时所见的Floyd算法的一般形式如下：12345678void Floyd() int i,j,k; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(distik+distkjdistij) distij=distik+distkj;注意下第6行这个地方，如果distik或者distkj不存在，程序中用一个很大的数代替。最好写成if(disti k!=INF & distkj!=INF & distik+distkjDISTIJ)，从而防止溢出所造成的错误。 A*算法通往某个方格的G值，求值的
人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论