數(shù)據(jù)結(jié)構(gòu)課程中棧和隊(duì)列實(shí)驗(yàn)教學(xué)方案設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)課程中棧和隊(duì)列實(shí)驗(yàn)教學(xué)方案設(shè)計(jì)

摘要：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程，對培養(yǎng)計(jì)算機(jī)專業(yè)設(shè)

計(jì)與創(chuàng)新型人才起著關(guān)鍵作用。該課程是理論性和實(shí)踐性很強(qiáng)的一門

課程。實(shí)驗(yàn)教學(xué)是其教學(xué)中的一個重要環(huán)節(jié)。棧和隊(duì)列是兩種非常重

要的線性結(jié)構(gòu)，它們有很多實(shí)際應(yīng)用。為了幫助學(xué)生充分理解、掌握

和靈活運(yùn)用這兩種數(shù)據(jù)結(jié)構(gòu)，本文給出一種棧和隊(duì)列的實(shí)驗(yàn)教學(xué)方案。

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

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

24-0274-03

一、引言

實(shí)驗(yàn)教學(xué)是學(xué)生從學(xué)習(xí)理論知識到走向社會的橋梁，對提高學(xué)生

綜合素質(zhì)、培養(yǎng)學(xué)生創(chuàng)新精神和實(shí)踐能力有著理論教學(xué)不可替代的特

殊作用口］。特別是主干課程的實(shí)踐教學(xué)，它是應(yīng)用型人才培養(yǎng)中的

關(guān)鍵環(huán)節(jié)［2］。課內(nèi)實(shí)驗(yàn)是指與理論課相捆綁的實(shí)踐教學(xué)，即嵌入到

專業(yè)基礎(chǔ)課或?qū)I(yè)課內(nèi)的實(shí)驗(yàn)實(shí)踐教學(xué)［3］。它是與理論教學(xué)并行實(shí)

施的實(shí)踐教學(xué)環(huán)節(jié)，能夠幫助學(xué)生深入理解和掌握所學(xué)的專業(yè)知識。

數(shù)據(jù)結(jié)構(gòu)是隨著處理對象的復(fù)雜性不斷增加而發(fā)展起來的一門

課程，作為計(jì)算機(jī)專業(yè)的核心課程，在專業(yè)人才培養(yǎng)鏈條中占有舉足

輕重的地位［4-7］。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)在抽象視圖和實(shí)現(xiàn)視圖中

的表示和處理方法［8,9］。抽象視圖涉及的是數(shù)據(jù)結(jié)構(gòu)的理論性部分，

實(shí)現(xiàn)視圖主要體現(xiàn)的是數(shù)據(jù)結(jié)構(gòu)的實(shí)踐性，理論指導(dǎo)實(shí)踐，實(shí)踐支撐

理論，因此設(shè)計(jì)有助于課堂理論教學(xué)的實(shí)驗(yàn)教學(xué)方案是非常有必要的

[10]o它可以解決學(xué)生對所學(xué)知識缺乏必要感性認(rèn)識的問題，將知識

傳授、技能訓(xùn)練、能力培養(yǎng)融于一體，使所學(xué)理論知識在實(shí)驗(yàn)中得到

驗(yàn)證和應(yīng)用[11]O

棧和隊(duì)列是兩種非常重要的數(shù)據(jù)結(jié)構(gòu)，它們有非常多的實(shí)際應(yīng)用

并且是實(shí)現(xiàn)其他復(fù)雜結(jié)構(gòu)的基礎(chǔ)，因此為了幫助學(xué)生掌握并靈活運(yùn)用

這兩種結(jié)構(gòu)，本文給出一種棧和隊(duì)列的實(shí)驗(yàn)教學(xué)方案。該方案的設(shè)計(jì)

思路也可以應(yīng)用于其他數(shù)據(jù)結(jié)構(gòu)或課程的實(shí)驗(yàn)教學(xué)方案的設(shè)計(jì)。

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

棧和隊(duì)列是兩種運(yùn)算受限的線性表，它們的插入和刪除運(yùn)算都被

限制在表的端點(diǎn)處進(jìn)行，只是具體的受限規(guī)則不一樣[12,13]。

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

