基于TCC的經典算法互動實驗平臺設計

黎孟雄， 李 楊， 黎知秋(.江蘇師范大學連云港校區 數學與信息工程學院，江蘇 連云港 006；.連云港市教育管理信息中心，江蘇 連云港 006；.微軟亞洲研究院，北京 00080)

0 引 言

“算法設計與分析”是計算機學科各專業非常重要的核心基礎課，要求學生通過對經典算法的設計思路、分析方法和實現技術進行學習研究，旨在培養學生運用時空復雜度思維來設計和應用算法以切實提高解決實際問題的能力，為開發高效的軟件系統奠定良好的基礎。這些經典算法包括：窮舉、遞歸、分治、動態規劃、貪心、分支限界、回溯和隨機等算法。不過，由于這些算法本身具有理論性強、內容抽象等特點，盡管“算法設計與分析”是一門理論和實踐結合緊密、強調知識和能力并重的課程，但學生在學習的過程當中卻普遍感覺枯燥乏味、興趣低下，不僅課內教學師生互動不足、教學不彰，學生課后復習的主觀能動性同樣是不盡人意[1-4]。主要原因就是大部分高校因為總教學時數和實驗條件的限制只考慮理論教學課時的安排，實驗課時安排較少甚至根本就沒有安排，嚴重影響了學生對算法原理、設計思想的理解和消化，影響了學生的動手實踐能力和技術創新能力的培養[5-8]。

因此，要有效提高該門課程的教學質量，除了需要在課堂內精心組織理論課的教學，還需要特別重視實驗課的教學，在上機實驗環節上使算法學習和實驗設計盡可能趣味化、具體化、生活化，即通過生動有趣的應用案例嵌入算法實驗教學，達到促進理論知識的轉化和掌握算法的精髓，感受算法之美，激發學生的學習興趣和潛能。所以，一方面為應對傳統實驗室受教學資源、師資力量和實驗時間等條件的制約，另一方面給學生提供一個更加便捷、易用的算法實驗環境，本文設計了基于微型C語言編譯器(Tiny C Compiler,TCC)的經典算法互動實驗平臺。該實驗平臺算法知識資源豐富，內嵌的TCC編譯軟件體積小，為純綠色版，整個系統毋需安裝配置，方便學生隨身攜帶使用。

1 TCC及其優點

TCC是一款功能強大的超輕量級開源C語言編譯器，完全支持標準ANSI C語言源程序及其所有的Windows函數和C語言運行庫函數，甚至所有的DLL、LIB都可以被它用來作為擴展函數使用[9]。同時TCC也是一個頗具特色的C語言解釋器，可以在省略編譯和鏈接的情況下直接運行C語言源程序，就如同運行任何一種腳本語言如Perl、Python、Ruby、Shell一樣方便，但解釋執行的效率卻比腳本語言高得多，這樣不僅可以顯著地加快程序開發速度和專注于功能實現，還可以把TCC嵌入到用戶的應用程序中當作一個動態代碼生成器。

TCC除了具有高效的程序解釋執行功能，還有以下幾個優點：

(1) 體積非常小巧。一個完整的包括C語言的預處理器、編譯器、匯編器和鏈接器在內的TCC可執行程序只有80 K byte大小，可以說是世界上體積最小的編譯器。因此，TCC幾乎可以被使用在任何場合來運行C語言程序，包括對存儲空間要求極為嚴苛的嵌入式系統等環境。

(2) 編譯速度極快。與Turb C、Pelles C、Cygwin、Mingw32、DJGPP等其他C語言編譯器不同，TCC采用了單趟編譯器(one-pass compiler)的“語法制導翻譯”方式來貫穿整個編譯器的實現，由語法分析來驅動預處理與詞法分析，同時也由語法分析來驅動語義分析與目標代碼生成。編譯過程中不構造代碼的任何“中間表示”(intermediate representation，IR)，連AST也不需要生成，所以編譯速度極為迅速。

(3) 兼容性強。任何C語言動態庫都可以被直接引用，還支持C語言和匯編語言混合編程。

(4) 安全性高。TCC自帶內存邊界檢查器，可以防止代碼引用無效或非法的內存地址，減少了很多潛在的安全漏洞，極大地提高了程序的安全性和健壯性。

2 實驗平臺的體系結構

基于TCC經典算法互動實驗平臺的設計目的主要是以更具拓展性的經典算法學習和設計為實驗主題的教學輔助系統，同時在知識咨詢、代碼編寫、算法演示動畫等方面也具備較強的人機互動功能。實驗平臺的總體結構主要包括4個核心功能部分：算法主題學習、算法實驗練習、人機智能互動和實驗過程管理等模塊。實驗平臺的功能體系結構如圖1所示。

圖1 經典算法互動實驗平臺體系結構

