數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐的螺旋式教學(xué)

張玉華

（蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006）

1 存在問題及對策

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專業(yè)的核心基礎(chǔ)課，是培養(yǎng)學(xué)生利用高級語言存儲(chǔ)表示外部數(shù)據(jù)，并對這些數(shù)據(jù)進(jìn)行操作和運(yùn)算的學(xué)科，是提升學(xué)生的邏輯思維能力、算法設(shè)計(jì)能力和編程能力，引領(lǐng)學(xué)生真正進(jìn)入計(jì)算機(jī)技術(shù)領(lǐng)域的橋梁課程，是一門非常重要且實(shí)踐性極強(qiáng)的課程。

多年來，數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)語言隨著技術(shù)的發(fā)展不斷變化發(fā)展。從Pascal語言，到C、C++、Java語言，甚至Python語言，數(shù)據(jù)結(jié)構(gòu)的應(yīng)用實(shí)踐始終是一個(gè)令學(xué)生煩惱、教師失望的環(huán)節(jié)，從總體來看，實(shí)踐教學(xué)的效果一直不夠理想。除了學(xué)生高級語言的編程基礎(chǔ)薄弱等原因之外[1]，最重要的原因還有3個(gè)：①數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)題目或陳舊缺乏新意，或粗制濫造缺乏實(shí)用性[2]，學(xué)生對數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)題目沒有興趣；②整個(gè)實(shí)踐過程處于無序、隨意、缺乏指導(dǎo)的狀態(tài)，教師的大部分工作是輔導(dǎo)個(gè)別學(xué)生進(jìn)行程序調(diào)試，沒有起到整體的引領(lǐng)作用；③缺乏及時(shí)、有效、公正的學(xué)習(xí)反饋和評價(jià)機(jī)制。

針對這樣的現(xiàn)狀，在較為充足的實(shí)踐課時(shí)保證下，可以將基本數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)、選擇和靈活運(yùn)用以及提高編程能力作為整體教學(xué)目標(biāo)，將實(shí)踐課程設(shè)計(jì)為驗(yàn)證與設(shè)計(jì)并重，理論與實(shí)踐、教學(xué)與實(shí)踐相結(jié)合，由教師、學(xué)生和助教共同參與，采用七步螺旋式教學(xué)的系統(tǒng)化工程。

2 七步螺旋式教學(xué)及實(shí)踐流程

七步螺旋式教學(xué)將每個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的完成分成7個(gè)步驟，分別是選題、題目分解、學(xué)生初步設(shè)計(jì)階段、中期指導(dǎo)和設(shè)計(jì)階段、學(xué)生后期實(shí)現(xiàn)階段、撰寫實(shí)驗(yàn)報(bào)告階段以及批改、反饋、分析、展示階段，每個(gè)步驟都精心設(shè)計(jì)，7個(gè)步驟環(huán)環(huán)相扣，總體自下向上，即后續(xù)的步驟是前面步驟的加強(qiáng)、反復(fù)和綜合，但存在回溯再向上的反復(fù)過程。

2.1 題目挑選和設(shè)計(jì)

通過對現(xiàn)有數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教材大量的研究和學(xué)習(xí)，結(jié)合教師多年來對數(shù)據(jù)結(jié)構(gòu)理論和實(shí)踐教學(xué)的理解，可以進(jìn)行題目挑選、改編或自主設(shè)計(jì)。

選題的原則一是系統(tǒng)性和完整性，即根據(jù)理論課程的知識(shí)體系和教學(xué)流程進(jìn)行選題，保證對數(shù)據(jù)結(jié)構(gòu)基本理論系統(tǒng)全面的驗(yàn)證、應(yīng)用和實(shí)踐，圍繞數(shù)據(jù)結(jié)構(gòu)的核心知識(shí)（棧、隊(duì)列、線性表、二叉樹、圖等數(shù)據(jù)結(jié)構(gòu)），遞歸的算法思想的運(yùn)用，查找、排序的算法實(shí)現(xiàn)及性能測試進(jìn)行題目的精選，完整覆蓋數(shù)據(jù)結(jié)構(gòu)的重要內(nèi)容。

二是保證題目的新穎性、有趣性、實(shí)用性、綜合性和可擴(kuò)展性。

