案例教學(xué)法在循環(huán)隊(duì)列教學(xué)中的探究

羅莉霞

摘要：隊(duì)列是一種非常重要的線性結(jié)構(gòu)，不僅在各類管理信息系統(tǒng)中應(yīng)用極多，而且在日常生活中的很多場(chǎng)合都有所運(yùn)用。循環(huán)隊(duì)列尤其是《數(shù)據(jù)結(jié)構(gòu)》課程中的重難點(diǎn)，為了幫助學(xué)生更好理解這個(gè)知識(shí)點(diǎn)，該文提出在循環(huán)隊(duì)列的教學(xué)過程中引入醫(yī)院的智能排隊(duì)叫號(hào)系統(tǒng)作為案例，教師通過開展一系列討論、分析、問答等師生互動(dòng)的活動(dòng)，最終讓學(xué)生提出可行的解決方案，以此來加深學(xué)生對(duì)基本原理、概念的認(rèn)識(shí)和理解。

關(guān)鍵詞：案例教學(xué)法；排隊(duì)叫號(hào)系統(tǒng)；循環(huán)隊(duì)列

中圖分類號(hào)：G64 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）01-0167-02

Abstract：The queue is an important linear structure. It is not only used in many management information systems， but also in many situations in our daily life. In particularly， circular-queue is the keystone in the data structure. In order to help students to understandit well， this paperintroduced the case of hospital intelligent calling and queuing systemswhile teaching， by guiding students to participate in the discussion， analysis， question and answer activities. After these interactive activities， the students were asked to come up with a feasible solution， thus deepening their understanding of the content.

Key words：case methodteaching；calling and queuing systems；circular-queue

案例教學(xué)是教師在教學(xué)過程中引入案例作為教學(xué)材料，結(jié)合教學(xué)主題，通過學(xué)生的調(diào)查、討論、問答等師生互動(dòng)的過程，來探討解決問題的思路和方案，使得學(xué)生積極主動(dòng)學(xué)習(xí)，從而培養(yǎng)學(xué)生更高層次能力的一種教學(xué)方法[1]。它是對(duì)傳統(tǒng)意義上“老師講、學(xué)生聽”這種教學(xué)方法的突破，它要求教師以引導(dǎo)為主，將教學(xué)的中心由以教師為中心轉(zhuǎn)換為以學(xué)生為中心，讓學(xué)生真正成為學(xué)習(xí)的主角，從而激發(fā)學(xué)生的學(xué)習(xí)興趣。

隊(duì)列是《數(shù)據(jù)結(jié)構(gòu)》課程中的重點(diǎn)，也是難點(diǎn)，它是一種非常重要的線性結(jié)構(gòu)。隨著服務(wù)行業(yè)業(yè)務(wù)種類和業(yè)務(wù)數(shù)量的急劇增長，隊(duì)列的應(yīng)用在生活中隨處可見，例如醫(yī)院的電子排隊(duì)機(jī)系統(tǒng)、銀行的叫號(hào)系統(tǒng)，以及工商、稅務(wù)、電信大廳的業(yè)務(wù)排隊(duì)系統(tǒng)等，這些基本上都是采用先來先服務(wù)的機(jī)制[2]。在循環(huán)隊(duì)列的教學(xué)過程中，筆者注意到相當(dāng)一部分學(xué)生對(duì)于“循環(huán)隊(duì)列”的認(rèn)知存在較大偏差，對(duì)于“循環(huán)隊(duì)列算法”的理解存在困惑，為了幫助學(xué)生更好掌握循環(huán)隊(duì)列這種結(jié)構(gòu)體，本文結(jié)合了醫(yī)院的智能排隊(duì)叫號(hào)系統(tǒng)，深入分析和探討循環(huán)隊(duì)列的數(shù)據(jù)存儲(chǔ)方式，以及主體算法的實(shí)現(xiàn)。本文所采用的教學(xué)思路亦可以運(yùn)用到其他數(shù)據(jù)結(jié)構(gòu)或者類似課程的教學(xué)中。

