數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 教案全套 蔣理 -單元1-8 緒論 -查找

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

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元1緒論教學時數(shù)4教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；教學方式混合式教學評價方式課堂考勤（20%），課堂活動參與程度（30%）線上單元測試（50%）教學資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語言描述），陳媛，清華大學大學出版社2.電腦50臺（含eclips）;3.網(wǎng)絡學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內(nèi)容課程介紹課程性質(zhì)：專業(yè)知識課程課程學習目標：掌握線性表、棧、隊列、樹和圖的數(shù)據(jù)邏輯組織結(jié)構(gòu)和數(shù)據(jù)存儲結(jié)構(gòu)，了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)。掌握計算機程序設計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法，掌握選擇與排序的處理算法。著力提高理論素養(yǎng)與解決實際問題的能力；基于所學理論知識，學會觀察問題、分析問題和解決問題，將理論知識熟練的運用于編程之中；增強思維能力和創(chuàng)新能力。企業(yè)崗位能力需求：能夠識別、分析、解決軟件編碼、軟件測試、軟件實施與維護等活動中的常見技術問題。具備終身學習意識和自主學習能力。1.1學習數(shù)據(jù)結(jié)構(gòu)的意義計算機的作用數(shù)值計算問題：線性方程，微分方程，線性代數(shù)……非數(shù)值計算問題：電話號碼查詢，計算機對弈，城市間鋪設光纜，數(shù)據(jù)結(jié)構(gòu)的研究對象：非數(shù)值計算領域的程序設計問題問題的操作對象：操作對象之間的關系，在操作對象上面施加的操作算法＋數(shù)據(jù)結(jié)構(gòu)＝程序1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)(data)：信息的載體，是對客觀事物的符號表示，能夠被計算機識別、存儲和加工處理。圖像、聲音、視頻等都可通過編碼由計算機處理，因此也屬于數(shù)據(jù)的范疇數(shù)據(jù)元素(dataelement)：數(shù)據(jù)的基本單位,也稱為元素、結(jié)點或記錄。數(shù)據(jù)元素可由若干個數(shù)據(jù)項（字段、域）構(gòu)成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位數(shù)據(jù)對象：數(shù)據(jù)的子集，具有相同性質(zhì)的數(shù)據(jù)元素的集合數(shù)據(jù)的結(jié)構(gòu)：數(shù)據(jù)元素的集合中，元素相互之間的關系邏輯結(jié)構(gòu)：集合,線性結(jié)構(gòu),樹型結(jié)構(gòu),圖狀結(jié)構(gòu)物理結(jié)構(gòu)：順序，鏈接，索引，散列數(shù)據(jù)結(jié)構(gòu)的形式：Data_Structures=(D,S)D是數(shù)據(jù)元素的有限集，S是D上關系的有限集關系用序偶表示:<ai,aj>或(ai,aj)ai稱為前驅(qū)或弧尾，aj稱為后續(xù)或弧頭例：某公司有1名經(jīng)理(M)，2個部門經(jīng)理(D)，每個部門各有3名職員(E)。人員之間的關系是：經(jīng)理指導部門經(jīng)理的工作，部門經(jīng)理指導職員的工作。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<M,D1>,<M,D2>,<D1,E11>,<D1,E12>…<D２,E23>}例：某公司有1名經(jīng)理，2個部門經(jīng)理，每個部門各有3名職員。人員之間的關系是：按人員年齡從大到小排列。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<D1,M>,<M,E11>,<E11,E21>,<E21,E12>…<E22,E23>}例：某公司有1名經(jīng)理，2個部門經(jīng)理，每個部門各有3名職員。人員之間的關系是：人員之間的友好關系。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={(M,D1),(M,D2),(D1,D2),(D2,E12)…(D２,E22)}數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器中的映象數(shù)據(jù)元素的存儲：用二進制位(bit)的位串表示數(shù)據(jù)元素關系的存儲順序存儲結(jié)構(gòu)：用元素之間存儲的相對位置表示關系鏈式存儲結(jié)構(gòu)：用存儲元素的引用（指針）表示關系教學重點數(shù)據(jù)結(jié)構(gòu)的基本概念教學難點數(shù)據(jù)結(jié)構(gòu)的基本概念教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務2考勤1考勤課程引入（10分鐘）課程介紹認真思考、記錄關鍵內(nèi)容講授和課堂練習（70分鐘）1.學習數(shù)據(jù)結(jié)構(gòu)的意義（10分鐘）2.非數(shù)值結(jié)算舉例（15分鐘）3.數(shù)據(jù)結(jié)構(gòu)的基本概念（20分鐘）4．數(shù)據(jù)結(jié)構(gòu)的形式定義舉例。（15分鐘）5.數(shù)據(jù)的存儲結(jié)構(gòu)。（10分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務第二次課（2學時）教學內(nèi)容1.3算法算法(Algorithm)：對特定問題求解步驟的一種描述，是指令的有限序列算法的特性：可執(zhí)行性、有窮性、確定性、輸入、輸出算法的描述方法：自然語言、程序設計語言、類程序設計語言、流程圖算法的設計原則算法應當滿足具體問題的需求正確性，四個層次：1.不含語法錯誤。2.對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果3.對于精心選擇的、典型、苛刻、帶有刁難性的幾組輸入數(shù)據(jù)，能夠得出滿足要求的結(jié)果。4.對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果健壯性：當輸入數(shù)據(jù)非法時，算法能適當?shù)刈龀龇磻粫a(chǎn)生出錯的結(jié)果或信息，不會導致程序執(zhí)行終斷可讀性：算法要方便閱讀和交流評價算法的指標：執(zhí)行需要占用多少機器資源時間資源;算法運行時花費的時間代價空間資源:程序中使用的數(shù)據(jù)結(jié)構(gòu)占用的空間代價算法執(zhí)行時間相關的因素事后統(tǒng)計法事前估算法:算法的策略、問題的規(guī)模、書寫程序的語言、編譯程序產(chǎn)生的機器代碼的質(zhì)量、機器執(zhí)行指令的速度算法的時間復雜性分析算法耗費的時間：1.算法中所有語句執(zhí)行時間之和。2.語句的執(zhí)行時間：該語句的頻度(語句重復執(zhí)行的次數(shù))，與該語句執(zhí)行一次所需時間的乘積。算法時間取決于控制結(jié)構(gòu)和原操作的綜合效果f(n)是算法中頻度最大的語句頻度，通常是最深層循環(huán)內(nèi)的原操作執(zhí)行的次數(shù)。隨著n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同。算法時間復雜度記作：T(n)=O(f(n))舉例：課堂練習：常見函數(shù)比較：通常有如下的函數(shù)關系：c<log2n<n<nlog2n<n2<n3<2n指數(shù)時間的關系為：O(2n)<O(n!)<O(nn)算法的時間復雜度不僅是問題規(guī)模n的函數(shù)，還與所處理的數(shù)據(jù)集有關。全面分析算法，需考慮它在最壞情況下的代價、最好情況下的代價和平均情況下的代價。算法的空間復雜度：S(n)=O(g(n))隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同算法所需的存儲量：輸入數(shù)據(jù)所占空間，程序本身所占空間，輔助變量所占空間教學重點算法教學難點時間復雜度分析教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授和課堂練習（80分鐘）1.算法的概念（10分鐘）2.算法的設計原則（10分鐘）3.評價算法的指標（10分鐘）4.算法的時間復雜性分析（20分鐘）5.算法的時間復雜性分析課堂練習（20分鐘）6.算法的空間復雜度（10分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動4.積極完成課堂練習總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。教學效果與反思根據(jù)單元測驗結(jié)果，90%的學生教好掌握了教學內(nèi)容，達成了單元教學目標。其中教學目標AOB1、AOB3達成情況較好，但BOB1達成情況一般。結(jié)合學生的課堂練習，在線測試等教學活動的結(jié)果來看，課堂出勤比較好，沒有缺課的情況；課堂練習獨立完成，但允許相互討論，掌握情況比較好；在線測試內(nèi)容有時間限制，有一部分內(nèi)容需要課后閱讀教材和查閱相關材料，所以對平時學習習慣不好的少部分同學有一定難度，所以會出現(xiàn)問題。教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設計課程代碼總學時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元2線性表教學時數(shù)10教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計算機程序設計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設計出適當?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)絡學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內(nèi)容2.1線性表的定義線性表：n(n≥0)個具有相同特性的數(shù)據(jù)元素的有限序列，n表示線性表的長度，即數(shù)據(jù)元素的個數(shù)，n=0時表為空表，n>0時記為:（a1，a2，…ai-1，ai，ai+1，…an）基本特征：有且只有一個第一元素，且只有一個最后元素。除第一元素之外，其它元素都有唯一的直接前趨。除最后元素之外，其它元素都有唯一的直接后繼線性表舉例：數(shù)據(jù)元素在不同問題中的含義各不相同，可以是一個數(shù)、一個符號，一個記錄，或其它復雜的信息數(shù)據(jù)元素是每一個學生的信息，包括：學號、姓名、成績共三個數(shù)據(jù)項線性表的運算初始化線性表，表置空，求線性表中第i個元素，查找滿足給定條件的數(shù)據(jù)元素，在線性表的第i個位置之前插入一個新的數(shù)據(jù)元素，刪除線性表中的第i個數(shù)據(jù)元素，查找表中第i個元素的前驅(qū)，查找表中第i個元素的后繼2.2線性表的順序存儲順序存儲：在內(nèi)存中開辟連續(xù)的存儲空間，用連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素順序表：順序存儲的線性表特點：邏輯上相鄰的數(shù)據(jù)元素，其物理位置也相鄰。利用物理位置上的關系，反映元素的邏輯關系順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點：靜態(tài)操作容易實現(xiàn)。根據(jù)定位公式容易確定表中元素的存儲位置，元素隨機存取缺點：1.動態(tài)操作實現(xiàn)效率較低，插入和刪除結(jié)點困難，擴展不靈活，容易造成空間浪費。2.建表時，若估計不到表的最大長度，就難以確定分配的空間，影響數(shù)據(jù)擴展，分配的空間過大，則會造成預留空間浪費教學重點線性表的順序存儲教學難點線性表的順序存儲教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務2考勤1考勤講授（50分鐘）1.線性表的定義（10分鐘）2.線性表舉例（10分鐘）3.線性表的順序存儲（15分鐘）4.順序存儲結(jié)構(gòu)的優(yōu)缺點（15分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動代碼實現(xiàn)演示（30分鐘）1.順序表運算代碼實現(xiàn)1.認真思考、記錄關鍵內(nèi)容總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務第二次課（2學時）教學內(nèi)容技能訓練：順序表操作目標：掌握順序表的數(shù)據(jù)插入與刪除方法訓練步驟：1創(chuàng)建線性表String[]strList自己設定長度。2創(chuàng)建方法add（intindex,Stringstr）{方法自己寫}//用于向strList的index位置插入str。3創(chuàng)建方法addInHead（Stringstr）{方法自己寫}//用于向strList的頭部插入str。4創(chuàng)建方法addInTail（Stringstr）{方法自己寫}//用于向strList的尾部插入str。5創(chuàng)建方法addByString（Stringstr1,Stringstr2）{方法自己寫}//用于向strList中第一個str1前插入str2。6創(chuàng)建方法delete（intindex）{方法自己寫}//用于將strList的index位置元素刪除（后面的元素依次遞補）。7創(chuàng)建方法deleteByString（Stringstr）{方法自己寫}//用于將strList的所有str元素刪除（后面的元素依次遞補）。8創(chuàng)建方法display（）{方法自己寫}//用于顯示strList的所有元素。9主函數(shù)中證明所有方法在各種正常情況下的正確性。教學重點順序表操作的實現(xiàn)教學難點順序表操作的實現(xiàn)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤技能訓練（80分鐘）1.布置技能訓練任務（5分鐘）2.在技能訓練過程中巡視并啟發(fā)學生解決遇到的問題。1.獨立完成老師下發(fā)的課堂練習2.在遇到問題時與同學討論。總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第三次課（2學時）教學內(nèi)容2.3線性表的鏈式存儲結(jié)構(gòu)鏈表：以鏈式結(jié)構(gòu)存儲的線性表。用一組在物理位置上任意的存儲單元來存儲線性表的結(jié)點。存儲單元可以是相鄰的，也可以是不相鄰的。物理位置上的關系不能反映結(jié)點間的邏輯關系鏈式存儲結(jié)構(gòu)的特點用任意位置的存儲單元存儲線性表的數(shù)據(jù)元素。結(jié)點間的邏輯關系借助結(jié)點中的指針(引用)實現(xiàn)。每個數(shù)據(jù)元素，除存儲本身信息外，還需存儲其直接后繼的信息。結(jié)點 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置單鏈表：鏈表中，每個結(jié)點只包含一個指針域結(jié)點的代碼結(jié)構(gòu)：publicclassSinNode{//SinNode為結(jié)點類型publicObjectdata;publicSinNodenext;}雙向鏈表：每一個結(jié)點中有兩個指針域。一個指向直接后繼，一個指向直接前趨結(jié)點的代碼結(jié)構(gòu)：publicclassDulNode{Objectdata;DulNodenext;DulNodeprior;}順序存儲與鏈式存儲的比較從時間角度：在按位置查找數(shù)據(jù)、查找元素的前趨和后繼方面，順序存儲有較大優(yōu)勢。在插入數(shù)據(jù)、刪除數(shù)據(jù)時，鏈式存儲有較大的優(yōu)勢。從空間角度：順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須規(guī)定其存儲規(guī)模。動態(tài)鏈表的存儲空間是動態(tài)分配的，只要內(nèi)存空間有空閑，就不會產(chǎn)生溢出。教學重點線性表的鏈式存儲結(jié)構(gòu)教學難點線性表的鏈式存儲結(jié)構(gòu)教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務2考勤1考勤講授（40分鐘）1.線性表的鏈式存儲結(jié)構(gòu)（10分鐘）2.鏈式存儲結(jié)構(gòu)的特點（5分鐘）3.單鏈表（10分鐘）4.雙向鏈表（10分鐘）5.順序存儲與鏈式存儲的比較（5分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動代碼實現(xiàn)演示（40分鐘）1.單向鏈表的代碼實現(xiàn)（20分鐘）2.雙向鏈表的代碼實現(xiàn)（20分鐘）1.認真思考、記錄關鍵內(nèi)容總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務第四次課（2學時）教學內(nèi)容技能訓練-鏈表操作目標：掌握鏈表的數(shù)據(jù)插入與刪除方法訓練步驟：1創(chuàng)建節(jié)點Node類，包含Stringstr；Nodenext；NodePrior；創(chuàng)建鏈表類（類名自己寫），創(chuàng)建雙向鏈表strList2創(chuàng)建方法add（intindex,Stringstr）{方法自己寫}//用于向strList的index位置插入str。3創(chuàng)建方法addInHead（Stringstr）{方法自己寫}//用于向strList的頭部插入str。4創(chuàng)建方法addInTail（Stringstr）{方法自己寫}//用于向strList的尾部插入str。5創(chuàng)建方法addByString（Stringstr1,Stringstr2）{方法自己寫}//用于向strList中第一個str1前插入str2。6創(chuàng)建方法deleteByIndex（intindex）{方法自己寫}//用于將strList的index位置元素刪除。7創(chuàng)建方法deleteByString（Stringstr）{方法自己寫}//用于將strList的所有str元素刪除。8創(chuàng)建方法display（）{方法自己寫}//用于顯示strList的所有元素。9主函數(shù)中證明所有方法在各種正常情況下的正確性。教學重點鏈表操作的實現(xiàn)教學難點鏈表操作的實現(xiàn)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤技能訓練（80分鐘）1.布置技能訓練任務（5分鐘）2.在技能訓練過程中巡視并啟發(fā)學生解決遇到的問題。1.獨立完成老師下發(fā)的課堂練習2.在遇到問題時與同學討論?？偨Y(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第五次課（2學時）教學內(nèi)容2.4線性表的應用1.有序單鏈表的合并：一元多項式求和2.稀疏矩陣的三元組表示法3.稀疏矩陣的十字鏈表表示法循環(huán)鏈表應用-約瑟夫環(huán)問題約瑟夫，是一個古猶太人，曾經(jīng)在一次羅馬叛亂中擔任將軍，后來戰(zhàn)敗，他和朋友及另外39個人躲在一口井里，但還是被發(fā)現(xiàn)了。羅馬人表示只要投降就不死，約瑟夫想投降，可是其他人堅決不同意。怎么辦呢，他想到一個主意：讓41個人圍成一個圓圈，從第一個人開始報數(shù)，數(shù)到3的那個人被旁邊的人殺死。這樣就可以避免自殺了，因為猶太人的信仰是禁止自殺的。結(jié)果一群人殺來殺去最后只剩下兩個了，就是約瑟夫和他朋友，于是兩人愉快地去投降了。問題：約瑟夫和朋友站在什么位置才保住了性命。請用循環(huán)鏈表實現(xiàn)過程（報數(shù)，移除圈），并輸出結(jié)果（幸存者的位置）。教學重點線性表的應用教學難點線性表的應用教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務2考勤1考勤講授（30分鐘）1.線性表的應用1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動技能訓練（50分鐘）1.布置技能訓練任務（5分鐘）2.在技能訓練過程中巡視并啟發(fā)學生解決遇到的問題。1.獨立完成老師下發(fā)的課堂練習2.在遇到問題時與同學討論?？偨Y(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務教學效果與反思根據(jù)單元測驗結(jié)果，90%的學生教好掌握了教學內(nèi)容，達成了單元教學目標。其中教學目標AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達成情況較好，但EOB1、EOB3達成情況一般。結(jié)合學生的課堂練習，在線測試等教學活動的結(jié)果來看，課堂出勤比較好，沒有缺課的情況；課堂練習獨立完成，但允許相互討論，掌握情況比較好；技能訓練課堂實現(xiàn)情況一般，部分學生需要課后另花時間完成。教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設計課程代碼總學時64課程負責人任課教師

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

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元4遞歸教學時數(shù)4教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；EOB1:掌握使用搜索引擎、論壇、幫助文檔、課外書籍等方法解決學習中出現(xiàn)的問題；教學方式混合式教學評價方式課堂考勤（20%），課堂活動參與程度（30%）線下課堂教學參與程度（50%）教學資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語言描述），陳媛，清華大學大學出版社2.電腦50臺（含eclips）;3.網(wǎng)絡學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內(nèi)容4.1遞歸的概念若一個對象部分地包含它自己，或用它自己給自己定義，則稱這個對象是遞歸的。若一個過程直接地或間接地調(diào)用自己，則稱這個過程是遞歸的過程。4.2遞歸設計：遞歸問題，必須符合以下三個條件可以把一個問題轉(zhuǎn)化為一個新的問題，這個新的問題的解決方法與原問題的解法相同，只是所處理的對象有所不同；可以通過轉(zhuǎn)化過程使問題得到簡化；要有明確的結(jié)束遞歸的條件，否則遞歸將會無止境地進行下去，直到耗盡系統(tǒng)資源，必須要有終止遞歸的條件。適用遞歸解決的問題1.定義是遞歸的2.數(shù)據(jù)結(jié)構(gòu)是遞歸的3.問題的解法是遞歸的遞歸的執(zhí)行過程遞歸設計步驟1.對原問題f(s)進行分析，假設出合理的“較小問題”f(s’)；2.假設f(s’)是可解的，在此基礎上確定f(s)的解，即給出f(s)與f(s’)的關系；3.確定特定情況，即（f(1)或f(0)）的解，由此作為遞歸出口。教學重點遞歸設計教學難點遞歸設計教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1平臺發(fā)布任務2考勤1考勤講授（80分鐘）1.遞歸的概念（10分鐘）2.遞歸設計（5分鐘）3.適用遞歸解決的問題（50分鐘）4.遞歸的執(zhí)行過程（10分鐘）5.遞歸設計步驟（5分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務第二次課（2學時）教學內(nèi)容遞歸的評價遞歸的優(yōu)點：可解決復雜問題；可縮短程序代碼、提高編程效率遞歸的缺點：不能提高程序的運行效率遞歸運行效率問題斐波那契數(shù)列的遞歸調(diào)用樹遞歸與回溯回溯法是從問題的某一種可能出發(fā)，搜索從這種情況出發(fā)所能達到的所有可能。當這一條路走到“盡頭”的時候，再倒回上一節(jié)點，從另一個可能出發(fā)，繼續(xù)搜索?；厮菔且环N思想，遞歸是一種解決問題的方法?；厮菘梢杂眠f歸來實現(xiàn)，也可以不用遞歸實現(xiàn)。迷宮問題迷宮中設置很多隔壁，對前進方向形成了多處障礙。假設迷宮的每個岔路口只有東南西北四個方向或是這四個方向的子集。回溯法思想：一種不斷試探且及時糾正錯誤的搜索方法。；從入口出發(fā)，按某一方向向前探索，若某處可以到達，則到達新起點；否則試探下一方向。；若所有的方向均沒有通路，則沿原路返回到前一點，換下一個方向再繼續(xù)試探，直到所有可能的通路都試探到。；結(jié)果是或找到一條通路，或無路可走又返回到入口點。遞歸實現(xiàn)：從入口出發(fā)，每到一個結(jié)點（岔路口），按東南西北的秩序訪問相應方向的下一個結(jié)點，如果相應方向沒有可以訪問的結(jié)點，則訪問下一個方向。如果四個方向全被訪問完，則返回到前一個結(jié)點。直到找到出口或回到入口。遞歸的關鍵問題為防止遞歸的無休止調(diào)用，在遞歸函數(shù)中要及時返回，這是結(jié)束條件的作用；在所有的遞歸函數(shù)中都有一個終止遞歸的條件判斷；遞歸函數(shù)可以簡化程序，但一般不能提高程序的執(zhí)行效率。教學重點遞歸的評價教學難點遞歸的評價教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1.平臺發(fā)布任務2.考勤1.考勤講授（60分鐘）1.遞歸的評價（10分鐘）2.遞歸運行效率問題（15分鐘）3.遞歸與回溯（15分鐘）4.迷宮問題（15分鐘）5.遞歸的關鍵（5分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動代碼實現(xiàn)演示（20分鐘）1.斐波那契數(shù)列的遞歸調(diào)用樹的代碼實現(xiàn)（20分鐘）1.認真思考、記錄關鍵內(nèi)容總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務教學效果與反思根據(jù)單元測驗結(jié)果，80%的學生教好掌握了教學內(nèi)容，達成了單元教學目標。其中教學目標AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達成情況較好，但EOB1、EOB3達成情況一般。結(jié)合學生的課堂練習，在線測試等教學活動的結(jié)果來看，課堂出勤比較好，沒有缺課的情況；課堂練習獨立完成，但允許相互討論，掌握情況比較好；技能訓練課堂實現(xiàn)情況一般，部分學生需要課后另花時間完成。在線測試內(nèi)容有時間限制，有一部分內(nèi)容需要課后閱讀教材和查閱相關材料，所以對平時學習習慣不好的少部分同學有一定難度，所以會出現(xiàn)問題。教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設計課程代碼總學時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元5樹教學時數(shù)10教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計算機程序設計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設計出適當?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)絡學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內(nèi)容5.1普通樹定義：樹是由n（n≥0）個結(jié)點組成的有限集合，當n＝0時稱為空樹；否則，在任一非空樹中必有一個稱為根的結(jié)點；當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,……Tm；其中每一個集合本身又是一棵樹，稱為根的子樹特點：非空樹中至少有一個根結(jié)點；樹中各子樹是互不相交的集合樹的表示樹的基本術語結(jié)點：樹中的元素，包括數(shù)據(jù)項及若干指向子樹的分支結(jié)點的度：結(jié)點擁有的子樹數(shù)葉子：度為0的結(jié)點，也叫終端結(jié)點分支結(jié)點：度不為0的結(jié)點，也叫非終端結(jié)點內(nèi)部結(jié)點：除根結(jié)點之外，分支結(jié)點也稱為內(nèi)部結(jié)點孩子：結(jié)點子樹的根稱為該結(jié)點的孩子雙親：孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親兄弟：同一雙親的孩子之間互成為兄弟祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點子孫：子樹中的任一結(jié)點都是該結(jié)點的子孫樹的度：一棵樹中最大的結(jié)點度數(shù)結(jié)點的層次：從根結(jié)點算起，根為第一層，它的孩子為第二層……堂兄弟：其雙親在同一層的結(jié)點互稱為堂兄弟深度：樹中結(jié)點的最大層次數(shù)有序樹：樹中結(jié)點的各子樹從左至右是有序的，最左邊的子樹的根稱為第一個孩子，最右邊的稱為最后一個孩子森林：m棵互不相交的樹的集合樹的邏輯特征縱向關系：祖先與子孫是縱向次序；任一結(jié)點都可以有零個或多個直接后繼結(jié)點；但至多只有一個直接前趨結(jié)點；葉結(jié)點無后繼；根結(jié)點無前趨橫向關系有序樹中，若k1和k2是兄弟，且k1在k2的左邊，則k1的任一子孫都在k2的任一子孫的左邊教學重點樹的基本術語教學難點無教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1.平臺發(fā)布任務2.考勤1.考勤講授（60分鐘）1.樹的定義（10分鐘）2.樹的表示（10分鐘）3.樹的基本術語（30分鐘）4.樹的邏輯特征（10分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（20分鐘）1.樹形結(jié)構(gòu)（5分鐘）2.樹的基本術語（15分鐘）1.認真思考2.積極回答問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習過程中出現(xiàn)的，問題。2.布置課后任務1.思考教師總結(jié)2.記錄課后任務第二次課（2學時）教學內(nèi)容二叉樹定義：二叉樹是結(jié)點的有限集合，或者是空樹，或者由一個根結(jié)點和兩棵二叉子樹構(gòu)成。左子樹，右子樹，子樹不相交特點：每個結(jié)點至多有二棵子樹；不存在度大于2的結(jié)點；子樹有左、右之分，次序不能任意顛倒?jié)M二叉樹深度為k的滿二叉樹，有2k-1個結(jié)點；2k-1是深度為K的二叉樹所具有的最大結(jié)點個數(shù)特點：每層上的結(jié)點數(shù)都達到最大值；只有度為0的結(jié)點和度為2的結(jié)點；每個結(jié)點均有兩棵高度相同的子樹；葉子結(jié)點都在樹的最下面一層上完全二叉樹葉子結(jié)點只出現(xiàn)在最低兩層上；對任意結(jié)點，若其右分支下的子孫最大層次為L，則其左分支下的子孫的最大層次為L或L+1；除最低層外，每一層上的結(jié)點數(shù)均達到最大值；在最低層上只缺少右邊的若干結(jié)點(也可不缺)。二叉樹的性質(zhì)性質(zhì)1：在二叉樹第i層上至多有2i-1個結(jié)點(i≥1)證明：當i=1時，只有一個根結(jié)點。顯然，2i-1＝20＝１是對的。假設對所有的j(1≤j﹤i)，命題成立。即第j層上至多有2j-1個結(jié)點，那么可以證明j=i時命題成立。歸納假設：第i-1層上至多有2i-2個結(jié)點。由于二叉樹的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2*2i-2＝2i-1。性質(zhì)2：深度為k的二叉樹至多有2k-１個結(jié)點(k≥1)證明：由性質(zhì)１可見，深度為k的二叉樹的最大結(jié)點數(shù)為：性質(zhì)3：對任意二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2,則n0=n2+1。證明：二叉樹中結(jié)點總數(shù)為：n=n0+n1+n2 (5-1)二叉樹的分支數(shù)為：n1+2*n2 (5-2)因此，結(jié)點總數(shù)為：n=n1+2*n2+1由(5-1)、(5-2)兩式可得：n0=n2+1性質(zhì)5：對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序號編號(從第1層到log2n+1層，每層從左到右)，則對任一結(jié)點i(1≤i≤n)，有：如果i=1，則結(jié)點i是根結(jié)點，無雙親，否則，其雙親結(jié)點為：i/2如果2i>n，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點);否則其左孩子是結(jié)點2i如果2i+1>n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1二叉樹的存儲順序存儲：將任意二叉樹“修補”成完全二叉樹；利用順序表對數(shù)據(jù)元素進行存儲；原二叉樹中空缺的結(jié)點在數(shù)組中相應單元置空。鏈式存儲：二叉鏈表：結(jié)點包含3個域：數(shù)據(jù)域和指向左、右子樹的指針域二叉樹的遍歷遍歷：按一定的規(guī)則和次序走遍二叉樹的所有結(jié)點；使每個結(jié)點都被訪問一次，且只被訪問一次，對結(jié)點進行各種操作遍歷二叉樹的目的：遍歷是對數(shù)據(jù)進行操作的基礎；得到二叉樹中各結(jié)點的一種線性順序；使非線性的二叉樹線性化，簡化有關的運算和處理先序遍歷，中序遍歷，后序遍歷線索二叉樹線索：指向前驅(qū)或后繼結(jié)點的指針稱為線索線索二叉樹：加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹教學重點二叉樹的遍歷教學難點二叉樹的性質(zhì)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（60分鐘）1.二叉樹樹的定義（10分鐘）2.二叉樹的性質(zhì)（20分鐘）3.二叉樹的存儲（10分鐘）4.二叉樹的遍歷（20分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（20分鐘）1.完全二叉樹（5分鐘）2.二叉樹的遍歷（15分鐘）1.認真思考2.積極回答問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第三次課（2學時）教學內(nèi)容技能訓練-二叉樹遍歷1.創(chuàng)建二叉樹結(jié)點類2.建立鏈式存儲二叉樹，結(jié)構(gòu)如圖。3.實現(xiàn)先序遍歷方法。4.實現(xiàn)中序遍歷方法。5.實現(xiàn)后序遍歷方法。6.測試代碼，核驗結(jié)果。教學重點二叉樹遍歷的代碼實現(xiàn)教學難點二叉樹遍歷的代碼實現(xiàn)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤技能訓練（80分鐘）1.布置技能訓練任務（5分鐘）2.在技能訓練過程中巡視并啟發(fā)學生解決遇到的問題。1.獨立完成老師下發(fā)的課堂練習2.在遇到問題時與同學討論?？偨Y(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第四次課（2學時）教學內(nèi)容5.3樹與二叉樹樹的存儲結(jié)構(gòu)二叉樹與樹的相互轉(zhuǎn)換樹轉(zhuǎn)二叉樹①加線：在兄弟之間加一連線②抹線：對每個結(jié)點，除了其第一孩子外，去除其與其余孩子之間的關系③旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整棵樹順時針轉(zhuǎn)45°二叉樹轉(zhuǎn)樹①加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來②抹線：抹掉原二叉樹中雙親與右孩子之間的連線③調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)森林轉(zhuǎn)二叉樹①將各棵樹分別轉(zhuǎn)換成二叉樹②將每棵樹的根結(jié)點用線相連③以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)二叉樹轉(zhuǎn)森林①抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹②還原：將孤立的二叉樹還原成樹樹的遍歷先序遍歷(與對應的二叉樹先序遍歷序列一致)。若樹非空，則：訪問根結(jié)點；依次先序遍歷根的各個子樹。后序遍歷(與對應的二叉樹中序遍歷序列一致)。若樹非空，則：依次后序遍歷根的各個子樹；訪問根結(jié)點層次遍歷：若樹非空，訪問根結(jié)點。若第1，…i(i≥1)層結(jié)點已被訪問，且第i+1層結(jié)點尚未訪問，則從左到右依次訪問第i+1層。教學重點樹與二叉樹轉(zhuǎn)換，二叉樹與森林轉(zhuǎn)換教學難點樹與二叉樹轉(zhuǎn)換，二叉樹與森林轉(zhuǎn)換教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（60分鐘）1.樹的存儲結(jié)構(gòu)（10分鐘）2.樹與二叉樹轉(zhuǎn)換（15分鐘）3.二叉樹與森林轉(zhuǎn)換（20分鐘）4.樹的遍歷（10分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（25分鐘）1.樹轉(zhuǎn)二叉樹（5分鐘）2.二叉樹轉(zhuǎn)森林（5分鐘）3.森林轉(zhuǎn)二叉樹（5分鐘）4.樹的遍歷（10分鐘）1.認真思考2.積極回答問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第五次課（2學時）教學內(nèi)容5.4哈夫曼樹哈夫曼樹相關概念路徑：若樹中存在某個結(jié)點序列k1,k2,…,kj，滿足Ki是ki+1的雙親，則該結(jié)點序列是樹上的一條路徑，路徑自上而下地經(jīng)過了樹上的每一條邊路徑長度：路徑經(jīng)過的邊數(shù)，稱為路徑長度樹的路徑長度：從樹根到樹中每一個結(jié)點的路徑長度之和，完全二叉樹的路徑長度最短結(jié)點的權(quán)：給樹的結(jié)點賦以一定意義的數(shù)值，稱為結(jié)點的權(quán)結(jié)點的帶權(quán)路徑長度：從樹根到某結(jié)點的路徑長度與該結(jié)點的權(quán)的積樹的帶權(quán)路徑長度（WPL）：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和哈夫曼樹：由n個帶權(quán)葉子結(jié)點構(gòu)成的二叉樹具有不同形態(tài)，其中帶權(quán)路徑長度（WPL）最小的二叉樹，又叫最優(yōu)二叉樹或最佳判定樹構(gòu)造哈夫曼樹的方法，哈夫曼算法：根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點的二叉樹，令其權(quán)值為分別wj；在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹；置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和；在森林中刪除這兩棵樹，并將新得到的二叉樹加入森林中；重復上述步驟，直到只含一棵樹為止，這棵樹即哈夫曼樹。哈夫曼樹的應用最佳判定樹哈夫曼編碼電報通訊中，電文以二進制的0,1序列傳送，發(fā)送端將電文中的字符轉(zhuǎn)換成0,1的二進制序列，接收端將收到的0,1序列轉(zhuǎn)換成對應的字符序列(譯碼)假定電文是英文，電文字符串由26個英文字母組成，需要編碼的字符集是{A,B,C,D,…,Z}方法一：等長的二進制編碼方法二：不等長的二進制編碼前綴碼：任一字符的編碼，不能是其他字符的前綴。假設字符集D={d1,d2,d3,…,dn}，每個字符di的編碼長度為li，每個字符di在電文中出現(xiàn)的次數(shù)是ci，則電文的總長度為:∑ci*li。每個字符di在電文中出現(xiàn)頻度的概率是wi，每個字符di的編碼長度為li，則電文的平均總長度為:∑wi*li尋找最優(yōu)前綴碼的方法用d1,d2,d3,…,dn作為葉子結(jié)點，用w1,w2,w3,…,wn作為葉子結(jié)點的權(quán)，構(gòu)造最優(yōu)二叉樹，將樹中每個結(jié)點的左分支置為0，右分支置為1，從根到葉子結(jié)點的一個標號序列，就是該葉子結(jié)點的編碼。例：設組成電文的字符集D及其概率分布如下：D={a,b,c,d,e}

