基于生成樹(shù)的學(xué)生互校驗(yàn)簽到算法實(shí)現(xiàn)

1、 基于生成樹(shù)的學(xué)生互校驗(yàn)簽到算法實(shí)現(xiàn) 吳偉銓 王芳摘 要： 文中講述了基于生成樹(shù)的學(xué)生互校驗(yàn)簽到算法的實(shí)現(xiàn)方案，主要思路是通過(guò)搭建WebSocket實(shí)時(shí)交互環(huán)境，獲取算法的信息輸入與結(jié)果反饋;文中對(duì)互校驗(yàn)算法進(jìn)行了分析并實(shí)現(xiàn);最后對(duì)算法進(jìn)行測(cè)試，結(jié)果表明，該方案能夠快速實(shí)現(xiàn)算法的校驗(yàn)。Key： 簽到;生成樹(shù);選座;相互校驗(yàn);考勤;算法： TP311 ： A DOI：10.3969/j.issn.1003-6970.2020.01.002本文著錄格式：吳偉銓，王芳. 基于生成樹(shù)的學(xué)生互校驗(yàn)簽到算法實(shí)現(xiàn)J. 軟件，2020，41（01）：0712【Abstract】： This paper des

2、cribes 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

3、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; Arithmetic0 引言目前，高校在針對(duì)學(xué)生課堂考勤簽到方面存在著許多問(wèn)題。傳統(tǒng)的點(diǎn)名考勤費(fèi)時(shí)費(fèi)力，占用了大量珍貴的課堂教學(xué)時(shí)間，考勤效率不高，同時(shí)存

4、在許多學(xué)生找同學(xué)幫忙答到渾水摸魚(yú)，考勤的準(zhǔn)確性不高。隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展，近些年涌現(xiàn)大批手機(jī)簽到系統(tǒng)，如使用無(wú)線局域網(wǎng)和手機(jī)IMEI的簽到系統(tǒng)1、使用藍(lán)牙技術(shù)和二維碼技術(shù)的點(diǎn)名軟件2，基于WIFI的室內(nèi)定位簽到3，基于GPS定位的簽到4-5等，但都存在其局限性，如無(wú)法精確判斷學(xué)生是否到達(dá)課室，在學(xué)校推廣與普及難度較大。本文講述了一種基于生成樹(shù)的學(xué)生互校驗(yàn)簽到算法6的實(shí)現(xiàn)方案。該方案基于WebSocket技術(shù)搭建實(shí)時(shí)交互環(huán)境，通過(guò)WebSocket獲取學(xué)生提交的選座信息經(jīng)處理轉(zhuǎn)化為生成樹(shù)，根據(jù)生成樹(shù)生成校驗(yàn)信息指令，學(xué)生通過(guò)指令完成二次校驗(yàn)，實(shí)現(xiàn)學(xué)生間相互校驗(yàn)。該方案既縮短了位置校驗(yàn)的時(shí)間，

5、提高課堂考勤的效率同時(shí)學(xué)生互校驗(yàn)很大程度上保證了校驗(yàn)的準(zhǔn)確度。最后，文章針對(duì)算法進(jìn)行分別進(jìn)行了10人次，50人次與100人次的測(cè)試，驗(yàn)證了算法的高效性。1 基于生成樹(shù)的互校驗(yàn)簽到算法設(shè)計(jì)1.1 基于生成樹(shù)的互校驗(yàn)簽到算法6第1步：根據(jù)選座座位表生成無(wú)向圖G第2步：調(diào)用DFS（或BFS）算法遍歷無(wú)向圖G，生成森林第3步：對(duì)生成森林中的每棵生成樹(shù)，根據(jù)樹(shù)的生成路徑，調(diào)用generateOrders算法（見(jiàn)算法2）生成要發(fā)送給每個(gè)節(jié)點(diǎn)的指令第4步：向每個(gè)節(jié)點(diǎn)表示的學(xué)生發(fā)送對(duì)應(yīng)的指令第5步：獲取學(xué)生根據(jù)指令提交的位置信息第6步：將位置信息與選座座位表進(jìn)行對(duì)比，生成簽到座位表1.2 基于生成樹(shù)的互校驗(yàn)簽

