摘要：數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的核心課程，對培養(yǎng)計算機(jī)專業(yè)設(shè)計與創(chuàng)新型人才起著關(guān)鍵作用。該課程是理論性和實踐性很強(qiáng)的一門課程。實驗教學(xué)是其教學(xué)中的一個重要環(huán)節(jié)。棧和隊列是兩種非常重要的線性結(jié)構(gòu)，它們有很多實際應(yīng)用。為了幫助學(xué)生充分理解、掌握和靈活運用這兩種數(shù)據(jù)結(jié)構(gòu)，本文給出一種棧和隊列的實驗教學(xué)方案。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；實驗教學(xué)方案；棧；隊列

中圖分類號：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2016）24-0274-03

一、引言

實驗教學(xué)是學(xué)生從學(xué)習(xí)理論知識到走向社會的橋梁，對提高學(xué)生綜合素質(zhì)、培養(yǎng)學(xué)生創(chuàng)新精神和實踐能力有著理論教學(xué)不可替代的特殊作用[1]。特別是主干課程的實踐教學(xué)，它是應(yīng)用型人才培養(yǎng)中的關(guān)鍵環(huán)節(jié)[2]。課內(nèi)實驗是指與理論課相捆綁的實踐教學(xué)，即嵌入到專業(yè)基礎(chǔ)課或?qū)I(yè)課內(nèi)的實驗實踐教學(xué)[3]。它是與理論教學(xué)并行實施的實踐教學(xué)環(huán)節(jié)，能夠幫助學(xué)生深入理解和掌握所學(xué)的專業(yè)知識。

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

棧和隊列是兩種非常重要的數(shù)據(jù)結(jié)構(gòu)，它們有非常多的實際應(yīng)用并且是實現(xiàn)其他復(fù)雜結(jié)構(gòu)的基礎(chǔ)，因此為了幫助學(xué)生掌握并靈活運用這兩種結(jié)構(gòu)，本文給出一種棧和隊列的實驗教學(xué)方案。該方案的設(shè)計思路也可以應(yīng)用于其他數(shù)據(jù)結(jié)構(gòu)或課程的實驗教學(xué)方案的設(shè)計。

二、認(rèn)識兩種重要的數(shù)據(jù)結(jié)構(gòu)——棧和隊列

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

（一）學(xué)習(xí)對象

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

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

（二）學(xué)習(xí)目標(biāo)

學(xué)習(xí)這兩種重要的線性結(jié)構(gòu)需要學(xué)生重點消化的知識點有：（1）棧/隊列的概念、類型定義及基本操作的定義和實現(xiàn)；（2）棧/隊列的結(jié)構(gòu)特性；（3）棧/隊列的靈活應(yīng)用。

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

三、棧和隊列的實驗教學(xué)方案設(shè)計

（一）實驗題目設(shè)計

根據(jù)棧和隊列的學(xué)習(xí)目標(biāo)和遵循循序漸進(jìn)的學(xué)習(xí)和教學(xué)原則，實驗題目被分為以下三個層次：基礎(chǔ)型實驗題目、設(shè)計型實驗題目和加強(qiáng)理解型實驗題目。

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

在棧的理論教學(xué)過程中可以開設(shè)棧的基礎(chǔ)型實驗，在棧的理論教學(xué)結(jié)束后可以開設(shè)棧的設(shè)計型實驗，在隊列的理論教學(xué)過程中可以開設(shè)隊列的基礎(chǔ)型實驗，在隊列的理論教學(xué)結(jié)束后可以開設(shè)隊列的設(shè)計型實驗和加強(qiáng)理解型實驗題目。表1給出了具體的實驗安排。

學(xué)生必須在相關(guān)內(nèi)容的理論教學(xué)過程中利用自己的課外時間完成全部基礎(chǔ)型實驗題目，教師根據(jù)學(xué)時安排選擇1～2道設(shè)計型實驗題目讓學(xué)生在上機(jī)課上完成，未選擇的題目應(yīng)向?qū)W生提供完整的源代碼和設(shè)計說明。相關(guān)內(nèi)容的理論教學(xué)結(jié)束后，學(xué)生必須利用自己的課外時間完成加強(qiáng)理解型實驗題目中的第1題和第2題，剩下兩題可以選做。

