吳偉銓 王芳

摘 ?要： 文中講述了基于生成樹的學生互校驗簽到算法的實現(xiàn)方案，主要思路是通過搭建WebSocket實時交互環(huán)境，獲取算法的信息輸入與結(jié)果反饋;文中對互校驗算法進行了分析并實現(xiàn);最后對算法進行測試，結(jié)果表明，該方案能夠快速實現(xiàn)算法的校驗。

關(guān)鍵詞： 簽到;生成樹;選座;相互校驗;考勤;算法

中圖分類號： TP311 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.01.002

本文著錄格式：吳偉銓，王芳. 基于生成樹的學生互校驗簽到算法實現(xiàn)[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 ?引言

目前，高校在針對學生課堂考勤簽到方面存在著許多問題。傳統(tǒng)的點名考勤費時費力，占用了大量珍貴的課堂教學時間，考勤效率不高，同時存在許多學生找同學幫忙答到渾水摸魚，考勤的準確性不高。隨著移動互聯(lián)網(wǎng)技術(shù)的發(fā)展，近些年涌現(xiàn)大批手機簽到系統(tǒng)，如使用無線局域網(wǎng)和手機IMEI的簽到系統(tǒng)[1]、使用藍牙技術(shù)和二維碼技術(shù)的點名軟件[2]，基于WIFI的室內(nèi)定位簽到[3]，基于GPS定位的簽到[4-5]等，但都存在其局限性，如無法精確判斷學生是否到達課室，在學校推廣與普及難度較大。

本文講述了一種基于生成樹的學生互校驗簽到算法[6]的實現(xiàn)方案。該方案基于WebSocket技術(shù)搭建實時交互環(huán)境，通過WebSocket獲取學生提交的選座信息經(jīng)處理轉(zhuǎn)化為生成樹，根據(jù)生成樹生成校驗信息指令，學生通過指令完成二次校驗，實現(xiàn)學生間相互校驗。該方案既縮短了位置校驗的時間，提高課堂考勤的效率同時學生互校驗很大程度上保證了校驗的準確度。最后，文章針對算法進行分別進行了10人次，50人次與100人次的測試，驗證了算法的高效性。

1 ?基于生成樹的互校驗簽到算法設計

1.1 ?基于生成樹的互校驗簽到算法[6]

第1步：根據(jù)選座座位表生成無向圖G

第2步：調(diào)用DFS（或BFS）算法遍歷無向圖G，生成森林

第3步：對生成森林中的每棵生成樹，根據(jù)樹的生成路徑，調(diào)用generateOrders算法（見算法2）生成要發(fā)送給每個節(jié)點的指令

第4步：向每個節(jié)點表示的學生發(fā)送對應的指令

第5步：獲取學生根據(jù)指令提交的位置信息

第6步：將位置信息與選座座位表進行對比，生成簽到座位表

1.2 ?基于生成樹的互校驗簽到算法分析

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

實現(xiàn)校驗算法的關(guān)鍵主要在于以下三個部分：（1）如何搭建實時同步的校驗環(huán)境;（2）如何將座位信息轉(zhuǎn)化后生成生成樹、生成指令;（3）如何進行二次校驗

2 ?基于生成樹的互校驗簽到算法實現(xiàn)

2.1 ?基于WebSocket技術(shù)搭建實時交互的校驗環(huán)境

互校驗簽到算法的實現(xiàn)對通信環(huán)境的要求：（1）提供一個能夠讓客戶端持續(xù)向服務器發(fā)送請求，服務器及時響應并作出相應的動作;（2）服務器主動向客戶端推送信息傳統(tǒng)的HTTP協(xié)議是一個請求-響應協(xié)議，通信只能有客戶端發(fā)起，做不到服務器主動向客戶端推送消息。目前許多網(wǎng)站實現(xiàn)推送技術(shù)，所用的技術(shù)都是Ajax輪詢。輪詢是在特定的時間間隔，通過瀏覽器對服務器發(fā)送HTTP請求，由服務器返回最新的數(shù)據(jù)給客戶端的瀏覽器。由于瀏覽器需要不斷的向服務器發(fā)出請求，而HTTP請求可能包含較長的頭部，真正有效的數(shù)據(jù)往往可能只是很小的一部分，這樣會浪費很多的帶寬等資源，效率低[7]。

HTML5定義的WebSocket協(xié)議則是一種在單個TCP連接上進行全雙工的通信協(xié)議[8]，使得客戶端和服務器之間的數(shù)據(jù)交換變得更加簡單，允許服務器主動向客戶端推送數(shù)據(jù)。在WebSocket API中，瀏覽器和服務器只需要完成一次握手，兩者之間就直接可以創(chuàng)建持久性的連接，并進行雙向數(shù)據(jù)傳輸，相比基于HTTP的輪詢技術(shù)，大大提高了效率和資源的利用率。

因此本文基于WebSocket協(xié)議搭建簽到校驗環(huán)境，后端使用Tomcat 搭建WebSocket服務器。

2.2 ?獲取學生選座信息生成無向圖

由于大學課室座位一般為行列對齊，形成m*n型。因此獲取學生的選座信息生成無向圖能夠轉(zhuǎn)化為以矩陣的形式表現(xiàn)的學生選座狀態(tài)矩陣和學生信息矩陣（與選座狀態(tài)矩陣對應）。

矩陣一般可使用二維數(shù)組進行存儲。

學生選座狀態(tài)矩陣用于表示學生當前的選座狀態(tài)，即已選座與未選座，因此可使用二維整型數(shù)組表示：0-未選座，1-已選座。數(shù)組可見圖1。

學生信息矩陣用于存儲選座狀態(tài)矩陣每個節(jié)點所對應的學生信息，矩陣中每個節(jié)點代表一個學生。由于二維數(shù)組每個節(jié)點無法存儲過多的信息，且此處的學生信息只為了標識學生是否選座，因此可使用字符串數(shù)組中保存學生學號，數(shù)組可見圖2。

2.3 ?調(diào)用DFS算法遍歷無向圖，生成森林S

由于無向圖在上一步驟中簡化為學生選座狀態(tài)數(shù)組（簡稱為選座表）與學生學號數(shù)組（簡稱為學號表）。因此本步驟算法可分為兩部分，第一部分為generateForest算法，遍歷選座表，判斷節(jié)點是否已經(jīng)加入森林，若未加入則以該節(jié)點為根節(jié)點調(diào)用DFS算法進行遍歷，最終生成森林;第二部分為DFS算法，遍歷選座表與學號表，生成對應關(guān)系的生成樹。

由于后續(xù)需要根據(jù)生成樹，調(diào)用generateOrders算法生成對應節(jié)點的指令并發(fā)送。因此，DFS算法遍歷后的生成樹的節(jié)點需要周圍節(jié)點（前位、左位、后位、右位）相關(guān)聯(lián)。

定義一個節(jié)點類（Node）。

由于在后續(xù)算法的實現(xiàn)中多使用迭代器遍歷，鏈表結(jié)構(gòu)的集合使用迭代器遍歷，速度會更快，因此本文使用LinkedList類存放生成樹與森林。

2.3.1 ?generateForest算法的設計

第一步，獲取選座表與學號表作為信息輸入，實例化森林LinkedList> arrList，用于存放DFS算法生成的生成樹。

第二步，座位表中任一節(jié)點都有存在成為生成樹根節(jié)點的可能性，因此本文采用for循環(huán)的雙重嵌套遍歷選座表（二維數(shù)組）。在循環(huán)體中，實例化生成樹LinkedList nodeArr，判斷當前位置是否被選中（選座狀態(tài)：0-未選座，1-已選座）和是否已加入森林（編寫函數(shù)，將生成的森林（arrList）與當前的生成樹（nodeArr）和當前位置作為參數(shù)傳入，判斷當前位置是否與arrList和nodeArr中節(jié)點Node中屬性（row，column）相同，若存在相同，表示當前位置已加入，反之則未加入），若當前位置滿足被選中且未加入森林，調(diào)用DFS算法遍歷，生成以當前節(jié)點有根的生成樹。

第三步，若生成樹不為空，將生成的生成樹加入森林（nodeArr）。

2.3.2 ?DFS算法的設計

深度優(yōu)先搜索（DFS）：在搜索過程中訪問某個頂點后，需要遞歸地訪問此頂點的所有未訪問過的相鄰頂點。

第一步，獲取數(shù)據(jù)輸入：

（1）根節(jié)點位置

（2）選座表（二維整型數(shù)組）和學號表（二維字符串數(shù)組）

（3）當前節(jié)點的父親節(jié)點（根節(jié)點無父親節(jié)點，這項置空）

（4）節(jié)點所在生成樹（nodeArr）和森林（arrList）

第二步，實例化當前節(jié)點（Node）與創(chuàng)建孩子鏈表LinkedList child存放當前節(jié)點的孩子節(jié)點，并將當前節(jié)點（Node）添加至生成樹（nodeArr）

第三步，為當前節(jié)點（Node）賦值：

（1）根據(jù)傳入的根節(jié)點位置設置屬性row和column

（2）根據(jù)學號表與row和column值設置屬性digits

（3）判斷獲取的父親節(jié)點是否為空，不為空則將該節(jié)點賦給屬性parent

第四步，搜索孩子節(jié)點：

（1）判斷節(jié)點前位的位置是否被選中且還未加入樹中，若滿足條件，再次調(diào)用DFS進行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中

（2）判斷節(jié)點左位的位置是否被選中且還未加入樹中，若滿足條件，再次調(diào)用DFS進行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中

（3）判斷節(jié)點后位的位置是否被選中且還未加入樹中，若滿足條件，再次調(diào)用DFS進行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中

（4）判斷節(jié)點右位的位置是否被選中且還未加入樹中，若滿足條件，再次調(diào)用DFS進行遞歸，并將遞歸返回結(jié)果添加到孩子鏈表（child）中

第五步，判斷孩子鏈表是否為空，若不為空，將該鏈表設置為節(jié)點屬性child的值

第六步，返回當前節(jié)點

2.4 ?對生成森林中的每棵生成樹，根據(jù)樹的生成路徑，調(diào)用generateOrders算法生成要發(fā)送給每個節(jié)點的指令

指令的生成依據(jù)：指令的生成根據(jù)生成樹中節(jié)點之間的父子關(guān)系（見表2）和節(jié)點本身的位置關(guān)系（見表3）。

生成指令的規(guī)則：指令規(guī)則需滿足所有節(jié)點都通過能提交信息或被提交信息（即他人提交自己的信息）供服務器進行驗證。本文采用父親掃孩子，孤點掃教師，一次提交雙方驗證的規(guī)則進行校驗。

（1）父親掃孩子：即父親節(jié)點可通過提交孩子的信息完成選座的二次校驗。

（2）孤點掃教師：孤點指周圍（前位、左位、后位、右位）無節(jié)點，單獨成為一棵生成樹的節(jié)點，此類節(jié)點無法通過父子節(jié)點的關(guān)系進行校驗，因此本文采用孤點掃教師的規(guī)則，即孤點通過提交教師給與的信息完成驗證。

（3）一次提交雙方驗證：即一次提交信息的過程，提交信息的一方與被提交信息的一方皆可以完成校驗。

因此，指令可分為三種，一是發(fā)送給孤點（該座位為孤點，請找教師進行校驗）;二是當前節(jié)點存在父親節(jié)點（請將你的信息提供給某某方同學）;三是當前節(jié)點存在孩子節(jié)點（請?zhí)峤荒衬撤酵瑢W信息）。由于考慮到每個座位的學生只發(fā)一種指令，大概率會造成部分同學無法完成校驗，因此對于同時存在父子節(jié)點或存在多個孩子節(jié)點的節(jié)點，采用糅合第二三種指令的方式生成指令。