6、到算法分析學(xué)生互校驗(yàn)簽到算法可劃分為以下幾個(gè)要點(diǎn)：（1）如何獲取學(xué)生座位信息;（2）如何生成樹(shù)，生成森林;（3）如何生成指令;（4）如何發(fā)送指令;（5）如何接收指令;（6）二次校驗(yàn)：如何提交校驗(yàn)信息、如何接受校驗(yàn)信息、如何進(jìn)行校驗(yàn);（7）返回結(jié)果其中，獲取學(xué)習(xí)選座信息，發(fā)送指令，接收指令，提交校驗(yàn)信息與返回結(jié)果，本質(zhì)上是一個(gè)與客戶端交互的過(guò)程。而在如今課堂上，簽到考勤依舊會(huì)消耗過(guò)多的課堂時(shí)間，因此在實(shí)現(xiàn)簽到算法的過(guò)程中需優(yōu)先考慮校驗(yàn)時(shí)間。而搭建一個(gè)能夠?qū)崟r(shí)進(jìn)行交互的環(huán)境，能夠很大程度減少簽到校驗(yàn)的時(shí)間，故本文的算法實(shí)現(xiàn)是基于實(shí)時(shí)交互校驗(yàn)的環(huán)境下進(jìn)行。實(shí)現(xiàn)校驗(yàn)算法的關(guān)鍵主要在于以下三個(gè)部分：（1

7、）如何搭建實(shí)時(shí)同步的校驗(yàn)環(huán)境;（2）如何將座位信息轉(zhuǎn)化后生成生成樹(shù)、生成指令;（3）如何進(jìn)行二次校驗(yàn)2 基于生成樹(shù)的互校驗(yàn)簽到算法實(shí)現(xiàn)2.1 基于WebSocket技術(shù)搭建實(shí)時(shí)交互的校驗(yàn)環(huán)境互校驗(yàn)簽到算法的實(shí)現(xiàn)對(duì)通信環(huán)境的要求：（1）提供一個(gè)能夠讓客戶端持續(xù)向服務(wù)器發(fā)送請(qǐng)求，服務(wù)器及時(shí)響應(yīng)并作出相應(yīng)的動(dòng)作;（2）服務(wù)器主動(dòng)向客戶端推送信息傳統(tǒng)的HTTP協(xié)議是一個(gè)請(qǐng)求-響應(yīng)協(xié)議，通信只能有客戶端發(fā)起，做不到服務(wù)器主動(dòng)向客戶端推送消息。目前許多網(wǎng)站實(shí)現(xiàn)推送技術(shù)，所用的技術(shù)都是Ajax輪詢。輪詢是在特定的時(shí)間間隔，通過(guò)瀏覽器對(duì)服務(wù)器發(fā)送HTTP請(qǐng)求，由服務(wù)器返回最新的數(shù)據(jù)給客戶端的瀏覽器。由于瀏覽器

8、需要不斷的向服務(wù)器發(fā)出請(qǐng)求，而HTTP請(qǐng)求可能包含較長(zhǎng)的頭部，真正有效的數(shù)據(jù)往往可能只是很小的一部分，這樣會(huì)浪費(fèi)很多的帶寬等資源，效率低7。HTML5定義的WebSocket協(xié)議則是一種在單個(gè)TCP連接上進(jìn)行全雙工的通信協(xié)議8，使得客戶端和服務(wù)器之間的數(shù)據(jù)交換變得更加簡(jiǎn)單，允許服務(wù)器主動(dòng)向客戶端推送數(shù)據(jù)。在WebSocket API中，瀏覽器和服務(wù)器只需要完成一次握手，兩者之間就直接可以創(chuàng)建持久性的連接，并進(jìn)行雙向數(shù)據(jù)傳輸，相比基于HTTP的輪詢技術(shù)，大大提高了效率和資源的利用率。因此本文基于WebSocket協(xié)議搭建簽到校驗(yàn)環(huán)境，后端使用Tomcat 搭建WebSocket服務(wù)器。2.2 獲