三是各實(shí)驗(yàn)的獨(dú)立性和相關(guān)性，一個(gè)實(shí)驗(yàn)可以對多種數(shù)據(jù)結(jié)構(gòu)或多個(gè)技能進(jìn)行操作，一個(gè)數(shù)據(jù)結(jié)構(gòu)、算法也可以在多個(gè)實(shí)驗(yàn)中反復(fù)出現(xiàn)。

比如用算24點(diǎn)游戲作為棧的綜合應(yīng)用設(shè)計(jì)題，不僅考查棧的實(shí)現(xiàn)和應(yīng)用，還考查窮舉、遞歸等算法思想，利用棧完成對輸入的算24點(diǎn)表達(dá)式的括號(hào)是否配對的檢查，對合法的表達(dá)式進(jìn)行求值，題目新穎，具有應(yīng)用意義，并且內(nèi)容全面，由淺入深，同時(shí)考慮到學(xué)生對知識(shí)點(diǎn)掌握的不同程度，設(shè)立選做和必做部分。由于選題極具實(shí)用性和可擴(kuò)展性，有些學(xué)有余力的學(xué)生還可將該題修改擴(kuò)充后做成手機(jī)上的算24點(diǎn)APP，極大地提升學(xué)習(xí)興趣和編程能力。

2.2 實(shí)驗(yàn)題目分解

如果直接把題目拋給學(xué)生，那么很多學(xué)生可能就會(huì)無所適從，因此需要教師圍繞該實(shí)踐課題的教學(xué)要求，將題目進(jìn)行由淺入深、由易到難的層層分解，即使是基礎(chǔ)較弱的學(xué)生，也可以從完成第一個(gè)小目標(biāo)入手，慢慢獲得信心，達(dá)到分層次教學(xué)的目的。

2.3 學(xué)生初步設(shè)計(jì)階段

教師將題目分解后通過教學(xué)網(wǎng)站發(fā)布，學(xué)生進(jìn)入初步設(shè)計(jì)階段。這個(gè)階段通常是完成驗(yàn)證性實(shí)驗(yàn)、基本輸入輸出等部分，要求學(xué)生分析初步設(shè)計(jì)階段的要求及整個(gè)題目中的核心數(shù)據(jù)結(jié)構(gòu)并加以定義和實(shí)現(xiàn)，要求學(xué)生必須細(xì)讀題目，結(jié)合所學(xué)數(shù)據(jù)結(jié)構(gòu)理論知識(shí)，運(yùn)用C++語言給出實(shí)現(xiàn)方案。工作量控制在大多數(shù)學(xué)生可以在2個(gè)學(xué)時(shí)之內(nèi)初步完成，教師和助教進(jìn)行巡視和個(gè)別指導(dǎo)。

2.4 中期指導(dǎo)和設(shè)計(jì)階段

教師根據(jù)學(xué)生初步設(shè)計(jì)階段完成的情況，利用實(shí)踐課堂1學(xué)時(shí)左右的時(shí)間對基本部分中出現(xiàn)的典型問題進(jìn)行范例分析，對接下來要完成的任務(wù)進(jìn)行分析，以圖解、提問等方式，對后續(xù)部分的要點(diǎn)和難點(diǎn)進(jìn)行提示。學(xué)生根據(jù)教師提示或自行進(jìn)行實(shí)驗(yàn)的整體設(shè)計(jì)，對初步設(shè)計(jì)階段完成的部分進(jìn)行修改、添加和完善，這是承前啟后的關(guān)鍵一步。

2.5 學(xué)生后期實(shí)現(xiàn)階段

學(xué)生定下總體設(shè)計(jì)方案，進(jìn)行程序編寫和調(diào)試，在這個(gè)階段仍然可能會(huì)修改之前不合理的設(shè)計(jì)；接受教師和助教的指導(dǎo)，通常通過2～4課時(shí)完成全部實(shí)驗(yàn)程序并提交。

2.6 撰寫實(shí)驗(yàn)報(bào)告階段

