云計算在《數據結構》實驗環節中的應用

朱潔，黃海平，陳興國，張毅

（1.南京郵電大學計算機學院，南京210023；2.南京理工大學計算機科學與工程學院，南京210094）

0 引言

《數據結構》主要研究各種數據的抽象表示、實現方法和算法的設計過程，是計算機軟件設計的重要理論和實踐基礎課程，該門課程也是面向非計算機專業學生的全校跨專業選修課之一。該課程先修課程為《高級語言程序設計》和《高等數學》，后續課程有《操作系統》和《算法分析與設計》等。在南京郵電大學《數據結構》大綱中規定，針對計算機相關專業的學生，該課程的課程目標包括：（1）使學生掌握數據結構的基本概念，熟悉合理組織數據的基本方法，培養學生運用計算思維分析計算機領域的相關工程問題的能力，為本專業后續課程學習及進一步的軟件開發打下良好的理論基礎；（2）能夠運用計算思維分析問題和解決問題，針對具體問題，分析數據元素的組成和邏輯關系，設計靈活高效的數據存儲結構，實現所需的運算，針對計算機領域復雜工程問題設計可行的研究方案；（3）能綜合運用數據結構的基本理論和設計方法，研究針對計算機領域復雜工程問題自主設計數據結構，并能對研究方案的可行性進行論證。與之對應地，當面向非計算機專業學生時，該課程的授課目標專注于使學生掌握數據結構的基本概念，熟悉合理組織數據的基本方法，培養學生運用計算思維進行問題分析與簡單算法設計的能力。可以看出，無論是面向計算機專業還是非計算機專業，該門課程的核心目標是培養學生的抽象思維能力、邏輯推理能力、和綜合運用所學分析問題和解決問題的能力。

1 《數據結構》課程教學現狀

該課程的難點是針對實際應用問題選擇合適的數據結構及設計有效的算法并實現，需要重視并強化上機實踐教學環節，提高學生的獨立編程能力。《高級語言程序設計》（即C語言課程）作為該門課程的先修課程，是全校各專業必修的通識課程，在學生大一下學期開始學習。而《數據結構》則是在大二上或大二下分別面向計算機或非計算機專業學生進行授課。眾所周知，大二學生（即使是計算機專業）的編程能力非常有限，大多數學生僅僅能做到通過《高級語言程序設計》考試，真正可以做到不被編程語法所束縛、做到具備“自由的理解數據結構思想”能力的學生非常少。作為《數據結構》授課教師，對學生的預期是：學生在學習先修課程《高級語言程序設計》時，能夠在課外花費相對于課題授課5倍甚至更多的時間去進行各種編程實踐，做好充分的實踐準備；然后在《數據結構》課程學習過程中，利用編程實踐手段來輔助理解數據邏輯表達內涵，從而提高分析與解決復雜工程問題的能力，為后續理論課程《算法分析與設計》和實踐課程《算法與數據結構設計》打下堅實基礎。也就是說，在《數據結構》學習過程中，編程是加深對理論理解的重要手段（但不是唯一手段）。但是，大多數學生都沒有做好這樣充分的準備工作，即使在授課過程中對書上的每一個編程案例進行逐行講解，仍然有很多學生都覺得這門課程難度太高，一邊要惡補編程，一邊又要充分發揮邏輯推導與抽象思維能力，還要兼顧考試題目的各種花樣，學習負擔與心理負擔都非常重。

《數據結構》試卷出題情況一般包括80%的理論題（考核對數據結構概念、定理與應用理解，包括選擇題、填空題和簡答題）和20%的實踐題（算法設計或編程填空）。針對這樣公開的出卷規律，存在一部分學生在學習《數據結構》課程時，完全放棄實踐環節，主攻80%的理論分。通過最近幾年試卷分析我們發現了一個規律：理論題得分率在80%以上的學生，實踐題得分率基本上不低于80%，這說明了卷面成績達到良好及以上的學生，都具備較強的算法設計能力。這也進一步表明，《數據結構》課程要想學好，不能放棄實踐環節。針對該試卷分析結論，課程組教師進行了較為激烈的討論，在無法改變學生語言基礎薄弱的現實情況下，如何能夠盡可能提高學生對本課程的學習興趣與信心，盡可能理解和掌握數據結構思想，是課程組討論的核心議題。根據討論結果，建議全體授課教師調整教學方法，將理論教學授課重點放在學生邏輯推理與抽象思維能力的培養上，在一定程度上弱化代碼的講解，讓學生不會對編碼望而生畏；通過畫圖、動畫等手段展示數據結構的各種算法過程與邏輯結構，先從理論上給學生一個鮮明而形象的印象，趁著學生興趣較濃的時候，適當地引入代碼實現，不建議逐行講解程序，而是在代碼上用各種色彩分塊，簡單地講一下代碼實現過程模塊，重點講解核心代碼。掃除學生對編程的心理障礙，激發興趣，反而能夠使得學生愿意在學有余力之余挑戰編程。

2 云計算在實驗環節中的應用設計