（二）教學(xué)方法

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

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

設(shè)計型實驗要求每位學(xué)生在上機(jī)課上獨立完成，教師前期參與指導(dǎo)。所謂前期參與指導(dǎo)是指教師參與學(xué)生在算法設(shè)計環(huán)節(jié)的討論，教師可以給出提示，同時鼓勵學(xué)生設(shè)計不同的算法。參與方式是面對面的交流。

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

（三）考核方法

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

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

對設(shè)計型實驗的考核分兩個部分：一是本次上機(jī)課上實驗的完成情況，包括程序是否調(diào)試成功、程序的運行結(jié)果是否正確，代碼編寫的質(zhì)量等；二是本次上機(jī)課結(jié)束后提交的實驗報告的完成情況，包括內(nèi)容是否完成、書寫是否規(guī)范等。

對加強(qiáng)理解型實驗的考核主要是考核學(xué)生提交的源代碼和設(shè)計報告的完成質(zhì)量。

設(shè)計型實驗的成績占總實驗成績的70%，加強(qiáng)理解型實驗的成績占總實驗成績的30%。

四、結(jié)語

數(shù)據(jù)結(jié)構(gòu)是一門理論性和實踐性很強(qiáng)的課程，其理論教學(xué)環(huán)節(jié)與實驗教學(xué)環(huán)節(jié)相輔相成。棧和隊列是兩種重要的線性結(jié)構(gòu)，為了提高它們的教學(xué)效果，增強(qiáng)實驗教學(xué)對其理論教學(xué)的促進(jìn)作用，本文提出了一種棧和隊列的實驗教學(xué)方案。該方案的設(shè)計思路同樣適用于其他數(shù)據(jù)結(jié)構(gòu)或課程的實驗教學(xué)方案設(shè)計。

參考文獻(xiàn)：

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

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

[3]張純?nèi)?，施曉?問題與案例驅(qū)動的課內(nèi)實踐教學(xué)分級模式探索[J].實驗室研究與探索，2012，31（1）：145-148.

[4]教育部高等學(xué)校計算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會.高等學(xué)校計算機(jī)科學(xué)與技術(shù)專業(yè)人才專業(yè)能力構(gòu)成與培養(yǎng)[M].北京：機(jī)械工業(yè)出版社，2010：143-147.

[5]董麗薇.數(shù)據(jù)結(jié)構(gòu)課程教學(xué)方法的改進(jìn)[J].沈陽師范大學(xué)學(xué)報（自然科學(xué)版），2012，30（2）：307-309.

[6]劉城霞，董宛，蔡英.數(shù)據(jù)結(jié)構(gòu)中基本教學(xué)案例的研究[J].計算機(jī)教育，2010，（03）：144-146.

[7]韓建民，鐘發(fā)榮，趙相福，等.基于ACM-ICPC訓(xùn)練模式的數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)探討[J].計算機(jī)教育，2013，（10）：103-107.

[8]沈華.數(shù)據(jù)結(jié)構(gòu)、算法和程序之間關(guān)系的探討[J].計算機(jī)教育，2013，（04）：58-61.

[9]沈華.數(shù)據(jù)結(jié)構(gòu)入門教學(xué)中的實例法[J].計算機(jī)教育，2013，（24）：64-66.

[10]沈華.數(shù)據(jù)結(jié)構(gòu)課內(nèi)實踐教學(xué)方案[J].實驗室研究與探索，2013，32（10）：396-400.

[11]劉光蓉.以計算思維能力培養(yǎng)為導(dǎo)向的C程序設(shè)計實驗教學(xué)[J].實驗技術(shù)與管理，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]沈華，楊曉艷，馬馳，等.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用：C語言描述[M].北京：機(jī)械工業(yè)出版社，2011.