9、取學(xué)生選座信息生成無(wú)向圖由于大學(xué)課室座位一般為行列對(duì)齊，形成m*n型。因此獲取學(xué)生的選座信息生成無(wú)向圖能夠轉(zhuǎn)化為以矩陣的形式表現(xiàn)的學(xué)生選座狀態(tài)矩陣和學(xué)生信息矩陣（與選座狀態(tài)矩陣對(duì)應(yīng)）。矩陣一般可使用二維數(shù)組進(jìn)行存儲(chǔ)。學(xué)生選座狀態(tài)矩陣用于表示學(xué)生當(dāng)前的選座狀態(tài)，即已選座與未選座，因此可使用二維整型數(shù)組表示：0-未選座，1-已選座。數(shù)組可見(jiàn)圖1。學(xué)生信息矩陣用于存儲(chǔ)選座狀態(tài)矩陣每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的學(xué)生信息，矩陣中每個(gè)節(jié)點(diǎn)代表一個(gè)學(xué)生。由于二維數(shù)組每個(gè)節(jié)點(diǎn)無(wú)法存儲(chǔ)過(guò)多的信息，且此處的學(xué)生信息只為了標(biāo)識(shí)學(xué)生是否選座，因此可使用字符串?dāng)?shù)組中保存學(xué)生學(xué)號(hào)，數(shù)組可見(jiàn)圖2。2.3 調(diào)用DFS算法遍歷無(wú)向圖，生成森

10、林S由于無(wú)向圖在上一步驟中簡(jiǎn)化為學(xué)生選座狀態(tài)數(shù)組（簡(jiǎn)稱為選座表）與學(xué)生學(xué)號(hào)數(shù)組（簡(jiǎn)稱為學(xué)號(hào)表）。因此本步驟算法可分為兩部分，第一部分為generateForest算法，遍歷選座表，判斷節(jié)點(diǎn)是否已經(jīng)加入森林，若未加入則以該節(jié)點(diǎn)為根節(jié)點(diǎn)調(diào)用DFS算法進(jìn)行遍歷，最終生成森林;第二部分為DFS算法，遍歷選座表與學(xué)號(hào)表，生成對(duì)應(yīng)關(guān)系的生成樹(shù)。由于后續(xù)需要根據(jù)生成樹(shù)，調(diào)用generateOrders算法生成對(duì)應(yīng)節(jié)點(diǎn)的指令并發(fā)送。因此，DFS算法遍歷后的生成樹(shù)的節(jié)點(diǎn)需要周圍節(jié)點(diǎn)（前位、左位、后位、右位）相關(guān)聯(lián)。定義一個(gè)節(jié)點(diǎn)類（Node）。由于在后續(xù)算法的實(shí)現(xiàn)中多使用迭代器遍歷，鏈表結(jié)構(gòu)的集合使用迭代器遍歷，

11、速度會(huì)更快，因此本文使用LinkedList類存放生成樹(shù)與森林。2.3.1 generateForest算法的設(shè)計(jì)第一步，獲取選座表與學(xué)號(hào)表作為信息輸入，實(shí)例化森林LinkedList arrList，用于存放DFS算法生成的生成樹(shù)。第二步，座位表中任一節(jié)點(diǎn)都有存在成為生成樹(shù)根節(jié)點(diǎn)的可能性，因此本文采用for循環(huán)的雙重嵌套遍歷選座表（二維數(shù)組）。在循環(huán)體中，實(shí)例化生成樹(shù)LinkedList nodeArr，判斷當(dāng)前位置是否被選中（選座狀態(tài)：0-未選座，1-已選座）和是否已加入森林（編寫(xiě)函數(shù)，將生成的森林（arrList）與當(dāng)前的生成樹(shù)（nodeArr）和當(dāng)前位置作為參數(shù)傳入，判斷當(dāng)前位置是否與

