《數(shù)據(jù)結(jié)構(gòu)》教案664282-

1、第一章：緒論1.1 數(shù)據(jù)結(jié)構(gòu)概念教學(xué)目的：理解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要意義掌握數(shù)據(jù)結(jié)構(gòu)的根本概念知識要點(diǎn)：數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法4技能要點(diǎn)：數(shù)據(jù)結(jié)構(gòu)、44教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P11；1、2課后分析與小結(jié)：本節(jié)課的重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)有關(guān)概念和術(shù)難點(diǎn)：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 11數(shù)值計算問題2非數(shù)值性問題2非數(shù)值問題求解算法+數(shù)據(jù)結(jié)構(gòu)=程序數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)算法：是對數(shù)據(jù)運(yùn)算的描述有關(guān)概念和術(shù)語數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)的四種根本存儲方法1順序存儲方法2鏈接存儲方

2、法3索引存儲方法4散列存儲方法板書或旁注教 師 授 課 教 案第一章：緒論算法描述算法分析教學(xué)目的：理解算法的定義、特性、描述方法掌握簡單的時間復(fù)雜度的估計知識要點(diǎn)：算法的特性、描述方法、算法編制的質(zhì)量要求、數(shù)據(jù)結(jié)構(gòu)的根本操作、時間復(fù)雜度、空間復(fù)雜度、技能要點(diǎn)：描述算法、分析簡單算法的時間復(fù)雜度教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P11；3、4課后分析與小結(jié)：本節(jié)課的重點(diǎn)：算法的特點(diǎn)和描述，算法分析難點(diǎn)：算法時間復(fù)雜度的估計審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第一章：緒論板書或旁注算法特性(1)有窮性(2)確定性(3)可行性(4)輸入(5)輸出

3、好的算法的特點(diǎn)(1)正確(2)可讀 (3)健壯 (4)高數(shù)據(jù)結(jié)構(gòu)的根本操作：1查找2讀取3插入4刪除5修改算法描述算法描述的種類：1框圖/流程圖算法2非形式算法3偽語言算法4高級語言算法1.3 算法分析時間復(fù)雜度:解決某問題所花費(fèi)的時間大小，即程序運(yùn)行從開始到結(jié)束所需要的時間，記為 T (n)空間復(fù)雜度:解決某問題的程序完全運(yùn)行時所占用的存儲空間大小，記為 S (n)MatrixMultidyT(n)如(1.1)n教 師 授 課 教 案教學(xué)單元章節(jié)：C語言第七章：數(shù)組一維數(shù)組的定義和引用二維數(shù)組的定義和引用字符數(shù)組教學(xué)目的： 理解一維數(shù)組、二維數(shù)組、字符數(shù)組的定義掌握一維數(shù)組、二維數(shù)組、字符數(shù)

4、組的引用和初始化方法掌握一維數(shù)組、二維數(shù)組、字符數(shù)組的簡單應(yīng)用程序知識要點(diǎn)： 一維數(shù)組、二維數(shù)組、字符數(shù)組的定義、引用、初始化一維數(shù)組、二維數(shù)組、字符數(shù)組相關(guān)的簡單程序技能要點(diǎn)：用數(shù)組來處理相關(guān)問題的程序教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：課后分析與小結(jié)：本節(jié)重點(diǎn)：數(shù)組的定義、引用、初始化本節(jié)難點(diǎn)：用數(shù)組求解簡單的問題審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第七章數(shù)組板書或旁注一維數(shù)組的定義 一維數(shù)組的引用 二維數(shù)組的定義和引用二維數(shù)組的定義 二維數(shù)組的引用 字符數(shù)組字符數(shù)組的定義 字符數(shù)組的引用字符數(shù)組的輸入輸出教學(xué)單元章節(jié)：C語言第十章：指針地

5、址和指針的概念變量的指針和指針變量教學(xué)目的： 理解地址和指針的概念掌握指針變量的定義和引用知識要點(diǎn)： 地址、指針、指針變量的定義和引用、指針變量作為函數(shù)參數(shù)技能要點(diǎn)：指針變量的定義和引用指針變量作為函數(shù)參數(shù)教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P278；10.1課后分析與小結(jié)：本節(jié)重點(diǎn)：指針的含義、指針變量的引用本節(jié)難點(diǎn)：指針變量的引用、指針變量作為函數(shù)參數(shù)審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注C語言第十章：指針地址和指針的概念地址的概念指針的概念定義一個指針變量1.定義指針變量的一般形式基類型* 指針變量名指針變量的引用&*指針變量作為

