數據結構課程中棧和隊列實驗教學方案設計

摘要：數據結構是計算機專業的核心課程，對培養計算機專業設計與創新型人才起著關鍵作用。該課程是理論性和實踐性很強的一門課程。實驗教學是其教學中的一個重要環節。棧和隊列是兩種非常重要的線性結構，它們有很多實際應用。為了幫助學生充分理解、掌握和靈活運用這兩種數據結構，本文給出一種棧和隊列的實驗教學方案。

關鍵詞：數據結構；實驗教學方案；棧；隊列

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2016）24-0274-03

一、引言

實驗教學是學生從學習理論知識到走向社會的橋梁，對提高學生綜合素質、培養學生創新精神和實踐能力有著理論教學不可替代的特殊作用[1]。特別是主干課程的實踐教學，它是應用型人才培養中的關鍵環節[2]。課內實驗是指與理論課相捆綁的實踐教學，即嵌入到專業基礎課或專業課內的實驗實踐教學[3]。它是與理論教學并行實施的實踐教學環節，能夠幫助學生深入理解和掌握所學的專業知識。

數據結構是隨著處理對象的復雜性不斷增加而發展起來的一門課程，作為計算機專業的核心課程，在專業人才培養鏈條中占有舉足輕重的地位[4-7]。數據結構主要研究數據在抽象視圖和實現視圖中的表示和處理方法[8，9]。抽象視圖涉及的是數據結構的理論性部分，實現視圖主要體現的是數據結構的實踐性，理論指導實踐，實踐支撐理論，因此設計有助于課堂理論教學的實驗教學方案是非常有必要的[10]。它可以解決學生對所學知識缺乏必要感性認識的問題，將知識傳授、技能訓練、能力培養融于一體，使所學理論知識在實驗中得到驗證和應用[11]。

棧和隊列是兩種非常重要的數據結構，它們有非常多的實際應用并且是實現其他復雜結構的基礎，因此為了幫助學生掌握并靈活運用這兩種結構，本文給出一種棧和隊列的實驗教學方案。該方案的設計思路也可以應用于其他數據結構或課程的實驗教學方案的設計。

二、認識兩種重要的數據結構——棧和隊列

棧和隊列是兩種運算受限的線性表，它們的插入和刪除運算都被限制在表的端點處進行，只是具體的受限規則不一樣[12，13]。

（一）學習對象

棧（stack）是運算受限的線性表，它被限制在表的一端進行插入和刪除操作。能進行插入和刪除的一端稱為棧頂，另一端稱為棧底。正是由于它插入和刪除操作上的限制使得它具有了一種獨特的“后進先出”（LIFO）的特性。棧的LIFO特性使得它具有非常多的應用，如：符號平衡問題、中綴表達式轉換為后綴表達式問題、后綴表達式的計算問題、函數調用的實現（包括遞歸函數的實現）、在股票市場中查找劃分、Web瀏覽器中的網頁訪問歷史、文本編輯器中的撤銷序列等。此外，棧還是其他很多算法的輔助數據結構和其他數據結構的組成部分。

隊列（queue）也是一種運算受限的線性表，它被限制在表的一端進行插入操作，在表的另一端進行刪除操作。進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊首。正是由于它插入和刪除操作上的限制使得它具有了一種獨特的“先進先出”（FIFO）的特性。隊列的FIFO特性使得它具有非常多的應用，如：操作系統中的作業調度、異步數據轉換、多道程序設計等。此外，隊列還是其他很多算法的輔助數據結構和其他數據結構的組成部分。

（二）學習目標

學習這兩種重要的線性結構需要學生重點消化的知識點有：（1）棧/隊列的概念、類型定義及基本操作的定義和實現；（2）棧/隊列的結構特性；（3）棧/隊列的靈活應用。

為了配合棧和隊列的理論教學，幫助學生理解和掌握上述知識點，我們需要精心設計棧和隊列的實驗教學方案。

三、棧和隊列的實驗教學方案設計

（一）實驗題目設計

根據棧和隊列的學習目標和遵循循序漸進的學習和教學原則，實驗題目被分為以下三個層次：基礎型實驗題目、設計型實驗題目和加強理解型實驗題目。

所謂基礎型實驗是指圍繞課程講授的棧/隊列的物理實現和其基本運算的實現來設置的實驗題目。設計基礎型實驗的目的是，通過實踐的方式驗證課堂上講授的重要知識點，給學生切身的感受，擺脫“紙上談兵”的感覺，這種立體的感受有助于學生深入理解和掌握這些知識點。設計型實驗要求學生能分別運用棧/隊列解決簡單應用問題。這類實驗題目主要是用來引導和加強學生對棧/隊列的靈活運用。設計加強理解型實驗的目的是強化學生對棧和隊列的結構特性的理解和體會。為了達到這個目的，加強理解型實驗題目的設計思路有兩個方面：（1）引導學生去思考并解決這樣兩個問題：能否利用棧的LIFO特性來實現隊列的FIFO特性？能否利用隊列的FIFO特性來實現棧的LIFO特性？（2）讓學生實現其他更為復雜的棧和隊列。