12、arrList和nodeArr中節(jié)點(diǎn)Node中屬性（row，column）相同，若存在相同，表示當(dāng)前位置已加入，反之則未加入），若當(dāng)前位置滿足被選中且未加入森林，調(diào)用DFS算法遍歷，生成以當(dāng)前節(jié)點(diǎn)有根的生成樹(shù)。第三步，若生成樹(shù)不為空，將生成的生成樹(shù)加入森林（nodeArr）。2.3.2 DFS算法的設(shè)計(jì)深度優(yōu)先搜索（DFS）：在搜索過(guò)程中訪問(wèn)某個(gè)頂點(diǎn)后，需要遞歸地訪問(wèn)此頂點(diǎn)的所有未訪問(wèn)過(guò)的相鄰頂點(diǎn)。第一步，獲取數(shù)據(jù)輸入：（1）根節(jié)點(diǎn)位置（2）選座表（二維整型數(shù)組）和學(xué)號(hào)表（二維字符串?dāng)?shù)組）（3）當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)（根節(jié)點(diǎn)無(wú)父親節(jié)點(diǎn)，這項(xiàng)置空）（4）節(jié)點(diǎn)所在生成樹(shù)（nodeArr）和森林（arr

13、List）第二步，實(shí)例化當(dāng)前節(jié)點(diǎn)（Node）與創(chuàng)建孩子鏈表LinkedList child存放當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)（Node）添加至生成樹(shù)（nodeArr）第三步，為當(dāng)前節(jié)點(diǎn)（Node）賦值：（1）根據(jù)傳入的根節(jié)點(diǎn)位置設(shè)置屬性row和column（2）根據(jù)學(xué)號(hào)表與row和column值設(shè)置屬性digits（3）判斷獲取的父親節(jié)點(diǎn)是否為空，不為空則將該節(jié)點(diǎn)賦給屬性parent第四步，搜索孩子節(jié)點(diǎn)：（1）判斷節(jié)點(diǎn)前位的位置是否被選中且還未加入樹(shù)中，若滿足條件，再次調(diào)用DFS進(jìn)行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中（2）判斷節(jié)點(diǎn)左位的位置是否被選中且還未加入樹(shù)中，若滿足條

14、件，再次調(diào)用DFS進(jìn)行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中（3）判斷節(jié)點(diǎn)后位的位置是否被選中且還未加入樹(shù)中，若滿足條件，再次調(diào)用DFS進(jìn)行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中（4）判斷節(jié)點(diǎn)右位的位置是否被選中且還未加入樹(shù)中，若滿足條件，再次調(diào)用DFS進(jìn)行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中第五步，判斷孩子鏈表是否為空，若不為空，將該鏈表設(shè)置為節(jié)點(diǎn)屬性child的值第六步，返回當(dāng)前節(jié)點(diǎn)2.4 對(duì)生成森林中的每棵生成樹(shù)，根據(jù)樹(shù)的生成路徑，調(diào)用generateOrders算法生成要發(fā)送給每個(gè)節(jié)點(diǎn)的指令指令的生成依據(jù)：指令的生成根據(jù)生成樹(shù)中節(jié)點(diǎn)之間的父子

15、關(guān)系（見(jiàn)表2）和節(jié)點(diǎn)本身的位置關(guān)系（見(jiàn)表3）。生成指令的規(guī)則：指令規(guī)則需滿足所有節(jié)點(diǎn)都通過(guò)能提交信息或被提交信息（即他人提交自己的信息）供服務(wù)器進(jìn)行驗(yàn)證。本文采用父親掃孩子，孤點(diǎn)掃教師，一次提交雙方驗(yàn)證的規(guī)則進(jìn)行校驗(yàn)。（1）父親掃孩子：即父親節(jié)點(diǎn)可通過(guò)提交孩子的信息完成選座的二次校驗(yàn)。（2）孤點(diǎn)掃教師：孤點(diǎn)指周圍（前位、左位、后位、右位）無(wú)節(jié)點(diǎn)，單獨(dú)成為一棵生成樹(shù)的節(jié)點(diǎn)，此類節(jié)點(diǎn)無(wú)法通過(guò)父子節(jié)點(diǎn)的關(guān)系進(jìn)行校驗(yàn)，因此本文采用孤點(diǎn)掃教師的規(guī)則，即孤點(diǎn)通過(guò)提交教師給與的信息完成驗(yàn)證。（3）一次提交雙方驗(yàn)證：即一次提交信息的過(guò)程，提交信息的一方與被提交信息的一方皆可以完成校驗(yàn)。因此，指令可分為三種，一

