消防通道与安全指示灯编程.pptVIP

消防通道与安全指示灯问题 问题描述 1.在一个复杂网络中有多个节点之间互相连通，可能存在回路，而节点中存在着一些出口，现在需要在节点之间的连通线上加一些“方向指示”，让其方向指向最近的出口。 2.节点之间的连通线路上，某些节点之间的连通线路可能会存在“突发状况（例如火情）”，使其之间的连接断开，这样先前通道上一些的“方向指示”就可能出现错误，需要重新设置其方向 3.当然，存在多个连通线路出现“突发状况”时，有可能会有一些节点成为“孤岛”，即出现无法到达出口的状况，这样连通线路上的“方向指示”就需要设置为第三种状态，让在逃生路上的人们“原地等待救援”并让系统查看者知晓其“孤岛”的位置 一个简单的消防通道路线图 例当出现突发状况时 问题分析 1.这个问题可以简化成为一个自由树节点深度问题，把所有的门当做顶点，由顶点开始遍历，这样每一个节点到顶点的深度就成为了它到顶点的距离，“方向指示灯”就可以简化为由深度高的节点指向深度低的节点。 2.当出现突发情况时，就相当于各节点的深度发生改变，需要重新“测量”各个节点的深度并重置方向指示灯。 3.当突发情况出现并由顶点（出口）遍历完所有连通中的节点时发现还有节点没有遍历到，那剩下那些变成为孤岛，需要把其中还在连通的指示灯变为原地等待标示 建立树后的消防图(数字表示深度) 当出现突发状况时重构 数据结构需求与算法分析 一、首先考虑存储节点所需的数据结构，其功能必须包括： 1.记录其是否出口 2.记录其有几个和它相连通的其他节点 3.记录其在建立自由树后的深度 4.提供总节点的数目以在突发状况时检查是否遍历完所有节点 5.记录和它相连的通道 二、考虑连通通道以及指示灯方向所需的数据结构功能： 1.记录这个“通道”和哪两个节点相连以及其状态（突发情况时是否断开） 2.存储这个通道指示灯的状态（是由高深度节点指向低深度节点还是处于孤岛之中） 3.提供其数目以供管理员修改原始的通道图 三、建立自由树时的遍历算法需要的功能： 1.正确的查找到所有出口并从出口开始遍历所有节点，找到所有节点在树中正确的深度 2.建立自由树时顺便重置通道中指示灯的方向 四、出现突发状况时的遍历算法需要的功能： 1.正确的断开所有出现突发情况的通道 2.找到所有出口并开始重构自由树，并重置指示灯的方向 3.找到所有孤岛并使仍然连通孤岛的通道指示灯变为“原地等待”信号 经过分析后我们可以得到这个连通图的数据结构的特点： 1.所有节点之间都是双向连通的 2.方向指示灯只由通道数据结构来控制，节点之间的连通与否其记录 3.所有节点和通道都有序号 这样就得到了符合这样数据结构的连通图示： 经过算法分析后的线路图 ADT(C++) Struct jiedian//节点结构体 { Int chukou; //用整形来记录是否出口 Int shendu;//记录深度 Tongdao* t [x]; //包含有X个指向通道数据结构的指针，X可由具体情况制定其个数 Int ifbianli;//记录是否在遍历过程中经过它 }jie[N]; //由于需要知道其具体数目N，所有用结构体数组来保存 Struct tongdao//通道数据结构体 { Int zhishideng; //用整形来记录指示灯的方向 Int ifconect; //记录是否可以通过 jiedian* j [2]; //因为通道只需知道它连接的节点，所以只需要2个指针 }tong[X*N]; //最大数为节点的X倍 //遍历建树算法的伪代码 Int jianshu() { For(iN) { If(jie[i].chukou==1) Bianli(jie[i],1); //如果为出口，那就以他为顶点(深度1)开始建立自由树 } } Int bianli(jiedian root,int shendu) { Root.ifbianli=x;//记录是否遍历经过它 If((root.shendu)shendu) root.shendu=shendu; //如果当前门经过的深度比先前的小，证明这个节点有更小的深度 For(ix) Tonglu(root.tong[i],shendu); //经过通道 Return 0; } Int tonglu(tongdao root,int shendu) { If(ifconect==0) Return 0;//如果不是连通的，则放弃向下遍历。 For(i2) If((root.j[i]-shendu)shendu){ Zhishideng=x;//设置指示灯，假设x为地理上正确的 return 0; //如果遇到下一个比他深度小的节点，则不需要继续向下 } Else{ Zhishideng=y;//设置指示灯，假设y为地理上正确的