教案課程名稱數據結構與算法設計課程代碼總學時64課程負責人任課教師

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