數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言版）-教案 李春葆 第10-16 教學(xué)周 二叉樹的建立、二叉樹遍歷和哈夫曼樹-常用的查找算法實(shí)現(xiàn)

成都東軟學(xué)院《數(shù)據(jù)結(jié)構(gòu)(Java)》課程/項(xiàng)目教案2-《數(shù)據(jù)結(jié)構(gòu)(Java)》課程/項(xiàng)目教案1-《數(shù)據(jù)結(jié)構(gòu)（Java）》課程/項(xiàng)目教案單元教案首頁(yè)單元CU（4）學(xué)時(shí)12周次第10－12教學(xué)周教學(xué)環(huán)境設(shè)計(jì)與組織安排課堂，筆記本電腦，小組合作單元名稱樹和二叉樹單元項(xiàng)目名稱二叉樹的建立、二叉樹遍歷和哈夫曼樹教學(xué)目標(biāo)及達(dá)成度理論知識(shí)理解并掌握樹形結(jié)構(gòu)的概念和算法專業(yè)技能對(duì)根據(jù)具體的問(wèn)題進(jìn)行數(shù)據(jù)結(jié)構(gòu)抽象化的能力熟練運(yùn)用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)算法的能力具有科技資料與文獻(xiàn)的收集與檢索能力具有自我學(xué)習(xí)能力及新技術(shù)開發(fā)與研究的能力職業(yè)道德理解工程師職業(yè)道德規(guī)范具備一名優(yōu)秀工程師的基本素質(zhì)教學(xué)重點(diǎn)難點(diǎn)二叉樹的二叉鏈表、三叉鏈表表示法；二叉樹的建立算法；三種二叉樹的遍歷算法（前序、中序、后序）；二叉樹的節(jié)點(diǎn)刪除算法；哈夫曼樹教學(xué)方法手段媒介教學(xué)方法：講授、討論、演示、練習(xí)、實(shí)驗(yàn)、研究性學(xué)習(xí)、案例、合作學(xué)習(xí)、指導(dǎo)教學(xué)、任務(wù)分析、自主學(xué)習(xí)、讀書、問(wèn)題教學(xué)。教學(xué)媒介：教科書、板書、多媒體。教學(xué)組織方式1.講評(píng)——課后作業(yè)2.互動(dòng)——演示二叉樹的基本操作3.講解——樹與二叉樹的基本概念，二叉樹的建立、遍歷算法，哈夫曼樹及哈夫曼編碼算法4.操作――編程實(shí)現(xiàn)二叉樹的建立、遍歷算法實(shí)踐環(huán)節(jié)課內(nèi)實(shí)踐環(huán)節(jié)：編程實(shí)現(xiàn)二叉樹的建立、遍歷算法，哈夫曼編碼課外實(shí)踐環(huán)節(jié)：平時(shí)成績(jī)管理系統(tǒng)中，學(xué)生成績(jī)按排序二叉樹方式建立，實(shí)現(xiàn)基本操作算法

