資源簡(jiǎn)介

教學(xué)設(shè)計(jì)
課程基本信息
課題 3.2隊(duì)列
教學(xué)目標(biāo)
1.依據(jù)解決問題的需要，恰當(dāng)?shù)倪x擇數(shù)據(jù)結(jié)構(gòu)隊(duì)列。 2.通過項(xiàng)目的實(shí)踐活動(dòng)，體驗(yàn)用隊(duì)列解決問題的基本流程，逐步形成運(yùn)用隊(duì)列結(jié)構(gòu)解決問題的思維方式和學(xué)科方法。
教學(xué)內(nèi)容
教學(xué)重點(diǎn)： 1.隊(duì)列的應(yīng)用是3.2隊(duì)列的概念、特性及基本操作的延續(xù)，是在學(xué)習(xí)了隊(duì)列相關(guān)的操作的基礎(chǔ)上，在現(xiàn)實(shí)問題中，恰當(dāng)?shù)倪x擇隊(duì)列來解決問題。 2.從實(shí)際問題中,能恰當(dāng)?shù)剡x擇隊(duì)列結(jié)構(gòu)，
教學(xué)難點(diǎn)： 1.抽象與建模、設(shè)計(jì)算法的過程，并用隊(duì)列的基本操作進(jìn)行編程實(shí)現(xiàn)，可以采用教材中提供的“銀行排隊(duì)叫號(hào)系統(tǒng)”實(shí)列，參考教材，逐步體驗(yàn)抽象與建模、設(shè)計(jì)算法、編程實(shí)現(xiàn)等過程。
教學(xué)過程
一、情景導(dǎo)入 ： 【展示生活中的隊(duì)列，以生活隊(duì)列為例進(jìn)行導(dǎo)入】 教師：我們?cè)谏钪腥コ匈?gòu)物、影院取票都需要排隊(duì)。去銀行、醫(yī)院辦理業(yè)務(wù)時(shí)，取號(hào)機(jī)能按照到達(dá)時(shí)間的先后順序，合理地安排辦事次序。這些事件對(duì)數(shù)據(jù)的處理都具有先到先處理的特性，可以使用隊(duì)列來解決。 學(xué)生：看圖片思考生活中的隊(duì)列應(yīng)用 目的：引出本課課例的隊(duì)列內(nèi)容，引發(fā)學(xué)生對(duì)生活中的思考。
二、知識(shí)點(diǎn)講解 【講解清楚隊(duì)列的概念、特性】 教師：隊(duì)列是一種先進(jìn)先出的線性表，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。隊(duì)列元素：就像同學(xué)們按學(xué)號(hào)排隊(duì)，學(xué)號(hào)1是該隊(duì)的隊(duì)首，學(xué)號(hào)6是隊(duì)尾，學(xué)號(hào)1-6都是隊(duì)列元素。隊(duì)列能實(shí)現(xiàn)隊(duì)尾入隊(duì)，隊(duì)首出隊(duì)。 隊(duì)列的第一特性：由概念可知，隊(duì)列具備“先進(jìn)先出、后進(jìn)后出”的特點(diǎn)。出隊(duì)時(shí)，隊(duì)首元素a1優(yōu)先出隊(duì)，緊接著是a2,a3,……,an-1 ，隊(duì)尾元素an最后出隊(duì)。 第二特性是有限序列性，隊(duì)列也是一種線性表結(jié)構(gòu)，元素個(gè)數(shù)是有限的。隊(duì)列可以是空的，也可以包含多個(gè)元素。隊(duì)列中所有元素呈現(xiàn)線性特征，隊(duì)首元素只有一個(gè)后繼點(diǎn)，隊(duì)尾元素只有一個(gè)前驅(qū)點(diǎn)，其他元素既有一個(gè)前驅(qū)點(diǎn)，又有一個(gè)后繼點(diǎn)。 三、課中小練習(xí) 學(xué)生做練習(xí)，老師講解 1. 幼兒園小朋友們排隊(duì)玩滑滑梯，輪流爬上去，再輪流滑下來，此過程用哪種數(shù)據(jù)結(jié)構(gòu)描述最合適（ ） A.鏈表 B.字典 C.字符串 D.隊(duì)列 2.下列事件執(zhí)行過程與隊(duì)列特征不相符的是（ ） A.在汽車加油站排隊(duì)加油時(shí)不允許插隊(duì) B.當(dāng)主機(jī)運(yùn)行速度與打印機(jī)的打印速度不匹配時(shí)，為打印機(jī)設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū) C.把書疊放成一摞，最底下的書要最后才能拿出來 D.CPU分時(shí)系統(tǒng)可以根據(jù)用戶請(qǐng)求，按順序快速運(yùn)行各程序段，實(shí)現(xiàn)多用戶“同時(shí)”工作的假象 四、對(duì)列的基本操作以及基礎(chǔ)代碼講解 教師：接下來，我們一起來學(xué)習(xí)一下隊(duì)列的基本操作。隊(duì)列一般按順序結(jié)構(gòu)存儲(chǔ)，可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，這被稱為鏈隊(duì)列,head紀(jì)錄鏈表的頭節(jié)點(diǎn),tail紀(jì)錄鏈表的隊(duì)尾節(jié)點(diǎn)。 下面隊(duì)列程序的模擬采用數(shù)組來實(shí)現(xiàn)。例如要“A”“B”“C”“D”按順序入隊(duì)、出隊(duì)時(shí)候，可以創(chuàng)建一個(gè)隊(duì)列que，長(zhǎng)度為5，由于操作中隊(duì)首元素和隊(duì)尾元素在數(shù)組que中的位置在改變，因此需要設(shè)置頭指針變量head和尾指針變量tail。python代碼如下。 通過建隊(duì)操作生成好之后，字母“A”“B”“C”“D”可以按順序入隊(duì)的python代碼如下，que[tail] =“A”，A入隊(duì)，tail指針后移準(zhǔn)備下一個(gè)元素入隊(duì)，依次重復(fù)，讓ABCD都入隊(duì)， 注意：tail到達(dá)最大下標(biāo)時(shí)不能再增加，隊(duì)列已滿！ 隊(duì)列中最多存儲(chǔ)n-1個(gè)元素。由此可得，那隊(duì)列為空是什么呢？非常好，head==tail時(shí)候隊(duì)列為空。隊(duì)列已滿的時(shí)候tail指向最后索引值的位置，即tail==n-1；聰明的你肯定發(fā)現(xiàn)了，head記錄隊(duì)首元素所在的位置，tail記錄隊(duì)尾元素的下一個(gè)位置.字母“A”“B”“C”“D”按順序出隊(duì)時(shí)，排在隊(duì)首的元素依次出隊(duì)，head指針變量依次加1，直至head值等于tail值時(shí)，隊(duì)列為空。所以來一起看一下while的條件，11111111111是不是應(yīng)該在這里填上head ！= tail ，表示隊(duì)列非空時(shí)候要循環(huán)做出隊(duì)操作。 五、假溢出引出循環(huán)隊(duì)列以及隊(duì)列個(gè)數(shù)計(jì)算公式推導(dǎo) 教師：根據(jù)上面的操作，我們發(fā)現(xiàn)此時(shí)在順序隊(duì)列中tail=4,已經(jīng)無法在插入數(shù)據(jù)，但實(shí)際上que[0]的數(shù)據(jù)已經(jīng)出隊(duì)，存儲(chǔ)空間可用，這種情況便稱之為“假溢出”。對(duì)于存儲(chǔ)空間有限的情況，可以使用循環(huán)隊(duì)列增加存儲(chǔ)空間的利用率。循環(huán)隊(duì)列就是將隊(duì)列的隊(duì)首和隊(duì)尾連接起來，形成邏輯上的環(huán)狀結(jié)構(gòu)。隊(duì)列為空時(shí)候head==tail，入隊(duì)tail+1，出隊(duì)head+1，循環(huán)隊(duì)列滿的時(shí)候，為了避免隊(duì)空和滿的條件都為head==tail，會(huì)在隊(duì)尾留一個(gè)空閑的數(shù)據(jù)單元，循環(huán)隊(duì)列最多可放n-1個(gè)數(shù)據(jù)元素。 我們來看一個(gè)列表，隊(duì)列中有兩個(gè)元素CD，tail已經(jīng)指向最后一個(gè)位置，若讓順序隊(duì)列在添加一個(gè)元素E，tail就出界報(bào)錯(cuò)，但是在循環(huán)隊(duì)列中E入隊(duì)，tail會(huì)循環(huán)到開頭位置，甚至還能再添加一個(gè)元素F入隊(duì)。循環(huán)隊(duì)列的代碼填空，若要隊(duì)伍未滿的時(shí)候可讓E入隊(duì)，if的條件應(yīng)該怎么填呢？注意看最后這句tail=（tail+1）%n循環(huán)隊(duì)列實(shí)現(xiàn)空間利用需要使用%形成環(huán)，所以當(dāng)head!=(tail+1)%n指的是隊(duì)伍未滿。來看看第二個(gè)填空,若隊(duì)伍非空，說明由元素可以出隊(duì)，head指針移動(dòng)可以參考剛剛?cè)腙?duì)時(shí)候tail的變化。那順序隊(duì)列和循環(huán)隊(duì)列里面怎么根據(jù)head和tail計(jì)算出隊(duì)列里面的元素個(gè)數(shù)呢 首先我們一起來看一下順序隊(duì)列,head=3,tail=6,那個(gè)數(shù)就是3個(gè),所以順序隊(duì)列元素的個(gè)數(shù)就是tail-head個(gè),而循環(huán)結(jié)構(gòu)我們分成兩個(gè)情況,一種是headtail的時(shí)候,來看一個(gè)例子,這個(gè)循環(huán)列表長(zhǎng)度為8,tail=3,head=5,個(gè)數(shù)是6個(gè),我們不難發(fā)現(xiàn)這種情況下個(gè)數(shù)為tail-head+n,所以我們可以一起總結(jié)通用個(gè)數(shù)的公式為(tail-head+n)%n python自帶的隊(duì)列模塊講解 隊(duì)列知識(shí)點(diǎn)復(fù)習(xí) 老師注意可以強(qiáng)化的點(diǎn)： 1. 面對(duì)生活中的問題，如何恰當(dāng)?shù)倪x擇數(shù)據(jù)結(jié)構(gòu)； 2. 面對(duì)問題，如何分析問題、設(shè)計(jì)算法； 3. 在編寫程序時(shí)，如何使用隊(duì)列的入隊(duì)、出隊(duì)等操作。如何從實(shí)際問題中恰當(dāng)?shù)倪x擇數(shù)據(jù)結(jié)構(gòu)，抽象并建模，結(jié)合入隊(duì)、出隊(duì)等操作，設(shè)計(jì)“銀行排隊(duì)系統(tǒng)”的算法。時(shí)間有多的同學(xué)，可以編寫程序，實(shí)現(xiàn)“銀行排隊(duì)系統(tǒng)”的功能。

展開更多......

收起↑