《大數(shù)據(jù)結構》教案設計99670

《《大數(shù)據(jù)結構》教案設計99670》由會員分享，可在線閱讀，更多相關《《大數(shù)據(jù)結構》教案設計99670（72頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 教學單元（章節(jié)）： 第一章：緒論 1.1 數(shù)據(jù)結構概念 教學目的： 理解學習數(shù)據(jù)結構的重要意義 掌握數(shù)據(jù)結構的基本概念 知識要點： 數(shù)據(jù)結構、邏輯結構、物理結構、算法 4種數(shù)據(jù)的存儲結構、程序與數(shù)據(jù)結構 技能要點： 數(shù)據(jù)結構、4種基本的數(shù)據(jù)結構、 4種數(shù)據(jù)的存儲結構 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P11；1、2 課后分析與小結： 本節(jié)課的重點： 數(shù)據(jù)結構有關概念和術語 難點： 學習數(shù)據(jù)結構的意義 審 批：教研室主任（簽字）

2、 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第一章：緒論 1.1.1 為什么要學習數(shù)據(jù)結構 1．計算機處理問題的分類 （1）數(shù)值計算問題 （2）非數(shù)值性問題 2．非數(shù)值問題求解???算法+數(shù)據(jù)結構=程序????? 數(shù)據(jù)結構：是指數(shù)據(jù)的邏輯結構和存儲結構????? 算法：是對數(shù)據(jù)運算的描述 1.1.2 有關概念和術語 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 數(shù)據(jù)結構：集合、線性、樹型、圖狀 數(shù)據(jù)結構：包括物理結構、邏輯結構 數(shù)據(jù)的四種基本存儲方法 （1

3、）順序存儲方法 （2）存儲方法 （3）索引存儲方法 （4）散列存儲方法 教 師 授 課 教 案 教學單元（章節(jié)）： 第一章：緒論 1.2 算法描述 1.3 算法分析 教學目的： 理解算法的定義、特性、描述方法 掌握簡單的時間復雜度的估計 知識要點： 算法的特性、描述方法、算法編制的質量要求、 數(shù)據(jù)結構的基本操作、時間復雜度、空間復雜度、 技能要點： 描述算法、分析簡單算法的時間復雜度 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況：

4、 P11；3、4 課后分析與小結： 本節(jié)課的重點：算法的特點和描述，算法分析 難點：算法時間復雜度的估計 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第一章：緒論 (1) 有窮性(2)確定性(3)可行性(4)輸入(5)輸出 好的算法的特點 (1) 正確 (2) 可讀 (3) 健壯 (4) 高效 數(shù)據(jù)結構的基本操作： （1）查找（2）讀?。?）插入（4）刪除（5）修改

5、 1.2.2 算法描述 算法描述的種類： （1）框圖/流程圖算法（2）非形式算法 （3）偽語言算法 （4）高級語言算法 1.3 算法分析 時間復雜度:解決某問題所花費的時間大小，即程序運行從開始到結束所需要的時間，記為T (n) 空間復雜度:解決某問題的程序完全運行時所占用的存儲空間大小，記為S (n) 【例】算法MatrixMultidy的時間復雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有?????? 教 師 授 課 教 案 教學單元（章節(jié)）： C語言 第七章：數(shù)組 7.1

6、一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 教學目的： 理解一維數(shù)組、二維數(shù)組、字符數(shù)組的定義 掌握一維數(shù)組、二維數(shù)組、字符數(shù)組的引用和初始化方法 掌握一維數(shù)組、二維數(shù)組、字符數(shù)組的簡單應用程序 知識要點： 一維數(shù)組、二維數(shù)組、字符數(shù)組的定義、引用、初始化 一維數(shù)組、二維數(shù)組、字符數(shù)組相關的簡單程序 技能要點：用數(shù)組來處理相關問題的程序 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： 課后分析

7、與小結： 本節(jié)重點：數(shù)組的定義、引用、初始化 本節(jié)難點：用數(shù)組求解簡單的問題 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第七章 數(shù)組 7.1 一維數(shù)組的定義和引用 7.2 二維數(shù)組的定義和引用 7.3 字符數(shù)組 教 師 授 課 教 案 教學單元（章節(jié)）： C語言 第十章：指針

8、 10.1 地址和指針的概念 10.2 變量的指針和指針變量 教學目的： 理解地址和指針的概念 掌握指針變量的定義和引用 知識要點： 地址、指針、指針變量的定義和引用、 指針變量作為函數(shù)參數(shù) 技能要點：指針變量的定義和引用 指針變量作為函數(shù)參數(shù) 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P278；10.1 課后分析與小結： 本節(jié)重點：指針的含義、指針變量的引用 本節(jié)難點：指針變量的引用、指針變量作為函數(shù)參數(shù) 審 批：教研室主任（簽字）

