云計算在《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)環(huán)節(jié)中的應(yīng)用

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

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

0 引言

《數(shù)據(jù)結(jié)構(gòu)》主要研究各種數(shù)據(jù)的抽象表示、實(shí)現(xiàn)方法和算法的設(shè)計過程，是計算機(jī)軟件設(shè)計的重要理論和實(shí)踐基礎(chǔ)課程，該門課程也是面向非計算機(jī)專業(yè)學(xué)生的全?？鐚I(yè)選修課之一。該課程先修課程為《高級語言程序設(shè)計》和《高等數(shù)學(xué)》，后續(xù)課程有《操作系統(tǒng)》和《算法分析與設(shè)計》等。在南京郵電大學(xué)《數(shù)據(jù)結(jié)構(gòu)》大綱中規(guī)定，針對計算機(jī)相關(guān)專業(yè)的學(xué)生，該課程的課程目標(biāo)包括：（1）使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，熟悉合理組織數(shù)據(jù)的基本方法，培養(yǎng)學(xué)生運(yùn)用計算思維分析計算機(jī)領(lǐng)域的相關(guān)工程問題的能力，為本專業(yè)后續(xù)課程學(xué)習(xí)及進(jìn)一步的軟件開發(fā)打下良好的理論基礎(chǔ)；（2）能夠運(yùn)用計算思維分析問題和解決問題，針對具體問題，分析數(shù)據(jù)元素的組成和邏輯關(guān)系，設(shè)計靈活高效的數(shù)據(jù)存儲結(jié)構(gòu)，實(shí)現(xiàn)所需的運(yùn)算，針對計算機(jī)領(lǐng)域復(fù)雜工程問題設(shè)計可行的研究方案；（3）能綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本理論和設(shè)計方法，研究針對計算機(jī)領(lǐng)域復(fù)雜工程問題自主設(shè)計數(shù)據(jù)結(jié)構(gòu)，并能對研究方案的可行性進(jìn)行論證。與之對應(yīng)地，當(dāng)面向非計算機(jī)專業(yè)學(xué)生時，該課程的授課目標(biāo)專注于使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，熟悉合理組織數(shù)據(jù)的基本方法，培養(yǎng)學(xué)生運(yùn)用計算思維進(jìn)行問題分析與簡單算法設(shè)計的能力?？梢钥闯?，無論是面向計算機(jī)專業(yè)還是非計算機(jī)專業(yè)，該門課程的核心目標(biāo)是培養(yǎng)學(xué)生的抽象思維能力、邏輯推理能力、和綜合運(yùn)用所學(xué)分析問題和解決問題的能力。

1 《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)現(xiàn)狀

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

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

2 云計算在實(shí)驗(yàn)環(huán)節(jié)中的應(yīng)用設(shè)計

2.1 《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)環(huán)節(jié)內(nèi)容

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

實(shí)驗(yàn)一：線性表的基本運(yùn)算及多項(xiàng)式的算術(shù)運(yùn)算（2學(xué)時）；該實(shí)驗(yàn)主要考核學(xué)生在線性表的順序存儲結(jié)構(gòu)和鏈表結(jié)構(gòu)上的各種操作，其核心代碼包括：順序表上的插入、刪除操作和單鏈表上插入、刪除操作；

實(shí)驗(yàn)二：二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)的實(shí)現(xiàn)（2學(xué)時）；該實(shí)驗(yàn)主要考核學(xué)生對二叉樹數(shù)據(jù)結(jié)構(gòu)的操作，其核心代碼包括：二叉樹的構(gòu)造和拆解操作，二叉樹先序、中序和后續(xù)遍歷遞歸算法的實(shí)現(xiàn)與應(yīng)用；

實(shí)驗(yàn)三：圖的基本運(yùn)算及飛機(jī)換乘次數(shù)最少問題（2學(xué)時）；該實(shí)驗(yàn)主要考核學(xué)生在圖的鄰接表數(shù)據(jù)結(jié)構(gòu)上的各種操作，其核心代碼包括：圖的鄰接表存儲結(jié)構(gòu)的構(gòu)造、圖的深度/寬度優(yōu)先遍歷算法的實(shí)現(xiàn)；

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

2.2 《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)環(huán)節(jié)實(shí)施現(xiàn)狀

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

（1）一半以上的學(xué)生第一次實(shí)驗(yàn)時耗費(fèi)大量時間熟悉開發(fā)工具，即使是在《高級語言程序設(shè)計》課程學(xué)習(xí)中已經(jīng)使用過的開發(fā)工具；

（2）書上僅提供算法主要方法，學(xué)生語法基礎(chǔ)較差，不能正確補(bǔ)全程序的其他部分，如頭文件定義、main函數(shù)中主要方法的調(diào)用、測試程序的開發(fā)；

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

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

（5）實(shí)驗(yàn)報告抄襲嚴(yán)重。

每學(xué)期僅有約10%的學(xué)生能夠完整地在實(shí)驗(yàn)課時間完成實(shí)驗(yàn)環(huán)節(jié)的驗(yàn)收工作，而大部分學(xué)生無法在課堂完成程序開發(fā)，更不用說達(dá)到加強(qiáng)對理論知識的理解目的。對于任課教師來說，實(shí)驗(yàn)課的2學(xué)時時間大部分用于幫助學(xué)生調(diào)試程序，而造成程序開發(fā)工作停滯不前的主要原因是一些小的語法錯誤，而非與數(shù)據(jù)結(jié)構(gòu)本身相關(guān)的問題。這對學(xué)生而言，不能充分利用教師的指導(dǎo)時間，其實(shí)也是一種資源浪費(fèi)。從學(xué)生心理角度而言，在課后完成實(shí)驗(yàn)其氛圍不如集體上機(jī)，而且很容易產(chǎn)生消極態(tài)度和惰性，這也導(dǎo)致了實(shí)驗(yàn)程序和報告存在大量抄襲現(xiàn)象。而部分態(tài)度認(rèn)真的學(xué)生，在課后繼續(xù)實(shí)驗(yàn)，但是因?yàn)椴荒芎腿握n教師實(shí)時互動，導(dǎo)致遇到困難無法及時解決。