6、函數(shù)參數(shù)(1)使一個指針變量指向另一個變量(2)通過指針變量訪問整型變量教 師 授 課 教 案教學(xué)單元章節(jié)：C語言第十章：指針指向數(shù)組元素的指針 字符串的表現(xiàn)形式指針運(yùn)算小結(jié)教學(xué)目的： 掌握通過指針引用數(shù)組元素理解字符串的表現(xiàn)形式掌握指針的相關(guān)運(yùn)算知識要點(diǎn)：數(shù)組與指針、字符串與指針、指針運(yùn)算技能要點(diǎn)：通過指針引用數(shù)組元素、字符串的表現(xiàn)形式指針的各種運(yùn)算教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P279；10.6 P279；10.9課后分析與小結(jié)：本節(jié)重點(diǎn)：指針運(yùn)算、通過指針引用數(shù)組元素和字符串本節(jié)難點(diǎn)：通過指針引用數(shù)組元素、字符串審 批：教研室主任簽字年月日抽 查：系部主任簽字年月

7、日教學(xué)內(nèi)容及過程板書或旁注數(shù)組與指針指向數(shù)組元素的指針通過指針引用數(shù)組元素數(shù)組元素的引用可以用1. 下標(biāo)法: ai2. 指針法: *(a+i) 或 *(p+i)字符串與指針字符串的表現(xiàn)形式用字符數(shù)組存放一個字符串用字符指針指向一個字符串 3指針運(yùn)算小結(jié)有關(guān)指針的數(shù)據(jù)類型的小結(jié)指針運(yùn)算小結(jié)教 師 授 課 教 案教學(xué)單元章節(jié)：C語言第十一章：結(jié)構(gòu)體與共用體11.1-11.5.1結(jié)構(gòu)體處理動態(tài)鏈表所需的函數(shù)11.10typedef教學(xué)目的：掌握結(jié)構(gòu)體變量的定義、引用和初始化掌握處理動態(tài)鏈表所需的函數(shù)掌握用 typedef 定義類型結(jié)構(gòu)體變量、結(jié)構(gòu)體數(shù)組，malloccallocfreetypedef

8、技能要點(diǎn)：結(jié)構(gòu)體變量的定義、引用和初始用typedef定義類型教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：課后分析與小結(jié)：本節(jié)重點(diǎn)：結(jié)構(gòu)體變量、處理動態(tài)鏈表所需的函數(shù)本節(jié)難點(diǎn)：結(jié)構(gòu)體變量的引用和初始化、用 typedef 定義類型審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日11.1 概述教學(xué)內(nèi)容及過程第十一章：結(jié)構(gòu)體與共用體板書或旁注先定義結(jié)構(gòu)體類型，再用類型標(biāo)識去定義變量定義類型的同時定義變量3. 直接定義結(jié)構(gòu)體類型變量結(jié)構(gòu)體變量的引用結(jié)構(gòu)體變量各成員的引用引用形式：結(jié)構(gòu)體變量名 . 成員名結(jié)構(gòu)體變量各成員的輸入、輸出結(jié)構(gòu)體變量的初始化結(jié)構(gòu)體數(shù)組4.結(jié)構(gòu)體數(shù)組的引用指針與

9、結(jié)構(gòu)體指向結(jié)構(gòu)體變量的指針指向結(jié)構(gòu)體變量的指針與結(jié)構(gòu)體變量的等價關(guān)系用指針處理鏈表3處理動態(tài)鏈表所需的函數(shù)內(nèi)存分配函數(shù)原型： void *malloc(unsigned size); 內(nèi)存分配函數(shù)原型： void *calloc(unsigned size); 內(nèi)存釋放函數(shù)原形：void free(void *p);11.10typedef1、使用的一般形式：typedef原類型名新類型名；typedef：int n100；將變量名換成新類型名：intNUM；在最前面加上typedef:typedefintNUM；用新類型名來定義變量：NUM3.用typedef定義類型的說明：(1)typed

10、eftypedef創(chuàng)造新的類型。(3) typedef 有利于程序的通用與移植。教 師 授 課 教 案第二章：線性表線性表的邏輯結(jié)構(gòu)線性表的順序存儲及操作實(shí)現(xiàn)教學(xué)目的：理解順序表的定義、特點(diǎn)及其主要操作掌握插入與刪除算法中數(shù)據(jù)元素的平均移動次數(shù)知識要點(diǎn)：線性表的定義、特點(diǎn)、根本操作順序表的定義、特點(diǎn)和存儲順序表的初始化、插入、刪除、查找操作，應(yīng)用舉例技能要點(diǎn)：線性表的邏輯結(jié)構(gòu)及根本操作線性表的順序存儲結(jié)構(gòu)及其根本操作實(shí)現(xiàn)教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P37；1P38；6課后分析與小結(jié)：本節(jié)重點(diǎn)：線性表的定義、特點(diǎn)和順序表的根本操作本節(jié)難點(diǎn)：順序表的插入和刪除算法及其時間