generateOrders算法：生成指令算法的關(guān)鍵在于怎樣保存對應節(jié)點的指令與如何判斷節(jié)點的性質(zhì)。對于節(jié)點指令的保存問題，本文采用哈希表HashMap orderMap保存指令與節(jié)點與指令的聯(lián)系，后續(xù)只需通過位置或?qū)W號便可取到對應的指令;對于如何判斷節(jié)點的性質(zhì)問題，本文采用迭代器遍歷森林中生成樹與遍歷生成樹中的節(jié)點，逐一比較。

步驟如下：

（1）判斷節(jié)點是否為孤點。孤點的判斷只需判斷節(jié)點所在的生成樹中節(jié)點的數(shù)量，當節(jié)點數(shù)量為1，即表示該節(jié)點為孤點。將孤點指令與節(jié)點Node放進orderMap中。

（2）判斷節(jié)點是否存在父節(jié)點。判斷是否存在父節(jié)點需判斷當前節(jié)點的屬性parent是否為NULL，若不為空，即表示節(jié)點存在父節(jié)點。若父節(jié)點存在，需判斷父節(jié)點與當前節(jié)點的位置（即屬性row與column），得出節(jié)點與父節(jié)點的位置關(guān)系（例如，前方），生成指令（例如，請將你的信息提供給前方同學）。將指令與節(jié)點Node放進orderMap中。

