PAGE35《數(shù)據(jù)結(jié)構(gòu)JAVA語言版》教案課次：1學(xué)時(shí)：2章節(jié)第1章緒論：1.1什么是數(shù)據(jù)結(jié)構(gòu)、1.2基本概念和術(shù)語教學(xué)目的和教學(xué)要求了解數(shù)據(jù)結(jié)構(gòu)的課程性質(zhì)、內(nèi)容、應(yīng)用領(lǐng)域及其與其他學(xué)科的關(guān)系；掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語；掌握四類基本的數(shù)據(jù)關(guān)系。教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語教學(xué)難點(diǎn)：四類基本的數(shù)據(jù)關(guān)系教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：計(jì)算機(jī)的應(yīng)用不再局限于科學(xué)計(jì)算，更多地用于控制，管理，數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。計(jì)算機(jī)加工處理的對象：數(shù)值，字符，表格，圖形聲音，圖象等具有一定結(jié)構(gòu)的數(shù)據(jù)。進(jìn)行程序設(shè)計(jì)時(shí)必須分析待處理的對象的特性及各對象之間存在的關(guān)系———產(chǎn)生背景。1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語1.數(shù)據(jù)（Data）2.數(shù)據(jù)元素（DataElement）3.數(shù)據(jù)對象（DataObject）4.結(jié)構(gòu)（DataStructure）存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(AbstractDataType)ADT的定義格式不唯一,我們采用下述格式定義一個(gè)ADT:ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象:<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系:<結(jié)構(gòu)關(guān)系的定義>基本操作:<基本操作的定義>}ADT抽象數(shù)據(jù)類型名教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)要求理解和掌握四類基本的數(shù)據(jù)關(guān)系；并在日常生活中舉例進(jìn)行說明。課后自我總結(jié)分析備注教案課次：2學(xué)時(shí)：2章節(jié)第1章：1.3抽象數(shù)據(jù)類型的表現(xiàn)與實(shí)現(xiàn)1.4算法和算法分析教學(xué)目的和教學(xué)要求理解抽象數(shù)據(jù)類型的表示及實(shí)現(xiàn)；對算法、算法要求、算法效率的度量進(jìn)行有效的分析。教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：抽象數(shù)據(jù)類型的表示及實(shí)現(xiàn)；算法、算法要求；教學(xué)難點(diǎn)：算法效率的度量及有效的分析；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4算法1.算法（Algorithm）的定義Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.(算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。)是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。2.算法的特性3.算法設(shè)計(jì)的要求１）算法的正確性(1)所設(shè)計(jì)的程序沒有語法錯(cuò)誤；(2)所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；(3)所設(shè)計(jì)的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。(4)程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。2）可讀性3）健壯性4）高效率和低存儲量、算法、語言和程序的關(guān)系教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1、從鍵盤接受兩個(gè)整數(shù)，輸出這兩個(gè)整數(shù)的最小公倍數(shù)和最大公約數(shù)。請嘗試用不同的算法實(shí)現(xiàn)，并分析這些算法的時(shí)間效率與空間效率。2、從鍵盤接受10個(gè)整數(shù)，在屏幕輸出這10個(gè)整數(shù)的遞增有序序列。請嘗試用不同的算法實(shí)現(xiàn)，并分析這些算法的時(shí)間效率與空間效率。課后自我總結(jié)分析備注教案課次：3學(xué)時(shí)：2章節(jié)第2章線性表：2.1線性表的類型定義2.2線性表的順序表示教學(xué)目的和教學(xué)要求理解線性表的定義和特點(diǎn)；掌握順序表以達(dá)到利用基本算法進(jìn)行較復(fù)雜算法設(shè)計(jì)的目的。教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：線性表的定義和特點(diǎn)；線性表的順序表示教學(xué)難點(diǎn)：線性表的順序表示教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中，存在唯一的一個(gè)被稱為“第一個(gè)”的數(shù)據(jù)元素；存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素；除第一個(gè)元素之外，集合中的每個(gè)元素均只有一個(gè)前驅(qū)；除最后一個(gè)元素之外，集合中的每個(gè)元素均只有一個(gè)后繼。2.1線性表的類型定義2.1.1線性表的邏輯結(jié)構(gòu)2.1.2線性表的抽象數(shù)據(jù)類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.2.1線性表的順序存儲結(jié)構(gòu)2.2.2線性表順序存儲結(jié)構(gòu)上的基本運(yùn)算1.初始化操作2.插入操作3.刪除操作教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)順序存儲方式下，建立線性表（12，13，24，28，30，42，77）并輸出，在線性表的第五個(gè)位置插入數(shù)據(jù)元素25，然后刪除線性表中的第四個(gè)數(shù)據(jù)元素，輸出變化后的線性表,最后清空線性表。課后自我總結(jié)分析備注教案課次：4學(xué)時(shí)：2章節(jié)第2章：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（1）教學(xué)目的和教學(xué)要求理解線性表的鏈表的特點(diǎn)，掌握在這種存儲結(jié)構(gòu)上各種基本運(yùn)算的實(shí)現(xiàn)算法以及效率的分析，并學(xué)習(xí)在這種存儲結(jié)構(gòu)上進(jìn)行算法設(shè)計(jì)的方法；以達(dá)到利用基本算法進(jìn)行較復(fù)雜算法設(shè)計(jì)的目的。教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)；教學(xué)難點(diǎn)：單鏈表的插入、刪除、查找和歸并操作；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1單鏈表線性表的鏈?zhǔn)酱鎯Γ簣D2.6單鏈表的邏輯狀態(tài)圖2.7帶頭結(jié)點(diǎn)單鏈表圖示2.3.2單鏈表上的基本運(yùn)算1.建立單鏈表2.查找3.單鏈表插入操作4.刪除5．合并單鏈表：教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)鏈?zhǔn)酱鎯Ψ绞较拢⒕€性表（12，13，24，28，30，42，77）并輸出，在線性表的第五個(gè)位置插入數(shù)據(jù)元素25，然后刪除線性表中的第四個(gè)數(shù)據(jù)元素，輸出變化后的線性表,最后清空線性表。課后自我總結(jié)分析備注教案課次：5學(xué)時(shí)：2章節(jié)第2章：2.3（2）2.4一元多項(xiàng)式的表示及相加教學(xué)目的和教學(xué)要求理解線性表的鏈表的特點(diǎn)，掌握在這種存儲結(jié)構(gòu)上各種基本運(yùn)算的實(shí)現(xiàn)算法以及效率的分析；掌握一元多項(xiàng)式的表示及相加的方法與算法。教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：循環(huán)鏈表、雙向鏈表及其算法；一元多項(xiàng)式的表示及相加的方法與算法；教學(xué)難點(diǎn)：雙向鏈表及其算法、一元多項(xiàng)式相加的方法；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：2.3.3循環(huán)鏈表2.3.4雙向鏈表1.雙向鏈表的前插操作2.雙向鏈表的刪除操作2.3.6順序表和鏈表的比較1.基于空間的考慮、2.基于時(shí)間的考慮、3.基于語言的考慮2.4一元多項(xiàng)式的表示及相加教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)開發(fā)一個(gè)多項(xiàng)式運(yùn)算系統(tǒng)，功能至少包含多項(xiàng)式的相加、相減、相乘。課后自我總結(jié)分析備注教案課次：6學(xué)時(shí)：2章節(jié)第3章棧和隊(duì)列：3.1棧、3.2.1數(shù)制轉(zhuǎn)換教學(xué)目的和教學(xué)要求理解棧的定義、特點(diǎn)，學(xué)習(xí)它的各種組織方式及算法；掌握它的空和滿的判斷條件；并學(xué)會它的簡單應(yīng)用。教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：棧的定義、特點(diǎn)，學(xué)習(xí)它的各種組織方式及算法；教學(xué)難點(diǎn)：棧的簡單應(yīng)用；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：3.1棧3.1.1棧的定義3.1.2棧的表示和實(shí)現(xiàn)1.順序棧順序棧基本操作的實(shí)現(xiàn):初始化、(2)取棧頂元素、(3)入棧、(4)出棧2.鏈棧3.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)從鍵盤輸入一個(gè)十進(jìn)制數(shù)，輸出與其等值的八進(jìn)制數(shù)。課后自我總結(jié)分析備注教案課次：7學(xué)時(shí)：2章節(jié)第3章棧和隊(duì)列：3.4隊(duì)列教學(xué)目的和教學(xué)要求掌握隊(duì)列的數(shù)據(jù)結(jié)構(gòu)和鏈隊(duì)列的相關(guān)操作；掌握循環(huán)隊(duì)列的相關(guān)內(nèi)容；教學(xué)重點(diǎn)、難點(diǎn)教學(xué)重點(diǎn)：列的數(shù)據(jù)結(jié)構(gòu)和鏈隊(duì)列的相關(guān)操作；教學(xué)難點(diǎn)：循環(huán)隊(duì)列的相關(guān)操作；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：3.4隊(duì)列3.4.1隊(duì)列的定義隊(duì)列(Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出(FistInFistOut，縮寫為FIFO)的特性。在隊(duì)列中，允許插入的一端叫做隊(duì)尾(rear)，允許刪除的一端則稱為隊(duì)頭(front)。3.4.2隊(duì)列的表示和實(shí)現(xiàn)鏈隊(duì)列:（1）初始化操作、（2）銷毀隊(duì)列、（3）入隊(duì)操作、（4）出隊(duì)操作3.4.3：循環(huán)隊(duì)列如何區(qū)分隊(duì)列“空”和“滿”另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列是空還是滿；少用一個(gè)元素空間，當(dāng)隊(duì)列頭指針在隊(duì)列尾指針的下一個(gè)位置上時(shí)為“滿”。當(dāng)Q.front=Q.rear時(shí)隊(duì)空；Q.front+1=Q.rear時(shí)隊(duì)滿循環(huán)隊(duì)列滿足條件(Q.rear+1)%MAXQSIZE==Q.front隊(duì)滿教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)利用棧和隊(duì)列實(shí)現(xiàn)判斷一個(gè)字符串是否是回文。隊(duì)列的基本操作算法、循環(huán)隊(duì)列的基本操作算法；課后自我總結(jié)分析備注教案課次：8學(xué)時(shí)：2章節(jié)第4章串：4.1串的定義、4.2.1定長順序存儲表示4.2.3串的塊鏈存儲表示4.3.1求子串位置的定位函數(shù)教學(xué)目的和教學(xué)要求掌握串的定義、定長順序存儲表示；了解串的塊鏈存儲表示；掌握求子串位置的定位函數(shù)（模式匹配算法）；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：串的定義、定長順序存儲表示；串的塊鏈存儲表示；教學(xué)難點(diǎn)：求子串位置的定位函數(shù)（模式匹配算法）；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：串的定義串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記為：S=′a1a2...an′(n≥0)串的順序存儲定義串的順序存儲把字符串中的數(shù)據(jù)元素存儲在一組編號連續(xù)的的存儲單元中，在Java語言中就是把字符串中的數(shù)據(jù)元素存放在char類型的一維數(shù)組中。順序串源碼實(shí)現(xiàn)教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)利用Java中的String類實(shí)現(xiàn)判斷一個(gè)字符串是否是回文。課后自我總結(jié)分析備注教案課次：9學(xué)時(shí)：2章節(jié)第5章數(shù)組和廣義表：5.1數(shù)組的定義、5.2數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)目的和教學(xué)要求掌握數(shù)組的定義、數(shù)組的順序表示和實(shí)現(xiàn)；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：數(shù)組的定義、數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)難點(diǎn)：數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：5.1數(shù)組的定義數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。對于數(shù)組的操作一般只有兩類：(1）獲得特定位置的元素值；(2）修改特定位置的元素值。5.2數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組一般不做插入和刪除操作，因此采用順序存儲結(jié)構(gòu)。由于存儲單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，則用一組連續(xù)存儲單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問題。數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，另一種是按列序存儲。Loc［i,j］=Loc［1,1］+n×(i-1)+(j-1)Loc［i,j,k］=Loc［1,1,1］+(i-1)×m×n+(j-1)×n+(k-1)對于ｎ維數(shù)組A(c1∶d1,c2∶d2，…,cn∶dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲地址的計(jì)算公式:LOC(aj1j2…jn)=LOC(a00…0)+(b2*b3*…*bn*j1+b3*…*bn*j2+…+bn*jn-1+jn)*lLOC(aj1j2…jn)=LOC(a00…0)+(=LOC(a00…0)+其中cn=L,ci-1=bi*ci教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)計(jì)算1-3維數(shù)組的任意元素的存儲地址；課后自我總結(jié)分析備注教案課次：10學(xué)時(shí)：2章節(jié)第5章數(shù)組和廣義表：5.3矩陣的壓縮存儲5.3.1特殊矩陣、5.3.2稀疏矩陣教學(xué)目的和教學(xué)要求掌握特殊矩陣和稀疏矩陣的存儲方法；掌握稀疏矩陣的轉(zhuǎn)置算法；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：特殊矩陣和稀疏矩陣的存儲方法；稀疏矩陣的轉(zhuǎn)置算法；教學(xué)難點(diǎn)：稀疏矩陣的轉(zhuǎn)置算法；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：5.3矩陣的壓縮存儲壓縮存儲：為多個(gè)值相同的元素只分配一個(gè)存儲空間，對零元素不分配空間。特殊矩陣：值相同的元素或零元素在矩陣中的分布有一定的規(guī)律。稀疏矩陣：矩陣中元素分布沒有規(guī)律，但零元素較多。5.3.1特殊矩陣三角矩陣大體分為三類：下三角矩陣、上三角矩陣和對稱矩陣Loc［i,j］=Loc［1,1］+i(i-1)/2+j-1帶狀矩陣5.3.2稀疏矩陣方法一：按照b.data中三元組的次序依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。方法二：按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中的恰當(dāng)位置。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：下三角、對稱、帶狀矩陣的數(shù)據(jù)元素的下標(biāo)地址的計(jì)算方法；2：稀疏矩陣的兩個(gè)轉(zhuǎn)置算法；課后自我總結(jié)分析備注教案課次：11學(xué)時(shí)：2章節(jié)第6章樹：6.1樹的定義和基本術(shù)語、6.2二叉樹、6.2.1二叉樹的定義、6.2.2二叉樹的性質(zhì)；教學(xué)目的和教學(xué)要求熟練掌握樹的定義和基本術(shù)語、熟練掌握二叉樹的定義及二叉樹的性質(zhì)；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：樹的定義和基本術(shù)語、二叉樹的定義；教學(xué)難點(diǎn)：二叉樹的性質(zhì)；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：6.1樹的定義和基本術(shù)語樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n>0時(shí)，該集合滿足如下條件：(1)其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。(2)其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m≥0）個(gè)互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。6.2二叉樹的定義6.2.1二叉樹的定義定義：我們把滿足以下兩個(gè)條件的樹形結(jié)構(gòu)叫做二叉樹（BinaryTree）：（1）每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即度都不大于2）；（2）二叉樹的子樹有左右之分，其次序不能任意顛倒。6.2.2二叉樹的性質(zhì)滿二叉樹：完全二叉樹：深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1~n的位置序號分別與滿二叉樹的結(jié)點(diǎn)1~n的位置序號一一對應(yīng)，則為完全二叉樹。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：二叉樹的基本形態(tài)；2：二叉樹的五個(gè)性質(zhì)；課后自我總結(jié)分析備注教案課次：12學(xué)時(shí)：2章節(jié)第6章樹和二叉樹：6.2.3二叉樹的存儲結(jié)構(gòu)、6.3.1遍歷二叉樹；教學(xué)目的和教學(xué)要求熟練掌握二叉樹的兩種存儲結(jié)構(gòu)；熟練掌握二叉樹的三種遍歷方法；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：二叉樹的兩種存儲結(jié)構(gòu)、二叉樹的三種遍歷方法；教學(xué)難點(diǎn)：二叉樹的三種遍歷方法；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：6.2.3二叉樹的存儲結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。二叉樹的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1：順序存儲結(jié)構(gòu)2.鏈?zhǔn)酱鎯Y(jié)構(gòu)對于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子：二叉樹的遍歷三種遍歷方法的遞歸定義。·先序遍歷（DLR）操作過程：若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作：(1)訪問根結(jié)點(diǎn)；(2)按先序遍歷左子樹；(3)按先序遍歷右子樹。·中序遍歷（LDR）操作過程：若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作：(1)按中序遍歷左子樹；(2)訪問根結(jié)點(diǎn)；(3)按中序遍歷右子樹。·后序遍歷（LRD）操作過程：若二叉樹為空，則空操作，否則依次執(zhí)行如下3個(gè)操作：(1)按后序遍歷左子樹；(2)按后序遍歷右子樹；(3)訪問根結(jié)點(diǎn)。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：對一些特殊樣式的二叉樹進(jìn)行順序存儲；2：對二叉樹進(jìn)行三種遍歷操作；課后自我總結(jié)分析備注教案課次：13學(xué)時(shí)：2章節(jié)第6章6.4樹和森林：6.4.1樹的存儲結(jié)構(gòu)、6.4.2森林與二叉樹的轉(zhuǎn)換、6.4.3樹和森林的遍歷教學(xué)目的和教學(xué)要求熟練掌握樹的三種存儲結(jié)構(gòu)；熟練掌握森林與二叉樹的轉(zhuǎn)換；熟練掌握樹和森林的遍歷；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：樹的三種存儲結(jié)構(gòu)、森林與二叉樹的轉(zhuǎn)換；教學(xué)難點(diǎn)：樹和森林的遍歷；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：6.4樹和森林6.4.1樹的存儲結(jié)構(gòu)樹的主要存儲方法有以下三種：雙親表示法、2.孩子表示法、3.孩子兄弟表示法6.4.2森林與二叉樹的轉(zhuǎn)換1.樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是：(1)樹中所有相鄰兄弟之間加一條連線。(2)對樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。(3)以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。2.森林轉(zhuǎn)換為二叉樹森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹，森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下：（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。3.二叉樹還原為樹或森林6.4.3樹的遍歷1.樹的遍歷：樹的遍歷方法主要有以下兩種：1）先根遍歷、2）后根遍歷2.森林的遍歷：森林的遍歷方法主要有以下三種：1）先序遍歷、2）中序遍歷、3）后序遍歷教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：把樹用三種方法存儲；2：把樹和森林與二叉樹進(jìn)行相互轉(zhuǎn)換；3：對樹和森林進(jìn)行遍歷；課后自我總結(jié)分析備注教案課次：14學(xué)時(shí)：2章節(jié)第6章6.6赫夫曼樹及其應(yīng)用、6.6.1最優(yōu)二叉樹（赫夫曼樹）、6.6.2赫夫曼編碼教學(xué)目的和教學(xué)要求熟練掌握哈夫曼樹的構(gòu)造方法；熟練掌握哈夫曼編碼的編碼方法；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：哈夫曼樹的構(gòu)造方法；教學(xué)難點(diǎn)：哈夫曼編碼的編碼方法；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：6.6赫夫曼樹及其應(yīng)用6.6.1最優(yōu)二叉樹1.路徑和路徑長度2.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度3.樹的帶權(quán)路徑長度構(gòu)造赫夫曼算法的步驟如下：（1）用給定的n個(gè)權(quán)值{w1,w2,…,wn}對應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森林F={T1,T2,…,Tn}，其中每一棵二叉樹Ti(1≤i≤n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空。（2）在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和。（3）從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹加入到森林F中。（4）重復(fù)（2）、（3）操作，直到森林中只含有一棵二叉樹為止，此時(shí)得到的這棵二叉樹就是赫夫曼樹。6.6.2赫夫曼編碼前綴編碼：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，可利用二叉樹設(shè)計(jì)前綴編碼。6.6.3赫夫曼編碼算法的實(shí)現(xiàn)教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：構(gòu)造哈夫曼樹；2：生成哈夫曼編碼；課后自我總結(jié)分析備注教案課次：15學(xué)時(shí)：2章節(jié)綜合習(xí)題（三）：樹與二叉樹的相關(guān)內(nèi)容；教學(xué)目的和教學(xué)要求要求熟練掌握樹、二叉樹、森林的相關(guān)存儲、遍歷、轉(zhuǎn)換的知識；能夠構(gòu)造哈夫曼樹、哈夫曼編碼；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：1：已知某二叉樹的先序遍歷和中序遍歷分別為：先序：18147311223527中序：37111418222735；求該二叉樹。2：已知某二叉樹的先序遍歷和中序遍歷分別為：先序：EBADCFHGIKJ中序：ABCDEFGHIJK；畫出該二叉樹。3已知某樹的先根遍歷和后根遍歷分別為：先根：GFKDAIEBCHJ后根：DIAEKFCJHBG、畫出該樹。4：數(shù)據(jù)傳輸中的二進(jìn)制編碼：要傳送數(shù)據(jù)state、seat、act、tea、cat、set、a、eat；如何使傳送的長度最短。（構(gòu)造哈夫曼樹、求出各個(gè)數(shù)據(jù)的哈夫曼編碼。）5：假設(shè)有一臺機(jī)器共有7種不同的指令，其使用頻率如表所示：求出各個(gè)指令的哈夫曼編碼。6：求出滿足下列條件的所有二叉樹：1：先序和后序相同；2：中序和后序相同；3：先序和中序相同；7：假設(shè)用于用于通訊的電文由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07、0.19、0.02、0.060.32、0.03、0.21、0.10；請為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。8：畫出和下列樹對應(yīng)的二叉樹：9：已知某二叉樹的先序建立時(shí)讀入的數(shù)據(jù)為：ABCΦΦDΦΦEFGΦΦΦHΦΦ；請求出該二叉樹。課后自我總結(jié)分析教案課次：16學(xué)時(shí)：2章節(jié)第7章圖：7.1圖的定義和術(shù)語教學(xué)目的和教學(xué)要求熟練掌握和理解有關(guān)圖的各種定義和術(shù)語；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：圖的各種定義和術(shù)語；教學(xué)難點(diǎn)：圖的生成樹、圖的連通性；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：7.1圖的定義與基本術(shù)語7.1.1圖的定義數(shù)據(jù)元素通常稱為頂點(diǎn)（vertex），VR是兩個(gè)頂點(diǎn)之間關(guān)系的集合。P（x，y）表示x和y之間有特定的關(guān)聯(lián)屬性P。若<x，y>∈VR，則<x，y>表示從頂點(diǎn)x到頂點(diǎn)y的一條弧（arc），并稱x為弧尾（tail）或起始點(diǎn)，稱y為弧頭（head）或終端點(diǎn)，此時(shí)圖中的邊是有方向的，稱這樣的圖為有向圖。若<x，y>∈VR，必有<y，x>∈VR，即VR是對稱關(guān)系，這時(shí)以無序?qū)Γ▁，y）來代替兩個(gè)有序?qū)Γ硎緓和y之間的一條邊（edge），此時(shí)的圖稱為無向圖。基本術(shù)語1:完全圖、稀疏圖與稠密圖2.子圖3.鄰接點(diǎn)4.度、入度和出度5.權(quán)與網(wǎng)6.路徑與回路7.連通圖8.生成樹一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖的全部頂點(diǎn)，只有n-1條邊（構(gòu)成樹的最小分支樹）若在一棵生成樹上添加一條邊必定構(gòu)成一個(gè)環(huán)。一棵有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊。若n個(gè)頂點(diǎn)小于n-1條邊，則必為非連通圖；多于n-1條邊一定有環(huán)，但僅有n-1條邊的圖不一定生成樹。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：無向圖及其連通分量；2：圖的生成樹；課后自我總結(jié)分析備注教案課次：17學(xué)時(shí)：4章節(jié)第7章圖：7.2圖的存儲結(jié)構(gòu)、7.2.1數(shù)組表示法、7.2.2鄰接表；7.2.3十字鏈表、7.2.4鄰接多重表；教學(xué)目的和教學(xué)要求理解和熟練掌握圖的四種存儲結(jié)構(gòu)；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：數(shù)組表示法、鄰接表、十字鏈表、鄰接多重表；教學(xué)難點(diǎn)：鄰接多重表；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：7.2圖的存儲結(jié)構(gòu)7.2.1鄰接矩陣表示法圖的鄰接矩陣表示法（AdjacencyMatrix）也稱作數(shù)組表示法。它采用兩個(gè)數(shù)組來表示圖：一個(gè)是用于存儲頂點(diǎn)信息的一維數(shù)組；另一個(gè)是用于存儲圖中頂點(diǎn)之間關(guān)聯(lián)關(guān)系的二維數(shù)組，這個(gè)關(guān)聯(lián)關(guān)系數(shù)組被稱為鄰接矩陣。7.2.2鄰接表表示法十字鏈表7.2.4鄰接多重表教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：數(shù)組表示法表示圖；2：鄰接表表示圖；3：十字鏈表表示圖；4：鄰接多重表表示圖；課后自我總結(jié)分析教案課次：18學(xué)時(shí)：2章節(jié)第7章圖：7.3：圖的遍歷；7.4：圖的連通性問題；教學(xué)目的和教學(xué)要求熟練掌握圖的遍歷操作；數(shù)量掌握求圖的連通分量的問題和最小生成樹的問題；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：圖的遍歷操作、求圖的連通分量的問題；教學(xué)難點(diǎn)：最小生成樹的問題；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：7.3圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪問圖中每一個(gè)結(jié)點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次圖的遍歷是圖的連通性問題，拓?fù)渑判颍箨P(guān)鍵路徑等的基礎(chǔ)。7.3.1深度優(yōu)先搜索采用遞歸的形式說明，則深度優(yōu)先搜索連通子圖的基本思想可表示為：（1）訪問出發(fā)點(diǎn)v0。（2）依次以v0的未被訪問的鄰接點(diǎn)為出發(fā)點(diǎn)，深度優(yōu)先搜索圖，直至圖中所有與v0有路徑相通的頂點(diǎn)都被訪問。7.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想是：（1）從圖中某個(gè)頂點(diǎn)v0出發(fā)，首先訪問v0。（2）依次訪問v0的各個(gè)未被訪問的鄰接點(diǎn)。（3）分別從這些鄰接點(diǎn)（端結(jié)點(diǎn)）出發(fā)，依次訪問它們的各個(gè)未被訪問的鄰接點(diǎn)（新的端結(jié)點(diǎn)）。7.4圖的連通性問題7.4.1無向圖的連通分量7.4.3最小生成樹應(yīng)用：如何在最節(jié)省經(jīng)費(fèi)的前提下建立通信網(wǎng)。我們可以利用MST性質(zhì)來生成一個(gè)連通網(wǎng)的最小生成樹。普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法便是利用了這個(gè)性質(zhì)。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：對圖進(jìn)行普里姆算法操作，求出最小生成樹；2：對圖進(jìn)行克魯斯卡爾算法操作，求出最小生成樹；課后自我總結(jié)分析備注教案課次：19學(xué)時(shí)：2章節(jié)第7章圖：7.5.1：拓?fù)渑判颍?.5.2：關(guān)鍵路徑；7.6.1：最短路徑問題教學(xué)目的和教學(xué)要求理解和熟練掌握圖的拓?fù)渑判虻姆椒ǎ焕斫夂驼莆涨蠼鈭D的關(guān)鍵路徑的問題；教學(xué)重點(diǎn)難點(diǎn)教學(xué)重點(diǎn)：圖的拓?fù)渑判虻姆椒ǎ粓D的關(guān)鍵路徑的問題；最短路徑問題；教學(xué)難點(diǎn)：圖的關(guān)鍵路徑的問題；最短路徑問題；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：7.5有向無環(huán)圖的應(yīng)用7.5.1拓?fù)渑判颍═opologicalSort）用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向無環(huán)圖，稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（ActivityOnVertexNetwork），簡稱為AOV-網(wǎng)。7.5.2關(guān)鍵路徑有向圖在工程計(jì)劃和經(jīng)營管理中有著廣泛的應(yīng)用。通常用有向圖來表示工程計(jì)劃時(shí)有兩種方法：·用頂點(diǎn)表示活動(dòng)，用有向弧表示活動(dòng)間的優(yōu)先關(guān)系，即上節(jié)所討論的AOV-網(wǎng)。·用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需要的時(shí)間。我們把用第二種方法構(gòu)造的有向無環(huán)圖叫做邊表示活動(dòng)的網(wǎng)（ActivityOnEdgeNetwork）,簡稱AOE-網(wǎng)。7.6.1求某一頂點(diǎn)到其它各頂點(diǎn)的最短路徑教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：給定圖的拓?fù)渑判虻膯栴}求解；2：給定圖的關(guān)鍵路徑的問題求解；3：給定圖的最短路徑的問題求解；課后自我總結(jié)分析教案課次：20學(xué)時(shí)：2章節(jié)綜合習(xí)題課（3）：圖的相關(guān)內(nèi)容教學(xué)目的和教學(xué)要求熟練掌握圖這一章的所有知識點(diǎn)的相關(guān)練習(xí)題；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、教學(xué)方法、輔助手段）教學(xué)進(jìn)程：1：求圖的鄰接矩陣和十字鏈表；2：求解圖的深度、廣度優(yōu)先搜索過程；3：用兩種方法構(gòu)造最小生成樹；4：對于