16、是發(fā)送給孤點(diǎn)（該座位為孤點(diǎn)，請(qǐng)找教師進(jìn)行校驗(yàn)）;二是當(dāng)前節(jié)點(diǎn)存在父親節(jié)點(diǎn)（請(qǐng)將你的信息提供給某某方同學(xué)）;三是當(dāng)前節(jié)點(diǎn)存在孩子節(jié)點(diǎn)（請(qǐng)?zhí)峤荒衬撤酵瑢W(xué)信息）。由于考慮到每個(gè)座位的學(xué)生只發(fā)一種指令，大概率會(huì)造成部分同學(xué)無(wú)法完成校驗(yàn)，因此對(duì)于同時(shí)存在父子節(jié)點(diǎn)或存在多個(gè)孩子節(jié)點(diǎn)的節(jié)點(diǎn)，采用糅合第二三種指令的方式生成指令。generateOrders算法：生成指令算法的關(guān)鍵在于怎樣保存對(duì)應(yīng)節(jié)點(diǎn)的指令與如何判斷節(jié)點(diǎn)的性質(zhì)。對(duì)于節(jié)點(diǎn)指令的保存問(wèn)題，本文采用哈希表HashMap orderMap保存指令與節(jié)點(diǎn)與指令的聯(lián)系，后續(xù)只需通過(guò)位置或?qū)W號(hào)便可取到對(duì)應(yīng)的指令;對(duì)于如何判斷節(jié)點(diǎn)的性質(zhì)問(wèn)題，本文采用迭代器遍歷

17、森林中生成樹(shù)與遍歷生成樹(shù)中的節(jié)點(diǎn)，逐一比較。步驟如下：（1）判斷節(jié)點(diǎn)是否為孤點(diǎn)。孤點(diǎn)的判斷只需判斷節(jié)點(diǎn)所在的生成樹(shù)中節(jié)點(diǎn)的數(shù)量，當(dāng)節(jié)點(diǎn)數(shù)量為1，即表示該節(jié)點(diǎn)為孤點(diǎn)。將孤點(diǎn)指令與節(jié)點(diǎn)Node放進(jìn)orderMap中。（2）判斷節(jié)點(diǎn)是否存在父節(jié)點(diǎn)。判斷是否存在父節(jié)點(diǎn)需判斷當(dāng)前節(jié)點(diǎn)的屬性parent是否為NULL，若不為空，即表示節(jié)點(diǎn)存在父節(jié)點(diǎn)。若父節(jié)點(diǎn)存在，需判斷父節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的位置（即屬性row與column），得出節(jié)點(diǎn)與父節(jié)點(diǎn)的位置關(guān)系（例如，前方），生成指令（例如，請(qǐng)將你的信息提供給前方同學(xué)）。將指令與節(jié)點(diǎn)Node放進(jìn)orderMap中。（3）判斷節(jié)點(diǎn)是否存在子節(jié)點(diǎn)。判斷是否存在子節(jié)點(diǎn)需判斷

18、當(dāng)前節(jié)點(diǎn)的屬性child是否為NULL，若不為空，即表示存在孩子節(jié)點(diǎn)。孩子節(jié)點(diǎn)存在，需進(jìn)一步判斷孩子節(jié)點(diǎn)的數(shù)量與孩子節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的位置關(guān)系，由于本文使用LinkedList結(jié)構(gòu)去存放孩子節(jié)點(diǎn)，因此此處只需通過(guò)迭代器遍歷child，在迭代中判斷每個(gè)孩子節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的位置，返回對(duì)應(yīng)位置信息（例如左后方），生成指令（例如，請(qǐng)?zhí)峤蛔蠛蠓酵瑢W(xué)信息）。將指令與節(jié)點(diǎn)Node放進(jìn)orderMap中。（4）判斷節(jié)點(diǎn)是否同時(shí)存在父子節(jié)點(diǎn)。當(dāng)一節(jié)點(diǎn)同時(shí)滿足上述（2）（3），則表示節(jié)點(diǎn)同時(shí)存在父子節(jié)點(diǎn)，因此節(jié)點(diǎn)指令只需糅合（2）（3）步驟獲得的指令（例如，請(qǐng)將你的信息提供給前方同學(xué)或提交左后方同學(xué)信息）。將指令與