（3）判斷節(jié)點是否存在子節(jié)點。判斷是否存在子節(jié)點需判斷當前節(jié)點的屬性child是否為NULL，若不為空，即表示存在孩子節(jié)點。孩子節(jié)點存在，需進一步判斷孩子節(jié)點的數(shù)量與孩子節(jié)點與當前節(jié)點的位置關(guān)系，由于本文使用LinkedList結(jié)構(gòu)去存放孩子節(jié)點，因此此處只需通過迭代器遍歷child，在迭代中判斷每個孩子節(jié)點與當前節(jié)點的位置，返回對應位置信息（例如左后方），生成指令（例如，請?zhí)峤蛔蠛蠓酵瑢W信息）。將指令與節(jié)點Node放進orderMap中。

（4）判斷節(jié)點是否同時存在父子節(jié)點。當一節(jié)點同時滿足上述（2）（3），則表示節(jié)點同時存在父子節(jié)點，因此節(jié)點指令只需糅合（2）（3）步驟獲得的指令（例如，請將你的信息提供給前方同學或提交左后方同學信息）。將指令與節(jié)點Node放進orderMap中。

2.5 ?向節(jié)點發(fā)送指令與獲取學生提交的信息

由于搭建了WebSocket實時交互的通信環(huán)境，此步驟技術(shù)難度大大降低，向節(jié)點發(fā)送指令與獲取提交信息皆可在WebSocket服務器中完成。作者在搭建WebSocket服務器，考慮到算法需要實現(xiàn)服務器對單一客戶端進行通信，在服務器中使用session來區(qū)別不同的客戶端，以學號作為標識將每個客戶端對應的WebSocket實例存放到ConcurrentHashMap< String， WebSocket> clients中。服務器通過OnMessage方法獲得用戶的選座信息與提交的驗證信息;通過學號遍歷clients，獲取對應的session，再通過session的getBasicRemote（）.sendText方法向客戶端發(fā)送指令與驗證結(jié)果。

