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

吴伟铨 王芳

摘  要： 文中讲述了基于生成树的学生互校验签到算法的实现方案，主要思路是通过搭建WebSocket实时交互环境，获取算法的信息输入与结果反馈;文中对互校验算法进行了分析并实现;最后对算法进行测试，结果表明，该方案能够快速实现算法的校验。

关键词： 签到;生成树;选座;相互校验;考勤;算法

中图分类号： TP311    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.01.002

本文著录格式：吴伟铨，王芳. 基于生成树的学生互校验签到算法实现[J]. 软件，2020，41（01）：0712

【Abstract】： This paper describes the implementation scheme of student mutual verification check-in algorithm based on the Spanning Tree. The main idea is to build the WebSocket real-time interactive environment to obtain the information input and the result feedback of the algorithm. The cross-checking algorithm is analyzed and implemented in the paper. Finally， the algorithm is tested and the results show that the scheme can quickly verify the algorithm.

【Key words】： Class sign-in; Spanning Tree; Seat selection; Mutual validation; Attendance; Arithmetic

0  引言

目前，高校在針对学生课堂考勤签到方面存在着许多问题。传统的点名考勤费时费力，占用了大量珍贵的课堂教学时间，考勤效率不高，同时存在许多学生找同学帮忙答到浑水摸鱼，考勤的准确性不高。随着移动互联网技术的发展，近些年涌现大批手机签到系统，如使用无线局域网和手机IMEI的签到系统[1]、使用蓝牙技术和二维码技术的点名软件[2]，基于WIFI的室内定位签到[3]，基于GPS定位的签到[4-5]等，但都存在其局限性，如无法精确判断学生是否到达课室，在学校推广与普及难度较大。

本文讲述了一种基于生成树的学生互校验签到算法[6]的实现方案。该方案基于WebSocket技术搭建实时交互环境，通过WebSocket获取学生提交的选座信息经处理转化为生成树，根据生成树生成校验信息指令，学生通过指令完成二次校验，实现学生间相互校验。该方案既缩短了位置校验的时间，提高课堂考勤的效率同时学生互校验很大程度上保证了校验的准确度。最后，文章针对算法进行分别进行了10人次，50人次与100人次的测试，验证了算法的高效性。

1  基于生成树的互校验签到算法设计

1.1  基于生成树的互校验签到算法[6]

第1步：根据选座座位表生成无向图G

第2步：调用DFS（或BFS）算法遍历无向图G，生成森林

第3步：对生成森林中的每棵生成树，根据树的生成路径，调用generateOrders算法（见算法2）生成要发送给每个节点的指令

第4步：向每个节点表示的学生发送对应的指令

第5步：获取学生根据指令提交的位置信息

第6步：将位置信息与选座座位表进行对比，生成签到座位表

1.2  基于生成树的互校验签到算法分析

学生互校验签到算法可划分为以下几个要点：（1）如何获取学生座位信息;（2）如何生成树，生成森林;（3）如何生成指令;（4）如何发送指令;（5）如何接收指令;（6）二次校验：如何提交校验信息、如何接受校验信息、如何进行校验;（7）返回结果其中，获取学习选座信息，发送指令，接收指令，提交校验信息与返回结果，本质上是一个与客户端交互的过程。而在如今课堂上，签到考勤依旧会消耗过多的课堂时间，因此在实现签到算法的过程中需优先考虑校验时间。而搭建一个能够实时进行交互的环境，能够很大程度减少签到校验的时间，故本文的算法实现是基于实时交互校验的环境下进行。

实现校验算法的关键主要在于以下三个部分：（1）如何搭建实时同步的校验环境;（2）如何将座位信息转化后生成生成树、生成指令;（3）如何进行二次校验

2  基于生成树的互校验签到算法实现

2.1  基于WebSocket技术搭建实时交互的校验环境

互校验签到算法的实现对通信环境的要求：（1）提供一个能够让客户端持续向服务器发送请求，服务器及时响应并作出相应的动作;（2）服务器主动向客户端推送信息传统的HTTP协议是一个请求-响应协议，通信只能有客户端发起，做不到服务器主动向客户端推送消息。目前许多网站实现推送技术，所用的技术都是Ajax轮询。轮询是在特定的时间间隔，通过浏览器对服务器发送HTTP请求，由服务器返回最新的数据给客户端的浏览器。由于浏览器需要不断的向服务器发出请求，而HTTP请求可能包含较长的头部，真正有效的数据往往可能只是很小的一部分，这样会浪费很多的带宽等资源，效率低[7]。

