基于生成树的学生互校验签到算法实现.doc

基于生成树的学生互校验签到算法实现
摘 要: 文中讲述了基于生成树的学生互校验签到算法的实现方案,主要思路是通过搭建WebSocket实时交互环境,获取算法的信息输入与结果反馈;文中对互校验算法进行了分析并实现;最后对算法进法实现
基于WebSocket技术搭建实时交互的校验环境
互校验签到算法的实现对通信环境的要求:(1)提供一个能够让客户端持续向服务器发送请求,服务器及时响应并作出相应的动作;(2)服务器主动向客户端推送信息传统的HTTP协议是一个请求-响应协议,通信只能有客户端发起,做不到服务器主动向客户端推送消息。目前许多网站实现推送技术,所用的技术都是Ajax轮询。轮询是在特定的时间间隔,通过浏览器对服务器发送HTTP请求,由服务器返回最新的数据给客户端的浏览器。由于浏览器需要不断的向服务器发出请求,而HTTP请求可能包含较长的头部,真正有效的数据往往可能只是很小的一部分,这样会浪费很多的带宽等资源,效率低[7]。
HTML5定义的WebSocket协议则是一种在单个TCP连接上进行全双工的通信协议[8],使得客户端和服务器之间的数据交换变得更加简单,允许服务器主动向客户端推送数据。在WebSocket API中,浏览器和服务器只需要完成一次握手,两者之间就直接可以创建持久性的连接,并进行双向数据传输,相比基于HTTP的轮询技术,大大提高了效率和资源的利用率。 因此本文基于WebSocket协议搭建签到校验环境,后端使用Tomcat 搭建WebSocket服务器。
获取学生选座信息生成无向图
由于大学课室座位一般为行列对齐,形成m*n型。因此获取学生的选座信息生成无向图能够转化为以矩阵的形式表现的学生选座状态矩阵和学生信息矩阵(与选座状态矩阵对应)。
矩阵一般可使用二维数组进行存储。
学生选座状态矩阵用于表示学生当前的选座状态,即已选座与未选座,因此可使用二维整型数组表示:0-未选座,1-已选座。数组可见图1。
学生信息矩阵用于存储选座状态矩阵每个节点所对应的学生信息,矩阵中每个节点代表一个学生。由于二维数组每个节点无法存储过多的信息,且此处的学生信息只为了标识学生是否选座,因此可使用字符串数组中保存学生学号,数组可见图2。
调用DFS算法遍历无向图,生成森林S
由于无向图在上一步骤中简化为学生选座状态数组(简称为选座表)与学生学号数组(简称为学号表)。因此本步驟算法可分为两部分,第一部分为generateForest算法,遍历选座表,判断节点是否已经加入森林,若未加入则以该节点为根节点调用DFS算法进行遍历,最终生成森林;第二部分为DFS算法,遍历选座表与学号表,生成对应关系的生成树。
由于后续需要根据生成树,调用generateOrders算法生成对应节点的指令并发送。因此,DFS算法遍历后的生成树的节点需要周围节点(前位、左位、后位、右位)相关联。
定义一个节点类(Node)。
由于在后续算法的实现中多使用迭代器遍历,链表结构的集合使用迭代器遍历,速度会更快,因此本文使用LinkedList类存放生成树与森林。
generateForest算法的设计
第一步,获取选座表与学号表作为信息输入,实例化森林LinkedList<LinkedList<Node>> arrList,用于存放DFS算法生成的生成树。
第二步,座位表中任一节点都有存在成为生成树根节点的可能性,因此本文采用for循环的双重嵌套遍历选座表(二维数组)。在循环体中,实例化生成树LinkedList<Node> nodeArr,判断当前位置是否被选中(选座状态:0-未选座,1-已选座)和是否已加入森林(编写函数,将生成的森林(arrList)与当前的生成树(nodeArr)和当前位置作为参数传入,判断当前位置是否与arrList和nodeArr中节点Node中属性(row,column)相同,若存在相同,表示当前位置已加入,反之则未加入),若当前位置满足被选中且未加入森林,调用DFS算法遍历,生成以当前节点有根的生成树。
第三步,若生成树不为空,将生成的生成树加入森林(nodeArr)。
DFS算法的设计
深度优先搜索(DFS):在搜索过程中访问某个顶点后,需要递归地访问此顶点的所有未访问过的相邻顶点。
第一步,获取数据输入:
(1)根节点位置
(2)选座表(二维整型数组)和学号表(二维字符串数组)
(3)当前节点的父亲节点(根节点无父亲节点,这项置空)
(4)节点所在生成树(n