2.6 ?將位置信息與選座座位表進行驗證，生成簽到座位表

首先，需解析學生提交的座位信息。提交信息的方式與信息內(nèi)容可自行擴展（例如，在登錄的時候為每個學生生成一個uuid，將uuid生成為二維碼，每個學生有對應的一個二維碼作為標識，提交信息的方式可以同時掃二維碼提交對應的uuid完成驗證）本文為了簡化將需要提交的信息code設置為學生學號。

驗證過程如下：

第一步，獲取學生學號與提交的信息code

第二步，判斷是否已經(jīng)結(jié)束選座

第三步，進入校驗流程：

（1）獲取選座時生成的座位森林arrList，遍歷arrList中每棵生成樹的節(jié)點（本文采用嵌套雙重迭代器進行查詢），找到與學生學號對應的節(jié)點。

（2）判斷節(jié)點是否存在孩子節(jié)點。若存在孩子節(jié)點，比較孩子節(jié)點的學號（屬性digits）是否與獲取的提交信息code匹配。若匹配通過WebSocket發(fā)送雙方校驗通過的信息到教師客戶端。若孩子節(jié)點皆無匹配項與不存在孩子，進入下一輪判定。

（3）判斷節(jié)點是否存在父節(jié)點。若存在父節(jié)點，比較父節(jié)點的學號（屬性digits）是否與獲取的提交信息code匹配。若匹配通過WebSocket發(fā)送雙方校驗通過的信息到教師客戶端。若父節(jié)點皆無匹配項與不存在父節(jié)點，進入下一輪判定。

（4）父子節(jié)點都判定失敗，跳出一重遍歷，判斷節(jié)點所在生成 樹的節(jié)點數(shù)量是否為1。若為1，比較教師工號與獲取的提交信息code。若匹配，通過WebSocket發(fā)送該學生校驗通過的信息到教師客戶端;若不匹配，發(fā)送該學生校驗失敗的信息到教師客戶端。為節(jié)點數(shù)量不為1，則發(fā)送雙方校驗失敗的信息到教師客戶端。