11、復(fù)雜度審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程線性表的實(shí)際例子線性表的定義線性表的根本操作初始化：Init_List(L)置空：Setnull_List(L)求長度：Length_List(L)取表元：Get_List(L,i)6.插入：Insert_List(L,x) 7.刪除：Delete_List(L,i)線性表的順序存儲結(jié)構(gòu)順序表的根本算法實(shí)現(xiàn)L插入刪除按值查找板書或旁注教 師 授 課 教 案教學(xué)單元章節(jié)：第二章：線性表單鏈表單鏈表上根本運(yùn)算的實(shí)現(xiàn)教學(xué)目的： 掌握單鏈表的定義、特點(diǎn)及存儲結(jié)構(gòu)掌握單鏈表的查找、插入與刪除算法理解帶首結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)知識要點(diǎn)：

12、 單鏈表的定義、特點(diǎn)、標(biāo)識、結(jié)點(diǎn)結(jié)構(gòu)和存儲結(jié)構(gòu)單鏈表的建立、求表長、查找、插入和刪除算法技能要點(diǎn)： 單鏈表的結(jié)點(diǎn)結(jié)構(gòu)和存儲結(jié)構(gòu)單鏈表的查找、插入與刪除算法教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P38；8課后分析與小結(jié)：本節(jié)重點(diǎn)：單鏈表的定義、特點(diǎn)和存儲結(jié)構(gòu)根本操作本節(jié)難點(diǎn)：單鏈表的查找、插入和刪除算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程2.3板書或旁注單鏈表單鏈表上的根本運(yùn)算的實(shí)現(xiàn)1頭部插入法建立2尾部插入法建立1帶頭結(jié)點(diǎn)的單鏈表2不帶頭結(jié)點(diǎn)的單鏈表1按序號查找2按值查找1后插節(jié)點(diǎn)2前插節(jié)點(diǎn)3插入運(yùn)算刪除操作(1)(2)教 師 授 課 教 案教學(xué)

13、單元章節(jié)：第二章：線性表循環(huán)鏈表雙向鏈表教學(xué)目的： 掌握單鏈表的定義、特點(diǎn)及存儲結(jié)構(gòu)掌握單鏈表的查找、插入與刪除算法理解帶首結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)知識要點(diǎn)： 循環(huán)鏈表和雙向鏈表的定義、特點(diǎn)、標(biāo)識、結(jié)點(diǎn)結(jié)構(gòu)兩個循環(huán)鏈表的連接、雙向鏈表中結(jié)點(diǎn)的插入和刪除順序表和鏈表的比擬技能要點(diǎn)： 兩個循環(huán)鏈表的連接算法雙向鏈表中結(jié)點(diǎn)的插入和刪除教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P38；7、9課后分析與小結(jié)：本節(jié)課的重點(diǎn)：循環(huán)鏈表和雙向鏈表的特點(diǎn)和根本操作難點(diǎn)：循環(huán)鏈表連接操作、雙向鏈表的插入和刪除審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程2.3.3循環(huán)鏈表一循環(huán)鏈表的定

14、二循環(huán)鏈表示意圖帶頭結(jié)點(diǎn)的單循環(huán)鏈表(2三循環(huán)鏈表的特四.循環(huán)鏈表的說明雙向循環(huán)鏈表一. 雙向鏈表的概念二. 雙鏈表示意圖三雙鏈表的類型定義四雙向鏈表的操作五. 順序表和鏈表的比擬板書或旁注教學(xué)單元章節(jié)：第三章：棧和隊列3.1 棧教學(xué)目的： 掌握棧的定義、特點(diǎn)和存儲結(jié)構(gòu)掌握順序棧和鏈棧的根本運(yùn)算理解棧與遞歸的關(guān)系知識要點(diǎn)： 上溢、下溢，?？张c棧滿的條件，棧與遞歸問題技能要點(diǎn)： 順序棧和鏈棧的置空、判棧空、入棧、出棧操作教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P63；1、3、4課后分析與小結(jié)：本節(jié)課的重點(diǎn)：順序棧和鏈棧的根本操難點(diǎn)：棧與遞歸問題審 批：教研室主任簽字年月日抽 查：系

15、部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注第三章：棧和隊列3.1 棧棧的定義和根本運(yùn)算棧：是限制僅在表尾進(jìn)行插入和刪除的線性表。1初始化棧：構(gòu)在一個空棧2置空棧：將 S 置成空棧3入棧：在棧頂插入一個新元素 X4出棧：刪除(彈出) 棧 S 的頂部元素5取棧頂)：取棧 S 的頂部元素6Empty_Stack (S)：棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)1順序棧的定義2順序棧根本運(yùn)算 置空棧 判空棧 入棧 出棧棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)1鏈棧的定義2鏈棧根本運(yùn)算 置空棧 判空棧 入棧 出棧棧與遞歸的實(shí)現(xiàn)1遞歸定義的數(shù)學(xué)函數(shù)2遞歸數(shù)據(jù)結(jié)構(gòu)的處理3遞歸求解方法1應(yīng)用遞歸算法的前提2Hanoi 塔問題的遞歸函數(shù)3Fibon