教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)樹形結(jié)構(gòu)是非線性結(jié)構(gòu)。其特點(diǎn)是數(shù)據(jù)元素只能有一個(gè)前驅(qū)，可以有零個(gè)或多個(gè)后繼。二、內(nèi)容導(dǎo)入樹是一種常用的非線性結(jié)構(gòu)。樹的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。三、主要內(nèi)容設(shè)計(jì)1.樹的定義【講授】樹的定義樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。若n=0，則稱為空樹；否則，有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為根，當(dāng)n>1時(shí)，其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的子集T1，T2，...，Tm，每個(gè)子集又是一棵樹。由此可以看出，樹的定義是遞歸。樹的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)?！景咐啃姓C(jī)構(gòu)，公司機(jī)構(gòu)2.樹的基本術(shù)語(yǔ)【講授】結(jié)點(diǎn)表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支。結(jié)點(diǎn)的度結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)。葉子結(jié)點(diǎn)（葉子）度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)度不為0的結(jié)點(diǎn)。結(jié)點(diǎn)的層次樹中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹的根為第2層，以此類推。樹的度樹中所有結(jié)點(diǎn)度的最大值。樹的深度樹中所有結(jié)點(diǎn)層次的最大值。有序樹、無(wú)序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無(wú)序樹?！練w納總結(jié)】教學(xué)重是對(duì)樹的概念理解，對(duì)術(shù)語(yǔ)的記憶?！菊n外學(xué)習(xí)要求】思考：怎樣存儲(chǔ)樹？既要保存數(shù)據(jù)，又要包含數(shù)據(jù)之間的關(guān)系?！菊n后分析及改進(jìn)】注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)在建立單鏈表的基礎(chǔ)上引入二叉鏈的概念。二、內(nèi)容導(dǎo)入任意一顆樹都可以轉(zhuǎn)化成二叉樹。反之二叉樹葉可以轉(zhuǎn)化成普通樹。三、主要內(nèi)容設(shè)計(jì)1．二叉樹的定義【講授】二叉樹也可以用遞歸的形式定義。即：二叉樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱為空二叉樹；當(dāng)n>0時(shí)，有且僅有一個(gè)結(jié)點(diǎn)為二叉樹的根，其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集，一個(gè)作為左子集，另一個(gè)作為右子集，每個(gè)子集又是一個(gè)二叉樹。【案例】【講授】2．滿二叉樹和完全二叉樹【講授】如果一個(gè)深度為K的二叉樹擁有2K-1個(gè)結(jié)點(diǎn)，則將它稱為滿二叉樹。有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。３．二叉樹的性質(zhì)【講授】５個(gè)性質(zhì)。均不用硬記，只要畫一個(gè)二叉樹圖就知道了。最重要的是性質(zhì)5，是根據(jù)結(jié)點(diǎn)編號(hào)建二叉樹的依據(jù)?！景咐俊局v授】４.二叉樹的順序存儲(chǔ)結(jié)構(gòu)【講授】按完全二叉樹對(duì)結(jié)點(diǎn)編號(hào)，結(jié)點(diǎn)編號(hào)與數(shù)組的下標(biāo)相同，根據(jù)下標(biāo)可以得倒雙親和孩子的關(guān)系。此種存儲(chǔ)方式對(duì)于數(shù)據(jù)較簡(jiǎn)單的二叉樹使用比較方便。如果數(shù)據(jù)是大結(jié)構(gòu)體，則可能浪費(fèi)較大空間?！景咐俊局v授】【歸納總結(jié)】【課外學(xué)習(xí)要求】實(shí)現(xiàn)并閱讀程序?！菊n后分析及改進(jìn)】注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)提問(wèn)：二叉樹為什么要用鏈?zhǔn)酱鎯?chǔ)？二、內(nèi)容導(dǎo)入二叉樹是一種非常重要的樹形結(jié)構(gòu),其它的樹形結(jié)構(gòu)文體可以變化為二叉樹三、主要內(nèi)容設(shè)計(jì)１．二叉樹的鏈?zhǔn)酱鎯?chǔ)【講授】根據(jù)二叉樹的性質(zhì)5，按完全二叉樹的編號(hào)，輸入結(jié)點(diǎn)編號(hào)和結(jié)點(diǎn)值，就可生成二叉鏈表。由于后面結(jié)點(diǎn)的指針要賦予前面結(jié)點(diǎn)的左、右孩子指針域，故應(yīng)設(shè)計(jì)一個(gè)指針數(shù)組，用于保存結(jié)點(diǎn)的指針。根據(jù)結(jié)點(diǎn)編號(hào)可以得出其雙親結(jié)點(diǎn)的編號(hào)，及其結(jié)點(diǎn)是雙親的左孩子還是右孩子。這樣就可以根據(jù)結(jié)點(diǎn)編號(hào)建立二叉樹?！緦?shí)驗(yàn)】按結(jié)點(diǎn)編號(hào)建立二叉樹結(jié)點(diǎn)編號(hào)整除2得雙親編號(hào)。若結(jié)點(diǎn)編號(hào)是偶數(shù)，則是左孩子，該結(jié)點(diǎn)的指針賦予雙親結(jié)點(diǎn)的左孩子指針域；若結(jié)點(diǎn)編號(hào)是奇數(shù)，則是右孩子，該結(jié)點(diǎn)的指針賦予雙親結(jié)點(diǎn)的右孩子指針域。教學(xué)重難點(diǎn)是建立二叉樹和顯示二叉樹。2顯示二叉樹【講授】用縮進(jìn)顯示出結(jié)點(diǎn)間的層次關(guān)系【實(shí)驗(yàn)】按結(jié)點(diǎn)編號(hào)建立二叉樹，并用縮進(jìn)顯示二叉樹【歸納總結(jié)】教學(xué)重難點(diǎn)是對(duì)程序的閱讀和理解?！菊n外學(xué)習(xí)要求】實(shí)現(xiàn)并閱讀程序?！菊n后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)1.提問(wèn)：二叉樹的存儲(chǔ)方式。2.提問(wèn)：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的編程思路。二、內(nèi)容導(dǎo)入對(duì)二叉樹的很多處理都是以遍歷為基礎(chǔ),因此我們要熟練的掌握遍歷。（順序表和單鏈表也存在遍歷的問(wèn)題，由于比較簡(jiǎn)單，沒(méi)有單獨(dú)作為問(wèn)題講解。）三、主要內(nèi)容設(shè)計(jì)１.先根遍歷【講授】先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹?！景咐俊局v授】２．中根遍歷【講授】先中序遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹?！景咐俊緦?shí)驗(yàn)】３.后根遍歷【講授】先后序遍歷左、右子樹，然后訪問(wèn)根結(jié)點(diǎn)?！景咐俊緦?shí)驗(yàn)】建立一顆二叉樹，用三種方法遍歷，顯示遍歷的結(jié)果?！練w納總結(jié)】教學(xué)重難點(diǎn)是對(duì)遍歷方式的遞歸過(guò)程的理解?！菊n外學(xué)習(xí)要求】完成并實(shí)現(xiàn)程序的運(yùn)行。深入理解遍歷的遞歸過(guò)程?！菊n后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)深入理解二叉鏈。二、內(nèi)容導(dǎo)入葉子結(jié)點(diǎn)沒(méi)有孩子，其指針域?yàn)榭?。為了利用空的指針域，引入線索二叉樹的概念。三、主要內(nèi)容設(shè)計(jì)1．線索二叉樹【講授】。葉子結(jié)點(diǎn)沒(méi)有孩子，其指針域?yàn)榭铡榱死每盏闹羔樣?，可以令左孩子指針指向該結(jié)點(diǎn)的直接前驅(qū)，令右孩子指針指向該結(jié)點(diǎn)的直接后繼。某結(jié)點(diǎn)的左指針可以指向左孩子，也可以指向直接前驅(qū)；同樣，右指針也可以指向右孩子，也可以直線直接后繼。因此又增加兩個(gè)標(biāo)志，左標(biāo)志為0，左指針指向左孩子；左標(biāo)志為1，左指針指向直接前驅(qū)。右標(biāo)志為0，右指針指向右孩子；右標(biāo)志為1，右標(biāo)志指向直接后繼。所謂直接前驅(qū)和直接后繼，是由按什么方式遍歷有關(guān)?！景咐恐行虮闅v的線索二叉樹程序。2.森林轉(zhuǎn)化成二叉樹【講授】1將各棵樹分別轉(zhuǎn)換成二叉樹2將每棵樹的根結(jié)點(diǎn)用線相連3以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)3.二叉樹轉(zhuǎn)換成森林【講授】1加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)2抹線：抹掉原二叉樹中雙親與右孩子之間的連線3調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)【實(shí)驗(yàn)】練習(xí)森林轉(zhuǎn)化成二叉樹，二叉樹轉(zhuǎn)換成森林的步驟。【歸納總結(jié)】線索二叉樹的程序?！菊n外學(xué)習(xí)要求】運(yùn)行并閱讀理解線索二叉樹的程序?！菊n后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)二、內(nèi)容導(dǎo)入在通訊中，電文是以二進(jìn)制的0、1序列傳送的。在發(fā)送端，將電文中的字符轉(zhuǎn)換成二進(jìn)制的0、1序列，在接受端，則需要將收到的0、1序列還原成對(duì)應(yīng)的字符序列。設(shè)給出一段報(bào)文：CASTSATA；希望的是傳送電文時(shí)長(zhǎng)度盡可能的短，試寫出對(duì)應(yīng)的二進(jìn)制0、1序列。三、主要內(nèi)容設(shè)計(jì)1．哈夫曼樹的概念【講授】把若干個(gè)帶權(quán)的葉子結(jié)點(diǎn)生成一顆二叉樹，要求結(jié)點(diǎn)的權(quán)乘以邊條數(shù)之和為最小?！景咐吭谕ㄓ嵵械膽?yīng)用。2.哈夫曼樹的生成【講授】原則：權(quán)小的結(jié)點(diǎn)離根結(jié)點(diǎn)遠(yuǎn)，權(quán)大的結(jié)點(diǎn)離根結(jié)點(diǎn)近。方法：先選兩個(gè)權(quán)小的生成一顆二叉樹，并形成一個(gè)有編號(hào)的新的根結(jié)點(diǎn)該結(jié)點(diǎn)的權(quán)為左、右子樹權(quán)之和。逐級(jí)進(jìn)行，每次都是選兩個(gè)權(quán)小的結(jié)點(diǎn)（包括新生成的根結(jié)點(diǎn)）生成二叉樹，（注意，選擇時(shí)，是從編號(hào)小的結(jié)點(diǎn)開始，若新結(jié)點(diǎn)的權(quán)和老結(jié)點(diǎn)的權(quán)相同，則選出的是老結(jié)點(diǎn)）。直到選完全部結(jié)點(diǎn)。哈夫曼樹應(yīng)用舉例—哈夫曼編碼?！局v授】把字母出現(xiàn)的頻率作為字母的權(quán)。權(quán)小的結(jié)點(diǎn)離根結(jié)點(diǎn)遠(yuǎn)，權(quán)大的結(jié)點(diǎn)離根結(jié)點(diǎn)近。這樣生成的二叉樹就是哈夫曼樹。把左子樹的邊當(dāng)作0，右子樹的邊當(dāng)作1，由根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的邊就組成哈夫曼編碼。哈夫曼編碼可以使文本的編碼最短。【練習(xí)】設(shè)給出一段報(bào)文：CASTCASTSATATATASA希望的是傳送電文時(shí)長(zhǎng)度盡可能的短（1）畫出構(gòu)造的哈夫曼樹（2）計(jì)算帶權(quán)路徑長(zhǎng)度（3）求各字符的哈夫曼編碼【歸納總結(jié)】何為哈夫曼樹？哈夫曼編碼？其作用是什么？【課外學(xué)習(xí)要求】1.給定一組數(shù)列（10,18,16,25,6,