9、 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 C語言 第十章：指針 10.1 地址和指針的概念 1．地址的概念 2. 指針的概念 10.2 變量的指針和指針變量 10.2.1 定義一個指針變量 1.定義指針變量的一般形式: 基類型 * 指針變量名 10.2.2 指針變量的引用 1. &—— 取址運算符。 2. * —— 指針運算符， 10.2.3 指針變量作為函數(shù)參數(shù) (1)使一個指針變量指向另一個變量 (2

10、)通過指針變量訪問整型變量 教 師 授 課 教 案 教學單元（章節(jié)）： C語言 第十章：指針 10.3.1 指向數(shù)組元素的指針 10.3.2 通過指針引用數(shù)組元素 10.4.1 字符串的表現(xiàn)形式 10.8 指針運算小結 教學目的： 掌握通過指針引用數(shù)組元素 理解字符串的表現(xiàn)形式 掌握指針的相關運算 知識要點：數(shù)組與指針、字符串與指針、指針運算 技能要點：通過指針引用數(shù)組元素、字符串的表現(xiàn)形式 指針的各種運算 教學方法： 講授+演示 教具及教學手段： 投影

11、 作業(yè)布置情況： P279；10.6 P279；10.9 課后分析與小結： 本節(jié)重點：指針運算、通過指針引用數(shù)組元素和字符串 本節(jié)難點：通過指針引用數(shù)組元素、字符串 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 10.3 數(shù)組與指針 10.3.1 指向數(shù)組元素的指針 定義一個指向數(shù)組元素的指針變量 10.3.2 通過指針引用數(shù)組元素 數(shù)組元素的引用可以用 1. 下標法: a[i] 2.

12、 指針法: *(a+i) 或 *(p+i) 10.4 字符串與指針 10.4.1 字符串的表現(xiàn)形式 1. 用字符數(shù)組存放一個字符串 2. 用字符指針指向一個字符串 3．字符串常量和字符指針的初始化 10.8 指針運算小結 10.8.1 有關指針的數(shù)據(jù)類型的小結 10.8.2 指針運算小結 教 師 授 課 教 案 教學單元（章節(jié)）： C語言 第十一章：結構體與共用體 11.1-11.5.1 結構體 11.7.3 處理動態(tài)鏈表所需的函數(shù) 11.10 用t

13、ypedef定義類型 教學目的：掌握結構體變量的定義、引用和初始化 掌握處理動態(tài)鏈表所需的函數(shù) 掌握用typedef定義類型 知識要點：結構體變量、結構體數(shù)組，malloc函數(shù) calloc函數(shù)、free函數(shù)、typedef 技能要點：結構體變量的定義、引用和初始化 用typedef定義類型 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： 課后分析與小結： 本節(jié)重點：結構體變量、處理動態(tài)鏈表所需的函數(shù) 本節(jié)難點：結構體變量的引用和初始化、用typedef定義類型 審 批：

14、教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第十一章：結構體與共用體 11.1 概述 1. 先定義結構體類型，再用類型標識去定義變量 2. 定義類型的同時定義變量3. 直接定義結構體類型變量 11.3 結構體變量的引用 1. 結構體變量各成員的引用 引用形式：結構體變量名 . 成員名 2. 結構體變量各成員的輸入、輸出 11.4 結構體變量的初始化 11.5 結構體數(shù)組 11.6 指針與結構體 1. 指向結

15、構體變量的指針 2. 指向結構體變量的指針與結構體變量的等價關系 11.7 用指針處理鏈表 11.7.3 處理動態(tài)鏈表所需的函數(shù) 存分配函數(shù)原型： void *malloc(unsigned size); 存分配函數(shù)原型： void *calloc(unsigned size); 存釋放函數(shù)原形：void free(void *p); 11.10 用typedef定義類型 1、使用的一般形式： typedef 原類型名 新類型名； 2.用typedef定義類型的方法（舉例） ① 先按定義數(shù)組變量形式書寫：int n[100]； ② 將變量名換成新類型名：int　N

16、UM［１００］； ③ 在最前面加上typedef: typedef int NUM［１００］； ④ 用新類型名來定義變量：NUM?。?； 3.用typedef定義類型的說明： (1) 用typedef可以聲明各種類型名，但不能用來定義變量。 (2)用typedef只是對已經(jīng)存在的類型增加一個類型名，而沒有創(chuàng)造新的類型。 (3) 使用typedef有利于程序的通用與移植。 教 師 授 課 教 案 教學單元（章節(jié)）： 第二章：線性表 2.1 線性表的邏輯結構 2.2 線性表的順序存儲及操作實現(xiàn) 教學目的： 理解順序表的定義、特點及其