16、acci 數(shù)列的遞歸算法教 師 授 課 教 案第三章：棧和隊列棧的應(yīng)用舉例隊列隊列應(yīng)用舉例教學(xué)目的：掌握隊列的定義、特點(diǎn)和存儲結(jié)構(gòu)掌握循環(huán)隊列和鏈隊列的根本運(yùn)算理解循環(huán)隊列的意義和隊列的應(yīng)用知識要點(diǎn)：隊列的定義、特點(diǎn)、存儲結(jié)構(gòu)、根本運(yùn)算循環(huán)隊列產(chǎn)生的原因，循環(huán)隊列和鏈隊列的主要操作假溢出，循環(huán)隊列隊空與隊滿的條件技能要點(diǎn)：循環(huán)隊列隊空與隊滿的條件，循環(huán)隊列和鏈隊列的入隊、出隊、判隊空操作教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P63；2、5、9課后分析與小結(jié)：本節(jié)課的重點(diǎn)：循環(huán)隊列和鏈隊列的根本操難點(diǎn)：棧的應(yīng)用、循環(huán)隊列審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)

17、容及過程第三章：棧和隊列3.2 棧的應(yīng)用舉例隊列隊列的定義和根本運(yùn)算Init_Queue(Q)QIn_Queue(Q,x)xQOut_Queue(Q,x)QFront_Queue(Q,x)QEmpty_Queue (Q)判隊空隊列的存儲和運(yùn)算實(shí)現(xiàn) 1循環(huán)隊列：定義、存儲結(jié)構(gòu)和根本操作鏈隊列1定義、特點(diǎn)和存儲結(jié)構(gòu)2根本操作隊列應(yīng)用舉例板書或旁注教 師 授 課 教 案第四章：串和數(shù)組4.1 串教學(xué)目的：掌握串的定義、特點(diǎn)、相關(guān)術(shù)語和根本運(yùn)算了解串的存儲結(jié)構(gòu)及其根本運(yùn)算實(shí)現(xiàn)知識要點(diǎn)：串的定義、特點(diǎn)、相關(guān)術(shù)語和根本運(yùn)算串的順序存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)技能要點(diǎn)：串的根本運(yùn)算定長串連接、求子串和串比擬操作

18、教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P78；2、3課后分析與小結(jié)：本節(jié)重點(diǎn)：串的定義、存儲結(jié)構(gòu)和根本運(yùn)算本節(jié)難點(diǎn)：串連接、求子串和串比擬算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第四章：串和數(shù)組串串的根本概念串的根本運(yùn)算1求串長2串賦值3串連接4求子串5串比擬6串定位插入刪除串替換串的存儲結(jié)構(gòu)串的定長順序存儲結(jié)構(gòu)堆分配存儲結(jié)構(gòu)定長順序串根本運(yùn)算的實(shí)現(xiàn)1串連接2子串3串比擬板書或旁注教 師 授 課 教 案第四章：串和數(shù)組4.2 數(shù)組教學(xué)目的：了解數(shù)組的邏輯存儲結(jié)構(gòu)和內(nèi)存映像了解稀疏矩陣的定義及其數(shù)組實(shí)現(xiàn)數(shù)組與線性表、數(shù)組的邏輯存儲結(jié)構(gòu)和內(nèi)存映像稀疏

19、矩陣的定義、壓縮存儲方法、轉(zhuǎn)置技能要點(diǎn)：數(shù)組的內(nèi)存映像、數(shù)組元素地址的計算稀疏矩陣的存儲、轉(zhuǎn)置教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P78；5、6課后分析與小結(jié)：本節(jié)重點(diǎn)：數(shù)組的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、稀疏矩陣本節(jié)難點(diǎn)：稀疏矩陣的壓縮方法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第四章：串和數(shù)組數(shù)組板書或旁注數(shù)組的邏輯結(jié)構(gòu)1 1 維數(shù)組2 2 維數(shù)組數(shù)組的內(nèi)存映像以行為主以列為主1 1 維數(shù)組物理地址計算函數(shù)表達(dá)式22稀疏矩陣教 師 授 課 教 案第五章：樹和二叉樹5.1二叉樹的根本概念二叉樹的主要性質(zhì)教學(xué)目的：掌握樹的定義、特點(diǎn)和相關(guān)術(shù)語理解樹的根本操作