實(shí)驗(yàn)報(bào)告是所完成實(shí)驗(yàn)項(xiàng)目的設(shè)計(jì)報(bào)告和說明書，應(yīng)該重內(nèi)容、輕形式，要求學(xué)生描述實(shí)驗(yàn)的總體設(shè)計(jì)方案、關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法，將實(shí)現(xiàn)過程中遇到的問題及解決的方法如實(shí)記錄，展示完成情況和實(shí)驗(yàn)結(jié)果，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析，總結(jié)心得體會(huì)?？紤]到很多學(xué)生沒有撰寫實(shí)驗(yàn)報(bào)告的經(jīng)驗(yàn)，教師可以給出第一個(gè)實(shí)驗(yàn)報(bào)告的參考樣例，并引導(dǎo)學(xué)生用流程圖、模塊結(jié)構(gòu)圖等方式清晰匯報(bào)所做工作。

2.7 批改、反饋、分析、展示階段

及時(shí)、有效、公正的學(xué)習(xí)反饋和評價(jià)機(jī)制是提升學(xué)生的學(xué)習(xí)興趣，幫助學(xué)生鞏固所學(xué)知識(shí)的有效途徑。在實(shí)驗(yàn)程序和報(bào)告提交之后，教師和助教對所有學(xué)生的程序和報(bào)告加以批改，為使實(shí)驗(yàn)成績更真實(shí)，每次實(shí)驗(yàn)都隨機(jī)選擇部分學(xué)生進(jìn)行面批，根據(jù)實(shí)驗(yàn)態(tài)度、分析能力、編程能力、實(shí)驗(yàn)結(jié)果、源代碼質(zhì)量、總結(jié)能力等多個(gè)方面進(jìn)行給分，通過教學(xué)平臺(tái)給出每個(gè)學(xué)生的實(shí)驗(yàn)評分和評語。最后評比出10%左右的優(yōu)秀作業(yè)進(jìn)行展示，學(xué)生以此作為一種榮譽(yù)，能夠形成較好的學(xué)習(xí)氛圍。

3 七步螺旋式教學(xué)實(shí)踐案例

以線性表的實(shí)現(xiàn)和應(yīng)用、查找和排序算法的實(shí)現(xiàn)和運(yùn)用作為學(xué)習(xí)目標(biāo)，以技能大賽信息查詢和評獎(jiǎng)作為題目，展開數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐螺旋式教學(xué)。

3.1 實(shí)驗(yàn)題目

某行業(yè)組織一次行業(yè)技能大賽，共設(shè)有10組選手參賽，每組的參賽選手少于10位。每位選手有一個(gè)6位選手編號(hào)，其中第3—4位是組別代碼，如編號(hào)是“030205”表明該選手在第2組?，F(xiàn)在比賽已經(jīng)結(jié)束，選手的編號(hào)、姓名和最終成績存儲(chǔ)在mark.txt中。mark.txt每行存儲(chǔ)一個(gè)選手的信息，3項(xiàng)信息之間以tab鍵作為分隔符。

3.2 題目分解

1）初步設(shè)計(jì)階段要求。

（1）設(shè)計(jì)并實(shí)現(xiàn)選手類，存儲(chǔ)選手信息。

（2）選擇一種數(shù)據(jù)結(jié)構(gòu)及其存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)所有選手的數(shù)據(jù)。

（3）將mark.txt文件的內(nèi)容存儲(chǔ)到（2）所選定的類對象中，并加以全部輸出。注意輸出格式盡量美觀。

2）最終完成階段要求。

（1）根據(jù)輸入的編號(hào)查詢某位選手的成績。

（2）根據(jù)輸入的組別查詢該組所有選手的成績，如輸入2，則顯示2組全部選手信息。

（3）評出個(gè)人獎(jiǎng)項(xiàng)。分別取個(gè)人成績最高的前10%、成績其次的前15%和成績再次的25%依次作為個(gè)人一等獎(jiǎng)、二等獎(jiǎng)和三等獎(jiǎng)選手，總共獲獎(jiǎng)選手為參賽選手人數(shù)的50%，得獎(jiǎng)人數(shù)按四舍五入計(jì)數(shù)。按成績遞減序依次輸出各獎(jiǎng)項(xiàng)獲得選手的各項(xiàng)信息。

（4）評出團(tuán)體獎(jiǎng)。根據(jù)每組成績最高的3位選手的總成績評出團(tuán)體獎(jiǎng)前3名，輸出前3名的組別和3人總成績。

要求界面友好美觀，功能完整正確，可實(shí)現(xiàn)查找、排序等算法，以完成相應(yīng)功能，可自行設(shè)計(jì)和添加其他的類和輔助算法。

3.3 學(xué)生初步設(shè)計(jì)階段