17、主要操作 掌握插入與刪除算法中數(shù)據(jù)元素的平均移動次數(shù) 知識要點： 線性表的定義、特點、基本操作 順序表的定義、特點和存儲 順序表的初始化、插入、刪除、查找操作，應用舉例 技能要點： 線性表的邏輯結構及基本操作 線性表的順序存儲結構及其基本操作實現(xiàn) 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P37；1 P38；6 課后分析與小結： 本節(jié)重點：線性表的定義、特點和順序表的基本操作 本節(jié)難點：順序表的插入和刪除算法及其時間復雜度 審 批：教研室主任（簽字） 年 月 日

18、 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 2.1 線性表的邏輯結構 2.1.0 線性表的實際例子 2.1.1 線性表的定義 2.1.2 線性表的基本操作 1. 初始化：Init_List(L) 2. 置空：Setnull_List(L) 3. 求長度：Length_List(L) 4. 取表元：Get_List(L,i) 5. 查找：Locate_List(L,x) 6.插入：Insert_List(L,x) 7.刪除：Del

19、ete_List(L,i) 2.2.1 線性表的順序存儲結構 2.2.2 順序表的基本算法實現(xiàn) 1. 初始化順序表L 2. 插入 3. 刪除 4. 按值查找 教 師 授 課 教 案 教學單元（章節(jié)）： 第二章：線性表 .1 單鏈表 .2 單鏈表上基本運算的實現(xiàn) 教學目的： 掌握單鏈表的定義、特點及存儲結構 掌握單鏈表的查找、插入與刪除算法 理解帶首結點的單鏈表的優(yōu)點 知識要點： 單鏈表的定義、特點、標識、結點結構和存儲結構 單鏈表的建立、求表長、查找、插入和刪

20、除算法 技能要點： 單鏈表的結點結構和存儲結構 單鏈表的查找、插入與刪除算法 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P38；8 課后分析與小結： 本節(jié)重點：單鏈表的定義、特點和存儲結構基本操作 本節(jié)難點：單鏈表的查找、插入和刪除算法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 2.3 線性表的鏈式存儲結構 2.3.1 單鏈表

21、2.3.2 單鏈表上的基本運算的實現(xiàn) （1）頭部插入法建立 （2）尾部插入法建立 （1）帶頭結點的單鏈表 （2）不帶頭結點的單鏈表 （1）按序號查找 （2）按值查找 （1）后插節(jié)點 （2）前插節(jié)點 （3）插入運算 5.刪除操作 (1)刪除節(jié)點 (2)刪除運算 教 師 授 課 教 案 教學單元（章節(jié)）： 第二章：線性表 .3 循環(huán)鏈表 .4 雙向鏈表 教學目的： 掌握單鏈表的定義、特點及存儲結構 掌握單鏈表的查找、插入與刪

22、除算法 理解帶首結點的單鏈表的優(yōu)點 知識要點： 循環(huán)鏈表和雙向鏈表的定義、特點、標識、結點結構 兩個循環(huán)鏈表的連接、雙向鏈表中結點的插入和刪除 順序表和鏈表的比較 技能要點： 兩個循環(huán)鏈表的連接算法 雙向鏈表中結點的插入和刪除 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P38；7、9 課后分析與小結： 本節(jié)課的重點：循環(huán)鏈表和雙向鏈表的特點和基本操作 難點：循環(huán)鏈表連接操作、雙向鏈表的插入和刪除 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字

23、） 年 月 日 教學容及過程 板書或旁注 2.3.3 循環(huán)鏈表 一． 循環(huán)鏈表的定義 二． 循環(huán)鏈表示意圖 (1)帶頭結點的單循環(huán)鏈表 (2)僅設尾指針的單循環(huán)鏈表 三． 循環(huán)鏈表的特點 四. 循環(huán)鏈表的說明 2.3.4 雙向循環(huán)鏈表 一. 雙向鏈表的概念 二. 雙鏈表示意圖 三．雙鏈表的類型定義 四．雙向鏈表的操作 五. 順序表和鏈表的比較 教 師 授 課 教 案 教學單元（章節(jié)）：

24、 第三章：棧和隊列 3.1 棧 教學目的：掌握棧的定義、特點和存儲結構 掌握順序棧和鏈棧的基本運算 理解棧與遞歸的關系 知識要點： 棧的定義、特點、基本運算，順序棧和鏈棧的主要操作 上溢、下溢，?？张c棧滿的條件，棧與遞歸問題 技能要點： 順序棧和鏈棧的置空、判?？铡⑷霔?、出棧操作 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P63；1、3、4 課后分析與小結： 本節(jié)課的重點： 順序棧和鏈棧的基本操作 難點： 棧與遞歸問題 審 批：教研室主任（簽字） 年

25、月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第三章：棧和隊列 3.1 棧 3.1.1 棧的定義和基本運算 棧：是限制僅在表尾進行插入和刪除的線性表。 （1）初始化棧：構在一個空棧 （2）置空棧：將S置成空棧 （3）入棧：在棧頂插入一個新元素X （4）出棧：刪除(彈出) 棧S的頂部元素 （5）取棧頂)：取棧S的頂部元素 （6）判斷空棧 Empty_Stack (S)：空棧返回1 3.1.2 棧的存儲實現(xiàn)和運算實現(xiàn) 1）順序棧的定義 2）順序?；?/p>

