羅莉霞

摘要：隊(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é)過(guò)程中引入醫(yī)院的智能排隊(duì)叫號(hào)系統(tǒng)作為案例，教師通過(guò)開展一系列討論、分析、問(wèn)答等師生互動(dòng)的活動(dòng)，最終讓學(xué)生提出可行的解決方案，以此來(lái)加深學(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é)過(guò)程中引入案例作為教學(xué)材料，結(jié)合教學(xué)主題，通過(guò)學(xué)生的調(diào)查、討論、問(wèn)答等師生互動(dòng)的過(guò)程，來(lái)探討解決問(wèn)題的思路和方案，使得學(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ù)量的急劇增長(zhǎng)，隊(duì)列的應(yīng)用在生活中隨處可見，例如醫(yī)院的電子排隊(duì)機(jī)系統(tǒng)、銀行的叫號(hào)系統(tǒng)，以及工商、稅務(wù)、電信大廳的業(yè)務(wù)排隊(duì)系統(tǒng)等，這些基本上都是采用先來(lái)先服務(wù)的機(jī)制[2]。在循環(huán)隊(duì)列的教學(xué)過(guò)程中，筆者注意到相當(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)為例來(lái)進(jìn)行分析，如果仔細(xì)觀察過(guò)醫(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ǔ)利用率來(lái)看，順序存儲(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ì)列的長(zhǎng)度，這個(gè)預(yù)估的長(zhǎng)度太大會(huì)使存儲(chǔ)空間無(wú)法被充分利用，長(zhǎng)度太小又會(huì)造成“溢出”，使得入隊(duì)操作不成功。就這一點(diǎn)來(lái)看，鏈?zhǔn)疥?duì)列的動(dòng)態(tài)分配空間機(jī)制為解決“溢出”提供了較好的解決思路。但是，就本案例而言，生活中需要用到這種排隊(duì)機(jī)制的地方，例如銀行、醫(yī)院、工商稅務(wù)大廳等場(chǎng)合，基本上每天的人流量是有限的，所以只要根據(jù)經(jīng)驗(yàn)值來(lái)設(shè)定一個(gè)較大值MaxSize，分配一塊連續(xù)的空間來(lái)存儲(chǔ)數(shù)據(jù)，這在理論上和實(shí)踐上都是可行的。endprint

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

最后，從描述的工具上來(lái)分析，循環(huán)隊(duì)列的操作和管理數(shù)據(jù)的工具是數(shù)組，這是很容易理解的，并且編寫代碼的難度不大。鏈?zhǔn)疥?duì)列則采用指針對(duì)其進(jìn)行管理和操作的，相對(duì)而言，指針的使用過(guò)程比較復(fù)雜，而且容易出錯(cuò)：例如指針傳遞過(guò)程中做了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ǔ)方式。

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

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

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

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

算法二：

intDispQueue（SqQueuesq）

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

{printf（"＼t＼t＼t＼a沒(méi)有人在排隊(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è)問(wèn)題，但是這不是最優(yōu)的。因?yàn)樵陧樞蜿?duì)列中有“假溢出”的情況產(chǎn)生，所以我們需要是將順序隊(duì)列的連續(xù)空間想象成首尾相連的環(huán)狀空間，如果隊(duì)首位置出現(xiàn)了空位，就可以將入隊(duì)的元素存入空閑的存儲(chǔ)空間，從而能夠充分利用空間，避免不必要的空間浪費(fèi)，循環(huán)隊(duì)列能夠很好地解決隊(duì)列“假溢出”這種情況[3]。但是問(wèn)題來(lái)了，能否像順序隊(duì)列一樣通過(guò)直接訪問(wèn)數(shù)組成員data[i]，讀取出相應(yīng)的隊(duì)列元素呢？答案是肯定的。

我們?nèi)匀豢梢远x一個(gè)循環(huán)控制變量i， 設(shè)定好i的初始值和終值，然后通過(guò)數(shù)組元素data[i]來(lái)逐個(gè)訪問(wèn)隊(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沒(méi)有人在排隊(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é)束語(yǔ)

本文就循環(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é)方法，通過(guò)對(duì)案例的分析和討論，大部分學(xué)生都能積極主動(dòng)思考，并參與到整個(gè)課堂教學(xué)的過(guò)程中來(lái)，從而理解并掌握了循環(huán)隊(duì)列的存儲(chǔ)方式和具體算法的實(shí)現(xiàn)過(guò)程。

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

參考文獻(xiàn)：

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

[2] 殷人昆. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[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.