HTML5定义的WebSocket协议则是一种在单个TCP连接上进行全双工的通信协议[8]，使得客户端和服务器之间的数据交换变得更加简单，允许服务器主动向客户端推送数据。在WebSocket API中，浏览器和服务器只需要完成一次握手，两者之间就直接可以创建持久性的连接，并进行双向数据传输，相比基于HTTP的轮询技术，大大提高了效率和资源的利用率。

因此本文基于WebSocket协议搭建签到校验环境，后端使用Tomcat 搭建WebSocket服务器。

2.2  获取学生选座信息生成无向图

由于大学课室座位一般为行列对齐，形成m*n型。因此获取学生的选座信息生成无向图能够转化为以矩阵的形式表现的学生选座状态矩阵和学生信息矩阵（与选座状态矩阵对应）。

矩阵一般可使用二维数组进行存储。

学生选座状态矩阵用于表示学生当前的选座状态，即已选座与未选座，因此可使用二维整型数组表示：0-未选座，1-已选座。数组可见图1。

学生信息矩阵用于存储选座状态矩阵每个节点所对应的学生信息，矩阵中每个节点代表一个学生。由于二维数组每个节点无法存储过多的信息，且此处的学生信息只为了标识学生是否选座，因此可使用字符串数组中保存学生学号，数组可见图2。

2.3  调用DFS算法遍历无向图，生成森林S

由于无向图在上一步骤中简化为学生选座状态数组（简称为选座表）与学生学号数组（简称为学号表）。因此本步驟算法可分为两部分，第一部分为generateForest算法，遍历选座表，判断节点是否已经加入森林，若未加入则以该节点为根节点调用DFS算法进行遍历，最终生成森林;第二部分为DFS算法，遍历选座表与学号表，生成对应关系的生成树。

由于后续需要根据生成树，调用generateOrders算法生成对应节点的指令并发送。因此，DFS算法遍历后的生成树的节点需要周围节点（前位、左位、后位、右位）相关联。

定义一个节点类（Node）。

由于在后续算法的实现中多使用迭代器遍历，链表结构的集合使用迭代器遍历，速度会更快，因此本文使用LinkedList类存放生成树与森林。

2.3.1  generateForest算法的设计

第一步，获取选座表与学号表作为信息输入，实例化森林LinkedList> arrList，用于存放DFS算法生成的生成树。

第二步，座位表中任一节点都有存在成为生成树根节点的可能性，因此本文采用for循环的双重嵌套遍历选座表（二维数组）。在循环体中，实例化生成树LinkedList nodeArr，判断当前位置是否被选中（选座状态：0-未选座，1-已选座）和是否已加入森林（编写函数，将生成的森林（arrList）与当前的生成树（nodeArr）和当前位置作为参数传入，判断当前位置是否与arrList和nodeArr中节点Node中属性（row，column）相同，若存在相同，表示当前位置已加入，反之则未加入），若当前位置满足被选中且未加入森林，调用DFS算法遍历，生成以当前节点有根的生成树。

第三步，若生成树不为空，将生成的生成树加入森林（nodeArr）。

2.3.2  DFS算法的设计

深度优先搜索（DFS）：在搜索过程中访问某个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点。

第一步，获取数据输入：

（1）根节点位置

（2）选座表（二维整型数组）和学号表（二维字符串数组）

（3）当前节点的父亲节点（根节点无父亲节点，这项置空）

（4）节点所在生成树（nodeArr）和森林（arrList）

第二步，实例化当前节点（Node）与创建孩子链表LinkedList child存放当前节点的孩子节点，并将当前节点（Node）添加至生成树（nodeArr）

第三步，为当前节点（Node）赋值：

（1）根据传入的根节点位置设置属性row和column

（2）根据学号表与row和column值设置属性digits

（3）判断获取的父亲节点是否为空，不为空则将该节点赋给属性parent

第四步，搜索孩子节点：

（1）判断节点前位的位置是否被选中且还未加入树中，若满足条件，再次调用DFS进行递归，并将递归返回结果添加到孩子链表（child）中

（2）判断节点左位的位置是否被选中且还未加入树中，若满足条件，再次调用DFS进行递归，并将递归返回结果添加到孩子链表（child）中

（3）判断节点后位的位置是否被选中且还未加入树中，若满足条件，再次调用DFS进行递归，并将递归返回结果添加到孩子链表（child）中

（4）判断节点右位的位置是否被选中且还未加入树中，若满足条件，再次调用DFS进行递归，并将递归返回结果添加到孩子链表（child）中

第五步，判断孩子链表是否为空，若不为空，将该链表设置为节点属性child的值

第六步，返回当前节点

2.4  对生成森林中的每棵生成树，根据树的生成路径，调用generateOrders算法生成要发送给每个节点的指令

指令的生成依据：指令的生成根据生成树中节点之间的父子关系（见表2）和节点本身的位置关系（见表3）。

