基于生成樹的學生互校驗簽到算法實現

吳偉銓 王芳

摘 ?要： 文中講述了基于生成樹的學生互校驗簽到算法的實現方案，主要思路是通過搭建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.