因此，如何能夠讓學(xué)生在實(shí)驗(yàn)上機(jī)時專注于數(shù)據(jù)結(jié)構(gòu)和算法核心代碼編寫與測試（尤其是針對非計算機(jī)專業(yè)學(xué)生），減輕學(xué)生對編程語法問題的畏懼感，提高實(shí)踐環(huán)節(jié)效率，達(dá)成實(shí)驗(yàn)?zāi)康?，是《?shù)據(jù)結(jié)構(gòu)》課程實(shí)踐環(huán)節(jié)所面對的最大難點(diǎn)。

2.3 云計算在《數(shù)據(jù)結(jié)構(gòu)》實(shí)踐環(huán)節(jié)的應(yīng)用

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

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

圖1 實(shí)驗(yàn)環(huán)節(jié)實(shí)施過程

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

實(shí)驗(yàn)課時內(nèi)實(shí)施階段：課程組教師為學(xué)生啟動虛擬機(jī)副本，提供給學(xué)生虛擬機(jī)IP地址和初始密碼；向?qū)W生簡單演示實(shí)驗(yàn)開發(fā)過程、數(shù)據(jù)讀寫接口的調(diào)用方法和實(shí)驗(yàn)測試方式；學(xué)生通過實(shí)驗(yàn)室臺式機(jī)遠(yuǎn)程訪問虛擬機(jī)，利用開發(fā)工具啟動初始項(xiàng)目，根據(jù)項(xiàng)目內(nèi)文件注釋進(jìn)行核心代碼的開發(fā)工作；遇到問題和與任課教師實(shí)時溝通，及時解決問題；

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

實(shí)驗(yàn)驗(yàn)收階段：任課教師可以登錄各臺服務(wù)器，檢查學(xué)生項(xiàng)目完成情況，并給出實(shí)驗(yàn)成績。

3 應(yīng)用實(shí)施與效果

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

該方案可以一定程度上緩解或解決該課程實(shí)踐環(huán)節(jié)所遇到的一些問題，在應(yīng)用效果上具有以下優(yōu)點(diǎn)：

（1）學(xué)生在實(shí)驗(yàn)室可以專注核心代碼的調(diào)試，達(dá)成實(shí)驗(yàn)環(huán)節(jié)的首要目的，即加強(qiáng)對數(shù)據(jù)結(jié)構(gòu)理論知識的理解；

（2）便于了解學(xué)生實(shí)際開發(fā)的參與情況，并可進(jìn)行少量限制（無網(wǎng)卡或網(wǎng)絡(luò)設(shè)限模式，無法使用USB，不能進(jìn)行拷貝和文件傳輸），一定程度上降低學(xué)生僅用簡單代碼拷貝蒙混過關(guān)的情況；

（3）課程組教師所需要進(jìn)行的準(zhǔn)備工作較為簡單，不涉及新系統(tǒng)的開發(fā)；

（4）學(xué)生可共享測試平臺資源，無需實(shí)驗(yàn)室提供任何軟件安裝、備份或維護(hù)工作；

（5）可實(shí)現(xiàn)快速的課后代碼驗(yàn)收工作，任課教師只需要查看數(shù)據(jù)庫中的實(shí)驗(yàn)結(jié)果記錄即可了解學(xué)生代碼的正確性，也可以快速執(zhí)行指定路徑下的可執(zhí)行文件，演示學(xué)生所開發(fā)程序；

（6）學(xué)生很難拷貝他人實(shí)驗(yàn)報告。

但是也存在以下不足之處，尚待改進(jìn)：

（1）實(shí)驗(yàn)代碼和報告的收集，需要任課教師在驗(yàn)收階段逐臺機(jī)器去收集；因?yàn)轫?xiàng)目代碼和實(shí)驗(yàn)報告都在指定目錄下，可以開發(fā)簡單的收集小程序進(jìn)行批量收集；

（2）代碼驗(yàn)收目前還是需要教師手動檢查數(shù)據(jù)庫中的計算結(jié)果；可以開發(fā)簡單驗(yàn)證程序，進(jìn)行自動化的檢驗(yàn)；

（3）因?yàn)橛布Y源數(shù)量不足，該實(shí)施方案不能覆蓋所有學(xué)生，后期將考慮租賃公有云服務(wù)器。

4 結(jié)語

該方案實(shí)施結(jié)果表明，在《數(shù)據(jù)結(jié)構(gòu)》實(shí)踐環(huán)節(jié)的教學(xué)過程中采用基于云的程序開發(fā)方案，可以充分調(diào)動學(xué)生學(xué)習(xí)的積極性，激發(fā)學(xué)生的學(xué)習(xí)熱情，使得學(xué)生在實(shí)踐過程中專注于分析問題和解決問題，提高他們的學(xué)習(xí)信心；提高教師在實(shí)踐環(huán)節(jié)的參與度，加大對實(shí)驗(yàn)課的監(jiān)控力度，一定程度上減少抄襲現(xiàn)象。