1 案例引入

為了貼合循環(huán)隊(duì)列這個(gè)教學(xué)主題，案例的選擇至關(guān)重要。首先看看生活中的例子，例如銀行存取款，進(jìn)入銀行服務(wù)大廳，我們會(huì)在發(fā)號(hào)機(jī)上取一個(gè)號(hào)碼，你的號(hào)碼條上顯示的內(nèi)容是：“您的號(hào)碼是098號(hào)，您前面有17個(gè)人在等待”，其中，“17”就是隊(duì)列中排隊(duì)的人數(shù)。毋庸置疑，本案例的數(shù)據(jù)存儲(chǔ)采用循環(huán)隊(duì)列的存儲(chǔ)方式，算法需計(jì)算隊(duì)列中排隊(duì)元素的個(gè)數(shù)。這是隊(duì)列的一般性應(yīng)用方向：計(jì)算隊(duì)列中排隊(duì)元素的個(gè)數(shù)。具體實(shí)現(xiàn)方式可參照文獻(xiàn)[2]給出的算法，算法如下：

算法一

int count（SqQueuesq）

{

（sq.rear+MaxSize-sq.front） % MaxSize；}

但是，隊(duì)列除了一般性的應(yīng)用之外，在醫(yī)院和工商稅務(wù)大廳的智能排隊(duì)叫號(hào)系統(tǒng)都有更深層次的應(yīng)用。我們具體以醫(yī)院的智能排隊(duì)叫號(hào)系統(tǒng)為例來進(jìn)行分析，如果仔細(xì)觀察過醫(yī)院的就診排隊(duì)顯示屏，就應(yīng)該知道它顯示的內(nèi)容主要包括：目前就診的患者姓名和排隊(duì)編號(hào)，以及排隊(duì)患者的姓名和排隊(duì)編號(hào)，以及目前排隊(duì)的人數(shù)。如果要實(shí)現(xiàn)這樣的功能，我們需要從以下兩個(gè)方面進(jìn)行討論和分析：

① 如何選用數(shù)據(jù)存儲(chǔ)類型，隊(duì)列的順序存儲(chǔ)方式還是鏈?zhǔn)酱鎯?chǔ)方式呢？

② 需要添加哪些模塊，才能滿足該系統(tǒng)的功能要求？

2 案例分析

數(shù)據(jù)存儲(chǔ)類型的選擇，我們需要結(jié)合案例的實(shí)際情況，從數(shù)據(jù)的存儲(chǔ)、選取和使用等方面對(duì)這兩種存儲(chǔ)方式進(jìn)行比較[2]：

首先，從存儲(chǔ)利用率來看，順序存儲(chǔ)方式下的存儲(chǔ)密度為1，存儲(chǔ)空間的利用率很高；但是鏈?zhǔn)疥?duì)列的存儲(chǔ)方式是不占優(yōu)勢(shì)的，因?yàn)樗枰獮槊總€(gè)數(shù)據(jù)元素附加一個(gè)指針用以存放下一個(gè)數(shù)據(jù)節(jié)點(diǎn)的地址，也就是邏輯關(guān)系，所以它的存儲(chǔ)密度小于1。

其次，就存儲(chǔ)的占用方式方面而言，和鏈?zhǔn)疥?duì)列不一樣，循環(huán)隊(duì)列的存儲(chǔ)空間是固定的，這就需要事先預(yù)估隊(duì)列的長度，這個(gè)預(yù)估的長度太大會(huì)使存儲(chǔ)空間無法被充分利用，長度太小又會(huì)造成“溢出”，使得入隊(duì)操作不成功。就這一點(diǎn)來看，鏈?zhǔn)疥?duì)列的動(dòng)態(tài)分配空間機(jī)制為解決“溢出”提供了較好的解決思路。但是，就本案例而言，生活中需要用到這種排隊(duì)機(jī)制的地方，例如銀行、醫(yī)院、工商稅務(wù)大廳等場(chǎng)合，基本上每天的人流量是有限的，所以只要根據(jù)經(jīng)驗(yàn)值來設(shè)定一個(gè)較大值MaxSize，分配一塊連續(xù)的空間來存儲(chǔ)數(shù)據(jù)，這在理論上和實(shí)踐上都是可行的。endprint