W={0.12,0.40,0.15,0.08,0.25}教學重點哈夫曼算法教學難點哈夫曼樹的應用教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（65分鐘）1.哈夫曼樹的概念（10分鐘）2.哈夫曼算法（20分鐘）3.哈夫曼樹的應用（35分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（15分鐘）1.哈夫曼樹的構(gòu)造與相關計算（15分鐘）1.認真思考2.積極回答問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。教學效果與反思根據(jù)單元測驗結(jié)果，80%的學生教好掌握了教學內(nèi)容，達成了單元教學目標。其中教學目標AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達成情況較好，但EOB1、EOB3達成情況一般。結(jié)合學生的課堂練習，在線測試等教學活動的結(jié)果來看，課堂出勤比較好，個別學生有缺課的情況；課堂練習獨立完成，但允許相互討論，掌握情況比較好；技能訓練課堂實現(xiàn)情況一般，部分學生需要課后另花時間完成。在線測試內(nèi)容有時間限制，有一部分內(nèi)容需要課后閱讀教材和查閱相關材料，所以對平時學習習慣不好的少部分同學有一定難度，所以會出現(xiàn)問題。樹的操作需要經(jīng)過課后編程消化思想。教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設計課程代碼總學時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元6圖教學時數(shù)10教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計算機程序設計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設計出適當?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)絡學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內(nèi)容6.1圖的概念圖的定義：G=(V，E)；V是非空有限集合，其元素稱為頂點；E是邊的集合,頂點偶對稱為邊圖的基本術語有向圖：G1=(V1，E1)；V1={v1，v2，v3，v4}；E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}弧：有序的頂點偶對：<x，y>無向圖：G2=(V2，E2)；V2={v1，v2，v3，v4，v5}；E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}邊：無序的頂點偶對(x，y)完全圖無向圖，邊的取值范圍是0到n(n-1)/2。有n(n-1)/2條邊的無向圖有向圖，邊的取值范圍是0到n(n-1)。有n(n-1)條弧的有向圖鄰接點無向圖G=(V，E)，若邊(v，v’)∈E；頂點v和v’互為鄰接點，即v和v’相鄰接；邊(v,v’)與頂點v,v’相關聯(lián)有向圖G=(V,E)，如果邊<v,v’>∈E；頂點v鄰接到v’,或v’鄰接于v；邊<v,v’>與頂點v,v’相關聯(lián)無向圖的度：與頂點v相關聯(lián)的邊數(shù)有向圖，入度、出度。頂點v的度為：TD(v)=ID(v)+OD(v)子圖：假設有兩個圖G=(V，E)，G'=(V'，E')。如果V'包含于V，E'包含于E，則稱G'是G的子圖路徑：在無向圖中,若存在一個頂點序列 vi,vp1,vp2,…,vpm，vj。使得(vi,vp1)、(vp1,vp2),...,(vpm,vj)∈E則稱頂點vi到vj存在一條路徑。如果G是有向圖，則路徑也是有向的。頂點序列應滿足<vi,vp1>,<vp1,vp2>,...,<vpm,vj>∈E路徑的長度：路徑上的邊的或弧的數(shù)目簡單路徑：頂點不重復出現(xiàn)的路徑稱為簡單路徑回路：第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)簡單回路：除了第一頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路權(quán)：在圖的每條邊上加上一個數(shù)字作權(quán)網(wǎng)：帶權(quán)的圖稱為網(wǎng)圖的存儲結(jié)構(gòu)鄰接矩陣鄰接矩陣是表示頂點間相鄰關系的矩陣若G是一個具有n頂點的圖則G的鄰接矩陣是如下定義的n×n矩陣：鄰接矩陣的特點無向圖的鄰接矩陣對稱，可壓縮存儲。有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖的鄰接矩陣不一定對稱。有n個頂點的有向圖需存儲空間為n2無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點Vi的出度是A中第i行元素之和，頂點Vi的入度是A中第i列元素之和網(wǎng)的鄰接矩陣定義：圖的鄰接表表示法頂點表：頂點表的每個結(jié)點中，指針域指向邊表的第一個結(jié)點，數(shù)據(jù)域存儲頂點的名稱或其它信息。頂點表的每個結(jié)點，相當于邊表頭結(jié)點邊表：把同一個頂點發(fā)出的邊鏈接在同一個鏈表中，鏈表的每一個結(jié)點代表一條邊，邊表結(jié)點中保存著與某頂點相關聯(lián)的另一頂點，和指向下一個表結(jié)點的指針十字鏈表：可看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的另一種鏈表。在弧結(jié)點中有四個域：尾域(tailvex)和頭域(headvex)，分別指示弧尾和弧頭這兩個頂點在圖中的編號。鏈域(hlink)：指向弧頭相同的下一條弧。鏈域(tlink)：指向指向弧尾相同的下一條弧。十字弧頭相同的弧在同一鏈表上，弧尾相同的弧也是在同一鏈表上。它們的頭結(jié)點即為頂點結(jié)點，它由三個域組成。data域：存儲和頂點相關的信息。firstin域和firstout域：分別指向以該頂點為弧頭或弧尾的第一個弧結(jié)點。邊集數(shù)組：用一維數(shù)組存儲圖中所有的邊。數(shù)組元素的個數(shù)要大于等于圖中的邊數(shù)，每個元素用于存儲一條邊的起點、終點(對于無向圖，可選定邊的任一端點為起點或終點)和權(quán)(若有的話)。各邊在數(shù)組中的次序可任意安排，也可根據(jù)具體要求而定。邊集數(shù)組只是存儲圖中所有邊的信息，若需要存儲頂點信息，同樣需要一個具有n個元素的一維數(shù)組。教學重點圖的相關概念，圖的相關術語教學難點圖的存儲結(jié)構(gòu)教學流程教學環(huán)節(jié)教師活動學生活動講評和考勤（5分鐘）1.平臺發(fā)布任務2.考勤1.考勤講授（55分鐘）1.圖的定義（10分鐘）2.圖的相關術語（20分鐘）3.圖的存儲結(jié)構(gòu)（25分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（25分鐘）1.圖的基本術語（10分鐘）2.鄰接矩陣（15分鐘）1.認真思考2.積極回答問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)2.記錄課后任務第二次課（2學時）教學內(nèi)容6.2圖的操作圖的遍歷：從圖中某頂點出發(fā)，沿一些邊訪問圖中頂點，使每個頂點都被訪問到，且僅被訪問一次。無重復，無遺漏。關鍵點：圖中可能存在回路；圖的頂點可能與其它頂點相通,在訪問完某頂點后,可能沿著某些邊回到曾經(jīng)訪問過的頂點；為避免重復訪問,可設輔助數(shù)組visited[]，將其初始化為0，遍歷時,如果某頂點i被訪問,將visited[i]置為1，以此防止頂點i被多次訪問。深度優(yōu)先遍歷：類似樹的深度遍歷。設初始狀態(tài)：圖中所有頂點都沒被訪問過；從圖中某一頂點v0出發(fā)，訪問v0，然后訪問與v0鄰接,但未被訪問過的任一頂點v1；接著訪問與v1鄰接，但未被訪問過的任意頂點V2；當達到某頂點時，發(fā)現(xiàn)其所有鄰接頂點均被訪問過，則退回到最近被訪問過的前一頂點；若它還有鄰接點未被訪問過，從未被訪問過的頂點中，任取一頂點,重復這一過程；若所有鄰接頂點被訪問過，則再回退；如此重復，直到所有頂點均被訪問過為止。廣度優(yōu)先搜索：類似于樹的層次遍歷。假設初始狀態(tài)是圖中所有頂點都沒被訪問過；從圖中某一頂點v0出發(fā)，訪問v0；然后訪問v0的全部鄰接點w1，w2，...，wt；再從這些被訪問的頂點出發(fā)，逐次訪問它們的鄰接點(已被訪問的頂點除外)；依此類推，直到所有頂點都被訪問為止。圖的生成樹連通：無向圖中，如果從頂點v到頂點v'有路徑，則稱v和v'是連通的連通圖：如果圖中任意兩個頂點都是連通的，則是連通圖連通分量：無向圖的極大連通子圖，連通圖只有一個連通分量，即其自身，非連通的無向圖有多個連通分量強連通圖：有向圖中，如果每一對頂點vi,vj∈V(vi!=vj)，從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖強連通分量：有向圖的極大強連通子圖稱作強連通分量，強連通圖的強連通分量是其自身，非強連通的有向圖可能有多個強連通分量生成樹：連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。一個圖可以有許多棵不同的生成樹生成樹具有以下共同特點：頂點個數(shù)與圖的頂點個數(shù)相同，是圖的極小連通子圖，一個有n個頂點的連通圖的生成樹有n-1條邊，生成樹中任意兩個頂點間的路徑是唯一的，在生成樹中再加一條邊必然形成回路，含n個頂點n-1條邊的圖不一定是生成樹連通無向圖的生成樹設G=(V，E)是一個連通圖，則從圖中任一頂點出發(fā)，遍歷圖G時，得到一個邊集T(G)，T(G)與圖中所有頂點一起構(gòu)成圖G的極小連通子圖，它是連通圖的一棵生成樹。由DFS得到的是深度優(yōu)先生成樹，由BFS得到的為廣度優(yōu)先生成樹非連通圖的生成樹非連通圖，每個連通分量中的頂點集和遍歷時走過的邊一起構(gòu)成若干棵生成樹。這些連通分量的生成樹組成非連通圖的生成森林圖的生成樹不是唯一的。從不同的頂點出發(fā)，能得到不同的生成樹。連通網(wǎng)絡G=(V,E)，各邊帶權(quán)，生成樹各邊帶權(quán)，生成樹的權(quán)：生成樹各邊權(quán)值的和，最小生成樹：權(quán)值最小的生成樹貪心（Prim）算法旅行推銷員問題推銷員從其中某一城市出發(fā)，唯一走遍n個城市，再回到出發(fā)的城市，求最短的路線。在帶權(quán)無向完全圖中，訪問每個頂點恰好一次，并且返回出發(fā)點、總權(quán)數(shù)最小的回路每一步都選擇當前狀態(tài)下的最優(yōu)解克魯斯卡爾（Kruskal）算法尋找每一步的最小路徑，拒絕回路教學重點二叉樹的遍歷教學難點二叉樹的性質(zhì)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（50分鐘）1.圖的遍歷（20分鐘）2.圖的生成樹（10分鐘）3.貪心算法（10分鐘）4.克魯斯卡爾算法（10分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（30分鐘）1.貪心算法（15分鐘）2.克魯斯卡爾算法（15分鐘）1.認真思考2.積極回答問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第三次課（2學時）教學內(nèi)容技能訓練-圖的遍歷實現(xiàn)下面兩張圖的深度優(yōu)先與廣度優(yōu)先遍歷。教學重點圖的遍歷的代碼實現(xiàn)教學難點圖的遍歷的代碼實現(xiàn)教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤代碼演示（30分鐘）1.圖的深度優(yōu)先搜索算法代碼實現(xiàn)（20分鐘）2.圖的廣度優(yōu)先搜索算法實現(xiàn)（10分鐘）1.認真思考2.遇到問題及時提問技能訓練（50分鐘）1.布置技能訓練任務（5分鐘）2.在技能訓練過程中巡視并啟發(fā)學生解決遇到的問題。1.獨立完成老師下發(fā)的課堂練習2.在遇到問題時與同學討論?？偨Y(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第四次課（2學時）教學內(nèi)容6.3圖的應用拓撲排序無環(huán)圖（DAG）：一個無環(huán)（回路）的有向圖叫做有向無環(huán)圖AOE網(wǎng)：頂點表示活動的網(wǎng)，頂點表示活動，弧表示活動間的先后關系，AOV網(wǎng)中不允許有回路拓撲排序的方法：從有向圖中任選一個入度為0的頂點，并訪問；對所有以它為尾的弧，弧頭頂點的入度減1；刪除該頂點和所有以它為尾的?。恢貜蜕鲜鰞刹?，直至全部頂點均已訪問，或當圖中不存在度為0的頂點為止；不存在度為0的頂點:存在環(huán)。舉例：關鍵路徑問題用有向圖表示工程計劃，頂點表示事件，弧表示活動。每個頂點表示在它之前的活動已完成，在它之后的活動可以開始。源點和匯點：正常情況(無環(huán))下，網(wǎng)中只有一個入度為零的點,稱為源點。一個出度為零的點,稱為匯點。關鍵路徑：完成整個工程的最短時間是從源點到匯點的最長路徑的長度(路徑長度等于路徑上各邊的權(quán)之和)。這條具有最大長度的路徑稱為關鍵路徑。ee(i)：表示事件Vi的最早發(fā)生時間le(i)：表示事件Vi的最遲發(fā)生時間e(k)：活動ak=<vi，vj>的最早開始時間l(k)：活動ak=<vi，vj>的最遲開始時間l(k)-e(k)：完成活動ak的時間余量關鍵活動：關鍵路徑上的活動舉例：教學重點拓撲排序，關鍵路徑問題教學難點拓撲排序，關鍵路徑問題教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（40分鐘）1.拓撲排序（20分鐘），講授、舉例、分析2.關鍵路徑問題（20分鐘），講授、舉例、分析1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動技能訓練（40分鐘）1.拓撲排序，利用鄰接表實現(xiàn)（40分鐘）1.認真思考2.積極編碼解決問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。第五次課（2學時）教學內(nèi)容最短路徑問題用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂點：表示城市邊：表示城市間的交通聯(lián)系權(quán)：表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑：最短路徑。單源最短路徑：從某個源點到其余各頂點的最短路徑迪杰斯特拉算法：采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節(jié)點，直到擴展到終點為止。舉例：求每個頂點之間的最短路徑弗洛伊德(Floyed)算法：依次以每個節(jié)點為中介，優(yōu)化距離矩陣。舉例：教學重點迪杰斯特拉算法，弗洛伊德算法教學難點迪杰斯特拉算法，弗洛伊德算法教學流程教學環(huán)節(jié)教師活動學生活動考勤（5分鐘）1.考勤1.考勤講授（45分鐘）1.迪杰斯特拉算法，講授、舉例、分析（20分鐘）2.弗洛伊德算法，講授、舉例、分析（25分鐘）1.積極回答教師提問2.認真思考、記錄關鍵內(nèi)容3.積極參與課堂的討論和互動課堂練習（35分鐘）1.迪杰斯特拉算法（15分鐘）2.弗洛伊德算法（20分鐘）1.認真思考2.積極畫圖解決問題總結(jié)與發(fā)布課后任務（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務1.思考教師總結(jié)，2.記錄教師的任務要求并在課后完成。教學效果與反思根據(jù)單元測驗結(jié)果，80%的學生教好掌握了教學內(nèi)容，達成了單元教學目標。其中教學目標AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達成情況較好，但EOB1、EOB3達成情況一般。結(jié)合學生的課堂練習，在線測試等教學活動的結(jié)果來看，課堂出勤比較好，個別學生有缺課的情況；課堂練習獨立完成，但允許相互討論，掌握情況比較好；技能訓練課堂實現(xiàn)情況一般，部分學生需要課后另花時間完成。在線測試內(nèi)容有時間限制，有一部分內(nèi)容需要課后閱讀教材和查閱相關材料，所以對平時學習習慣不好的少部分同學有一定難度，所以會出現(xiàn)問題。圖的遍歷與操作編程難度較大，不要求靈活掌握編碼技巧，但要求掌握圖的基本操作的方法。教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設計課程代碼總學時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學單元單元7排序教學時數(shù)10教學目標AOB1:掌握計算機程序設計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計算機程序設計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對算法的科學分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設計出適當?shù)乃惴ê统绦颉OB1:掌握使用搜索引擎、論壇、幫助文檔、課外書籍等方法解決學習中出現(xiàn)的問題；EOB2:能主動閱讀書后拓展知識并進行實驗驗證；EOB3:能獨立分析解決問題，能把自己的想法用代碼實現(xiàn)。教學方式混合式教學評價方式課堂考勤（20%），課堂活動參與程度（20%）線上單元測試（40%）線下課堂教學參與程度（20%）教學資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語言描述），陳媛，清華大學大學出版社2.電腦50臺（含eclips）;3.網(wǎng)絡學習資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學設計第一次課（2學時）教學內(nèi)容1排序的概念排序：整理文件中的記錄，使它們按關鍵字遞增(或遞減)次序重新排列排序方法的穩(wěn)定性：若存在多個關鍵字相同的記錄，經(jīng)過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，則稱該排序方法是穩(wěn)定的否則，若具有相同關鍵字的記錄之間的相對次序發(fā)生變化，則稱該排序方法是不穩(wěn)定的排序的分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問按排序的策略插入排序：直接插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡單選擇排序、堆排序歸并排序：2-路歸并排序排序的基本操作關鍵操作：比較兩個關鍵字大小，將記錄從一個位置移動到另一個位置不同存儲方式的排序過程：以順序表作為存儲結(jié)