2.1 《數據結構》實驗環節內容

在學生基本掌握數據結構理論知識后，通過上機實踐，一方面使學生加深對課內所學各種數據邏輯結構、存儲表示和運算基本內容的理解，學習如何運用所學的數據結構和算法知識處理應用問題的方法；另一方面，在程序設計方法、C語言編程環境以及程序的調試和測試等方面得到必要的訓練。上機實踐教學環節要求學生能設計結構清晰的算法和程序，學習分析所設計算法的時間和空間復雜度，選擇足夠的測試用例進行測試，并在實驗結束后認真完成實驗報告，整理所編寫源程序代碼和可執行程序，遞交實驗報告和程序。南京郵電大學《數據結構》課程教學大綱中設定的實踐環節包括4個實驗[1]：

實驗一：線性表的基本運算及多項式的算術運算（2學時）；該實驗主要考核學生在線性表的順序存儲結構和鏈表結構上的各種操作，其核心代碼包括：順序表上的插入、刪除操作和單鏈表上插入、刪除操作；

實驗二：二叉樹的基本操作及哈夫曼編碼譯碼系統的實現（2學時）；該實驗主要考核學生對二叉樹數據結構的操作，其核心代碼包括：二叉樹的構造和拆解操作，二叉樹先序、中序和后續遍歷遞歸算法的實現與應用；

實驗三：圖的基本運算及飛機換乘次數最少問題（2學時）；該實驗主要考核學生在圖的鄰接表數據結構上的各種操作，其核心代碼包括：圖的鄰接表存儲結構的構造、圖的深度/寬度優先遍歷算法的實現；

實驗四：各種內排序算法的實現及性能比較（2學時）；該實驗主要考核各種排序算法的實現，其核心代碼包括：簡單選擇排序的選擇操作、插入排序的插入操作、冒泡排序的冒泡操作、快速排序算法的劃分操作、兩路合并算法的合并操作和堆排序算法的調整操作等。

2.2 《數據結構》實驗環節實施現狀

實踐環節首要是為了加強學生對理論知識的理解，其次才是對學生編程能力的鍛煉。要求學生能夠獨立完成程序開發環境的搭建（如果采用非實驗室已安裝開發工具語言）、完整的程序開發（文件頭、核心代碼、測試代碼）和調試工作。如要在2個學時之類完成上述工作，需要學生具備較為扎實的開發基礎或至少在實驗課之前快速熟悉開發工具，而這對于大二學生而言僅是一種理想狀態，僅有少數學生可以達成，更不用說非計算機專業學生。實際的實驗環節實施過程中存在問題包括：

（1）一半以上的學生第一次實驗時耗費大量時間熟悉開發工具，即使是在《高級語言程序設計》課程學習中已經使用過的開發工具；

（2）書上僅提供算法主要方法，學生語法基礎較差，不能正確補全程序的其他部分，如頭文件定義、main函數中主要方法的調用、測試程序的開發；

（3）在main函數中寫入固定測試數據，或需要學生手動輸入特定格式的輸入數據，不能多角度地展示算法效果，也增加任課教師課后驗收學生實驗結果的難度；更有甚者，在程序中偽造實驗結果，產生虛假的演示效果；

（4）實驗驗收時，存在拷貝他人程序直接演示的情況，不能正確回答針對算法核心代碼的問題；

（5）實驗報告抄襲嚴重。

每學期僅有約10%的學生能夠完整地在實驗課時間完成實驗環節的驗收工作，而大部分學生無法在課堂完成程序開發，更不用說達到加強對理論知識的理解目的。對于任課教師來說，實驗課的2學時時間大部分用于幫助學生調試程序，而造成程序開發工作停滯不前的主要原因是一些小的語法錯誤，而非與數據結構本身相關的問題。這對學生而言，不能充分利用教師的指導時間，其實也是一種資源浪費。從學生心理角度而言，在課后完成實驗其氛圍不如集體上機，而且很容易產生消極態度和惰性，這也導致了實驗程序和報告存在大量抄襲現象。而部分態度認真的學生，在課后繼續實驗，但是因為不能和任課教師實時互動，導致遇到困難無法及時解決。

因此，如何能夠讓學生在實驗上機時專注于數據結構和算法核心代碼編寫與測試（尤其是針對非計算機專業學生），減輕學生對編程語法問題的畏懼感，提高實踐環節效率，達成實驗目的，是《數據結構》課程實踐環節所面對的最大難點。

2.3 云計算在《數據結構》實踐環節的應用

云計算是一種基于互聯網的計算新方式，通過互聯網上異構、自治的服務為個人和企業用戶提供按需即取的計算[2]。著名咨詢機構Gartner將云計算定義為“云計算是利用互聯網技術來將龐大且可伸縮的IT能力集合起來作為服務提供給多個客戶的技術”[3]。云計算的應用之一就是開發測試云。開發測試總是繁瑣、易錯和耗時的過程，特別是在準備測試環境上面，還有會遇到諸如測試資源管理混亂，難于重現問題發生的環境和缺乏壓力測試所需要的強大計算能力等棘手問題。而開發測試云能有效解決上面這些問題，其通過友好的Web界面，可以預約、部署、管理和回收整個開發測試的環境，通過預先配置好（包括操作系統，中間件和開發測試軟件）的虛擬鏡像來快速地構建一個個異構的開發測試環境，通過快速備份/恢復等虛擬化技術來重現問題，并利用云的強大的計算能力來對應用進行壓力測試。