第四步，校驗結(jié)束。

當學生完成校驗后，前端可通過分析選座表，學號表反饋信息生成簽到座位表，本文只分析算法實現(xiàn)，不考慮前端具體實現(xiàn)，故此處不詳細分析。

3 ?基于生成樹的互校驗簽到算法測試

為了保證算法在實際運用中的可行性與穩(wěn)定性，作者搭建了一個簡單的SSM項目進行模擬測試。

3.1 ?開發(fā)環(huán)境

硬件參數(shù)——CPU：Intel（R） Core（TM） i5-7200U CPU @ 2.5 GHz 2.70 GHz;內(nèi)存：8.00 GB;存儲：SSD 128 G;網(wǎng)絡：40 M

開發(fā)平臺——Windows 10系統(tǒng)PC機;Eclipse +JDK1.8;Tomcat7服務器

3.2 ?算法測試

（1）測試流程：學生提交座位信息進行選座，當所有學生完成選座，教師結(jié)束選座。系統(tǒng)根據(jù)選座信息調(diào)用算法生成森林和指令，通過WebSocket向?qū)膶W生發(fā)送指令。

（2）學生根據(jù)指令在code框中輸入對應同學學號。系統(tǒng)接受信息調(diào)用算法進行校驗，最終向教師發(fā)送結(jié)果，完成校驗。圖4為測試流程圖。

（3）測試用例：

1）教師用例：2017012

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

3）校驗信息用例：2017001提交2017005（父掃子通過）;2017006提交2017005（子掃父通過）;2017002提交2017001（無關(guān)座位失?。?2017009提交2017012（非孤點掃教師通過）;2017010提交2017012（孤點掃教師通過）;2017010提交2017003（孤點掃無關(guān)座位失敗）

（3）算法執(zhí)行時間：

1）教師結(jié)束選座后，系統(tǒng)生成森林，生成指令，發(fā)送指令到客戶端的執(zhí)行時間：當參與簽到的學生為10人時，執(zhí)行時間為5 ms;當參與簽到的學生為50人時，執(zhí)行時間為31 ms;當參與簽到的學生為100人時，執(zhí)行時間為60 ms;2）單位學生提交校驗信息，系統(tǒng)完成校驗并返回結(jié)果的時間為3 ms。因此粗略估計，當參與簽到的學生為10人時，校驗信息步驟的執(zhí)行時間為30 ms;當參與簽到的學生為50人時，校驗信息步驟的執(zhí)行時間為150 ms;當參與簽到的學生為100人時，校驗信息步驟的執(zhí)行時間為300 ms;綜上所述，當一個班級有10位學生，互校驗算法的執(zhí)行時間為35 ms，平均每人3.50 ms;當一個班級有50位學生，互校驗算法的執(zhí)行時間為181 ms，平均每人3.68 ms;當一個班級有100位學生，互校驗算法的執(zhí)行時間為360 ms，平均每人3.60 ms。

4 ?結(jié)語

本文實現(xiàn)了基于生成樹的學生互校驗簽到的算法，該算法解決方案的實現(xiàn)基于Java搭建WebSocket實時交互環(huán)境，在WebSocket交互環(huán)境的基礎上進行算法的實現(xiàn)，大大簡化了獲取選座信息，提交校驗信息等信息傳遞環(huán)節(jié)的實現(xiàn)難度?；谏蓸涞膶W生互校驗簽到算法執(zhí)行速度快，具有很強的實用性和推廣價值。

參考文獻

[1] 劉冬梅， 任亞平， 周杰等. 基于Android的手機簽到系統(tǒng)[J]. 科技資訊， 2017， 14： 17-18.

[2] 陳三清， 殷鵬. 基于Android手機的課堂點名軟件設計與實現(xiàn)[J]. 電腦知識與技術(shù)， 2017， 7： 95-99.

[3] 蔣航， 蔡秋楓. 基于室內(nèi)定位的學生簽到系統(tǒng)設計[J]. 電腦知識與技術(shù)， 2017， 1： 54-55.

[4] 張勁波， 周澤崇， 李雅杰等. 基于Android的上課簽到軟件分析與設計[J]. 電腦編程技巧與維護， 2017， 2（3）： 28.

[5] 徐寧. 基于微信平臺的并行簽到考勤管理系統(tǒng)[J]. 電腦知識與技術(shù)， 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.