生成指令的规则：指令规则需满足所有节点都通过能提交信息或被提交信息（即他人提交自己的信息）供服务器进行验证。本文采用父亲扫孩子，孤点扫教师，一次提交双方验证的规则进行校验。

（1）父亲扫孩子：即父亲节点可通过提交孩子的信息完成选座的二次校验。

（2）孤点扫教师：孤点指周围（前位、左位、后位、右位）无节点，单独成为一棵生成树的节点，此类节点无法通过父子节点的关系进行校验，因此本文采用孤点扫教师的规则，即孤点通过提交教师给与的信息完成验证。

（3）一次提交双方验证：即一次提交信息的过程，提交信息的一方与被提交信息的一方皆可以完成校验。

因此，指令可分为三种，一是發送给孤点（该座位为孤点，请找教师进行校验）;二是当前节点存在父亲节点（请将你的信息提供给某某方同学）;三是当前节点存在孩子节点（请提交某某方同学信息）。由于考虑到每个座位的学生只发一种指令，大概率会造成部分同学无法完成校验，因此对于同时存在父子节点或存在多个孩子节点的节点，采用糅合第二三种指令的方式生成指令。

generateOrders算法：生成指令算法的关键在于怎样保存对应节点的指令与如何判断节点的性质。对于节点指令的保存问题，本文采用哈希表HashMap orderMap保存指令与节点与指令的联系，后续只需通过位置或学号便可取到对应的指令;对于如何判断节点的性质问题，本文采用迭代器遍历森林中生成树与遍历生成树中的节点，逐一比较。

步骤如下：

（1）判断节点是否为孤点。孤点的判断只需判断节点所在的生成树中节点的数量，当节点数量为1，即表示该节点为孤点。将孤点指令与节点Node放进orderMap中。

（2）判断节点是否存在父节点。判断是否存在父节点需判断当前节点的属性parent是否为NULL，若不为空，即表示节点存在父节点。若父节点存在，需判断父节点与当前节点的位置（即属性row与column），得出节点与父节点的位置关系（例如，前方），生成指令（例如，请将你的信息提供给前方同学）。将指令与节点Node放进orderMap中。

（3）判断节点是否存在子节点。判断是否存在子节点需判断当前节点的属性child是否为NULL，若不为空，即表示存在孩子节点。孩子节点存在，需进一步判断孩子节点的数量与孩子节点与当前节点的位置关系，由于本文使用LinkedList结构去存放孩子节点，因此此处只需通过迭代器遍历child，在迭代中判断每个孩子节点与当前节点的位置，返回对应位置信息（例如左后方），生成指令（例如，请提交左后方同学信息）。将指令与节点Node放进orderMap中。

（4）判断节点是否同时存在父子节点。当一节点同时满足上述（2）（3），则表示节点同时存在父子节点，因此节点指令只需糅合（2）（3）步骤获得的指令（例如，请将你的信息提供给前方同学或提交左后方同学信息）。将指令与节点Node放进orderMap中。

2.5  向节点发送指令与获取学生提交的信息

由于搭建了WebSocket实时交互的通信环境，此步骤技术难度大大降低，向节点发送指令与获取提交信息皆可在WebSocket服务器中完成。作者在搭建WebSocket服务器，考虑到算法需要实现服务器对单一客户端进行通信，在服务器中使用session来区别不同的客户端，以学号作为标识将每个客户端对应的WebSocket实例存放到ConcurrentHashMap< String， WebSocket> clients中。服务器通过OnMessage方法获得用户的选座信息与提交的验证信息;通过学号遍历clients，获取对应的session，再通过session的getBasicRemote（）.sendText方法向客户端发送指令与验证结果。

2.6  将位置信息与选座座位表进行验证，生成签到座位表

首先，需解析学生提交的座位信息。提交信息的方式与信息内容可自行扩展（例如，在登录的时候为每个学生生成一个uuid，将uuid生成为二维码，每个学生有对应的一个二维码作为标识，提交信息的方式可以同时扫二维码提交对应的uuid完成验证）本文为了简化将需要提交的信息code设置为学生学号。

验证过程如下：

第一步，获取学生学号与提交的信息code

第二步，判断是否已经结束选座

第三步，进入校验流程：

（1）获取选座时生成的座位森林arrList，遍历arrList中每棵生成树的节点（本文采用嵌套双重迭代器进行查询），找到与学生学号对应的节点。

（2）判断节点是否存在孩子节点。若存在孩子节点，比较孩子节点的学号（属性digits）是否与获取的提交信息code匹配。若匹配通过WebSocket发送双方校验通过的信息到教师客户端。若孩子节点皆无匹配项与不存在孩子，进入下一轮判定。