在棧的理論教學過程中可以開設棧的基礎型實驗，在棧的理論教學結束后可以開設棧的設計型實驗，在隊列的理論教學過程中可以開設隊列的基礎型實驗，在隊列的理論教學結束后可以開設隊列的設計型實驗和加強理解型實驗題目。表1給出了具體的實驗安排。

學生必須在相關內容的理論教學過程中利用自己的課外時間完成全部基礎型實驗題目，教師根據學時安排選擇1～2道設計型實驗題目讓學生在上機課上完成，未選擇的題目應向學生提供完整的源代碼和設計說明。相關內容的理論教學結束后，學生必須利用自己的課外時間完成加強理解型實驗題目中的第1題和第2題，剩下兩題可以選做。

（二）教學方法

因為三種類型實驗的要求、難易程度不同，因此在學生參與形式、教師參與程度、教師參與方式等方面需要區別對待。表2給出了對三種類型實驗在上述這幾個方面的設計。

基礎型實驗要求每位學生利用課外時間獨立完成，教師全程參與指導。所謂全程參與指導是指從算法基本思想到算法實現的各個環節（包括編程技巧、程序調試與測試等）都要參與指導。參與方式多種多樣，例如利用QQ等即時通訊工具進行指導，約定時間和地點進行答疑，等等。

設計型實驗要求每位學生在上機課上獨立完成，教師前期參與指導。所謂前期參與指導是指教師參與學生在算法設計環節的討論，教師可以給出提示，同時鼓勵學生設計不同的算法。參與方式是面對面的交流。

加強理解型實驗要求每位學生利用課外時間獨立完成，教師后期參與指導。所謂后期參與指導是指教師在收齊學生提交的源碼和設計報告后，對其進行分析總結，并將總結結果以班級為單位采用面對面的方式反饋給學生。

（三）考核方法

對三種類型的實驗采用不同的考核辦法。表3給出了這方面的設計。

對基礎型實驗不做專門考核的原因是學生基礎型實驗完成的好壞會直接影響設計型實驗和加強理解型實驗的完成，因此對其他兩種類型實驗的考核間接考核了基礎型實驗。

對設計型實驗的考核分兩個部分：一是本次上機課上實驗的完成情況，包括程序是否調試成功、程序的運行結果是否正確，代碼編寫的質量等；二是本次上機課結束后提交的實驗報告的完成情況，包括內容是否完成、書寫是否規范等。

對加強理解型實驗的考核主要是考核學生提交的源代碼和設計報告的完成質量。

設計型實驗的成績占總實驗成績的70%，加強理解型實驗的成績占總實驗成績的30%。

四、結語

數據結構是一門理論性和實踐性很強的課程，其理論教學環節與實驗教學環節相輔相成。棧和隊列是兩種重要的線性結構，為了提高它們的教學效果，增強實驗教學對其理論教學的促進作用，本文提出了一種棧和隊列的實驗教學方案。該方案的設計思路同樣適用于其他數據結構或課程的實驗教學方案設計。

參考文獻：

[1]朱金秀，金紀東，周妍，等.實踐教學與就業能力培養相融合的研究與探索[J].實驗室研究與探索，2011，30（4）：105-107.

[2]榮瑞芬，閆文杰，李京霞，等.實踐教學課程考核評價模式探索[J].實驗技術與管理，2011，28（3）：232-234.

[3]張純容，施曉秋.問題與案例驅動的課內實踐教學分級模式探索[J].實驗室研究與探索，2012，31（1）：145-148.

[4]教育部高等學校計算機科學與技術教學指導委員會.高等學校計算機科學與技術專業人才專業能力構成與培養[M].北京：機械工業出版社，2010：143-147.

[5]董麗薇.數據結構課程教學方法的改進[J].沈陽師范大學學報（自然科學版），2012，30（2）：307-309.

[6]劉城霞，董宛，蔡英.數據結構中基本教學案例的研究[J].計算機教育，2010，（03）：144-146.

[7]韓建民，鐘發榮，趙相福，等.基于ACM-ICPC訓練模式的數據結構實踐教學探討[J].計算機教育，2013，（10）：103-107.

[8]沈華.數據結構、算法和程序之間關系的探討[J].計算機教育，2013，（04）：58-61.

[9]沈華.數據結構入門教學中的實例法[J].計算機教育，2013，（24）：64-66.

[10]沈華.數據結構課內實踐教學方案[J].實驗室研究與探索，2013，32（10）：396-400.

[11]劉光蓉.以計算思維能力培養為導向的C程序設計實驗教學[J].實驗技術與管理，2013，30（1）：154-156，191.

[12]Korsh J F，Garrett L J. Data structures，algorithms and program style using c[M].Boston，PWS-Kent Publishing Co，US，1986.

[13]沈華，楊曉艷，馬馳，等.數據結構及應用：C語言描述[M].北京：機械工業出版社，2011.