20、掌握二叉樹的定義、相關(guān)概念和主要性質(zhì)知識要點(diǎn)：樹的定義、特點(diǎn)、相關(guān)術(shù)語和根本操作二叉樹、完全二叉樹、滿二叉樹的定義完全二叉樹、滿二叉樹的性質(zhì)技能要點(diǎn)：樹的相關(guān)術(shù)語、樹的遍歷二叉樹、完全二叉樹、滿二叉樹二叉樹的結(jié)點(diǎn)個數(shù)、完全二叉樹的深度教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P107；1、2、8、9課后分析與小結(jié)：本節(jié)重點(diǎn)：樹和二叉樹的相關(guān)概念、二叉樹的性質(zhì)本節(jié)難點(diǎn)：二叉樹的主要性質(zhì)審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第五章：樹和二叉樹樹的定義和相關(guān)術(shù)語樹的根本操作(1)Initiate(tt。(2)Root(xxtx(4)Child(t，x，i)t

21、xix)tx stxi(7)Delete(t，x，i)txi(8)Traverse(t二叉樹二叉樹的根本概念二叉樹二叉樹的主要性質(zhì)1：層數(shù)與節(jié)點(diǎn)的關(guān)系2：深度與節(jié)點(diǎn)的關(guān)系3：24：完全二叉樹的深度與節(jié)點(diǎn)的關(guān)系性質(zhì) 5：完全二叉樹的相關(guān)性質(zhì)板書或旁注教 師 授 課 教 案第五章：樹和二叉樹二叉樹的根本操作與存儲實(shí)現(xiàn)二叉樹的遍歷教學(xué)目的：2理解二叉樹的根本操作掌握二叉樹的遍歷方法知識要點(diǎn)：二叉樹的順序存儲、二叉鏈表存儲、三叉鏈表存儲二叉樹的根本操作先序遍歷、中序遍歷、后序遍歷、層次遍歷技能要點(diǎn)：二叉樹的順序存儲、二叉樹鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)先序遍歷、中序遍歷、后序遍歷、層次遍歷二叉樹的過程教學(xué)方法：講

22、授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P107；3、4、5、6課后分析與小結(jié)：本節(jié)重點(diǎn)：二叉樹的存儲結(jié)構(gòu)和遍歷方法本節(jié)難點(diǎn)：先序、中序、后序遍歷二叉樹審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注第五章：樹和二叉樹二叉樹的根本操作與存儲實(shí)現(xiàn)1二叉鏈表存儲2三叉鏈表存儲(1)Initiatebt(2)Createx，lbt，rbt(3)InsertLbt，x，parent(4)DeleteLbt，parent(5)InsertRbt，x，parent(6)DeleteRbt，parent(7)serch bt，x(8)Traversebt二叉樹的遍歷教 師 授

23、 課 教 案第五章：樹和二叉樹5.3樹和森林教學(xué)目的：3掌握樹、森林與二叉樹的轉(zhuǎn)換方法掌握樹和森林的遍歷方法知識要點(diǎn)：樹的雙親表示法、孩子鏈表表示法、孩子兄弟表示法樹和森林轉(zhuǎn)換為二叉樹、二叉樹轉(zhuǎn)換為樹和森林樹的先根遍歷、后根遍歷，森林的先序遍歷、后序遍歷技能要點(diǎn)：二叉樹的順序存儲結(jié)構(gòu)、二叉樹鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)樹、森林與二叉樹的轉(zhuǎn)換過方法、樹和森林的遍歷教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P108；7、15、16課后分析與小結(jié)：本節(jié)重點(diǎn)：樹、森林與二叉樹的轉(zhuǎn)換、樹和森林的遍本節(jié)難點(diǎn)：樹的存儲樹、森林與二叉樹的轉(zhuǎn)換審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過

24、程板書或旁注第五章：樹和二叉樹樹和森林樹的存儲樹、森林與二叉樹的轉(zhuǎn)換樹和森林的遍歷1先根遍歷2后根遍歷1先序遍歷2后序遍歷教 師 授 課 教 案第五章：樹和二叉樹5.4最優(yōu)二叉樹哈夫曼樹教學(xué)目的：理解哈夫曼樹的相關(guān)定義掌握最優(yōu)二叉樹的構(gòu)建方法掌握哈夫曼編碼的定義和實(shí)現(xiàn)過程哈夫曼樹、帶權(quán)路徑長度、哈夫曼編碼、等長編碼、不等長編碼技能要點(diǎn)：構(gòu)造哈夫曼樹設(shè)計哈夫曼編碼教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P109；20、21課后分析與小結(jié)：本節(jié)重點(diǎn)：最優(yōu)二叉樹和哈夫曼編碼的構(gòu)造方法本節(jié)難點(diǎn)：帶權(quán)路徑、哈夫曼編碼審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第五章

25、：樹和二叉樹哈夫曼樹的根本概念哈夫曼樹的構(gòu)造算法1. 哈夫曼樹的構(gòu)造步驟哈夫曼編碼4. 哈夫曼編碼的構(gòu)造過程哈夫曼編碼的算法實(shí)現(xiàn)板書或旁注教 師 授 課 教 案教學(xué)單元章節(jié)：第六章：圖圖的根本概念圖的存儲表示教學(xué)目的： 掌握圖的定義和相關(guān)術(shù)語理解圖的根本操作掌握圖的兩種存儲結(jié)構(gòu)知識要點(diǎn)： 圖、無向圖、有向圖、完全圖、度、入度、出度、權(quán)和網(wǎng)路徑、回路、子圖、連通圖、強(qiáng)連通圖、生成樹圖的根本操作、鄰接矩陣、鄰接表技能要點(diǎn)：圖的相關(guān)術(shù)語、圖的鄰接矩陣的表圖的鄰接表的表示教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P138；1、24課后分析與小結(jié)：本節(jié)重點(diǎn)：圖的相關(guān)術(shù)語和存儲表示本節(jié)難點(diǎn)：鄰