第三，就存取方式而言，循環(huán)隊(duì)列只需要根據(jù)數(shù)組元素的下標(biāo)直接讀取數(shù)據(jù)，而鏈?zhǔn)疥?duì)列卻需要從頭至尾逐個(gè)訪問讀取，從查找效率上來看，鏈?zhǔn)疥?duì)列的查找效率還是沒有循環(huán)隊(duì)列的效率高。

最后，從描述的工具上來分析，循環(huán)隊(duì)列的操作和管理數(shù)據(jù)的工具是數(shù)組，這是很容易理解的，并且編寫代碼的難度不大。鏈?zhǔn)疥?duì)列則采用指針對(duì)其進(jìn)行管理和操作的，相對(duì)而言，指針的使用過程比較復(fù)雜，而且容易出錯(cuò)：例如指針傳遞過程中做了0值傳遞，造成地址丟失，那么很多數(shù)據(jù)就會(huì)丟失；又例如由于人為的失誤在入隊(duì)函數(shù)中寫入死循環(huán)，會(huì)導(dǎo)致系統(tǒng)內(nèi)存寫滿，從而造成災(zāi)難性的后果，這恰好是初學(xué)者容易犯錯(cuò)的地方。所以結(jié)合本案例的要求，對(duì)于僅需在隊(duì)首（隊(duì)尾）進(jìn)行刪除（插入）操作，以及經(jīng)常執(zhí)行查找操作的線性表，宜采用隊(duì)列的順序存儲(chǔ)方式。

接下來，我們分析該功能需要實(shí)現(xiàn)哪些模塊？

模塊一，獲取排隊(duì)的號(hào)碼。這個(gè)號(hào)碼就是元素入隊(duì)的序號(hào)，可以直接通過定義全局變量來實(shí)現(xiàn)，全局變量被初始化為0，元素每入隊(duì)一次，全局變量就自加1一次。這是容易實(shí)現(xiàn)的。

模塊二，讀出隊(duì)列中排隊(duì)元素的值。我們需要設(shè)計(jì)出這個(gè)隊(duì)列的遍歷算法，讀取出排隊(duì)患者的姓名和排隊(duì)編號(hào)。循環(huán)隊(duì)列的基本算法中并沒有提及如何順序訪問到每一個(gè)隊(duì)列元素，這種算法如何實(shí)現(xiàn)呢？筆者給出了以下的可行方案。

設(shè)計(jì)循環(huán)隊(duì)列遍歷算法，我們首先回顧順序隊(duì)列是如何實(shí)現(xiàn)遍歷算法的，如果要逐個(gè)訪問如下圖中順序隊(duì)列的元素值，我們可以通過算法二這個(gè)簡(jiǎn)單的循環(huán)實(shí)現(xiàn)：

算法二：

intDispQueue（SqQueuesq）

{if（sq.rear==sq.front）

{printf（"＼t＼t＼t＼a沒有人在排隊(duì)＼n＼n"）；

return 0； }

for（i=sq.front+1；i<=sq.rear；i++）

printf（“%c正在排隊(duì)＼n”，sq.data[i]）；

return 1；}

仔細(xì)觀察圖1，上述的算法二似乎能夠很完美地解決這個(gè)問題，但是這不是最優(yōu)的。因?yàn)樵陧樞蜿?duì)列中有“假溢出”的情況產(chǎn)生，所以我們需要是將順序隊(duì)列的連續(xù)空間想象成首尾相連的環(huán)狀空間，如果隊(duì)首位置出現(xiàn)了空位，就可以將入隊(duì)的元素存入空閑的存儲(chǔ)空間，從而能夠充分利用空間，避免不必要的空間浪費(fèi)，循環(huán)隊(duì)列能夠很好地解決隊(duì)列“假溢出”這種情況[3]。但是問題來了，能否像順序隊(duì)列一樣通過直接訪問數(shù)組成員data[i]，讀取出相應(yīng)的隊(duì)列元素呢？答案是肯定的。