（3）判断节点是否存在父节点。若存在父节点，比较父节点的学号（属性digits）是否与获取的提交信息code匹配。若匹配通过WebSocket发送双方校验通过的信息到教师客户端。若父节点皆无匹配项与不存在父节点，进入下一轮判定。

（4）父子节点都判定失败，跳出一重遍历，判断节点所在生成 树的节点数量是否为1。若为1，比较教师工号与获取的提交信息code。若匹配，通过WebSocket发送该学生校验通过的信息到教师客户端;若不匹配，发送该学生校验失败的信息到教师客户端。为节点数量不为1，则发送双方校验失败的信息到教师客户端。

第四步，校验结束。

当学生完成校验后，前端可通过分析选座表，学号表反馈信息生成签到座位表，本文只分析算法实现，不考虑前端具体实现，故此处不详细分析。

3  基于生成树的互校验签到算法测试

为了保证算法在实际运用中的可行性与稳定性，作者搭建了一个简单的SSM项目进行模拟测试。

3.1  开发环境

硬件参数——CPU：Intel（R） Core（TM） i5-7200U CPU @ 2.5 GHz 2.70 GHz;内存：8.00 GB;存储：SSD 128 G;网络：40 M

开发平台——Windows 10系统PC机;Eclipse +JDK1.8;Tomcat7服务器

3.2  算法測试

（1）测试流程：学生提交座位信息进行选座，当所有学生完成选座，教师结束选座。系统根据选座信息调用算法生成森林和指令，通过WebSocket向对应的学生发送指令。

（2）学生根据指令在code框中输入对应同学学号。系统接受信息调用算法进行校验，最终向教师发送结果，完成校验。图4为测试流程图。

（3）测试用例：

1）教师用例：2017012

2）学生用例：2017001、2017002、2017003、2017004、2017005、2017006、2017007、2017008、2017009、2017010（座位表见表2）

3）校验信息用例：2017001提交2017005（父扫子通过）;2017006提交2017005（子扫父通过）;2017002提交2017001（无关座位失败）;2017009提交2017012（非孤点扫教师通过）;2017010提交2017012（孤点扫教师通过）;2017010提交2017003（孤点扫无关座位失败）

（3）算法执行时间：

1）教师结束选座后，系统生成森林，生成指令，发送指令到客户端的执行时间：当参与签到的学生为10人时，执行时间为5 ms;当参与签到的学生为50人时，执行时间为31 ms;当参与签到的学生为100人时，执行时间为60 ms;2）单位学生提交校验信息，系统完成校验并返回结果的时间为3 ms。因此粗略估计，当参与签到的学生为10人时，校验信息步骤的执行时间为30 ms;当参与签到的学生为50人时，校验信息步骤的执行时间为150 ms;当参与签到的学生为100人时，校验信息步骤的执行时间为300 ms;综上所述，当一个班级有10位学生，互校验算法的执行时间为35 ms，平均每人3.50 ms;当一个班级有50位学生，互校验算法的执行时间为181 ms，平均每人3.68 ms;当一个班级有100位学生，互校验算法的执行时间为360 ms，平均每人3.60 ms。

4  结语

本文实现了基于生成树的学生互校验签到的算法，该算法解决方案的实现基于Java搭建WebSocket实时交互环境，在WebSocket交互环境的基础上进行算法的实现，大大简化了获取选座信息，提交校验信息等信息传递环节的实现难度。基于生成树的学生互校验签到算法执行速度快，具有很强的实用性和推广价值。

参考文献

[1] 刘冬梅， 任亚平， 周杰等. 基于Android的手机签到系统[J]. 科技资讯， 2017， 14： 17-18.

[2] 陈三清， 殷鹏. 基于Android手机的课堂点名软件设计与实现[J]. 电脑知识与技术， 2017， 7： 95-99.

[3] 蒋航， 蔡秋枫. 基于室内定位的学生签到系统设计[J]. 电脑知识与技术， 2017， 1： 54-55.

[4] 张劲波， 周泽崇， 李雅杰等. 基于Android的上课签到软件分析与设计[J]. 电脑编程技巧与维护， 2017， 2（3）： 28.

[5] 徐宁. 基于微信平台的并行签到考勤管理系统[J]. 电脑知识与技术， 2016， 30： 77-79.

[6] 王芳， 蔡沂. 基于生成树的学生互校验签到应用研究[J]. 软件， 2018， 7： 6-11.

[7] HTML5 WebSocket[EB/OL]. [2019-09-20]. https：//www. runoob.com/html/html5-websocket.html.

[8] WebSocket[EB/OL]. [2019-09-20]. https：//baike.baidu.com/ item/WebSocket.