1）比賽選手Player類。

在這個(gè)案例中，程序的主要操作對象是各位比賽選手，各位選手需存儲(chǔ)處理的信息即為他的編號(hào)、姓名和成績，因此設(shè)計(jì)Player類，其數(shù)據(jù)成員包括num，name和score，另外配備構(gòu)造方法、輸出方法等。

2）線性表List類模板。

根據(jù)題意，題目要求將所有選手的信息進(jìn)行統(tǒng)一存儲(chǔ)，之后要進(jìn)行選手查找、根據(jù)成績進(jìn)行排序評獎(jiǎng)等操作，所涉及的其他操作也都可以在線性結(jié)構(gòu)下很方便地完成，因此采用線性表作為邏輯結(jié)構(gòu)也是最合理自然的。

世界范圍內(nèi)對能源互聯(lián)網(wǎng)沒有統(tǒng)一的名稱和定義,在眾多對能源互聯(lián)網(wǎng)不同形態(tài)的描述中,兩種具有代表性的觀點(diǎn)是:“能源系統(tǒng)的類互聯(lián)網(wǎng)化”和“互聯(lián)網(wǎng)+智能電網(wǎng)+智慧能源”。前者借鑒互聯(lián)網(wǎng)開放對等、即插即用的理念和體系架構(gòu),結(jié)構(gòu)上難以區(qū)分能源網(wǎng)絡(luò)和信息網(wǎng)絡(luò),運(yùn)行模式上采用區(qū)域自治和骨干管控相結(jié)合的方式,其研究和實(shí)踐還沒有統(tǒng)一的目標(biāo)和方向,現(xiàn)階段有一些示范工程建設(shè)和實(shí)驗(yàn)室的研究。后者借助互聯(lián)網(wǎng)收集信息,分析決策后指導(dǎo)能源網(wǎng)絡(luò)的運(yùn)行調(diào)度,信息網(wǎng)絡(luò)可以認(rèn)為是能源網(wǎng)絡(luò)的支持決策網(wǎng)絡(luò),其本質(zhì)與早些時(shí)候提出的智能電網(wǎng)類似,以德國、中國為代表。在現(xiàn)階段的技術(shù)水平下,后者比前者更具可操作性。

假設(shè)用playerList對象來表示所有選手的線性表。

線性表的存儲(chǔ)結(jié)構(gòu)可以采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，假設(shè)本次實(shí)驗(yàn)采用順序存儲(chǔ)結(jié)構(gòu)，即用連續(xù)的存儲(chǔ)空間作為線性表元素的存儲(chǔ)空間?？梢詫⒃擃惗x在list.h中，各方法的實(shí)現(xiàn)部分代碼可以添加在該文件下方。

List類中定義的Error_code枚舉類型用于返回各方法執(zhí)行的結(jié)果狀態(tài)代碼，定義如下：

enum Error_code { success，underflow，overflow，not_present，range_error }；

3）文件內(nèi)容讀取到List對象中并加以輸出。

（1）文件內(nèi)容讀取到playList中。

void readFile（string filename，List＜Player＞ &playerList） //將文件中的數(shù)據(jù)存入列表

3.4 教師中期指導(dǎo)階段

1）教師分析學(xué)生初步設(shè)計(jì)階段出現(xiàn)的問題。

（1）Player類的構(gòu)造方法就可以完成3項(xiàng)信息的讀取，有學(xué)生用3個(gè)方法分別設(shè)置3個(gè)變量，沒有必要。

（2）List類為模板類時(shí)，定義和實(shí)現(xiàn)部分要放在一個(gè)文件中，有同學(xué)用list.h和list.cpp分別表示定義和實(shí)現(xiàn)部分時(shí)，注意在主程序要#include "list.cpp"。注意不能重復(fù)包含頭文件。

（3）其他低級錯(cuò)誤，如有學(xué)生在類定義結(jié)束時(shí)忘了加分號(hào)等。

2）進(jìn)一步完成實(shí)驗(yàn)分析提示。

（1）根據(jù)編號(hào)進(jìn)行查詢。可在list類中添加一個(gè)新的方法：Error_code searchByNum（string &target，int &position）；即根據(jù)target字符串，到當(dāng)前l(fā)ist中按選手的編號(hào)進(jìn)行順序查找。