(1) 算法主題學習模塊。實驗平臺內嵌的SQLite數據庫儲存了豐富的算法資源，除了涵蓋傳統的窮舉、遞歸、分治、貪心、回溯、隨機、分支限界和動態規劃等所有經典算法，還增加了卷積神經網絡、深度學習、樸素貝葉斯、模糊聚類、隱馬爾科夫、遺傳算法、快速傅里葉變換之類能應用在人工智能、大數據分析等前沿技術方面的熱門算法。對于每個算法知識的講解，均包括提出問題、解決策略、算法設計、編碼實現、分析評估和應用案例等幾個部分。在內容上比“算法設計與分析”課程的相關教材更加細致深入，補充了教材中沒有涉及或者闡述得不夠詳細的知識點，是課堂教學的重要拓展和延續，從而構建了一個比較完整的算法知識學習體系。另外，學習模塊還使用了大量有針對性的算法演示動畫，力圖讓抽象復雜的算法執行過程盡可能具體化、形象化。

(2) 算法實驗練習模塊。算法的編程實踐練習是算法學習過程中最重要的一環，也是實驗平臺最核心的模塊。平臺里的實驗題目選材新穎有趣又實用性強，寓理論于實踐中啟迪思維、開闊眼界。比如窮舉算法的實驗練習題有“百錢買百雞問題”“誰在說謊”“雞兔同籠”“QQ密碼找回”等；遞歸算法的實驗練習題有“兔子繁殖問題”“漢諾塔游戲”“小猴吃桃”“公交路線查詢”等；貪心算法的實驗練習題有“貨船裝箱調度”“物流網絡優化”“多機作業調度”“系統故障排查”等。為了提高上機實驗效率、減輕代碼編寫工作量，學生只需要編寫算法程序的關鍵部分即可。由于TCC能夠動態調用C語言腳本，所以學生編寫的代碼能夠完美地嵌入到已經預先編好的其余代碼中運行。當然，學生提交程序代碼之后實驗平臺會自動驗證以判斷算法是否正確。通過完成這些實驗練習，可以幫助學生理解和拓寬算法在求解問題中的靈活應用，并提高編寫程序解決實際問題的能力。

(3) 人機智能互動模塊。在算法設計的上機實驗過程中有很多學生總會或多或少地面臨一些問題和困難，如果不及時加以解決，哪怕是一個小的語法錯誤，也會嚴重影響整個實驗的進度。因此實驗平臺嵌入了智能導學機器人來模擬指導老師進行答疑解惑。通過和導學機器人的互動，學生不僅可以獲得相關范例算法的偽代碼流程以及程序實現的常見方法和技巧，更重要的是還可以對正在編寫的程序代碼進行語法檢查和診斷，如果程序編寫有錯則可精確定位到錯誤位置并得到詳細的錯誤提示信息和對應的輔導意見。

(4) 實驗過程管理模塊。為了督促學生從被動學習轉為主動學習，學生登錄實驗平臺后的所有操作過程都會被記錄在本地SQLite數據庫，當系統聯網后這些記錄信息會自動發送給任課教師，將在最終的實驗成績中有所體現。學生的操作過程包括算法主題的有效學習時長、完成的實驗題數量、實驗進度、實驗結果、實驗報告、人機互動等所有和實驗相關的行為狀態。為了防止學生實驗過程中的掛機行為，實驗平臺在啟動伊始就隨之在后臺進行非法進程監控和網頁內容監管[10]，一旦發現學生有玩游戲、看影視等行為就會立即彈窗警告。

3 關鍵技術的設計

3.1 實驗平臺的構建

經典算法互動實驗平臺基于Microsoft .NET Framework，采用Visual C#開發，后臺數據存儲使用嵌入式關系型數據庫SQLite，驅動引擎只有System.Data.SQLite.dll一個文件，小巧實用。為了數據庫內資料的安全，系統設計了多級用戶權限，有如:系統管理員、教師、注冊學生和普通游客等。

實驗平臺的用戶界面元素主要由算法知識資源呈現和學生實驗練習兩個核心單元構建而成。算法實驗練習模塊是整個系統的設計重點，每一個實驗都是把固定的算法邏輯放在主程序中，而將學生編寫的代碼部分寫入TCC腳本文件。這樣，把經常需要修改的邏輯部分用TCC來實現，則在學生驗證算法程序時就不需要頻繁編譯。另外，調用TCC腳本最方便的地方就是可以直接把指針當參數和返回值在腳本和宿主程序之間互相傳遞。因此，實驗平臺構建的關鍵在于TCC編譯器的調用，方法如下：

ProcessStarInfo AlgorithmTcc = new ProcessStarInfo("D: cc cc.exe",s); //設置路徑

AlgorithmTcc.Arguments = "-run " + strShowSname; //運行時的參數

AlgorithmTcc.RedirectStandardOutput = true; //調用程序獲取輸出信息