19、節(jié)點(diǎn)Node放進(jìn)orderMap中。2.5 向節(jié)點(diǎn)發(fā)送指令與獲取學(xué)生提交的信息由于搭建了WebSocket實(shí)時(shí)交互的通信環(huán)境，此步驟技術(shù)難度大大降低，向節(jié)點(diǎn)發(fā)送指令與獲取提交信息皆可在WebSocket服務(wù)器中完成。作者在搭建WebSocket服務(wù)器，考慮到算法需要實(shí)現(xiàn)服務(wù)器對(duì)單一客戶端進(jìn)行通信，在服務(wù)器中使用session來(lái)區(qū)別不同的客戶端，以學(xué)號(hào)作為標(biāo)識(shí)將每個(gè)客戶端對(duì)應(yīng)的WebSocket實(shí)例存放到ConcurrentHashMap clients中。服務(wù)器通過(guò)OnMessage方法獲得用戶的選座信息與提交的驗(yàn)證信息;通過(guò)學(xué)號(hào)遍歷clients，獲取對(duì)應(yīng)的session，再通過(guò)sessio

20、n的getBasicRemote（）.sendText方法向客戶端發(fā)送指令與驗(yàn)證結(jié)果。2.6 將位置信息與選座座位表進(jìn)行驗(yàn)證，生成簽到座位表首先，需解析學(xué)生提交的座位信息。提交信息的方式與信息內(nèi)容可自行擴(kuò)展（例如，在登錄的時(shí)候?yàn)槊總€(gè)學(xué)生生成一個(gè)uuid，將uuid生成為二維碼，每個(gè)學(xué)生有對(duì)應(yīng)的一個(gè)二維碼作為標(biāo)識(shí)，提交信息的方式可以同時(shí)掃二維碼提交對(duì)應(yīng)的uuid完成驗(yàn)證）本文為了簡(jiǎn)化將需要提交的信息code設(shè)置為學(xué)生學(xué)號(hào)。驗(yàn)證過(guò)程如下：第一步，獲取學(xué)生學(xué)號(hào)與提交的信息code第二步，判斷是否已經(jīng)結(jié)束選座第三步，進(jìn)入校驗(yàn)流程：（1）獲取選座時(shí)生成的座位森林arrList，遍歷arrList中每棵生

21、成樹(shù)的節(jié)點(diǎn)（本文采用嵌套雙重迭代器進(jìn)行查詢），找到與學(xué)生學(xué)號(hào)對(duì)應(yīng)的節(jié)點(diǎn)。（2）判斷節(jié)點(diǎn)是否存在孩子節(jié)點(diǎn)。若存在孩子節(jié)點(diǎn)，比較孩子節(jié)點(diǎn)的學(xué)號(hào)（屬性digits）是否與獲取的提交信息code匹配。若匹配通過(guò)WebSocket發(fā)送雙方校驗(yàn)通過(guò)的信息到教師客戶端。若孩子節(jié)點(diǎn)皆無(wú)匹配項(xiàng)與不存在孩子，進(jìn)入下一輪判定。（3）判斷節(jié)點(diǎn)是否存在父節(jié)點(diǎn)。若存在父節(jié)點(diǎn)，比較父節(jié)點(diǎn)的學(xué)號(hào)（屬性digits）是否與獲取的提交信息code匹配。若匹配通過(guò)WebSocket發(fā)送雙方校驗(yàn)通過(guò)的信息到教師客戶端。若父節(jié)點(diǎn)皆無(wú)匹配項(xiàng)與不存在父節(jié)點(diǎn)，進(jìn)入下一輪判定。（4）父子節(jié)點(diǎn)都判定失敗，跳出一重遍歷，判斷節(jié)點(diǎn)所在生成 樹(shù)的節(jié)點(diǎn)

