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

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

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

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

單元教案授課日期年月日—月日授課地點(diǎn)授課班級(jí)班級(jí)人數(shù)教學(xué)單元單元3棧和隊(duì)列教學(xué)時(shí)數(shù)8教學(xué)目標(biāo)AOB1:掌握計(jì)算機(jī)程序設(shè)計(jì)中的線性表、棧、隊(duì)列、樹和圖的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB2:掌握計(jì)算機(jī)程序設(shè)計(jì)中的線性表、棧、隊(duì)列、樹、圖的數(shù)據(jù)增、刪、改、查操作運(yùn)算。了解遞歸的處理算法。掌握選擇與排序處理算法；AOB3:掌握對(duì)算法的科學(xué)分析方法。BOB1:能根據(jù)實(shí)際問(wèn)題中的數(shù)據(jù)特性選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；BOB2:設(shè)計(jì)出適當(dāng)?shù)乃惴ê统绦?。EOB1:掌握使用搜索引擎、論壇、幫助文檔、課外書籍等方法解決學(xué)習(xí)中出現(xiàn)的問(wèn)題；EOB2:能主動(dòng)閱讀書后拓展知識(shí)并進(jìn)行實(shí)驗(yàn)驗(yàn)證；EOB3:能獨(dú)立分析解決問(wèn)題，能把自己的想法用代碼實(shí)現(xiàn)。教學(xué)方式混合式教學(xué)評(píng)價(jià)方式課堂考勤（20%），課堂活動(dòng)參與程度（20%）線上單元測(cè)試（40%）線下課堂教學(xué)參與程度（20%）教學(xué)資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言描述），陳媛，清華大學(xué)大學(xué)出版社2.電腦50臺(tái)（含eclips）;3.網(wǎng)絡(luò)學(xué)習(xí)資源：/forums/ST_Arithmetic：課程平臺(tái)網(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ù)元素之間是一對(duì)一的關(guān)系存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)運(yùn)算規(guī)則：只能在棧頂運(yùn)算，且訪問(wè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()：棧置空操作。不論棧是否為空棧，置為空棧棧的順序存儲(chǔ)結(jié)構(gòu)（順序棧）利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈棧）組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂教學(xué)重點(diǎn)棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)教學(xué)難點(diǎn)棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)講評(píng)和考勤（5分鐘）1平臺(tái)發(fā)布任務(wù)2考勤1考勤講授（30分鐘）1.棧的定義（5分鐘）2.棧的基本操作（5分鐘）3.棧的順序存儲(chǔ)（10分鐘）4.棧的鏈?zhǔn)酱鎯?chǔ)（10分鐘）1.積極回答教師提問(wèn)2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)代碼實(shí)現(xiàn)演示（50分鐘）1.棧的順序存儲(chǔ)代碼實(shí)現(xiàn)（25分鐘）2.棧的鏈?zhǔn)酱鎯?chǔ)代碼實(shí)現(xiàn)（25分鐘）1.認(rèn)真思考、記錄關(guān)鍵內(nèi)容總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過(guò)程中出現(xiàn)的，問(wè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ù)中證明所有方法在各種正常情況下的正確性，尤其是?？张c棧滿的狀態(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)練過(guò)程中巡視并啟發(fā)學(xué)生解決遇到的問(wèn)題。1.獨(dú)立完成老師下發(fā)的課堂練習(xí)2.在遇到問(wèn)題時(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)的逆序排列起來(lái)（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn)的余數(shù)排在前面）2.單鏈表的逆置3.表達(dá)式求值對(duì)算術(shù)表達(dá)式求值：1+2*4-9/3遵循先乘除后加減、先左后右及先括號(hào)內(nèi)，后括號(hào)外的四則運(yùn)算法則，其計(jì)算順序應(yīng)為：采用“運(yùn)算符優(yōu)先數(shù)法”對(duì)每種運(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ì)方法，通過(guò)主函數(shù)調(diào)用模塊來(lái)解決復(fù)雜的實(shí)際問(wèn)題。由于函數(shù)調(diào)用后，需返回調(diào)用處，所以在調(diào)用時(shí)，需用棧記錄斷點(diǎn)的地址以及有關(guān)信息，以便返回。5.地圖四染色問(wèn)題“四染色”：可以用不多于四色對(duì)地圖著色，使相鄰的地區(qū)不重色算法思想：回溯法①?gòu)牡谝惶?hào)地區(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)講評(píng)和考勤（5分鐘）1平臺(tái)發(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.地圖四染色問(wèn)題（25分鐘）1.積極回答教師提問(wèn)2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過(guò)程中出現(xiàn)的，問(wèn)題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第四次課（2學(xué)時(shí)）教學(xué)內(nèi)容隊(duì)列隊(duì)列的定義：只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表邏輯結(jié)構(gòu)：元素之間是一對(duì)一的關(guān)系存儲(chǔ)結(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ì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)，稱為順序隊(duì)列由一個(gè)存放隊(duì)列元素的一維數(shù)組，和隊(duì)頭、隊(duì)尾“指針”組成。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)是單鏈表，同時(shí)帶有頭指針和尾指針頭指針指向隊(duì)頭結(jié)點(diǎn)尾指針指向隊(duì)尾結(jié)點(diǎn)教學(xué)重點(diǎn)隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)，隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)教學(xué)難點(diǎn)隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)，隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)教學(xué)流程教學(xué)環(huán)節(jié)教師活動(dòng)學(xué)生活動(dòng)講評(píng)和考勤（5分鐘）1平臺(tái)發(fā)布任務(wù)2考勤1考勤講授（30分鐘）1.隊(duì)列的定義（10分鐘）2.隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)（10分鐘）3.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)（10分鐘）1.積極回答教師提問(wèn)2.認(rèn)真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動(dòng)代碼實(shí)現(xiàn)演示（50分鐘）1.棧的順序存儲(chǔ)代碼實(shí)現(xiàn)（25分鐘）2.棧的鏈?zhǔn)酱鎯?chǔ)代碼實(shí)現(xiàn)（25分鐘）1.認(rèn)真思考、記錄關(guān)鍵內(nèi)容總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過(guò)程中出現(xiàn)的，問(wèn)題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)教學(xué)效果與反思根據(jù)單元測(cè)驗(yàn)結(jié)果，90%的學(xué)生教好掌握了教學(xué)內(nèi)容，達(dá)成了單元教學(xué)目標(biāo)。其中教學(xué)目標(biāo)AOB1、AOB2、AOB3、BOB1、BOB2、EOB1、EOB2、EOB3達(dá)成情況較好，但EOB1、EOB3達(dá)成情況一般。結(jié)合學(xué)生的課堂練習(xí)，在線測(cè)試等教學(xué)活動(dòng)的結(jié)果來(lái)看，課堂出勤比較好，沒(méi)有缺課的情況；課堂練習(xí)獨(dú)立完成，但允許相互討論，掌握情況比較好；技能訓(xùn)練課堂實(shí)現(xiàn)情況一般，部分學(xué)生需要課后另花時(shí)間完成。在線測(cè)試內(nèi)容有時(shí)間限制，有一部分內(nèi)容需要課后閱讀教材和查閱相關(guān)材料，所以對(duì)平時(shí)學(xué)習(xí)習(xí)慣不好的少部分同學(xué)有一定難度，所以會(huì)出現(xiàn)問(wèn)題。教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程代碼總學(xué)時(shí)64課程負(fù)責(zé)人任課教師

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

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

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

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

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