AlgorithmTcc.RedirectStandardInput = true; //接受來自調用程序的輸入信息

AlgorithmTcc.RedirectStandardError = true; //接受錯誤提示信息

AlgorithmTcc.UseShellExecute = false; //不使用系統默認程序啟動,重定向輸入流、輸出流和錯誤流

AlgorithmTcc.CreateNoWindow = true; //不顯示程序窗口

Process proTcc = Process.Start(AlgorithmTcc); //調用運行TCC編譯器

string strOutput = proTcc.StandardOutput.ReadToEnd() + proTcc.StandardError.ReadToEnd();

Tcc_Compiler.Text = strOutput; //把輸出信息顯示在文本框

AlgorithmTcc.WaitForExit();

AlgorithmTcc.Close(); //退出TCC

學生在編寫算法程序時，如果感覺邏輯復雜、代碼行過多，可以懸浮代碼窗口，調用代碼編輯器Sublime Text，它支持語法高亮、代碼補全、代碼折疊、行號顯示以及全屏免打擾模式等。

基于TCC的經典算法互動實驗平臺的用戶主界面如圖2所示。

3.2 人機智能互動

實驗平臺的人機互動主要體現在知識咨詢和代碼編寫錯誤的智能提示兩方面。

學生在進行算法編程實驗時如果遇到困難，可以向智能導學機器人求助咨詢，機器人首先從編程技巧知識庫和算法FAQ知識庫中檢索反饋，如果沒有答案則啟動垂直搜索引擎從Internet上檢索，模糊聚類后進行Top-N排序推薦最佳答案。

在代碼編寫方面的人機互動對實驗的順利進行顯得更為重要。C語言的靈活性雖然帶來了程序效率的提升，但其代碼編寫的隨意性也使得程序出錯概率較高。在用其他語言編程時可以輕易發現的錯誤，由于C語言編譯器不進行強制類型檢查、語法檢查也不嚴格而無法檢查到，帶來了代碼編寫的諸多隱患。

C語言的代碼檢查軟件主要有Coverity、Fortify、Flawfinder、PC-lint、Rats和Splint等[11]。前面兩種都偏重量級，需要提交源代碼到服務器審查，不便于隨身攜帶、隨時使用；Flawfinder和PC-lint的詞法掃描和語法分析速度極快，都內嵌了一些漏洞數據庫，如緩沖區溢出、格式化串漏洞等，但誤報率很高；Rats則掃描規則比較粗糙；Splint是一款功能強大而又小巧方便的開源靜態代碼檢測工具，會進行多種常規編程規范檢查，包括標點符號、流程結構錯誤、數組下標越界、數據類型不匹配、使用未定義變量、冗余代碼、忽略返回值、無限循環、內存泄漏以及其它編程陷阱和格式缺陷等[12]。

圖2 算法實驗平臺的用戶主界面

所以，實驗平臺使用Splint作為學生代碼檢測的內嵌工具，以期幫助他們節省程序測試時間、提高算法代碼質量、規范編程風格和行為。

splint需通過cmd命令行打開運行，其語法形式如下: splint [+/-options] *.c。options為各種參數設置，使用+/-開啟或關閉對應參數，例如：splint-showcol test.c，即在檢測test.c源程序時，警告消息中不顯示列數，splint +varuse test.c，即在檢測test.c源程序時，在警告消息中顯示未使用變量提示。當然也可以使用splintrc配置文件來設置各種參數，splint在安裝之后，splintrc文件中已經對大部分常規參數作了默認設定。splint命令行中指定的參數設置會覆蓋splintrc文件中的同名參數默認設定。

為了方便與學生進行人機互動，實驗平臺在學生提交算法程序時內部調用splint命令異步執行，然后通過導學機器人讀取splint運行后的警告信息列表予以彈窗提示，如圖3所示。

圖3 算法實驗平臺的人機智能互動

3.3 算法演示動畫

算法演示動畫的目的就是把抽象的算法知識具體化、形象化，以便學生更容易理解和掌握。算法在軟件中還體現為算法代碼，所以算法演示動畫的另外一個目的就是需要實現程序可視化[13]，比如通過顯示循環語句結構的執行流程來表現循環的邊界條件，或者通過輸出控件監視變量值的變化情況來動態觀察一些關鍵參數對算法的影響。并且同步高亮顯示當前運行的代碼行。

傳統的算法演示動畫一般都采用OpenGL、GDI+、HTML5和Flash等技術制作，動畫效果的表現力都非常好。不過，基于矢量圖形和流技術的Flash動畫以其體積容量更小、交互性更強、實現速度更快等特點而成為實驗平臺制作算法演示動畫的首選。ActionScript是Flash內置的動作腳本語言，也是一種完全的面向對象的編程語言，功能強大、類庫豐富，通過與外部應用程序的通信能為算法演示動畫添加特殊或復雜的人機互動功能[14]。