（2）根據(jù)組別進(jìn)行查詢。由于需要根據(jù)組別選出所有該組選手的信息，需要得到一條新的鏈表以方便后續(xù)的輸出，設(shè)為new_list，則可在list類中再添加一個(gè)方法：void getByGroup（List＜Player＞ &new_list，int &target，int &position）。

（3）個(gè)人獎(jiǎng)項(xiàng)獲取并輸出。可以先將表進(jìn)行逆序排序，然后根據(jù)題目給出的百分比依次獲得獲獎(jiǎng)選手。排序算法可采用之前學(xué)過的insertionsort或其他在順序表下有效的排序算法。注意將算法改寫成遞減排序的要求。另外，排序時(shí)按照成績進(jìn)行大小比較，因此在Player類中添加按照成績比較大小的“＜”“＞”方法。

（4）團(tuán)體獎(jiǎng)獲取并輸出?？衫胓etByGroup方法按組別進(jìn)行查詢并生成各組子表，對每個(gè)子表按選手成績進(jìn)行遞減排序，將每組的編號(hào)信息和前3名總成績依次進(jìn)行存儲(chǔ)，假設(shè)存儲(chǔ)在一個(gè)groupList中?？梢远xGroup類，存放各組的組號(hào)和該組前3名選手的總成績。

（5）程序結(jié)構(gòu)及函數(shù)間調(diào)用關(guān)系。關(guān)系圖如圖1所示。

3.5 學(xué)生后期完成階段

學(xué)生根據(jù)教師的提示，可借鑒教師思路或自主完成接下來的任務(wù)。需主要完成的算法為查找算法、排序算法以及根據(jù)題目要求依次進(jìn)行信息檢索和評獎(jiǎng)。

1）按編號(hào)查找算法。

圖1 程序框架結(jié)構(gòu)和函數(shù)間調(diào)用關(guān)系圖

2）按組別查找算法。

3）排序算法。

4）主程序文件中調(diào)用List類的外部方法。

5）主程序。

3.6 撰寫實(shí)踐報(bào)告階段

通過多個(gè)實(shí)踐報(bào)告的練習(xí)，學(xué)生已經(jīng)基本掌握了課程實(shí)踐報(bào)告的撰寫方法，不僅可以清晰地匯報(bào)所做工作，還對一些實(shí)驗(yàn)中具有共性的技術(shù)問題的解決方案有了相應(yīng)的積累。

3.7 批改、反饋、分析和展示階段

在本例題中，經(jīng)過總共5個(gè)學(xué)時(shí)的代碼編寫和調(diào)試，63%的學(xué)生可以完成整個(gè)實(shí)驗(yàn)，19%的學(xué)生完成前面4個(gè)小題，12%的學(xué)生只完成前面3個(gè)小題，另有6%的學(xué)生完成2個(gè)或更少的實(shí)驗(yàn)。根據(jù)每個(gè)小題的得分點(diǎn)，對所有學(xué)生進(jìn)行評分和反饋。

將完成較好的學(xué)生的實(shí)驗(yàn)程序進(jìn)行演示，分析其合理和可以完善的地方，進(jìn)一步總結(jié)編程思路，對程序結(jié)構(gòu)作直觀的演示，從而幫助更多的學(xué)生提高工程設(shè)計(jì)能力和編程能力。

4 結(jié) 語

通過將每個(gè)實(shí)驗(yàn)設(shè)計(jì)為圍繞某種數(shù)據(jù)結(jié)構(gòu)，綜合運(yùn)用已學(xué)的其他數(shù)據(jù)結(jié)構(gòu)，選用或設(shè)計(jì)相關(guān)算法，熟練運(yùn)用編程語言，實(shí)驗(yàn)?zāi)繕?biāo)的開放性螺旋式過程最終完成。一個(gè)學(xué)期的實(shí)踐中，學(xué)生通過與教師的互動(dòng)和充分的實(shí)踐，在多個(gè)實(shí)驗(yàn)中對知識(shí)和技能進(jìn)行螺旋式反復(fù)、交叉練習(xí)，能夠在實(shí)際應(yīng)用中正確選擇數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，分析并完成其基本算法的實(shí)現(xiàn)，基本達(dá)到數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)和實(shí)踐的目的，但由于教學(xué)任務(wù)緊，人力相對不足，具體實(shí)施的細(xì)節(jié)還需要更多的完善。