26、接矩陣、鄰接表審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注第六章：圖圖的定義和術(shù)語1有向圖、無向圖、完全圖2頂點(diǎn)、邊、弧、弧頭、弧尾3度、入度、出度4權(quán)和網(wǎng)5路徑和路徑長度、回路、簡單路徑、簡單回路6子圖、連通圖、強(qiáng)連通圖7連通的、連通分量、強(qiáng)連通分量8生成樹、生成森林圖的根本操作1CreatgraphG2DestroyGraphG3GetVexG，v(4PutVexG，v，value5InsertvexG，v6DeletevexG，v7InsertArc G ，v，u 8DeleteArc G ，v，u9DFSTraverseG，v10BFSTtaverse

27、G，v11Locatevexg，v12FiirstAdjvexg，v13nextAdjvexg，v，w鄰接矩陣鄰接矩陣存儲結(jié)構(gòu)的定義鄰接表鄰接表存儲結(jié)構(gòu)的定義表示方法教 師 授 課 教 案教學(xué)單元章節(jié)：第六章：圖最小生成樹教學(xué)目的： 掌握圖的兩種遍歷方法理解最小生成樹的的相關(guān)概念掌握用 Prim 算法構(gòu)造最小生成樹的過程知識要點(diǎn)： 深度優(yōu)先搜索、廣度優(yōu)先搜索最小生成樹、 Prim技能要點(diǎn)：深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍用Prim算法構(gòu)造最小生成樹教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P138；3、5課后分析與小結(jié)：本節(jié)重點(diǎn)：圖的兩種遍歷、最小生成樹Prim審 批：教研室主任簽

28、字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第六章：圖圖的遍歷板書或旁注深度優(yōu)先搜索深度優(yōu)先搜索的定義廣度優(yōu)先搜索廣度優(yōu)先搜索的定義廣度優(yōu)先搜索的算法實(shí)現(xiàn)圖的應(yīng)用最小生成樹1 Prim2 Prim3 Prim 算法的 C 語言描述教 師 授 課 教 案教學(xué)單元章節(jié)：第六章：圖最短路徑拓?fù)渑判蚪虒W(xué)目的： 理解最短路徑問題和拓?fù)渑判虻囊饬xDijkstra了解拓?fù)渑判虻姆椒ㄖR要點(diǎn)： Dijkstra有向無環(huán)圖、AOV技能要點(diǎn)：用Dijkstra算法求單元最短路徑拓?fù)渑判蛩惴ń虒W(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P139；6課后分析與小結(jié)：本節(jié)重點(diǎn)：最短路徑問題和拓?fù)渑判虮竟?jié)難點(diǎn)

29、：Dijkstra 算法、拓?fù)渑判蛩惴▽?批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第六章：圖6.4 圖的應(yīng)用板書或旁注.2最短路徑2.單源最短路徑3.Dijkstra4.Dijkstra 算法的 C 語言實(shí)現(xiàn)6.4.3拓?fù)渑判蛴邢驘o環(huán)圖AVO拓?fù)渑判蛲負(fù)渑判虻母静襟E拓?fù)渑判虻乃惴ㄋ枷虢?師 授 課 教 案教學(xué)單元章節(jié)：第七章 查找根本概念和術(shù)語靜態(tài)查找表教學(xué)目的： 了解查找的概念和靜態(tài)查找表結(jié)構(gòu)理解順序查找和折半查找及其性能分析方法知識要點(diǎn)： 關(guān)鍵碼、查找表、平均查找長度順序查找、有序表的折半查找、分塊查找技能要點(diǎn)：順序查找、有序表的折半查找和分塊查找算法的根本思想教

30、學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P167： 1、3課后分析與小結(jié)：本節(jié)重點(diǎn)：順序查找、折半查找和分塊查找算法本節(jié)難點(diǎn)：折半查找算法的根本思想審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第七章 查找靜態(tài)查找表板書或旁注靜態(tài)查找表結(jié)構(gòu)順序查找1根本思想2算法實(shí)現(xiàn)3性能分析1根本思路2算法實(shí)現(xiàn)3性能分析分塊查找1根本思路2性能分析教 師 授 課 教 案教學(xué)單元章節(jié)：第七章 查找7.4 哈希表教學(xué)目的： 理解哈希方法理解沖突處理方法知識要點(diǎn)： 哈希表和哈希方法、常用的哈希函數(shù)沖突處理方法、哈希表的查找和性能分析技能要點(diǎn)：哈希函數(shù)的比擬、解決地址沖突的處理方法