棧（stack）是運(yùn)算受限的線性表，它被限制在表的一端進(jìn)行插

入和刪除操作。能進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。

正是由于它插入和刪除操作上的限制使得它具有了一種獨(dú)特的“后

進(jìn)先出”（LIFO）的特性。棧的LIFO特性使得它具有非常多的應(yīng)用，

如：符號平衡問題、中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式問題、后綴表達(dá)式

的計(jì)算問題、函數(shù)調(diào)用的實(shí)現(xiàn)（包括遞歸函數(shù)的實(shí)現(xiàn)）、在股票市場

中查找劃分、Web瀏覽器中的網(wǎng)頁訪問歷史、文本編輯器中的撤銷序

列等。此外，棧還是其他很多算法的輔助數(shù)據(jù)結(jié)構(gòu)和其他數(shù)據(jù)結(jié)構(gòu)的

組成部分。

隊(duì)列（queue）也是一種運(yùn)算受限的線性表，它被限制在表的一

端進(jìn)行插入操作，在表的另一端進(jìn)行刪除操作。進(jìn)行插入操作的一端

稱為隊(duì)尾，進(jìn)行刪除操作的一端稱為隊(duì)首。正是由于它插入和刪除操

作上的限制使得它具有了一種獨(dú)特的“先進(jìn)先出”（FIFO）的特性。

隊(duì)列的FIFO特性使得它具有非常多的應(yīng)用，如：操作系統(tǒng)中的作業(yè)

調(diào)度、異步數(shù)據(jù)轉(zhuǎn)換、多道程序設(shè)計(jì)等。此外，隊(duì)列還是其他很多算

法的輔助數(shù)據(jù)結(jié)構(gòu)和其他數(shù)據(jù)結(jié)構(gòu)的組成部分。

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

學(xué)習(xí)這兩種重要的線性結(jié)構(gòu)需要學(xué)生重點(diǎn)消化的知識點(diǎn)有：（1）

棧/隊(duì)列的概念、類型定義及基本操作的定義和實(shí)現(xiàn)；（2）棧/隊(duì)列的

結(jié)構(gòu)特性；（3）棧/隊(duì)列的靈活應(yīng)用。

為了配合棧和隊(duì)列的理論教學(xué)，幫助學(xué)生理解和掌握上述知識點(diǎn),

我們需要精心設(shè)計(jì)棧和隊(duì)列的實(shí)驗(yàn)教學(xué)方案。

三、棧和隊(duì)列的實(shí)驗(yàn)教學(xué)方案設(shè)計(jì)

（一）實(shí)驗(yàn)題目設(shè)計(jì)

根據(jù)棧和隊(duì)列的學(xué)習(xí)目標(biāo)和遵循循序漸進(jìn)的學(xué)習(xí)和教學(xué)原則，實(shí)

驗(yàn)題目被分為以下三個層次：基礎(chǔ)型實(shí)驗(yàn)題目、設(shè)計(jì)型實(shí)驗(yàn)題目和加

強(qiáng)理解型實(shí)驗(yàn)題目。

所謂基礎(chǔ)型實(shí)驗(yàn)是指圍繞課程講授的棧/隊(duì)列的物理實(shí)現(xiàn)和其基

本運(yùn)算的實(shí)現(xiàn)來設(shè)置的實(shí)驗(yàn)題目。設(shè)計(jì)基礎(chǔ)型實(shí)驗(yàn)的目的是，通過實(shí)

踐的方式驗(yàn)證課堂上講授的重要知識點(diǎn)，給學(xué)生切身的感受，擺脫

“紙上談兵”的感覺，這種立體的感受有助于學(xué)生深入理解和掌握這

些知識點(diǎn)。設(shè)計(jì)型實(shí)驗(yàn)要求學(xué)生能分別運(yùn)用棧/隊(duì)列解決簡單應(yīng)用問

題。這類實(shí)驗(yàn)題目主要是用來引導(dǎo)和加強(qiáng)學(xué)生對棧/隊(duì)列的靈活運(yùn)用。

設(shè)計(jì)加強(qiáng)理解型實(shí)驗(yàn)的目的是強(qiáng)化學(xué)生對棧和隊(duì)列的結(jié)構(gòu)特性的理