26、本運算 ⑴ 置空棧 ⑵判空棧 ⑶ 入棧 ⑷ 出棧 3.1.2 棧的存儲實現(xiàn)和運算實現(xiàn) 1）鏈棧的定義 2）鏈?；具\算 ⑴ 置空棧 ⑵判空棧 ⑶ 入棧 ⑷ 出棧 3.1.3 棧與遞歸的實現(xiàn) （1）遞歸定義的數(shù)學函數(shù) （2）遞歸數(shù)據(jù)結構的處理 （3）遞歸求解方法 （1）應用遞歸算法的前提 （2）Hanoi塔問題的遞歸函數(shù) （3）Fibonacci數(shù)列的遞歸算法 教 師 授 課 教 案 教學單元（章節(jié)）： 第三章：棧和隊列 3.2 棧的應用舉例 3.3 隊列 3.4 隊列應用舉例 教學目的： 掌握隊列的

27、定義、特點和存儲結構 掌握循環(huán)隊列和鏈隊列的基本運算 理解循環(huán)隊列的意義和隊列的應用 知識要點： 隊列的定義、特點、存儲結構、基本運算 循環(huán)隊列產(chǎn)生的原因，循環(huán)隊列和鏈隊列的主要操作 假溢出，循環(huán)隊列隊空與隊滿的條件 技能要點： 循環(huán)隊列隊空與隊滿的條件， 循環(huán)隊列和鏈隊列的入隊、出隊、判隊空操作 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P63；2、5、9 課后分析與小結： 本節(jié)課的重點： 循環(huán)隊列和鏈隊列的基本操作 難點： 棧的應用、循環(huán)隊列 審 批：教研室主任（簽字）

28、 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第三章：棧和隊列 3.2 棧的應用舉例 3.3 隊列 2.隊列結構的基本操作 1. Init_Queue(Q) 將Q置為一個空隊列 2. In_Queue(Q,x) 插入元素x為隊Q的新隊尾元素 3. Out_Queue(Q,x) 刪除Q的隊頭元素，并返回其值 4. Front_Queue(Q,x) 返回Q的隊頭元素 5. Empty_Queue (Q) 判隊空 1．

29、順序隊列：定義、特點和存儲結構 2. 循環(huán)隊列：定義、存儲結構和基本操作 3. 鏈隊列 1）定義、特點和存儲結構 2）基本操作 3.4 隊列應用舉例 教 師 授 課 教 案 教學單元（章節(jié)）： 第四章：串和數(shù)組 4.1 串 教學目的： 掌握串的定義、特點、相關術語和基本運算 了解串的存儲結構及其基本運算實現(xiàn) 知識要點： 串的定義、特點、相關術語和基本運算 串的順序存儲結構和堆分配存儲結構 技能要點： 串的基本運算 定長串連接、求子串和串比較操作 教學方法： 講

30、授+演示 教具及教學手段： 投影 作業(yè)布置情況： P78；2、3 課后分析與小結： 本節(jié)重點：串的定義、存儲結構和基本運算 本節(jié)難點：串連接、求子串和串比較算法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第四章：串和數(shù)組 4.1 串 （1）求串長 （2）串賦值 （3）串連接 （4）求子串 （5）串比較 （6）串定位 (7) 插入 (8) 刪

31、除 (9) 串替換 4.1.2 串的存儲結構 1. 串的定長順序存儲結構 2. 堆分配存儲結構 3. 定長順序串基本運算的實現(xiàn) （1）串連接 （2）子串 （3）串比較 教 師 授 課 教 案 教學單元（章節(jié)）： 第四章：串和數(shù)組 4.2 數(shù)組 教學目的： 了解數(shù)組的邏輯存儲結構和存映像 了解稀疏矩陣的定義及其數(shù)組實現(xiàn) 知識要點： 數(shù)組與線性表、數(shù)組的邏輯存儲結構和存映像 稀疏矩陣的定義、壓縮存儲方法、轉置 技能要點： 數(shù)組的存映像、數(shù)組元素地址的計算 稀疏矩陣的

32、存儲、轉置 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P78；5、6 課后分析與小結： 本節(jié)重點：數(shù)組的邏輯結構和物理結構、稀疏矩陣 本節(jié)難點：稀疏矩陣的壓縮方法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第四章：串和數(shù)組 4.2 數(shù)組 1） 1維數(shù)組 2） 2維數(shù)組 1）以行為主 2）以列為主 1） 1維數(shù)