9,16）分別代表字符A,B,C,D,E,F,G出現(xiàn)的頻度，試畫出哈夫曼樹，給出各字符的編碼。2.閱讀理解哈夫曼編碼的程序。【課后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。單元教案首頁(yè)單元CU（5）學(xué)時(shí)2周次第13教學(xué)周教學(xué)環(huán)境設(shè)計(jì)與組織安排課堂，筆記本電腦，小組合作單元名稱圖單元項(xiàng)目名稱圖的建立及遍歷教學(xué)目標(biāo)及達(dá)成度理論知識(shí)理解并掌握?qǐng)D形結(jié)構(gòu)的建立及遍歷專業(yè)技能對(duì)根據(jù)具體的問(wèn)題進(jìn)行數(shù)據(jù)結(jié)構(gòu)抽象化的能力熟練運(yùn)用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)算法的能力具有較強(qiáng)的口頭表述能力職業(yè)道德能夠正確認(rèn)識(shí)人生價(jià)值的自我實(shí)現(xiàn)和對(duì)他人所負(fù)的責(zé)任具有正直并勇于負(fù)責(zé)的職業(yè)道德和敬業(yè)精神教學(xué)重點(diǎn)難點(diǎn)圖形的表示法（鄰接數(shù)組表示法、鄰接列表表示法）；圖形的遍歷算法（深度優(yōu)先法、廣度優(yōu)先法）教學(xué)方法手段媒介教學(xué)方法：講授、討論、演示、練習(xí)、實(shí)驗(yàn)、研究性學(xué)習(xí)、案例、合作學(xué)習(xí)、指導(dǎo)教學(xué)、任務(wù)分析、自主學(xué)習(xí)、讀書、問(wèn)題教學(xué)。教學(xué)媒介：教科書、板書、多媒體。教學(xué)組織方式1.講評(píng)——課后作業(yè)2.互動(dòng)——分組理解圖這種數(shù)據(jù)結(jié)構(gòu)，了解圖的應(yīng)用，全班匯報(bào)3.講解——圖的基本概念，圖的存儲(chǔ)及遍歷算法實(shí)踐環(huán)節(jié)課內(nèi)實(shí)踐環(huán)節(jié)：編程實(shí)現(xiàn)圖的遍歷算法教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)二、內(nèi)容導(dǎo)入現(xiàn)實(shí)生活中還有一種結(jié)點(diǎn)間是多對(duì)多的關(guān)系。如城市交通、管線等。三、主要內(nèi)容設(shè)計(jì)1．圖的基本概念【講授】1各結(jié)點(diǎn)之間的關(guān)系是多對(duì)多的系。2圖的相關(guān)術(shù)語(yǔ)：完全圖、稠密圖、稀疏圖、鄰接點(diǎn)、度、入度、出度、子圖、權(quán)、網(wǎng)、路徑、回路、路徑長(zhǎng)度、無(wú)向圖的連通圖、連通分量、有向圖的強(qiáng)連通圖、強(qiáng)連通分量?！景咐俊局v授】2.圖的兩種存儲(chǔ)結(jié)構(gòu)【講授】1鄰接矩陣表示：頂點(diǎn)表，鄰接矩陣。2鄰接表表示：頂點(diǎn)表，邊表。3.無(wú)向圖和有向圖的區(qū)別。3.網(wǎng)的兩種存儲(chǔ)結(jié)構(gòu)【講授】1鄰接矩陣表示：頂點(diǎn)表，鄰接矩陣。2鄰接表表示：頂點(diǎn)表，邊表。3.無(wú)向網(wǎng)和有向網(wǎng)的區(qū)別。４.網(wǎng)和圖在存儲(chǔ)上的區(qū)別。【實(shí)驗(yàn)】無(wú)向圖和有向圖、無(wú)向網(wǎng)和有向網(wǎng)的程序?！練w納總結(jié)】術(shù)語(yǔ)較多，容易混淆。重在對(duì)比分析?！菊n外學(xué)習(xí)要求】學(xué)習(xí)鞏固術(shù)語(yǔ)，理解圖的存儲(chǔ)結(jié)構(gòu)。【課后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。單元教案首頁(yè)單元CU（7）學(xué)時(shí)8周次第14－15教學(xué)周教學(xué)環(huán)境設(shè)計(jì)與組織安排課堂，筆記本電腦，小組合作單元名稱排序單元項(xiàng)目名稱常用的排序算法實(shí)現(xiàn)教學(xué)目標(biāo)及達(dá)成度理論知識(shí)理解并掌握常用排序算法的思想和實(shí)現(xiàn)方法專業(yè)技能具有較強(qiáng)的技術(shù)文檔寫作能力具有科技資料與文獻(xiàn)的收集與檢索能力具有自我學(xué)習(xí)能力及新技術(shù)開發(fā)與研究的能力職業(yè)道德理解工程師職業(yè)道德規(guī)范具備一名優(yōu)秀工程師的基本素質(zhì)教學(xué)重點(diǎn)難點(diǎn)交換式排序法（冒泡排序法和快速排序法）；選擇式排序法（選擇排序法）；插入式排序法（插入排序法和二叉排序法）。教學(xué)方法手段媒介教學(xué)方法：講授、討論、演示、練習(xí)、實(shí)驗(yàn)、研究性學(xué)習(xí)、案例、合作學(xué)習(xí)、指導(dǎo)教學(xué)、任務(wù)分析、自主學(xué)習(xí)、讀書、問(wèn)題教學(xué)。教學(xué)媒介：教科書、板書、多媒體。教學(xué)組織方式1.講評(píng)——課后作業(yè)2.互動(dòng)——分組學(xué)習(xí)多種排序算法3.講解——學(xué)生將排序算法做為動(dòng)畫或PPT，做全班講解4.操作――編程實(shí)現(xiàn)排序算法實(shí)踐環(huán)節(jié)課內(nèi)實(shí)踐環(huán)節(jié)：編程實(shí)現(xiàn)排序算法課外實(shí)踐環(huán)節(jié)：平時(shí)成績(jī)管理系統(tǒng)中，對(duì)學(xué)生平時(shí)成績(jī)、考勤成績(jī)、作業(yè)成績(jī)用不同的排序算法排序。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)二、內(nèi)容導(dǎo)入三、主要內(nèi)容設(shè)計(jì)1．排序的定義【講授】將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列【案例】2排序的分類【講授】按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過(guò)程中需對(duì)外存進(jìn)行訪問(wèn)的排序按排序依據(jù)原則插入排序：直接插入排序交換排序：冒泡排序選擇排序：簡(jiǎn)單選擇排序歸并排序：2-路歸并排序2.冒泡排序【講授】1兩輛比較,后面的小,則交換位置。N個(gè)數(shù)比較N-1遍（外重循環(huán)）第1遍比較N-1次，…第N-1遍比較1次（內(nèi)重循環(huán)）2改進(jìn)的冒泡排序若某遍比較沒(méi)有發(fā)生交換，則排序結(jié)束。【實(shí)驗(yàn)】冒泡排序程序?！練w納總結(jié)】教學(xué)重難點(diǎn)是對(duì)順序棧及其操作的理解?！菊n外學(xué)習(xí)要求】完成四級(jí)項(xiàng)目第三階段：學(xué)生信息按順序棧存儲(chǔ)實(shí)現(xiàn)。【課后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)二、內(nèi)容導(dǎo)入三、主要內(nèi)容設(shè)計(jì)1．選擇排序【講授】永遠(yuǎn)用第一個(gè)與后面的比較,后面的小,則交換位置。【實(shí)驗(yàn)】選擇排序程序2.插入排序【講授】把數(shù)組看成兩個(gè)序列，一個(gè)是已排好的序列，在數(shù)組的前面，另一個(gè)是未排序的序列，在數(shù)組的后面剛開始時(shí)，認(rèn)為a[0]已排好的序列，a[1]及其以后是未排序的序列把未排序序列的第一當(dāng)作待插數(shù)，其排序過(guò)程如下：一）待插數(shù)與已排序序列的最后一個(gè)比較，1）待插數(shù)大于已排序的的最后一個(gè)，待插數(shù)原位不動(dòng)，作為已排序序列的最后一個(gè)2）待插數(shù)小于已排序的的最后一個(gè)，則待插數(shù)應(yīng)插入在已排序序列前面某個(gè)位置這是一個(gè)邊比較邊移位的過(guò)程。二邊比較邊移位的過(guò)程如下：從已排序序列的最后一個(gè)開始，逐個(gè)與待插數(shù)比較若待插數(shù)小，則一排序序列數(shù)據(jù)向后移位自到待插數(shù)大為止，該位置就是插入位置【實(shí)驗(yàn)】插入排序程序?！練w納總結(jié)】教學(xué)重難點(diǎn)是對(duì)順序棧及其操作的理解?！菊n外學(xué)習(xí)要求】完成四級(jí)項(xiàng)目第三階段：學(xué)生信息按順序棧存儲(chǔ)實(shí)現(xiàn)?！菊n后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)二、內(nèi)容導(dǎo)入三、主要內(nèi)容設(shè)計(jì)1．歸并排序【講授】歸并——將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，叫~2-路歸并排序排序過(guò)程設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1兩兩合并，得到?n/2?個(gè)長(zhǎng)度為2或1的有序子序列再兩兩合并，……如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止【實(shí)驗(yàn)】歸并排序程序【歸納總結(jié)】教學(xué)重難點(diǎn)是對(duì)順序棧及其操作的理解。【課外學(xué)習(xí)要求】完成四級(jí)項(xiàng)目第三階段：學(xué)生信息按順序棧存儲(chǔ)實(shí)現(xiàn)?！菊n后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。教學(xué)設(shè)計(jì)【教學(xué)進(jìn)程安排】重點(diǎn)設(shè)計(jì)教學(xué)步驟與具體內(nèi)容安排。一、課外學(xué)習(xí)講評(píng)講評(píng)習(xí)題。二、內(nèi)容導(dǎo)入三、主要內(nèi)容設(shè)計(jì)1.【討論】學(xué)生分組演示三級(jí)項(xiàng)目（1）演示+講解（2）評(píng)委組提問(wèn)：小組回答問(wèn)題（3）評(píng)委打分2.【講授】教師講評(píng)（1）公布名次（2）講評(píng)三級(jí)項(xiàng)目的完成情況（3）總結(jié)學(xué)生完成的三級(jí)項(xiàng)目的優(yōu)缺點(diǎn)（4）布置假期改進(jìn)方案【歸納總結(jié)】對(duì)所有作品進(jìn)行講評(píng)?！菊n外學(xué)習(xí)要求】完成教材習(xí)題及復(fù)習(xí)，準(zhǔn)備好期末考試【課后分析及改進(jìn)】教學(xué)團(tuán)隊(duì)對(duì)課程/項(xiàng)目教學(xué)設(shè)計(jì)的可行性、知識(shí)與能力指標(biāo)的達(dá)成度、教與學(xué)環(huán)節(jié)的設(shè)計(jì)、教學(xué)重點(diǎn)與難點(diǎn)的把握、教學(xué)方法手段的有效性、師生雙邊活動(dòng)的設(shè)計(jì)、課內(nèi)與課外的結(jié)合、教與學(xué)的效果等課堂教學(xué)過(guò)程情況進(jìn)行總結(jié)與分析，共同研討確定改進(jìn)措施與方案。注釋：教學(xué)設(shè)計(jì)按每次課2學(xué)時(shí)撰寫。單元教案首頁(yè)單元CU（6）學(xué)時(shí)4周次第16教學(xué)周教學(xué)環(huán)境設(shè)計(jì)與組織安排課堂，筆記本電腦，小組合作單元名稱查找單元項(xiàng)目名稱常用的查找算法實(shí)現(xiàn)教學(xué)目標(biāo)及達(dá)成度理論知識(shí)理解并掌握常用查找算法的思想和實(shí)現(xiàn)方法專業(yè)技能具有較強(qiáng)的技術(shù)文檔寫作能力具有科技資料與文獻(xiàn)的收集與檢索能力具有自我學(xué)習(xí)能力及新技術(shù)開發(fā)與研究的能力職業(yè)道德具有正直并勇于負(fù)責(zé)的職業(yè)道德和敬業(yè)精神具備一名優(yōu)秀工程師的基本素質(zhì)教