第三單元 特殊的線性表項目四 探索電子排隊預訂功能的實現(xiàn)——隊列的應(yīng)用第一課時 分析問題 ?教材分析本節(jié)的主要內(nèi)容是分析問題。通過以探索電子排隊預訂功能的實現(xiàn)為主線，整個項目分為問題分析、設(shè)計算法和程序?qū)崿F(xiàn)三個部分。本節(jié)課從分析電子排隊預定功能中先來先服務(wù)的思想入手，結(jié)合活動幫助學生理解隊列的概念以及“進隊”“出隊”。通過本節(jié)課的學習能培養(yǎng)學生的信息意識和計算思維能力。?教學目標1.理解隊列的概念和特征；2.理解隊首、隊尾指針的作用；3.理解順序隊列、鏈式隊列存儲的原理和特點；4.能用循環(huán)隊列解決順序隊列可能出現(xiàn)的“假隊滿”和“假隊空”問題；5.培養(yǎng)學生的信息意識和計算思維能力。?教學重點1.理解隊列的概念和特征。2.理解順序隊列、鏈式隊列存儲的原理和特點；?教學難點1.能用循環(huán)隊列解決順序隊列可能出現(xiàn)的“假隊滿”和“假隊空”問題。2.培養(yǎng)學生的信息意識和計算思維能力。?教學方法體驗法、講授法、討論法、示例法?教學準備　　計算機教室、多媒體設(shè)備、多媒體廣播軟件、教學課件、Python編程環(huán)境、學生上機練習的程序文件，預先編制的Python程序文件等。?教學過程一、新課導入日常生活中，商品和服務(wù)需求大于供給的情況時有發(fā)生，例如限量商品發(fā)售、醫(yī)院專家門診號等。為了避免商場、醫(yī)院或營業(yè)廳里人潮擁擠，等候的客戶排起長龍，一些企事業(yè)單位在相應(yīng)網(wǎng)站或手機App上提供了預約服務(wù)，如圖3-1所示?？蛻糨斎肷矸?、賬號信息提交后自動進入電子排隊預訂系統(tǒng)。你知道電子排隊預訂系統(tǒng)是如何實現(xiàn)排隊預約的嗎？    圖3-1電子排隊預訂系統(tǒng) 二、分析問題電子排隊預訂系統(tǒng)是計算機自動控制的排隊系統(tǒng)，排隊的特點是先來先服務(wù)，那計算機是怎么實現(xiàn)自動排隊的呢？當客戶在電子排隊預訂系統(tǒng)提交信息后，客戶的預訂數(shù)據(jù)就進入隊列，稱為進隊(也稱人隊)，即在隊尾(rear)插入個客戶賬號數(shù)據(jù)；當正式購買商品時就到隊列中取出客戶賬號數(shù)據(jù)，稱為出隊，即在隊首(front)取出一個客戶賬號數(shù)據(jù)(客戶賬號數(shù)據(jù)暫用A0001形式替代)，如圖3-2所示。圖3-2預訂一購買隊列用先進先出的數(shù)據(jù)結(jié)構(gòu)來存儲排隊的客戶賬號數(shù)據(jù)，就可以方便地實現(xiàn)先來先服務(wù)，這種數(shù)據(jù)結(jié)構(gòu)稱為隊列。 思考與討論生活中還有其他類似的先進先出的例子嗎？生活中需要排隊的問題，如醫(yī)院掛號看病、加油站排隊加油、小孩子排隊滑滑梯、一隊人過獨木橋等。 核心概念隊列( queue)是一種只允許在表的前端(隊頭)進行刪除操作，而在表的后端(隊尾)進行插入操作的線性表。隊列又稱為先進先出( first in first out,fifo)表。 小貼士隊列是一種操作上受限制的線性表，只允許在隊首和隊尾進行操作。 三、隊列排隊的隊伍在計算機中稱為隊列，隊列是一種只能在表的首端取出數(shù)據(jù)，在表的尾端添加數(shù)據(jù)的線性表，即隊列是操作上有限制的線性表，隊列是一種先進先出數(shù)據(jù)結(jié)構(gòu)。隊列的抽象數(shù)據(jù)類型表示如下：              ADT Queue數(shù)據(jù)對象：D={ ai｜ai ∈ ElemSet,i=1,2,…,n,n>=0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>｜ai-1,ai∈D,i=2,…,n}基本操作:def_init_(self)  #初始化一個空隊列 def QEmpty(self)  #若隊列空，則返回True,否則返回 False        def QLength(self)  #返回隊列的元素個數(shù)        def GetHeac(self)  #返回隊列的隊頭元素        def EnQueue(self.e)  #e元素進隊        def OutQueue(self)  #元素出隊  隊列有兩種存儲方式，一種是用數(shù)組存儲，這種方式存儲的隊列稱為順序隊列；另一種用鏈表存儲，這種方式存儲的隊列稱為鏈隊列，如圖3-4所示。元素插入隊尾稱為進隊隊首元素取出稱為出隊。隊首用front指針指示，隊尾用rear指針指示。圖3-4鏈隊列用數(shù)組存儲隊列元素時，會遇到指針溢出問題。即當隊滿時，再有元素進隊，就會產(chǎn)生指針的溢出(上溢出)；當隊空時，再要取出元素，也會產(chǎn)生指針的溢出(下溢出)。另外，還有“假溢出”問題。隨著元素的進隊和出隊，整個隊列是向數(shù)組下標較大的位置移動。當移動到數(shù)組中下標最大的位置后，隊列空間就用盡了。此時，即使數(shù)組下標較小的位置處還有空閑空間，元素也無法進隊了，這種現(xiàn)象就叫“假溢出”。解決以上問題可以有兩種方法：一是每次隊首元素出隊后面的元素都向前移動一次。但這種做法會使出隊效率較低。另一種方法是采用循環(huán)隊列，即把隊列的首尾相連，當隊尾指針超出數(shù)組長度時，就將其設(shè)回到最初的隊首位置(數(shù)組下標為0)。如圖3-5所示圖中為8個空間的隊列形成的循環(huán)。為了能實現(xiàn)循環(huán)，可以采用指針加1除隊列空間數(shù)后取余，替代指針加1的方法，即rear=(rear+ 1)%size(隊尾指針循環(huán))，front( (front+1)%size(隊首指針循環(huán))，其中，%就是取余運算，size為隊列的空間數(shù)。圖3-5  循環(huán)隊列四、課后活動1.假設(shè)排隊預訂客戶賬號數(shù)據(jù)為A001、A002000、A000下面空的隊列中依次A0001進隊，A0002進隊，A003進隊，叫號出隊，A004進隊，叫號出隊，叫號出隊，叫號出隊，畫出隊列的變化過程。(1)                 (2)                 (3)(4)                  (5)                 (6) 2.請嘗試寫出隊列的抽象數(shù)據(jù)類型定義。 活動答案參考：1.  2. ADTQueue：數(shù)據(jù)對象：D={ai ｜ai, ∈ ElemSet, i=1, 2, 3,…,n, n>=0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>｜ai-1,ai∈D,i=2,…，n}基本操作：           def InitQueue(self)   #建立一個空隊列           def QEmpty(self)   #若空隊列，則返回True,否則返回 Flase           def QLength(self)   #返回隊列的元素個數(shù)            def GetHead(self)   #返回隊列的隊頭元素           def EnQueue(self,e)   #e元素進隊            def OutQueue(self)   #元素出隊       

