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

1、消防通道与安全指示灯问题问题描述 1.在一个复杂网络中有多个节点之间互相连通，可能存在回路，而节点中存在着一些出口，现在需要在节点之间的连通线上加一些“方向指示”，让其方向指向最近的出口。 2.节点之间的连通线路上，某些节点之间的连通线路可能会存在“突发状况（例如火情）”，使其之间的连接断开，这样先前通道上一些的“方向指示”就可能出现错误，需要重新设置其方向 3.当然，存在多个连通线路出现“突发状况”时，有可能会有一些节点成为“孤岛”，即出现无法到达出口的状况，这样连通线路上的“方向指示”就需要设置为第三种状态，让在逃生路上的人们“原地等待救援”并让系统查看者知晓其“孤岛”的位置一个简单的消防

2、通道路线图出口出口出口出口因为这个点到两个出口之间的距离是一样的，所以他可以选择任意方向，其他同理例当出现突发状况时出口出口出口出口孤岛，需要把方向指示设置为原地等待因为连通线路的阻断，这一线路上的方向指示需要变向问题分析 1.这个问题可以简化成为一个自由树节点深度问题，把所有的门当做顶点，由顶点开始遍历，这样每一个节点到顶点的深度就成为了它到顶点的距离，“方向指示灯”就可以简化为由深度高的节点指向深度低的节点。 2.当出现突发情况时，就相当于各节点的深度发生改变，需要重新“测量”各个节点的深度并重置方向指示灯。 3.当突发情况出现并由顶点（出口）遍历完所有连通中的节点时发现还有节点没有遍历到

3、，那剩下那些变成为孤岛，需要把其中还在连通的指示灯变为原地等待标示建立树后的消防图(数字表示深度)1213331214出口出口出口出口当出现突发状况时重构12153x141出口出口出口出口x这里为了表示方便，直接把断开的通道删除了数据结构需求与算法分析 一、首先考虑存储节点所需的数据结构，其功能必须包括： 1.记录其是否出口 2.记录其有几个和它相连通的其他节点 3.记录其在建立自由树后的深度 4.提供总节点的数目以在突发状况时检查是否遍历完所有节点 5.记录和它相连的通道 二、考虑连通通道以及指示灯方向所需的数据结构功能： 1.记录这个“通道”和哪两个节点相连以及其状态（突发情况时是否断开）

4、 2.存储这个通道指示灯的状态（是由高深度节点指向低深度节点还是处于孤岛之中） 3.提供其数目以供管理员修改原始的通道图 三、建立自由树时的遍历算法需要的功能： 1.正确的查找到所有出口并从出口开始遍历所有节点，找到所有节点在树中正确的深度 2.建立自由树时顺便重置通道中指示灯的方向 四、出现突发状况时的遍历算法需要的功能： 1.正确的断开所有出现突发情况的通道 2.找到所有出口并开始重构自由树，并重置指示灯的方向 3.找到所有孤岛并使仍然连通孤岛的通道指示灯变为“原地等待”信号 经过分析后我们可以得到这个连通图的数据结构的特点： 1.所有节点之间都是双向连通的 2.方向指示灯只由通道数据结构

5、来控制，节点之间的连通与否其记录 3.所有节点和通道都有序号 这样就得到了符合这样数据结构的连通图示：经过算法分析后的线路图1326741089出口出口出口出口512345678910ADT(C+) Struct jiedian/节点结构体Int chukou;/用整形来记录是否出口Int shendu;/记录深度Tongdao* t x;/包含有X个指向通道数据结构的指针，X可由具体情况制定其个数Int ifbianli;/记录是否在遍历过程中经过它jieN;/由于需要知道其具体数目N，所有用结构体数组来保存 Struct tongdao/通道数据结构体Int zhishideng;/用整形

6、来记录指示灯的方向Int ifconect;/记录是否可以通过jiedian* j 2;/因为通道只需知道它连接的节点，所以只需要2个指针tongX*N;/最大数为节点的X倍 /遍历建树算法的伪代码 Int jianshu() For(ishendu)root.shendu=shendu;/如果当前门经过的深度比先前的小，证明这个节点有更小的深度For(ix)Tonglu(root.tongi,shendu);/经过通道Return 0; Int tonglu(tongdao& root,int shendu)If(ifconect=0)Return 0;/如果不是连通的，则放弃向下遍历。For(ishendu)shendu)Zhishideng=x;/设置指示灯，假设x为地理上正确的return 0;/如果遇到下一个比他深度小的节点，则不需要继续向下ElseZhishideng=y;/设置指示灯，假设y为地理上正确的bianli(*root.ji,shendu+1