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

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

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