31、教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P167：6課后分析與小結(jié)：本節(jié)重點(diǎn)：常用的哈希函數(shù)、沖突處理方法本節(jié)難點(diǎn)：沖突處理方法、哈希表的查找和性能分析審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第七章 查找7.4 哈希表哈希表和哈希方法常用的哈希函數(shù)沖突處理方法1線性探測法2二次探測法3雙哈希函數(shù)探測法哈希表的查找及其分析板書或旁注教 師 授 課 教 案教學(xué)單元章節(jié)：第八章 排序根本概念簡單排序方法教學(xué)目的： 理解排序的根本概念掌握插入排序、簡單項選擇擇排序的方法知識要點(diǎn)： 排序的根本概念和性能分析直接插入排序、冒泡排序、簡單項選擇擇排序技能要點(diǎn)： 直接

32、插入排序、冒泡排序和簡單項選擇擇排序的性能分析教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P186：1課后分析與小結(jié)：本節(jié)重點(diǎn)：冒泡排序算法、直接插入排序算法本節(jié)難點(diǎn)：冒泡排序算法、簡單項選擇擇排序算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程第八章 排序根本概念板書或旁注直接插入排序直接插入排序方法的思路直接插入排序算法實(shí)現(xiàn)冒泡排序冒泡排序方法的思路冒泡排序算法實(shí)現(xiàn)簡單項選擇擇排序簡單項選擇擇排序方法的思路簡單項選擇擇排序算法實(shí)現(xiàn)簡單項選擇擇排序效率分析教 師 授 課 教 案教學(xué)單元章節(jié)：第八章 排序快速排序8.5 歸并排序8.7 排序方法的比擬和討論教學(xué)

33、目的： 理解快速排序和歸并排序的方法及性能分析了解主要排序方法各自的特點(diǎn)知識要點(diǎn)： 快速排序、兩路歸并的迭代算法兩路歸并的遞歸算法、主要排序方法各自的特點(diǎn)技能要點(diǎn)： 快速排序、兩路歸并的迭代算法兩路歸并的遞歸算法、排序方法的比擬教學(xué)方法：講授+演示教具及教學(xué)手段：投影作業(yè)布置情況：P186：1、2課后分析與小結(jié)：本節(jié)重點(diǎn)：兩路歸并算法、快速排序算法本節(jié)難點(diǎn)：兩路歸并算法、快速排序算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注第八章 排序8.3 快速排序快速排序的根本思路快速排序算法實(shí)現(xiàn)快速排序的過程示意快速排序效率分析8.5 歸并排序歸并排序的根本思路歸并排

34、序算法實(shí)現(xiàn)1兩路歸并的迭代算法2兩路歸并的遞歸算法歸并排序的過程示意歸并排序效率分析8.7 排序方法的比擬和討論空間三個方面來比擬從排序方法的穩(wěn)定性角度對各種排序方法加以比擬。教 師 授 課 教 案教學(xué)單元章節(jié)：實(shí)驗1 對線性表進(jìn)行順序存儲的操作的實(shí)現(xiàn)教學(xué)目的： 1掌握線性表的抽象數(shù)據(jù)類型。2掌握線性表的順序存儲及相關(guān)算法。知識要點(diǎn)： C對線性表順序存儲的各種操作的實(shí)現(xiàn)技能要點(diǎn)：用 C 實(shí)現(xiàn)線性表順序存儲的根本操作：插入、刪除、查找等教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)布置情況：上機(jī)實(shí)驗課后分析與小結(jié)：本節(jié)重難點(diǎn)：用 C 實(shí)現(xiàn)線性表順序存儲的根本操作審 批：教研

35、室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言實(shí)現(xiàn)線性表順序存儲結(jié)構(gòu)的創(chuàng)立、插入、刪除、查找、合并等算法。順序線性表的定義建立順序線性表求線性表長度查找數(shù)據(jù)元素數(shù)據(jù)元素插入數(shù)據(jù)元素刪除排序,從小到大教 師 授 課 教 案2 對線性表進(jìn)行鏈?zhǔn)酱鎯Φ牟僮鞯膶?shí)現(xiàn)教學(xué)目的： 1掌握線性表的抽象數(shù)據(jù)類型。2掌握線性表的鏈?zhǔn)酱鎯跋嚓P(guān)算法。C 對線性表鏈?zhǔn)酱鎯Φ母鞣N操作的實(shí)現(xiàn)技能要點(diǎn)：用 C 實(shí)現(xiàn)線性表鏈?zhǔn)酱鎯Φ母静僮鳎翰迦?、刪除、查找等教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)布置情況：上機(jī)實(shí)驗課后分析與小結(jié)：本節(jié)重難點(diǎn)：用 C 實(shí)現(xiàn)

