數(shù)據(jù)結構課程實踐的螺旋式教學

張玉華

（蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006）

1 存在問題及對策

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

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

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

2 七步螺旋式教學及實踐流程

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

2.1 題目挑選和設計

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

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

二是保證題目的新穎性、有趣性、實用性、綜合性和可擴展性。

三是各實驗的獨立性和相關性，一個實驗可以對多種數(shù)據(jù)結構或多個技能進行操作，一個數(shù)據(jù)結構、算法也可以在多個實驗中反復出現(xiàn)。

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

2.2 實驗題目分解

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

2.3 學生初步設計階段

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

2.4 中期指導和設計階段

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

2.5 學生后期實現(xiàn)階段

學生定下總體設計方案，進行程序編寫和調試，在這個階段仍然可能會修改之前不合理的設計；接受教師和助教的指導，通常通過2～4課時完成全部實驗程序并提交。

2.6 撰寫實驗報告階段

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

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

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

3 七步螺旋式教學實踐案例

以線性表的實現(xiàn)和應用、查找和排序算法的實現(xiàn)和運用作為學習目標，以技能大賽信息查詢和評獎作為題目，展開數(shù)據(jù)結構課程實踐螺旋式教學。

3.1 實驗題目

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

3.2 題目分解

1）初步設計階段要求。

（1）設計并實現(xiàn)選手類，存儲選手信息。

（2）選擇一種數(shù)據(jù)結構及其存儲結構，存儲所有選手的數(shù)據(jù)。

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

2）最終完成階段要求。

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

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

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

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

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

3.3 學生初步設計階段

1）比賽選手Player類。

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

2）線性表List類模板。

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

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

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

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

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

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

3）文件內容讀取到List對象中并加以輸出。

（1）文件內容讀取到playList中。

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

3.4 教師中期指導階段

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

（1）Player類的構造方法就可以完成3項信息的讀取，有學生用3個方法分別設置3個變量，沒有必要。

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

（3）其他低級錯誤，如有學生在類定義結束時忘了加分號等。

2）進一步完成實驗分析提示。

（1）根據(jù)編號進行查詢?？稍趌ist類中添加一個新的方法：Error_code searchByNum（string &target，int &position）；即根據(jù)target字符串，到當前l(fā)ist中按選手的編號進行順序查找。

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

（3）個人獎項獲取并輸出?？梢韵葘⒈磉M行逆序排序，然后根據(jù)題目給出的百分比依次獲得獲獎選手。排序算法可采用之前學過的insertionsort或其他在順序表下有效的排序算法。注意將算法改寫成遞減排序的要求。另外，排序時按照成績進行大小比較，因此在Player類中添加按照成績比較大小的“＜”“＞”方法。

（4）團體獎獲取并輸出。可利用getByGroup方法按組別進行查詢并生成各組子表，對每個子表按選手成績進行遞減排序，將每組的編號信息和前3名總成績依次進行存儲，假設存儲在一個groupList中?？梢远xGroup類，存放各組的組號和該組前3名選手的總成績。

（5）程序結構及函數(shù)間調用關系。關系圖如圖1所示。

3.5 學生后期完成階段

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

1）按編號查找算法。

圖1 程序框架結構和函數(shù)間調用關系圖

2）按組別查找算法。

3）排序算法。

4）主程序文件中調用List類的外部方法。

5）主程序。

3.6 撰寫實踐報告階段

通過多個實踐報告的練習，學生已經基本掌握了課程實踐報告的撰寫方法，不僅可以清晰地匯報所做工作，還對一些實驗中具有共性的技術問題的解決方案有了相應的積累。

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

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

將完成較好的學生的實驗程序進行演示，分析其合理和可以完善的地方，進一步總結編程思路，對程序結構作直觀的演示，從而幫助更多的學生提高工程設計能力和編程能力。

4 結 語

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