33、組物理地址計算函數(shù)表達式 2） 2維數(shù)組物理地址計算函數(shù)表達式 4.2.3 稀疏矩陣 教 師 授 課 教 案 教學單元（章節(jié)）： 第五章：樹和二叉樹 5.1 樹的概念和基本操作 教學目的： 掌握樹的定義、特點和相關術語 理解樹的基本操作 掌握二叉樹的定義、相關概念和主要性質 知識要點： 樹的定義、特點、相關術語和基本操作 二叉樹、完全二叉樹、滿二叉樹的定義 完全二叉樹、滿二叉樹的性質 技能要點：樹的相關術語、樹的遍

34、歷 二叉樹、完全二叉樹、滿二叉樹 二叉樹的結點個數(shù)、完全二叉樹的深度 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P107；1、2、8、9 課后分析與小結： 本節(jié)重點：樹和二叉樹的相關概念、二叉樹的性質 本節(jié)難點：二叉樹的主要性質 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第五章：樹和二叉樹 5.1 樹的概念和基本操作 5.1.1 樹的定義和相關術語

35、 5.1.2 樹的基本操作 (1)Initiate(t)初始化一棵空樹t。 (2)Root(x)求結點x所在樹的根結點。 (3)Parent(t，x)求樹t中結點x的雙親結點。 (4)Child(t，x，i)求樹t中結點x的第i個孩子結點。 (5)RightSibling(t，x)求樹t中結點x的第一個右邊兄弟結點。 (6)Insert(t，x，i，s)把以s為根結點的樹插入到樹 t中作為結點x的第i棵子樹。 (7)Delete(t，x，i)在樹t中刪除結點x的第i棵子樹。 (8)Traverse(t)是樹的遍歷操作 ,訪問每個結點。 5.2 二叉樹

36、 1．二叉樹 2. 二叉樹的相關概念：滿二叉樹、完全二叉樹 性質1：層數(shù)與節(jié)點的關系 性質2：深度與節(jié)點的關系 性質3：非空二叉樹的度為2的結點與葉子節(jié)點的關系 性質4：完全二叉樹的深度與節(jié)點的關系 性質5：完全二叉樹的相關性質 教 師 授 課 教 案 教學單元（章節(jié)）： 第五章：樹和二叉樹 教學目的： 掌握二叉樹的2種存儲結構 理解二叉樹的基本操作 掌握二叉樹的遍歷方法 知識要點： 二叉樹的順序存儲、二叉鏈表存儲、三叉鏈表存儲 二叉樹的基本操作 先序遍歷、中序遍歷、后序遍歷、層次遍歷 技能要點： 二叉樹的順序

37、存儲、二叉樹鏈式存儲的存儲結構 先序遍歷、中序遍歷、后序遍歷、層次遍歷二叉樹的過程 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P107；3、4、5、6 課后分析與小結： 本節(jié)重點：二叉樹的存儲結構和遍歷方法 本節(jié)難點：先序、中序、后序遍歷二叉樹 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第五章：樹和二叉樹 1）二叉鏈表存儲

38、 2）三叉鏈表存儲 (1)Initiate（bt） (2)Create（x，lbt，rbt） (3)InsertL（bt，x，parent） (4)DeleteL（bt，parent） (5)InsertR（bt，x，parent） (6)DeleteR（bt，parent） (7)serch （bt，x） (8)Traverse（bt） 教 師 授 課 教 案 教學單元（章節(jié)）： 第五章：樹和二叉樹 5.3 樹和森林 教學目的： 理解樹的3種存儲結構 掌握樹

39、、森林與二叉樹的轉換方法 掌握樹和森林的遍歷方法 知識要點： 樹的雙親表示法、孩子鏈表表示法、孩子兄弟表示法 樹和森林轉換為二叉樹、二叉樹轉換為樹和森林 樹的先根遍歷、后根遍歷，森林的先序遍歷、后序遍歷 技能要點： 二叉樹的順序存儲結構、二叉樹鏈式存儲的存儲結構 樹、森林與二叉樹的轉換過方法、樹和森林的遍歷 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P108；7、15、16 課后分析與小結： 本節(jié)重點：樹、森林與二叉樹的轉換、樹和森林的遍歷 本節(jié)難點：樹的存儲 樹、森林與二

40、叉樹的轉換 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第五章：樹和二叉樹 5.3 樹和森林 5.3.1 樹的存儲 5.3.2樹、森林與二叉樹的轉換 1）先根遍歷 2）后根遍歷 （1）先序遍歷 （2）后序遍歷 教 師 授 課 教 案 教學單元（章節(jié)）： 第五章：樹和二叉樹 5.4 最優(yōu)二叉樹——哈

41、夫曼樹 教學目的： 理解哈夫曼樹的相關定義 掌握最優(yōu)二叉樹的構建方法 掌握哈夫曼編碼的定義和實現(xiàn)過程 知識要點： 哈夫曼樹、帶權路徑長度、哈夫曼編碼、 等長編碼、不等長編碼 技能要點： 構造哈夫曼樹 設計哈夫曼編碼 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P109；20、21 課后分析與小結： 本節(jié)重點：最優(yōu)二叉樹和哈夫曼編碼的構造方法 本節(jié)難點：帶權路徑、哈夫曼編碼 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字）