所做實驗是課內實驗，一般是隨著理論教學進度情況進行實驗安排，四個實驗不具備連續性，間隔至少2周以上。一般高校計算機實驗室網絡環境較好，但是出于安全考慮，電腦會定期還原。因此，僅為某個課程在計算機實驗室內部進行開發測試私有云平臺的部署，不太符合實驗室的實際情況。而租賃公有云進行實驗，費用不菲。考慮到以上情況，設計以下基于云計算技術的實驗環節實施方案（如圖1所示）：

圖1 實驗環節實施過程

準備工作階段：課程組教師提供臺服務器，按照數據中心管理軟件搭建私有云數據中心；課程組教師創建初始虛擬機，在該虛擬機上部署實驗開發環境（主要指開發工具軟件和數據庫軟件）和實驗報告撰寫工具（Office軟件），創建四個初始項目分別對應四個實驗內容；初始項目包含所有必須頭文件、庫函數、配置文件、核心方法空白的主要代碼文件（需具有大量注釋）、數據讀寫接口（即數據庫操作的主要方法已經給出）；數據庫配置完成并導入多個測試實例用于算法驗證；虛擬機設置成無網卡模式；課程組教師為申請使用云開發模式進行實驗的學生（因為還是存在一些學生愿意挑戰項目編程開發工作的全部過程），創建初始虛擬機副本；

實驗課時內實施階段：課程組教師為學生啟動虛擬機副本，提供給學生虛擬機IP地址和初始密碼；向學生簡單演示實驗開發過程、數據讀寫接口的調用方法和實驗測試方式；學生通過實驗室臺式機遠程訪問虛擬機，利用開發工具啟動初始項目，根據項目內文件注釋進行核心代碼的開發工作；遇到問題和與任課教師實時溝通，及時解決問題；

實驗課時外實施階段：學生在課外可以在同一個開發環境下繼續開發工作，如遇到問題無法解決，可及時給任課教師在線留言（一般任課教師都會給學生提供在線答疑途徑），任課教師可以登錄特定虛擬機幫助學生定位問題，找到解決方案；學生必須在虛擬機指定目錄下的模板上進行實驗報告撰寫工作；

實驗驗收階段：任課教師可以登錄各臺服務器，檢查學生項目完成情況，并給出實驗成績。

3 應用實施與效果

課程組準備4臺惠普2U機架式服務器，配置為8核、16G內存、3TB硬盤；服務器安裝XenServer構建私有云數據中心；初始虛擬機配置為：1CPU、2G內存、20G硬盤，安裝 Windows Visual Studio 2010、Windows Office軟件、MySQL、初始四個實驗項目和實驗報告模板；每臺服務器上可同時啟動8臺虛擬機，共計32臺虛擬機，能夠滿足大部分學生申請。

該方案可以一定程度上緩解或解決該課程實踐環節所遇到的一些問題，在應用效果上具有以下優點：

（1）學生在實驗室可以專注核心代碼的調試，達成實驗環節的首要目的，即加強對數據結構理論知識的理解；

（2）便于了解學生實際開發的參與情況，并可進行少量限制（無網卡或網絡設限模式，無法使用USB，不能進行拷貝和文件傳輸），一定程度上降低學生僅用簡單代碼拷貝蒙混過關的情況；

（3）課程組教師所需要進行的準備工作較為簡單，不涉及新系統的開發；

（4）學生可共享測試平臺資源，無需實驗室提供任何軟件安裝、備份或維護工作；

（5）可實現快速的課后代碼驗收工作，任課教師只需要查看數據庫中的實驗結果記錄即可了解學生代碼的正確性，也可以快速執行指定路徑下的可執行文件，演示學生所開發程序；

（6）學生很難拷貝他人實驗報告。

但是也存在以下不足之處，尚待改進：

（1）實驗代碼和報告的收集，需要任課教師在驗收階段逐臺機器去收集；因為項目代碼和實驗報告都在指定目錄下，可以開發簡單的收集小程序進行批量收集；

（2）代碼驗收目前還是需要教師手動檢查數據庫中的計算結果；可以開發簡單驗證程序，進行自動化的檢驗；

（3）因為硬件資源數量不足，該實施方案不能覆蓋所有學生，后期將考慮租賃公有云服務器。

4 結語

該方案實施結果表明，在《數據結構》實踐環節的教學過程中采用基于云的程序開發方案，可以充分調動學生學習的積極性，激發學生的學習熱情，使得學生在實踐過程中專注于分析問題和解決問題，提高他們的學習信心；提高教師在實踐環節的參與度，加大對實驗課的監控力度，一定程度上減少抄襲現象。