36、線性表鏈?zhǔn)酱鎯Φ母静僮鲗?批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言實(shí)現(xiàn)線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的創(chuàng)立、插入、刪除、查找、排序等算法。單鏈表的定義頭輸入法建立單鏈表插入結(jié)點(diǎn)刪除結(jié)點(diǎn)查找元素排序查找單鏈表結(jié)點(diǎn)逆置教 師 授 課 教 案教學(xué)單元章節(jié)：實(shí)驗3棧及棧的應(yīng)用實(shí)驗教學(xué)目的： 1掌握棧的抽象數(shù)據(jù)類型。掌握實(shí)現(xiàn)棧的各種操作的算法。理解棧與遞歸的關(guān)系。知識要點(diǎn)：棧的每種操作在順棧和鏈棧上的實(shí)現(xiàn)算法用描述中綴換后綴算法技能要點(diǎn)：棧的每種操作在順棧和鏈棧上的實(shí)現(xiàn)算用描述中綴換后綴算法教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)

37、布置情況：上機(jī)實(shí)驗課后分析與小結(jié)：本節(jié)重難點(diǎn)：棧的每種操作在順棧和鏈棧上的實(shí)現(xiàn)算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言實(shí)現(xiàn)順序棧和鏈棧存儲結(jié)構(gòu)的主要算法。用描述中綴換后綴算法CCCCC教 師 授 課 教 案教學(xué)單元章節(jié)：實(shí)驗4隊列及隊列應(yīng)用實(shí)驗教學(xué)目的： 1掌握隊列的抽象數(shù)據(jù)類型。2掌握隊列的各種操作的實(shí)現(xiàn)算法。知識要點(diǎn)： 12用描述進(jìn)隊，出隊的算法。技能要點(diǎn)：1用描述隊列的各種操作在順隊和鏈隊上的實(shí)現(xiàn)算法2用描述進(jìn)隊，出隊的算法。教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)布置情況：上機(jī)實(shí)驗課后分析與小結(jié)

38、：本節(jié)重難點(diǎn)：用描述隊列的各種操作在順隊和鏈隊上的實(shí)現(xiàn)審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言描述隊列的各種操作在順隊和鏈隊上的實(shí)現(xiàn)算法。用描述進(jìn)隊，出隊的算法。CCC 語言實(shí)現(xiàn)鏈隊列的定義、創(chuàng)立、置空、判空算法C 語言實(shí)現(xiàn)鏈隊列的出隊、入隊、查找算法.教學(xué)單元章節(jié)：實(shí)驗5串的操作實(shí)驗教學(xué)目的： 1串的抽象數(shù)據(jù)類型。2掌握串的各種操作的實(shí)現(xiàn)算法。知識要點(diǎn)： 用描述串類型并實(shí)現(xiàn)相關(guān)串操作算法。技能要點(diǎn)：用描述串類型并實(shí)現(xiàn)相關(guān)串操作算法。教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)布置情況：上機(jī)實(shí)驗課后分析與小結(jié)：

39、本節(jié)重難點(diǎn)： 用描述串類型并實(shí)現(xiàn)相關(guān)串操作審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言描述串類型并實(shí)現(xiàn)相關(guān)串操作1C 語言實(shí)現(xiàn)串定義2C 語言實(shí)現(xiàn)串字符定位3C4C5C 語言實(shí)現(xiàn)串字符刪除教 師 授 課 教 案教學(xué)單元章節(jié)：實(shí)驗6二叉樹的根本操作教學(xué)目的： 1.掌握樹的操作實(shí)現(xiàn)算法。2.掌握二叉樹的建立，遍歷等算法。知識要點(diǎn)： 1用 C 描述二叉樹的運(yùn)算算法。C技能要點(diǎn)： 1用 C 描述二叉樹的運(yùn)算算法。C 教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)布置情況：上機(jī)實(shí)驗課后分析與小結(jié)：本節(jié)重難點(diǎn)：用 C 描述二叉樹

40、的根本操作、遍歷算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言描述二叉樹的建立，遍歷等算法。CCCCC教 師 授 課 教 案教學(xué)單元章節(jié)：實(shí)驗7二叉樹的應(yīng)用教學(xué)目的：掌握哈夫曼樹的構(gòu)造算。知識要點(diǎn)：用C描述哈夫曼樹的構(gòu)造算法技能要點(diǎn)：用C描述哈夫曼樹的構(gòu)造算法教學(xué)方法：講授+演示+實(shí)驗教具及教學(xué)手段：PC機(jī)、Turbo C作業(yè)布置情況：上機(jī)實(shí)驗課后分析與小結(jié)：本節(jié)重難點(diǎn)：用 C 描述哈夫曼樹的構(gòu)造算法審 批：教研室主任簽字年月日抽 查：系部主任簽字年月日教學(xué)內(nèi)容及過程板書或旁注實(shí)驗內(nèi)容：用 C 語言描述哈夫曼樹的構(gòu)造算法教 師 授 課 教 案教學(xué)單元章節(jié)：實(shí)驗8圖的創(chuàng)立遍歷等根