42、 年 月 日 教學容及過程 板書或旁注 第五章：樹和二叉樹 5.4 最優(yōu)二叉樹——哈夫曼樹 5.4.1 哈夫曼樹的基本概念 1. 哈夫曼樹的構造步驟 4. 哈夫曼編碼的構造過程 5.4.4 哈夫曼編碼的算法實現(xiàn) 教 師 授 課 教 案 教學單元（章節(jié)）： 第六章：圖 6.1 圖的基本概念 6.2 圖的存儲表示 教學目的： 掌握圖的定義和相關術語 理解

43、圖的基本操作 掌握圖的兩種存儲結構 知識要點： 圖、無向圖、有向圖、完全圖、度、入度、出度、權和網(wǎng) 路徑、回路、子圖、連通圖、強連通圖、生成樹 圖的基本操作、鄰接矩陣、鄰接表 技能要點：圖的相關術語、圖的鄰接矩陣的表示 圖的鄰接表的表示 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P138；1、2、4 課后分析與小結： 本節(jié)重點：圖的相關術語和存儲表示 本節(jié)難點：鄰接矩陣、鄰接表 審 批：教研室主任（簽字）

44、 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第六章：圖 6.1 圖的基本概念 1）有向圖、無向圖、完全圖 2）頂點、邊、弧、弧頭、弧尾 3）度、入度、出度 4）權和網(wǎng) 5）路徑和路徑長度、回路、簡單路徑、簡單回路 6）子圖、連通圖、強連通圖 7）連通的、連通分量、強連通分量 8）生成樹、生成森林 6.1.2 圖的基本操作 （1）Creatgraph（G） （2）DestroyGraph（G） （3）