22、數(shù)量是否為1。若為1，比較教師工號(hào)與獲取的提交信息code。若匹配，通過(guò)WebSocket發(fā)送該學(xué)生校驗(yàn)通過(guò)的信息到教師客戶端;若不匹配，發(fā)送該學(xué)生校驗(yàn)失敗的信息到教師客戶端。為節(jié)點(diǎn)數(shù)量不為1，則發(fā)送雙方校驗(yàn)失敗的信息到教師客戶端。第四步，校驗(yàn)結(jié)束。當(dāng)學(xué)生完成校驗(yàn)后，前端可通過(guò)分析選座表，學(xué)號(hào)表反饋信息生成簽到座位表，本文只分析算法實(shí)現(xiàn)，不考慮前端具體實(shí)現(xiàn)，故此處不詳細(xì)分析。3 基于生成樹(shù)的互校驗(yàn)簽到算法測(cè)試為了保證算法在實(shí)際運(yùn)用中的可行性與穩(wěn)定性，作者搭建了一個(gè)簡(jiǎn)單的SSM項(xiàng)目進(jìn)行模擬測(cè)試。3.1 開(kāi)發(fā)環(huán)境硬件參數(shù)CPU：Intel（R） Core（TM） i5-7200U CPU 2.5

23、GHz 2.70 GHz;內(nèi)存：8.00 GB;存儲(chǔ)：SSD 128 G;網(wǎng)絡(luò)：40 M開(kāi)發(fā)平臺(tái)Windows 10系統(tǒng)PC機(jī);Eclipse +JDK1.8;Tomcat7服務(wù)器3.2 算法測(cè)試（1）測(cè)試流程：學(xué)生提交座位信息進(jìn)行選座，當(dāng)所有學(xué)生完成選座，教師結(jié)束選座。系統(tǒng)根據(jù)選座信息調(diào)用算法生成森林和指令，通過(guò)WebSocket向?qū)?yīng)的學(xué)生發(fā)送指令。（2）學(xué)生根據(jù)指令在code框中輸入對(duì)應(yīng)同學(xué)學(xué)號(hào)。系統(tǒng)接受信息調(diào)用算法進(jìn)行校驗(yàn)，最終向教師發(fā)送結(jié)果，完成校驗(yàn)。圖4為測(cè)試流程圖。（3）測(cè)試用例：1）教師用例：20170122）學(xué)生用例：2017001、2017002、2017003、20170

24、04、2017005、2017006、2017007、2017008、2017009、2017010（座位表見(jiàn)表2）3）校驗(yàn)信息用例：2017001提交2017005（父掃子通過(guò)）;2017006提交2017005（子掃父通過(guò)）;2017002提交2017001（無(wú)關(guān)座位失敗）;2017009提交2017012（非孤點(diǎn)掃教師通過(guò)）;2017010提交2017012（孤點(diǎn)掃教師通過(guò)）;2017010提交2017003（孤點(diǎn)掃無(wú)關(guān)座位失?。?）算法執(zhí)行時(shí)間：1）教師結(jié)束選座后，系統(tǒng)生成森林，生成指令，發(fā)送指令到客戶端的執(zhí)行時(shí)間：當(dāng)參與簽到的學(xué)生為10人時(shí)，執(zhí)行時(shí)間為5 ms;當(dāng)參與簽到的學(xué)生為50人時(shí)，執(zhí)行時(shí)間為31 ms;當(dāng)參與簽到的學(xué)生為100人時(shí)，執(zhí)行時(shí)間為60 ms;2）單位學(xué)生提交校驗(yàn)信息，系統(tǒng)完成校驗(yàn)并返回結(jié)果的時(shí)間為3 ms。因此粗略估計(jì)，當(dāng)參與簽到的學(xué)生為10人時(shí)，校驗(yàn)信息步驟的執(zhí)行時(shí)間為30 ms;當(dāng)參與簽到的學(xué)生為50人時(shí)，校驗(yàn)信息