我們?nèi)匀豢梢远x一個(gè)循環(huán)控制變量i， 設(shè)定好i的初始值和終值，然后通過數(shù)組元素data[i]來逐個(gè)訪問隊(duì)列成員，如何設(shè)置i的初值和終值呢？首先我們分析循環(huán)隊(duì)列的存儲(chǔ)情況，基本上可以分為以下兩種情況：①rear≥front，②rear

① rear≥front這種情況和順序隊(duì)列的實(shí)現(xiàn)方法類似，不在贅述；

② rear

4=（3+1）% MaxSize0=（4+1）% MaxSize1=（5+1）% MaxSize

我們將將算法二中i++改進(jìn)為 i = （i + 1） % MaxSize， 綜合上述分析，循環(huán)隊(duì)列遍歷算法如下：

算法三：

intCircDispQueue（SqQueuesq）

{if（sq.rear==sq.front）

{printf（"＼t＼t＼t＼a沒有人在排隊(duì)＼n＼n"）；

return 0； }

int i=sq.front+1；

while（i<=sq.rear）

{printf（“%c正在排隊(duì)＼n”，sq.data[i]）；

i=（i+1）%MaxSize；}

return 1； }

3 結(jié)束語

本文就循環(huán)隊(duì)列教學(xué)中如何采用案例教學(xué)法的組織和實(shí)施方法做了探討，特別引入了實(shí)際生活中醫(yī)院的智能排隊(duì)叫號(hào)系統(tǒng)作為案例，并就這個(gè)系統(tǒng)的實(shí)現(xiàn)宜采用的數(shù)據(jù)存儲(chǔ)方式，以及實(shí)現(xiàn)的主體功能模塊等內(nèi)容做了詳細(xì)的分析和討論。實(shí)踐證明，在課堂上中采用本文闡述的案例教學(xué)法是一種行之有效的教學(xué)方法，通過對(duì)案例的分析和討論，大部分學(xué)生都能積極主動(dòng)思考，并參與到整個(gè)課堂教學(xué)的過程中來，從而理解并掌握了循環(huán)隊(duì)列的存儲(chǔ)方式和具體算法的實(shí)現(xiàn)過程。

案例教學(xué)法可以讓學(xué)生結(jié)合教學(xué)主題的理論知識(shí)參與到案例的調(diào)查、分析、討論等活動(dòng)中來，進(jìn)而提高他們分析問題和解決問題的能力，反過來還能加深他們對(duì)基本原理和概念的理解[4]。所有理論知識(shí)的學(xué)習(xí)和儲(chǔ)備最終都是為了能夠解決生活中的實(shí)際問題，這恰好又是大學(xué)生普遍存在的短板，這就要求教師在課堂教學(xué)中采用多種更為科學(xué)有效的教學(xué)方式，提高學(xué)生學(xué)習(xí)的效率[5]。

參考文獻(xiàn)：

[1] 張家軍，靳玉樂. 論案例教學(xué)的本質(zhì)與特點(diǎn)[J].中國教育學(xué)刊，2004（1）：48-50.

[2] 殷人昆. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，2012：54-55，74.

[3] 李春葆.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程[M].北京：清華大學(xué)出版社，2014（1）：87-92.

[4] 姜彥偉. 關(guān)于循環(huán)隊(duì)列遍歷算法的討論及修正[J]. 工業(yè)儀表與自動(dòng)化裝置，2015（6）：86-89.

[5] 吳高臣，劉爽. 實(shí)踐導(dǎo)向：案例教學(xué)法研究[J]. 黑龍江高教研究，2011（12）：178-181.