45、GetVex（G，v） (4）PutVex（G，v，value） （5）Insertvex（G ，v） （6）Deletevex（G，v） （7）InsertArc（ G ，v，u） （8）DeleteArc（ G ，v，u） （9）DFSTraverse（G，v） （10）BFSTtaverse（G，v） （11）Locatevex（g，v） （12）FiirstAdjvex（g，v） （13）nextAdjvex（g，v，w） 6.2 圖的存儲表示 1. 鄰接矩陣存儲結構的定義 2. 表示方法 6.2.2

46、 鄰接表 1. 鄰接表存儲結構的定義 2. 表示方法 教 師 授 課 教 案 教學單元（章節(jié)）： 第六章：圖 6.3 圖的遍歷 6.4.1 最小生成樹 教學目的： 掌握圖的兩種遍歷方法 理解最小生成樹的的相關概念 掌握用Prim算法構造最小生成樹的過程 知識要點： 深度優(yōu)先搜索、廣度優(yōu)先搜索 最小生成樹、 Prim算法思路 技能要點：深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷 用Prim算法構造最小生成樹 教學方法： 講授+演示 教具及教學手段：

47、 投影 作業(yè)布置情況： P138；3、5 課后分析與小結： 本節(jié)重點：圖的兩種遍歷、最小生成樹 本節(jié)難點：用Prim算法構造最小生成樹 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第六章：圖 6.3 圖的遍歷 6.3.1 深度優(yōu)先搜索 1. 深度優(yōu)先搜索的定義 2. 深度優(yōu)先搜索的算法實現(xiàn) 6.3.2 廣度優(yōu)先搜索 1. 廣度優(yōu)先搜索的定義 2. 廣度優(yōu)先搜索的算法實現(xiàn) 6.

48、4 圖的應用 6.4.1 最小生成樹 1） Prim算法的基本思想 2） Prim算法的基本步驟 3） Prim算法的C語言描述 教 師 授 課 教 案 教學單元（章節(jié)）： 第六章：圖 .2 最短路徑 .3 拓撲排序 教學目的： 理解最短路徑問題和拓撲排序的意義 了解用Dijkstra算法求單源最短路徑 了解拓撲排序的方法 知識要點： 最短路徑問題、Dijkstra算法的基本思想、 有向無環(huán)圖、AOV網(wǎng)、拓撲排序的步驟 技能要點：用Dijkstra算法求單元最短路徑

49、 拓撲排序算法 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P139；6 課后分析與小結： 本節(jié)重點：最短路徑問題和拓撲排序 本節(jié)難點：Dijkstra算法、拓撲排序算法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第六章：圖 6.4 圖的應用 .2 最短路徑 6.4.

50、3 拓撲排序 1. 有向無環(huán)圖 2. AVO網(wǎng) 3. 拓撲排序 4. 拓撲排序的基本步驟 5. 拓撲排序的算法思想 教 師 授 課 教 案 教學單元（章節(jié)）： 第七章 查找 7.1 基本概念和術語 7.2 靜態(tài)查找表 教學目的： 了解查找的概念和靜態(tài)查找表結構 理解順序查找和折半查找及其性能分析方法 知識要點： 關鍵碼、查找表、平均查找長度 順序查找、有序表的折半查找、分塊查找 技能要點：順序查找、有序表的折半查找和 分塊查找算法的基本思想 教學方法： 講授+演

51、示 教具及教學手段： 投影 作業(yè)布置情況： P167： 1、3 課后分析與小結： 本節(jié)重點：順序查找、折半查找和分塊查找算法 本節(jié)難點：折半查找算法的基本思想 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第七章 查找 7.1 基本概念和術語 7.2 靜態(tài)查找表 7.2.1 靜態(tài)查找表結構 7.2.2 順序查找 1）基本思想 2）算法實現(xiàn) 3）性能分析

52、 7.2.3 有序表的折半查找 1）基本思路 2）算法實現(xiàn) 3）性能分析 7.2.4 分塊查找 1）基本思路 2）性能分析 教 師 授 課 教 案 教學單元（章節(jié)）： 第七章 查找 7.4 哈希表 教學目的： 理解哈希方法 理解沖突處理方法 知識要點： 哈希表和哈希方法、常用的哈希函數(shù) 沖突處理方法、哈希表的查找和性能分析 技能要點：哈希函數(shù)的比較、解決地址沖突的處理方法 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P167：

53、6 課后分析與小結： 本節(jié)重點：常用的哈希函數(shù)、沖突處理方法 本節(jié)難點：沖突處理方法、哈希表的查找和性能分析 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第七章 查找 7.4 哈希表 7.4.1 哈希表和哈希方法 7.4.2 常用的哈希函數(shù) 7.4.3 沖突處理方法 （1）線性探測法 （2）二次探測法 （3）雙哈希函數(shù)探測法 7.4.4 哈希表的查找及其分析

54、 教 師 授 課 教 案 教學單元（章節(jié)）： 第八章 排序 8.1 基本概念 8.2 簡單排序方法 教學目的： 理解排序的基本概念 掌握插入排序、簡單選擇排序的方法 知識要點： 排序的基本概念和性能分析 直接插入排序、冒泡排序、簡單選擇排序 技能要點：直接插入排序、冒泡排序和 簡單選擇排序的性能分析 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況： P186：1 課后分析與小結： 本節(jié)重點：冒泡排序算法、直接插入排序算法 本節(jié)難點：冒泡排序算法

55、、簡單選擇排序算法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第八章 排序 8.1 基本概念 8.2 簡單排序方法 8.2.1 直接插入排序 1. 直接插入排序方法的思路 2. 直接插入排序算法實現(xiàn) 3. 直接插入排序效率分析 8.2.2 冒泡排序 1. 冒泡排序方法的思路 2. 冒泡排序算法實現(xiàn) 3. 冒泡排序效率分析 8.2.3 簡單選擇排序 1. 簡單選擇排序方法的思

56、路 2. 簡單選擇排序算法實現(xiàn) 3. 簡單選擇排序效率分析 教 師 授 課 教 案 教學單元（章節(jié)）： 第八章 排序 8.3 快速排序 8.5 歸并排序 8.7 排序方法的比較和討論 教學目的： 理解快速排序和歸并排序的方法及性能分析 了解主要排序方法各自的特點 知識要點： 快速排序、兩路歸并的迭代算法 兩路歸并的遞歸算法、主要排序方法各自的特點 技能要點：快速排序、兩路歸并的迭代算法 兩路歸并的遞歸算法、排序方法的比較 教學方法： 講授+演示 教具及教學手段： 投影 作業(yè)布置情況：

57、 P186：1、2 課后分析與小結： 本節(jié)重點：兩路歸并算法、快速排序算法 本節(jié)難點：兩路歸并算法、快速排序算法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 第八章 排序 8.3 快速排序 1. 快速排序的基本思路 2. 快速排序算法實現(xiàn) 3. 快速排序的過程示意 4. 快速排序效率分析 8.5 歸并排序 1. 歸并排序的基本思路 2. 歸并排序算法實現(xiàn) 1）兩路歸并的迭代

58、算法 2）兩路歸并的遞歸算法 3. 歸并排序的過程示意 4. 歸并排序效率分析 8.7 排序方法的比較和討論 1. 從從算法的時間復雜度、空間復雜度和算法所需的輔助空間三個方面來比較 2. 從排序方法的穩(wěn)定性角度對各種排序方法加以比較。 教 師 授 課 教 案 教學單元（章節(jié)）： 實驗1 對線性表進行順序存儲的操作的實現(xiàn) 教學目的： 1．掌握線性表的抽象數(shù)據(jù)類型。 2．掌握線性表的順序存儲及相關算法。 知識要點：用C語言采用順存存儲結構定義線性表 對線性表順序存儲的各種操作的實現(xiàn)

59、技能要點：用C實現(xiàn)線性表順序存儲的基本操作：插入、刪除、查找等 教學方法： 講授+演示+實驗 教具及教學手段： 作業(yè)布置情況： 上機實驗 課后分析與小結： 本節(jié)重難點：用C實現(xiàn)線性表順序存儲的基本操作 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 實驗容： 用C語言實現(xiàn)線性表順序存儲結構的創(chuàng)建、插入、刪除、查找、合并等算法。

60、 7.排序,從小到大 教 師 授 課 教 案 教學單元（章節(jié)）：實驗2 對線性表進行鏈式存儲的操作的實現(xiàn) 教學目的： 1．掌握線性表的抽象數(shù)據(jù)類型。 2．掌握線性表的鏈式存儲及相關算法。 知識要點：用C語言采用鏈式存儲結構定義線性表 對線性表鏈式存儲的各種操作的實現(xiàn) 技能要點：用C實現(xiàn)線性表鏈式存儲的基本操作：插入、刪除、查找等 教學方法： 講授+演示+實驗 教具及教學手段： 作業(yè)布置情況： 上機實驗 課后分析與小結： 本節(jié)重難點：用C實現(xiàn)線性表鏈式存儲的基

61、本操作 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字） 年 月 日 教學容及過程 板書或旁注 實驗容： 用C語言實現(xiàn)線性表鏈式存儲結構的創(chuàng)建、插入、刪除、查找、排序等算法。 1. 單鏈表的定義 2. 頭輸入法建立單鏈表 3. 插入結點 4. 刪除結點 5. 查找元素 6. 排序 7. 查找單鏈表結點 8. 逆置 教 師 授 課 教 案 教學單元（章節(jié)）： 實驗3 棧

62、及棧的應用實驗 教學目的： 1．掌握棧的抽象數(shù)據(jù)類型。 2．掌握實現(xiàn)棧的各種操作的算法。 3．理解棧與遞歸的關系。 知識要點：棧的每種操作在順棧和鏈棧上的實現(xiàn)算法 用Ｃ描述中綴換后綴算法 技能要點：棧的每種操作在順棧和鏈棧上的實現(xiàn)算法 用Ｃ描述中綴換后綴算法 教學方法： 講授+演示+實驗 教具及教學手段： 作業(yè)布置情況： 上機實驗 課后分析與小結： 本節(jié)重難點：棧的每種操作在順棧和鏈棧上的實現(xiàn)算法 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字）

63、 年 月 日 教學容及過程 板書或旁注 實驗容： 用C語言實現(xiàn)順序棧和鏈棧存儲結構的主要算法。用Ｃ描述中綴換后綴算法 1. C語言實現(xiàn)順序棧的定義、創(chuàng)建、置空、判?？账惴? 2. C語言實現(xiàn)順序棧的出棧、入棧、查找算法 3. C語言實現(xiàn)鏈棧的定義、創(chuàng)建、置空、判棧空算法 4. C語言實現(xiàn)鏈棧的出棧、入棧、查找算法 5. C語言實現(xiàn)中綴表達式轉化成后綴表達式并求值 教 師 授 課 教 案 教學單元（章節(jié)）： 實驗4　隊列及隊列應用實驗 教學目的： 1．掌

64、握隊列的抽象數(shù)據(jù)類型。 2．掌握隊列的各種操作的實現(xiàn)算法。 知識要點： 1．用Ｃ描述隊列的各種操作在順隊和鏈隊上的實現(xiàn)算法。 2．用Ｃ描述進隊，出隊的算法。 技能要點：1．用Ｃ描述隊列的各種操作在順隊和鏈隊上的實現(xiàn)算法。 2．用Ｃ描述進隊，出隊的算法。 教學方法： 講授+演示+實驗 教具及教學手段： 作業(yè)布置情況： 上機實驗 課后分析與小結： 本節(jié)重難點：用Ｃ描述隊列的各種操作在順隊和鏈隊上的實現(xiàn) 審 批：教研室主任（簽字） 年 月 日 抽 查：系部主任（簽字）

65、 年 月 日 教學容及過程 板書或旁注 實驗容： 用C語言描述隊列的各種操作在順隊和鏈隊上的實現(xiàn)算法。用Ｃ描述進隊，出隊的算法。 C語言實現(xiàn)順序隊列的定義、創(chuàng)建、置空、判空算法 C語言實現(xiàn)順序隊列的出隊、入隊、查找算法 C語言實現(xiàn)鏈隊列的定義、創(chuàng)建、置空、判空算法 C語言實現(xiàn)鏈隊列的出隊、入隊、查找算法 1. 教 師 授 課 教 案 教學單元（章節(jié)）： 實驗5　串的操作實驗 教學目的：1．串的抽象數(shù)據(jù)類型。 2．掌握串的各種操作的實現(xiàn)算法。

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