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

摘要：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程，對(duì)培養(yǎng)計(jì)算機(jī)專業(yè)設(shè)計(jì)與創(chuàng)新型人才起著關(guān)鍵作用。該課程是理論性和實(shí)踐性很強(qiáng)的一門課程。實(shí)驗(yàn)教學(xué)是其教學(xué)中的一個(gè)重要環(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ì)列

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

一、引言

實(shí)驗(yàn)教學(xué)是學(xué)生從學(xué)習(xí)理論知識(shí)到走向社會(huì)的橋梁，對(duì)提高學(xué)生綜合素質(zhì)、培養(yǎng)學(xué)生創(chuàng)新精神和實(shí)踐能力有著理論教學(xué)不可替代的特殊作用[1]。特別是主干課程的實(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í)。

數(shù)據(jù)結(jié)構(gòu)是隨著處理對(duì)象的復(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]。它可以解決學(xué)生對(duì)所學(xué)知識(shí)缺乏必要感性認(rèn)識(shí)的問題，將知識(shí)傳授、技能訓(xùn)練、能力培養(yǎng)融于一體，使所學(xué)理論知識(shí)在實(shí)驗(yàn)中得到驗(yàn)證和應(yīng)用[11]。

棧和隊(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í)兩種重要的數(shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列

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

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

棧（stack）是運(yùn)算受限的線性表，它被限制在表的一端進(jìn)行插入和刪除操作。能進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。正是由于它插入和刪除操作上的限制使得它具有了一種獨(dú)特的“后進(jìn)先出”（LIFO）的特性。棧的LIFO特性使得它具有非常多的應(yīng)用，如：符號(hào)平衡問題、中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式問題、后綴表達(dá)式的計(jì)算問題、函數(shù)調(diào)用的實(shí)現(xiàn)（包括遞歸函數(shù)的實(shí)現(xiàn)）、在股票市場(chǎng)中查找劃分、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)消化的知識(shí)點(diǎn)有：（1）棧/隊(duì)列的概念、類型定義及基本操作的定義和實(shí)現(xiàn)；（2）棧/隊(duì)列的結(jié)構(gòu)特性；（3）棧/隊(duì)列的靈活應(yīng)用。

為了配合棧和隊(duì)列的理論教學(xué)，幫助學(xué)生理解和掌握上述知識(shí)點(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)題目被分為以下三個(gè)層次：基礎(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)證課堂上講授的重要知識(shí)點(diǎn)，給學(xué)生切身的感受，擺脫“紙上談兵”的感覺，這種立體的感受有助于學(xué)生深入理解和掌握這些知識(shí)點(diǎn)。設(shè)計(jì)型實(shí)驗(yàn)要求學(xué)生能分別運(yùn)用棧/隊(duì)列解決簡(jiǎn)單應(yīng)用問題。這類實(shí)驗(yàn)題目主要是用來引導(dǎo)和加強(qiáng)學(xué)生對(duì)棧/隊(duì)列的靈活運(yùn)用。設(shè)計(jì)加強(qiáng)理解型實(shí)驗(yàn)的目的是強(qiáng)化學(xué)生對(duì)棧和隊(duì)列的結(jié)構(gòu)特性的理解和體會(huì)。為了達(dá)到這個(gè)目的，加強(qiáng)理解型實(shí)驗(yàn)題目的設(shè)計(jì)思路有兩個(gè)方面：（1）引導(dǎo)學(xué)生去思考并解決這樣兩個(gè)問題：能否利用棧的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ū)別對(duì)待。表2給出了對(duì)三種類型實(shí)驗(yàn)在上述這幾個(gè)方面的設(shè)計(jì)。

基礎(chǔ)型實(shí)驗(yàn)要求每位學(xué)生利用課外時(shí)間獨(dú)立完成，教師全程參與指導(dǎo)。所謂全程參與指導(dǎo)是指從算法基本思想到算法實(shí)現(xiàn)的各個(gè)環(huán)節(jié)（包括編程技巧、程序調(diào)試與測(cè)試等）都要參與指導(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í)鼓勵(lì)學(xué)生設(shè)計(jì)不同的算法。參與方式是面對(duì)面的交流。

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

（三）考核方法

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

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

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

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

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

四、結(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é)對(duì)其理論教學(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é)課程考核評(píng)價(jià)模式探索[J].實(shí)驗(yàn)技術(shù)與管理，2011，28（3）：232-234.

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

[4]教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì).高等學(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，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.