數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 教案 -單元3棧和隊列

教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程代碼總學時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元3棧和隊列教學時數(shù)8教學目標AOB1:掌握計算機程序設(shè)計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計算機程序設(shè)計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設(shè)計出適當?shù)乃惴ê统绦?。EOB1:掌握使用搜索引擎、論壇、幫助文檔、課外書籍等方法解決學習中出現(xiàn)的問題；EOB2:能主動閱讀書后拓展知識并進行實驗驗證；EOB3:能獨立分析解決問題，能把自己的想法用代碼實現(xiàn)。教學方式混合式教學評價方式課堂考勤（20%），課堂活動參與程度（20%）線上單元測試（40%）線下課堂教學參與程度（20%）教學資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語言描述），陳媛，清華大學大學出版社2.電腦50臺（含eclips）;3.網(wǎng)絡(luò)學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設(shè)計第一次課（2學時）教學內(nèi)容3.1棧定義：只能在表的一端進行插入和刪除的線性表邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間是一對一的關(guān)系存儲結(jié)構(gòu)：順序存儲或鏈式存儲運算規(guī)則：只能在棧頂運算，且訪問結(jié)點時依照后進先出（LIFO）或先進后出（FILO）的原則基本操作：建棧、判斷棧滿或棧空、入棧、出棧、取棧頂元素值棧的結(jié)構(gòu)棧是僅在表尾進行插入、刪除操作的線性表表尾(即an端)稱為棧頂(top)表頭(即a1端)稱為棧底(bottom)插入元素到棧頂?shù)牟僮?，稱為入棧從棧頂刪除元素的操作，稱為出棧棧的基本操作initStack()：初始化操作。設(shè)置一個空棧isEmpty()：判?？蘸瘮?shù)。若為空棧，函數(shù)值為1，否則為0size()：求棧深函數(shù)。函數(shù)值為棧中當前的元素個數(shù)top()：讀棧頂元函數(shù)。若棧不空，函數(shù)值為棧頂元素，否則為空元素NULLpush(x)：進棧操作。將元素x插入棧中，使x成為棧的棧頂元素pop()：出棧函數(shù)。若棧不空，函數(shù)值為棧頂元素，且從棧中刪除當前棧頂元素，否則函數(shù)值為空元素NULLclear()：棧置空操作。不論棧是否為空棧，置為空棧棧的順序存儲結(jié)構(gòu)（順序棧）利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素棧的鏈式存儲結(jié)構(gòu)（鏈棧）組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂教學重點棧的順序存儲和鏈式存儲教學難點棧的順序存儲和鏈式存儲教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務(wù)2考勤1考勤講授（30分鐘）1.棧的定義（5分鐘）2.棧的基本操作（5分鐘）3.棧的順序存儲（10分鐘）4.棧的鏈式存儲（10分鐘）1.積極回答教師提問2.認真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動代碼實現(xiàn)演示（50分鐘）1.棧的順序存儲代碼實現(xiàn)（25分鐘）2.棧的鏈式存儲代碼實現(xiàn)（25分鐘）1.認真思考、記錄關(guān)鍵內(nèi)容總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第二次課（2學時）教學內(nèi)容技能訓練：棧操作目標：掌握入棧與出棧操作訓練步驟：一、用順序表實現(xiàn)棧1創(chuàng)建棧類，創(chuàng)建數(shù)組，設(shè)定數(shù)組最大值。2創(chuàng)建入棧方法push(){參數(shù)、方法自己寫}3創(chuàng)建出棧方法pop(){方法自己寫}4創(chuàng)建查看棧頂元素的方法getTop(){方法自己寫}5主函數(shù)中證明所有方法在各種正常情況下的正確性，尤其是?？张c棧滿的狀態(tài)。二、用鏈表實現(xiàn)棧1創(chuàng)建棧類，創(chuàng)建鏈表棧。2創(chuàng)建入棧方法push(){參數(shù)、方法自己寫}3創(chuàng)建出棧方法pop(){方法自己寫}4創(chuàng)建查看棧頂元素的方法getTop(){方法自己寫}5主函數(shù)中證明所有方法在各種正常情況下的正確性，尤其是棧空的狀態(tài)。教學重點棧操作的實現(xiàn)教學難點棧操作的實現(xiàn)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤技能訓練（80分鐘）1.布置技能訓練任務(wù)（5分鐘）2.在技能訓練過程中巡視并啟發(fā)學生解決遇到的問題。1.獨立完成老師下發(fā)的課堂練習2.在遇到問題時與同學討論。總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。第三次課（2學時）教學內(nèi)容棧的應(yīng)用1.十進制數(shù)轉(zhuǎn)換成二進制數(shù)把所有的余數(shù)按出現(xiàn)的逆序排列起來（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn)的余數(shù)排在前面）2.單鏈表的逆置3.表達式求值對算術(shù)表達式求值：1+2*4-9/3遵循先乘除后加減、先左后右及先括號內(nèi)，后括號外的四則運算法則，其計算順序應(yīng)為：采用“運算符優(yōu)先數(shù)法”對每種運算符賦于一個優(yōu)先數(shù)：運算符：*/+-#優(yōu)先數(shù)：22110其中#是表達式結(jié)束符表達式求值時，設(shè)立兩個棧運算符棧(OPTR)操作數(shù)棧(OPND)分別存放表達式中的運算符和操作數(shù)4.函數(shù)調(diào)用模塊化程序設(shè)計方法，通過主函數(shù)調(diào)用模塊來解決復(fù)雜的實際問題。由于函數(shù)調(diào)用后，需返回調(diào)用處，所以在調(diào)用時，需用棧記錄斷點的地址以及有關(guān)信息，以便返回。5.地圖四染色問題“四染色”：可以用不多于四色對地圖著色，使相鄰的地區(qū)不重色算法思想：回溯法①從第一號地區(qū)開始逐一染色，每一個地區(qū)逐次用色數(shù)1、2、3、4進行試探。②若當前所取的色數(shù)與周圍已染色的地區(qū)不重色，則用棧記下該地區(qū)的色數(shù)，否則依次用下一色數(shù)進行試探。③若出現(xiàn)用1..4色均與相鄰地區(qū)發(fā)生重色，則需退?；厮?，修改當前棧頂?shù)纳珨?shù)。教學重點棧的應(yīng)用教學難點棧的應(yīng)用教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務(wù)2考勤1考勤講授（80分鐘）1.十進制數(shù)轉(zhuǎn)換成二進制數(shù)（10分鐘）2.單鏈表的逆置（10分鐘）3.表達式求值（25分鐘）4.函數(shù)調(diào)用（10分鐘）5.地圖四染色問題（25分鐘）1.積極回答教師提問2.認真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第四次課（2學時）教學內(nèi)容隊列隊列的定義：只能在表的一端進行插入，在表的另一端進行刪除的線性表邏輯結(jié)構(gòu)：元素之間是一對一的關(guān)系存儲結(jié)構(gòu)：順序隊列和鏈隊列運算規(guī)則：隊尾入隊、隊頭出隊，遵循先進先出（FIFO）的原則基本操作：入隊、出隊、建空隊列、判隊空或隊滿在隊尾插入元素稱為入隊在隊首刪除元素稱為出隊隊列的順序存儲結(jié)構(gòu)隊列的順序存儲，稱為順序隊列由一個存放隊列元素的一維數(shù)組，和隊頭、隊尾“指針”組成。隊列的鏈式存儲結(jié)構(gòu)鏈隊列：隊列的鏈式存儲是單鏈表，同時帶有頭指針和尾指針頭指針指向隊頭結(jié)點尾指針指向隊尾結(jié)點教學重點隊列的順序存儲實現(xiàn)，隊列的鏈式存儲實現(xiàn)教學難點隊列的順序存儲實現(xiàn)，隊列的鏈式存儲實現(xiàn)教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務(wù)2考勤1考勤講授（30分鐘）1.隊列的定義（10分鐘）2.隊列的順序存儲實現(xiàn)（10分鐘）3.隊列的鏈式存儲實現(xiàn)（10分鐘）1.積極回答教師提問2.認真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動代碼實現(xiàn)演示（50分鐘）1.棧的順序存儲代碼實現(xiàn)（25分鐘）2.棧的鏈式存儲代碼實現(xiàn)（25分鐘）1.認真思考、記錄關(guān)鍵內(nèi)容總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)教學效果與反思根據(jù)單元測驗結(jié)果，90%的學生教好掌握了教學內(nèi)容，達成了單元教學目標。其中教學目標AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達