解和體會。為了達(dá)到這個目的，加強(qiáng)理解型實(shí)驗(yàn)題目的設(shè)計(jì)思路有兩

個方面：（1）引導(dǎo)學(xué)生去思考并解決這樣兩個問題：能否利用棧的

LIFO特性來實(shí)現(xiàn)隊(duì)列的FIFO特性？能否利用隊(duì)列的FIFO特性來實(shí)

現(xiàn)棧的LIFO特性？（2）讓學(xué)生實(shí)現(xiàn)其他更為復(fù)雜的棧和隊(duì)列。

在棧的理論教學(xué)過程中可以開設(shè)棧的基礎(chǔ)型實(shí)驗(yàn)，在棧的理論教

學(xué)結(jié)束后可以開設(shè)棧的設(shè)計(jì)型實(shí)驗(yàn)，在隊(duì)列的理論教學(xué)過程中可以開

設(shè)隊(duì)列的基礎(chǔ)型實(shí)驗(yàn)，在隊(duì)列的理論教學(xué)結(jié)束后可以開設(shè)隊(duì)列的設(shè)計(jì)

型實(shí)驗(yàn)和加強(qiáng)理解型實(shí)驗(yàn)題目。表1給出了具體的實(shí)驗(yàn)安排。

學(xué)生必須在相關(guān)內(nèi)容的理論教學(xué)過程中利用自己的課外時(shí)間完

成全部基礎(chǔ)型實(shí)驗(yàn)題目，教師根據(jù)學(xué)時(shí)安排選擇1?2道設(shè)計(jì)型實(shí)驗(yàn)

題目讓學(xué)生在上機(jī)課上完成，未選擇的題目應(yīng)向?qū)W生提供完整的源代

碼和設(shè)計(jì)說明。相關(guān)內(nèi)容的理論教學(xué)結(jié)束后，學(xué)生必須利用自己的課

外時(shí)間完成加強(qiáng)理解型實(shí)驗(yàn)題目中的第1題和第2題，剩下兩題可以

選做。

（二）教學(xué)方法

因?yàn)槿N類型實(shí)驗(yàn)的要求、難易程度不同，因此在學(xué)生參與形式、

教師參與程度、教師參與方式等方面需要區(qū)別對待。表2給出了對三

種類型實(shí)驗(yàn)在上述這幾個方面的設(shè)計(jì)。

基礎(chǔ)型實(shí)驗(yàn)要求每位學(xué)生利用課外時(shí)間獨(dú)立完成，教師全程參與

指導(dǎo)。所謂全程參與指導(dǎo)是指從算法基本思想到算法實(shí)現(xiàn)的各個環(huán)節(jié)

（包括編程技巧、程序調(diào)試與測試等）都要參與指導(dǎo)。參與方式多種

多樣，例如利用QQ等即時(shí)通訊工具進(jìn)行指導(dǎo)，約定時(shí)間和地點(diǎn)進(jìn)行

答疑，等等。

設(shè)計(jì)型實(shí)驗(yàn)要求每位學(xué)生在上機(jī)課上獨(dú)立完成，教師前期參與指

導(dǎo)。所謂前期參與指導(dǎo)是指教師參與學(xué)生在算法設(shè)計(jì)環(huán)節(jié)的討論，教

師可以給出提示，同時(shí)鼓勵學(xué)生設(shè)計(jì)不同的算法。參與方式是面對面

的交流。

加強(qiáng)理解型實(shí)驗(yàn)要求每位學(xué)生利用課外時(shí)間獨(dú)立完成，教師后期

參與指導(dǎo)。所謂后期參與指導(dǎo)是指教師在收齊學(xué)生提交的源碼和設(shè)計(jì)

報(bào)告后，對其進(jìn)行分析總結(jié)，并將總結(jié)結(jié)果以班級為單位采用面對面

的方式反饋給學(xué)生。

（三）考核方法

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

計(jì)。

對基礎(chǔ)型實(shí)驗(yàn)不做專門考核的原因是學(xué)生基礎(chǔ)型實(shí)驗(yàn)完成的好