Flash算法演示動畫通過ActionScript腳本語言的ExternalInterface類與C#程序進行互動通信[15]。ExternalInterface.call方法用來從ActionScript調用C#程序的函數。為了將值返回 ActionScript，C#可以調用ActiveX對象的SetReturnValue方法，將結果作為該方法的參數進行傳遞。而從C#程序調用ActionScript函數時，首先用ExternalInterface.addCallback方法注冊，然后再使用CallFunction方法調用該函數。

Flash算法演示動畫與C#程序通信的方法如下：

(1) C#調用Flash定義的函數

Flash端代碼：

ExternalInterface.addCallback("FormCallback",FormCallback);

function FormCallback(msg:String):void{} //接收C#調用函數

C#端代碼：

commandStr = "〈invoke name='FormCallback' returntype='xml'〉〈arguments〉〈string〉參數字符串〈/string〉〈/arguments〉〈/invoke〉";

Desktop.CallFunction(commandStr); //其中Desktop為Flash控件的名稱。

(2) Flash調用C#定義的函數

Flash端代碼：

ExternalInterface.addCallback("FormCallback",FormCallback);

function FormCallback(msg:String):void //接收C#調用函數

{ ExternalInterface.call("Messagebox",msg)}; //發送命令和參數給Form

C#端代碼：

private void flashCall(object sender)

{ //解析命令字符串取得參數值

XmlDocument xml = new XmlDocument();

xml.LoadXml(e.request);

string FunctionName = xml.FirstChild.Attributes[0].Value;

XmlNode node = xml.getElementsByTagName_r("arguments").Item(0);

string msg=node.ChildNodes[0].InnerText;

MessageBox.show(msg);}

4 結 語

基于TCC的經典算法互動實驗平臺的設計開發，改善了“算法設計與分析”課程的實驗教學環境和效果，使學生能輕松、直觀地學習和掌握各種經典算法知識，也能非常方便地獨立完成各類算法實驗。學習資源庫里的絕大部分應用案例和實驗練習題都與生活息息相關，淋漓盡致地展現了算法解決問題的本質，讓學生愛上算法，并樂在其中。該實驗平臺人機互動功能強，既適合任課教師組織課內教學和實驗，也方便學生課后自學和訓練。不過，實驗平臺在對學生的算法程序進行錯誤檢查時的還未能做到中文提示，會給部分英語水平較弱的學生帶來一些困擾，所以，未來實驗平臺的研究將在人機互動方面加以優化和完善，做到更具人性化。

參考文獻(References)：

[1] 王 丹,付利華,杜金蓮.算法分析與設計課程中的“三化一體”教學方法[J].計算機教育,2016(7):120-121,125.

[2] 向金海,任繼平,余文君.“算法設計與分析”課程教學與實踐方法探討[J].計算機教育,2012(6):87-89.

[3] 趙曉麗.應用型本科院?！端惴ㄔO計與分析》課程實踐教學改革研究[J].長治學院學報,2016,33(2):72-74.

[4] 李曉鴻,駱嘉偉,季 潔.“數據結構與算法分析”研究型實踐教學的探索[J].實驗室研究與探索,2012,31(1):121-125.

[5] 陳湘驥,徐東風,方鳳美.算法類程序設計課程多層次實踐教學體系的構建[J].實驗室研究與探索,2012,31(8):319-322.

[6] 劉 波.“算法設計與分析”教學探討[J].高等理科教育,2007(04):78-80.

[7] 王曉明,黃襄念.本科算法設計與分析課程教學存在的問題及改進措施[J].高等教育研究,2012,29(2):43-46.

[8] 何克晶,張星明,鄭運平.算法設計與分析課程全方位實踐教學改革探索[J].計算機教育,2017(2):45-49.

[9] Tiny C Compiler Reference Documentation[EB/OL].[2017-01-28].http://bellard.org/tcc/tcc-doc.html

[10] 黎孟雄,郭鵬飛.軟件實驗室智能管理系統的研究與實現[J].實驗技術與管理,2013,30(6):62-64.

[11] 羅琴靈,蔣朝惠.多策略軟件代碼缺陷檢測方法研究[J].貴州大學學報(自然科學版),2015,32(3):113-118.

[12] Splint Manual[EB/OL].[2017-03-09].http://www.splint.org/manual/manual.html

[13] 李曉鴻,劉 叢,駱嘉偉.基于學習者視角的算法可視化系統研究綜述[J].計算機科學,2015(s2):431-437.

[14] 李海英.ActionScript在動態交互式C語言算法仿真動畫中的研究[J].中國教育信息化,2012(19):79-81.

[15] ExternalInterface類[EB/OL].[2017-02-17].http://help.adobe.com/zh_CN/as3/dev/index.html