相關(guān)課件

滬教版（2019）3.程序?qū)崿F(xiàn)評優(yōu)課ppt課件：

這是一份滬教版（2019）3.程序?qū)崿F(xiàn)評優(yōu)課ppt課件，文件包含項目五第三課時pptx、項目五第三課時doc等2份課件配套教學資源，其中PPT共14頁， 歡迎下載使用。

2020-2021學年2.設(shè)計算法優(yōu)質(zhì)ppt課件：

這是一份2020-2021學年2.設(shè)計算法優(yōu)質(zhì)ppt課件，文件包含項目五第二課時pptx、項目五第二課時doc等2份課件配套教學資源，其中PPT共21頁， 歡迎下載使用。

高中信息技術(shù)滬教版（2019）選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.分析問題完美版課件ppt：

這是一份高中信息技術(shù)滬教版（2019）選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.分析問題完美版課件ppt，文件包含項目五第一課時pptx、項目五第一課時doc等2份課件配套教學資源，其中PPT共23頁， 歡迎下載使用。

英語朗讀寶

相關(guān)課件 更多

2021學年3.程序?qū)崿F(xiàn)獲獎ppt課件

2021學年3.程序?qū)崿F(xiàn)獲獎ppt課件
高中信息技術(shù)滬教版（2019）選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2.設(shè)計算法優(yōu)秀ppt課件

高中信息技術(shù)滬教版（2019）選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2.設(shè)計算法優(yōu)秀ppt課件
高中信息技術(shù)滬教版（2019）選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2.設(shè)計算法一等獎?wù)n件ppt

高中信息技術(shù)滬教版（2019）選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2.設(shè)計算法一等獎?wù)n件ppt
信息技術(shù)滬教版（2019）1.問題分析精品ppt課件

信息技術(shù)滬教版（2019）1.問題分析精品ppt課件
資料下載及使用幫助
版權(quán)申訴
版權(quán)申訴
若您為此資料的原創(chuàng)作者，認為該資料內(nèi)容侵犯了您的知識產(chǎn)權(quán)，請掃碼添加我們的相關(guān)工作人員，我們盡可能的保護您的合法權(quán)益。
入駐教習網(wǎng)，可獲得資源免費推廣曝光，還可獲得多重現(xiàn)金獎勵，申請 精品資源制作， 工作室入駐。
版權(quán)申訴二維碼
高中信息技術(shù)滬教版 (2019)選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)電子課本

1. 分析問題

版本： 滬教版 (2019)

年級： 選修1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

切換課文
所有DOC左下方推薦
歡迎來到教習網(wǎng)
  • 900萬優(yōu)選資源，讓備課更輕松
  • 600萬優(yōu)選試題，支持自由組卷
  • 高質(zhì)量可編輯，日均更新2000+
  • 百萬教師選擇，專業(yè)更值得信賴
微信掃碼注冊
qrcode
二維碼已過期
刷新

微信掃碼，快速注冊

手機號注冊
手機號碼

手機號格式錯誤

手機驗證碼 獲取驗證碼

手機驗證碼已經(jīng)成功發(fā)送，5分鐘內(nèi)有效

設(shè)置密碼

6-20個字符，數(shù)字、字母或符號

注冊即視為同意教習網(wǎng)「注冊協(xié)議」及「隱私條款」
QQ注冊
手機號注冊
微信注冊

注冊成功

返回
頂部