壞會直接影響設(shè)計(jì)型實(shí)驗(yàn)和加強(qiáng)理解型實(shí)驗(yàn)的完成，因此對其他兩種

類型實(shí)驗(yàn)的考核間接考核了基礎(chǔ)型實(shí)驗(yàn)。

對設(shè)計(jì)型實(shí)驗(yàn)的考核分兩個部分：一是本次上機(jī)課上實(shí)驗(yàn)的完成

情況，包括程序是否調(diào)試成功、程序的運(yùn)行結(jié)果是否正確，代碼編寫

的質(zhì)量等；二是本次上機(jī)課結(jié)束后提交的實(shí)驗(yàn)報(bào)告的完成情況，包括

內(nèi)容是否完成、書寫是否規(guī)范等。

對加強(qiáng)理解型實(shí)驗(yàn)的考核主要是考核學(xué)生提交的源代碼和設(shè)計(jì)

報(bào)告的完成質(zhì)量。

設(shè)計(jì)型實(shí)驗(yàn)的成績占總實(shí)驗(yàn)成績的70%,加強(qiáng)理解型實(shí)驗(yàn)的成績

占總實(shí)驗(yàn)成績的30%o

四、結(jié)語

數(shù)據(jù)結(jié)構(gòu)是一門理論性和實(shí)踐性很強(qiáng)的課程，其理論教學(xué)環(huán)節(jié)與

實(shí)驗(yàn)教學(xué)環(huán)節(jié)相輔相成。棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)，為了提高

它們的教學(xué)效果，增強(qiáng)實(shí)驗(yàn)教學(xué)對其理論教學(xué)的促進(jìn)作用，本文提出

了一種棧和隊(duì)列的實(shí)驗(yàn)教學(xué)方案。該方案的設(shè)計(jì)思路同樣適用于其他

數(shù)據(jù)結(jié)構(gòu)或課程的實(shí)驗(yàn)教學(xué)方案設(shè)計(jì)。

參考文獻(xiàn)：

［1］朱金秀，金紀(jì)東，周妍，等.實(shí)踐教學(xué)與就業(yè)能力培養(yǎng)相融合

的研究與探索［J］.實(shí)驗(yàn)室研究與探索，2011,30(4)：105-107.

［2］榮瑞芬，閆文杰，李京霞，等.實(shí)踐教學(xué)課程考核評價(jià)模式探

索口］.實(shí)驗(yàn)技術(shù)與管理,2011,28(3)：232-234.

［3］張純?nèi)?，施曉?問題與案例驅(qū)動的課內(nèi)實(shí)踐教學(xué)分級模式探

索［J］.實(shí)驗(yàn)室研究與探索，2012,31(1)：145-148.

［4］教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會.高等學(xué)

校計(jì)算機(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é)

報(bào)(自然科學(xué)版)，2012,30(2)：307-309.

[6]劉城霞，董宛，蔡英.數(shù)據(jù)結(jié)構(gòu)中基本教學(xué)案例的研究[J].

計(jì)算機(jī)教育，2010,(03)：144-146.

[7]韓建民，鐘發(fā)榮，趙相福，等.基于ACM-ICPC訓(xùn)練模式的數(shù)

據(jù)結(jié)構(gòu)實(shí)踐教學(xué)探討[J].計(jì)算機(jī)教育，2013,(10)：103-107.

[8]沈華.數(shù)據(jù)結(jié)構(gòu)、算法和程序之間關(guān)系的探討[J].計(jì)算機(jī)教育,

2013,(04)：58-61.

[9]沈華.數(shù)據(jù)結(jié)構(gòu)入門教學(xué)中的實(shí)例法[J].計(jì)算機(jī)教育，2013,

(24)：64-66.

[10]沈華.數(shù)據(jù)結(jié)構(gòu)課內(nèi)實(shí)踐教學(xué)方案[J].實(shí)驗(yàn)室研究與探索，

2013,32(10)：396-400.

[11]劉光蓉.以計(jì)算思維能力培養(yǎng)為導(dǎo)向的C程序設(shè)計(jì)實(shí)驗(yàn)教學(xué)

[J].實(shí)驗(yàn)技術(shù)與管理，2013,