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

教學(xué)單元（章節(jié)）:第一章:緒論

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種數(shù)據(jù)的存儲結(jié)構(gòu)、程序與數(shù)據(jù)結(jié)構(gòu)

技能要點(diǎn)：數(shù)據(jù)結(jié)構(gòu)、4種基本的數(shù)據(jù)結(jié)構(gòu)、

4種數(shù)據(jù)的存儲結(jié)構(gòu)

教學(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)的意義

審批：教研室主任(簽字）年月日

抽查：系部主任（簽字)年月日

1

教學(xué)內(nèi)容及過程板書或旁注

第一章：緒論

1.1數(shù)據(jù)結(jié)構(gòu)概念

1。1。1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1．計(jì)算機(jī)處理問題的分類（1）數(shù)值計(jì)算問題

（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)算的描述

1。1。2有關(guān)概念和術(shù)語

數(shù)據(jù)

數(shù)據(jù)元素

數(shù)據(jù)項(xiàng)

數(shù)據(jù)結(jié)構(gòu):集合、線性、樹型、圖狀

數(shù)據(jù)結(jié)構(gòu):包括物理結(jié)構(gòu)、邏輯結(jié)構(gòu)

數(shù)據(jù)的四種基本存儲方法

（1）順序存儲方法

（2）鏈接存儲方法

(3）索引存儲方法

(4)散列存儲方法

教師授課教案

2

教學(xué)單元(章節(jié))：第一章:緒論

1.2算法描述

1.3算法分析

教學(xué)目的：理解算法的定義、特性、描述方法

掌握簡單的時間復(fù)雜度的估計(jì)

知識要點(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ù)雜度的估計(jì)

審批：教研室主任(簽字)年月日

抽查:系部主任（簽字）年月日

教學(xué)內(nèi)容及過程板書或旁注

3

第一章：緒論

1.2算法描述

1.2。1算法特性

(1)有窮性（2）確定性(3）可行性（4)輸入(5）輸出

好的算法的特點(diǎn)

(1)正確（2)可讀（3)健壯（4)高效

數(shù)據(jù)結(jié)構(gòu)的基本操作：

（1）查找(2）讀?。?）插入（4）刪除（5）修改

1。2。2算法描述

算法描述的種類:

(1）框圖/流程圖算法（2）非形式算法

(3）偽語言算法（4）高級語言算法

1.3算法分析

時間復(fù)雜度:解決某問題所花費(fèi)的時間大小,即程序運(yùn)行從開始

到結(jié)束所需要的時間，記為T（n)

空間復(fù)雜度:解決某問題的程序完全運(yùn)行時所占用的存儲空間

大小,記為S(n）

【例】算法MatrixMultidy的時間復(fù)雜度T(n)如(1。1）式所示，

當(dāng)n趨向無窮大時，顯然有

教師授課教案

4

教學(xué)單元（章節(jié)）：C語言第七章：數(shù)組

7.1一維數(shù)組的定義和引用

7。2二維數(shù)組的定義和引用

7。3字符數(shù)組

教學(xué)目的：理解一維數(shù)組、二維數(shù)組、字符數(shù)組的定義

掌握一維數(shù)組、二維數(shù)組、字符數(shù)組的引用和初始化方法

掌握一維數(shù)組、二維數(shù)組、字符數(shù)組的簡單應(yīng)用程序

知識要點(diǎn):一維數(shù)組、二維數(shù)組、字符數(shù)組的定義、引用、初始化

一維數(shù)組、二維數(shù)組、字符數(shù)組相關(guān)的簡單程序

技能要點(diǎn)：用數(shù)組來處理相關(guān)問題的程序

教學(xué)方法：講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況:P152；7。1P152;7。3

P153；7.11P153；7。15

課后分析與小結(jié)：

本節(jié)重點(diǎn)：數(shù)組的定義、引用、初始化

本節(jié)難點(diǎn)：用數(shù)組求解簡單的問題

審批:教研室主任(簽字)年月日

抽查:系部主任(簽字）年月日

5

教學(xué)內(nèi)容及過程板書或旁注

第七章數(shù)組

7。1一維數(shù)組的定義和引用

7.1。1一維數(shù)組的定義

7.1.2一維數(shù)組的引用

7。1。3一維數(shù)組的初始化

7。1.4一維數(shù)組程序舉例

7.2二維數(shù)組的定義和引用

7。2.1二維數(shù)組的定義

7。2。2二維數(shù)組的引用

7.2.3二維數(shù)組的初始化

7.2.4二維數(shù)組程序舉例

7。3字符數(shù)組

7.3.1字符數(shù)組的定義

7。3。2字符數(shù)組的初始化

7。3.3字符數(shù)組的引用

7.3。5字符數(shù)組的輸入輸出

6

教師授課教案

教學(xué)單元（章節(jié)）：C語言第十章:指針

10。1地址和指針的概念

10.2變量的指針和指針變量

教學(xué)目的:理解地址和指針的概念

掌握指針變量的定義和引用

知識要點(diǎn):地址、指針、指針變量的定義和引用、

指針變量作為函數(shù)參數(shù)

技能要點(diǎn):指針變量的定義和引用

指針變量作為函數(shù)參數(shù)

教學(xué)方法:講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況:P278；10。1

P278；10。2

課后分析與小結(jié)：

本節(jié)重點(diǎn)：指針的含義、指針變量的引用

本節(jié)難點(diǎn):指針變量的引用、指針變量作為函數(shù)參數(shù)

審批：教研室主任(簽字）年月日

抽查：系部主任（簽字）年月日

7

教學(xué)內(nèi)容及過程板書或旁注

C語言第十章：指針

10。1地址和指針的概念

1．地址的概念

2。指針的概念

10.2變量的指針和指針變量

10。2.1定義一個指針變量

1。定義指針變量的一般形式：

基類型＊指針變量名

2。定義指針變量的注意事項(xiàng)

10。2.2指針變量的引用

1。&—-取址運(yùn)算符。

2.＊——指針運(yùn)算符,

10。2.3指針變量作為函數(shù)參數(shù)

（1)使一個指針變量指向另一個變量

（2)通過指針變量訪問整型變量

8

教師授課教案

教學(xué)單元（章節(jié))：C語言第十章：指針

10。3。1指向數(shù)組元素的指針

10。3。2通過指針引用數(shù)組元素

10。4。1字符串的表現(xiàn)形式

10。8指針運(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ù)組元素、字符串

審批：教研室主任（簽字）年月日

抽查：系部主任(簽字）年月日

9

教學(xué)內(nèi)容及過程板書或旁注

10。3數(shù)組與指針

10。3.1指向數(shù)組元素的指針

定義一個指向數(shù)組元素的指針變量

10.3.2通過指針引用數(shù)組元素

數(shù)組元素的引用可以用

1。下標(biāo)法:a[i］

2。指針法：＊（a+i）或*（p+i)

10.4字符串與指針

10。4。1字符串的表現(xiàn)形式

1。用字符數(shù)組存放一個字符串

2。用字符指針指向一個字符串

3．字符串常量和字符指針的初始化

10。8指針運(yùn)算小結(jié)

10。8。1有關(guān)指針的數(shù)據(jù)類型的小結(jié)

10。8。2指針運(yùn)算小結(jié)

1。指針變量的加減

2。指針變量賦值

3.指針變量的比較

10

教師授課教案

教學(xué)單元（章節(jié)）：C語言第十一章：結(jié)構(gòu)體與共用體

11.1-11.5.1結(jié)構(gòu)體

11。7。3處理動態(tài)鏈表所需的函數(shù)

11。10用typedef定義類型

教學(xué)目的：掌握結(jié)構(gòu)體變量的定義、引用和初始化

掌握處理動態(tài)鏈表所需的函數(shù)

掌握用typedef定義類型

知識要點(diǎn)：結(jié)構(gòu)體變量、結(jié)構(gòu)體數(shù)組，malloc函數(shù)

calloc函數(shù)、free函數(shù)、typedef

技能要點(diǎn)：結(jié)構(gòu)體變量的定義、引用和初始化

用typedef定義類型

教學(xué)方法：講授+演示

教具及教學(xué)手段:投影

作業(yè)布置情況:P318；11。1

P318;11.5

課后分析與小結(jié):

本節(jié)重點(diǎn)：結(jié)構(gòu)體變量、處理動態(tài)鏈表所需的函數(shù)

本節(jié)難點(diǎn):結(jié)構(gòu)體變量的引用和初始化、用typedef定義類型

審批:教研室主任(簽字）年月日

抽查：系部主任（簽字）年月日

11

教學(xué)內(nèi)容及過程板書或旁注

第十一章：結(jié)構(gòu)體與共用體

11。1概述

11.2定義結(jié)構(gòu)體類型變量的方法

1.先定義結(jié)構(gòu)體類型，再用類型標(biāo)識去定義變量

2.定義類型的同時定義變量3。直接定義結(jié)構(gòu)體類型變量

11.3結(jié)構(gòu)體變量的引用

1.結(jié)構(gòu)體變量各成員的引用

引用形式：結(jié)構(gòu)體變量名。成員名

2。結(jié)構(gòu)體變量各成員的輸入、輸出

11.4結(jié)構(gòu)體變量的初始化

11.5結(jié)構(gòu)體數(shù)組

1.結(jié)構(gòu)體數(shù)組的定義2.結(jié)構(gòu)體數(shù)組的初始化

3。結(jié)構(gòu)體數(shù)組stu的存儲結(jié)構(gòu)4。結(jié)構(gòu)體數(shù)組的引用

11.6指針與結(jié)構(gòu)體

1.指向結(jié)構(gòu)體變量的指針

2。指向結(jié)構(gòu)體變量的指針與結(jié)構(gòu)體變量的等價關(guān)系

11。7用指針處理鏈表

3處理動態(tài)鏈表所需的函數(shù)

內(nèi)存分配函數(shù)原型:void＊malloc（unsignedsize)；

內(nèi)存分配函數(shù)原型：void＊calloc(unsignedsize）；

內(nèi)存釋放函數(shù)原形：voidfree(void＊p）；

11。10用typedef定義類型

1、使用的一般形式：

typedef原類型名新類型名;

2。用typedef定義類型的方法（舉例）

①先按定義數(shù)組變量形式書寫：intn［100］；

②將變量名換成新類型名：intNUM[１００］；

③在最前面加上typedef:typedefintNUM［１００］；

④用新類型名來定義變量:NUMｎ;

3。用typedef定義類型的說明:

（1）用typedef可以聲明各種類型名，但不能用來定義變量。

（2)用typedef只是對已經(jīng)存在的類型增加一個類型名，而沒

有創(chuàng)造新的類型。

（3）使用typedef有利于程序的通用與移植。

12

教師授課教案

教學(xué)單元（章節(jié)）：第二章：線性表

2。1線性表的邏輯結(jié)構(gòu)

2。2線性表的順序存儲及操作實(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；1

P38；6

課后分析與小結(jié)：

本節(jié)重點(diǎn)：線性表的定義、特點(diǎn)和順序表的基本操作

本節(jié)難點(diǎn)：順序表的插入和刪除算法及其時間復(fù)雜度

審批:教研室主任(簽字）年月日

抽查：系部主任(簽字）年月日

13

教學(xué)內(nèi)容及過程板書或旁注

2.1線性表的邏輯結(jié)構(gòu)

2.1。0線性表的實(shí)際例子

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.刪除：Delete_List（L，i）

2。2線性表的順序存儲結(jié)構(gòu)

2。2。1線性表的順序存儲結(jié)構(gòu)

1。順序表的定義和特點(diǎn)

2.順序表的存儲和類型定義

2。2。2順序表的基本算法實(shí)現(xiàn)

1.初始化順序表L

2.插入

3.刪除

4.按值查找

14

教師授課教案

教學(xué)單元（章節(jié)）：第二章：線性表

2。3。1單鏈表

2。3。2單鏈表上基本運(yùn)算的實(shí)現(xiàn)

教學(xué)目的:掌握單鏈表的定義、特點(diǎn)及存儲結(jié)構(gòu)

掌握單鏈表的查找、插入與刪除算法

理解帶首結(jié)點(diǎn)的單鏈表的優(yōu)點(diǎn)

知識要點(diǎn)：單鏈表的定義、特點(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):單鏈表的查找、插入和刪除算法

審批：教研室主任（簽字）年月日

抽查：系部主任（簽字)年月日

15

教學(xué)內(nèi)容及過程板書或旁注

2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

2。3。1單鏈表

1。單鏈表的定義和特點(diǎn)

2。單鏈表的存儲結(jié)構(gòu)和類型定義

2.3.2單鏈表上的基本運(yùn)算的實(shí)現(xiàn)

1。建立單鏈表

(1)頭部插入法建立

(2）尾部插入法建立

2.求表長

（1）帶頭結(jié)點(diǎn)的單鏈表

（2）不帶頭結(jié)點(diǎn)的單鏈表

3。查找操作

（1)按序號查找

(2）按值查找

4.插入操作

（1)后插節(jié)點(diǎn)

(2)前插節(jié)點(diǎn)

(3）插入運(yùn)算

5。刪除操作

（1)刪除節(jié)點(diǎn)

(2)刪除運(yùn)算

16

教師授課教案

教學(xué)單元（章節(jié)）:第二章：線性表

2.3。3循環(huán)鏈表

2。3.4雙向鏈表

教學(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)鏈表連接操作、雙向鏈表的插入和刪除

審批：教研室主任(簽字）年月日

抽查：系部主任(簽字）年月日

17

教學(xué)內(nèi)容及過程板書或旁注

2.3.3循環(huán)鏈表

一．循環(huán)鏈表的定義

二．循環(huán)鏈表示意圖

（1)帶頭結(jié)點(diǎn)的單循環(huán)鏈表

（2）僅設(shè)尾指針的單循環(huán)鏈表

三．循環(huán)鏈表的特點(diǎn)

四。循環(huán)鏈表的說明

2。3。4雙向循環(huán)鏈表

一.雙向鏈表的概念

二。雙鏈表示意圖

三．雙鏈表的類型定義

四．雙向鏈表的操作

1。雙向鏈表中結(jié)點(diǎn)的前插

2.雙向鏈表中結(jié)點(diǎn)的刪除

五。順序表和鏈表的比較

18

教師授課教案

教學(xué)單元(章節(jié))：第三章：棧和隊(duì)列

3.1棧

教學(xué)目的：掌握棧的定義、特點(diǎn)和存儲結(jié)構(gòu)

掌握順序棧和鏈棧的基本運(yùn)算

理解棧與遞歸的關(guān)系

知識要點(diǎn)：棧的定義、特點(diǎn)、基本運(yùn)算，順序棧和鏈棧的主要操作

上溢、下溢，?？张c棧滿的條件，棧與遞歸問題

技能要點(diǎn)：順序棧和鏈棧的置空、判棧空、入棧、出棧操作

教學(xué)方法:講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況:P63;1、3、4

課后分析與小結(jié):

本節(jié)課的重點(diǎn)：順序棧和鏈棧的基本操作

難點(diǎn):棧與遞歸問題

審批：教研室主任（簽字）年月日

抽查:系部主任（簽字）年月日

19

教學(xué)內(nèi)容及過程板書或旁注

第三章：棧和隊(duì)列

3。1棧

3。1.1棧的定義和基本運(yùn)算

1。棧的定義

棧:是限制僅在表尾進(jìn)行插入和刪除的線性表.

2。基本運(yùn)算

(1）初始化棧：構(gòu)在一個空棧

(2)置空棧：將S置成空棧

（3）入棧：在棧頂插入一個新元素X

（4)出棧：刪除(彈出）棧S的頂部元素

（5）取棧頂）：取棧S的頂部元素

（6）判斷空棧Empty_Stack(S):空棧返回1

3。1.2棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)

1.順序棧

1)順序棧的定義

2）順序?；具\(yùn)算

⑴置空棧

⑵判空棧

⑶入棧

⑷出棧

3.1。2棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)

2。鏈棧

1）鏈棧的定義

2）鏈?；具\(yùn)算

⑴置空棧

⑵判空棧

⑶入棧

⑷出棧

3。1。3棧與遞歸的實(shí)現(xiàn)

1.具有遞歸特性的問題

（1)遞歸定義的數(shù)學(xué)函數(shù)

(2）遞歸數(shù)據(jù)結(jié)構(gòu)的處理

(3)遞歸求解方法

2。遞歸算法的設(shè)計(jì)方法與遞歸過程的實(shí)現(xiàn)

（1)應(yīng)用遞歸算法的前提

（2）Hanoi塔問題的遞歸函數(shù)

（3）Fibonacci數(shù)列的遞歸算法

20

教師授課教案

教學(xué)單元(章節(jié)）:第三章：棧和隊(duì)列

3.2棧的應(yīng)用舉例

3。3隊(duì)列

3。4隊(duì)列應(yīng)用舉例

教學(xué)目的:掌握隊(duì)列的定義、特點(diǎn)和存儲結(jié)構(gòu)

掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算

理解循環(huán)隊(duì)列的意義和隊(duì)列的應(yīng)用

知識要點(diǎn)：隊(duì)列的定義、特點(diǎn)、存儲結(jié)構(gòu)、基本運(yùn)算

循環(huán)隊(duì)列產(chǎn)生的原因，循環(huán)隊(duì)列和鏈隊(duì)列的主要操作

假溢出,循環(huán)隊(duì)列隊(duì)空與隊(duì)滿的條件

技能要點(diǎn)：循環(huán)隊(duì)列隊(duì)空與隊(duì)滿的條件，

循環(huán)隊(duì)列和鏈隊(duì)列的入隊(duì)、出隊(duì)、判隊(duì)空操作

教學(xué)方法:講授+演示

教具及教學(xué)手段:投影

作業(yè)布置情況:P63;2、5、9

課后分析與小結(jié)：

本節(jié)課的重點(diǎn)：循環(huán)隊(duì)列和鏈隊(duì)列的基本操作

難點(diǎn):棧的應(yīng)用、循環(huán)隊(duì)列

審批：教研室主任（簽字）年月日

抽查:系部主任（簽字）年月日

21

教學(xué)內(nèi)容及過程板書或旁注

第三章：棧和隊(duì)列

3.2棧的應(yīng)用舉例

1。數(shù)制轉(zhuǎn)換

2.表達(dá)式求值

3.3隊(duì)列

3.3。1隊(duì)列的定義和基本運(yùn)算

1。隊(duì)列的定義和特點(diǎn)

2。隊(duì)列結(jié)構(gòu)的基本操作

1。Init_Queue(Q）將Q置為一個空隊(duì)列

2。In_Queue(Q，x）插入元素x為隊(duì)Q的新隊(duì)尾元素

3。Out_Queue（Q，x)刪除Q的隊(duì)頭元素，并返回其值

4。Front_Queue(Q，x）返回Q的隊(duì)頭元素

5.Empty_Queue(Q)判隊(duì)空

3。3.2隊(duì)列的存儲和運(yùn)算實(shí)現(xiàn)

1．順序隊(duì)列:定義、特點(diǎn)和存儲結(jié)構(gòu)

2.循環(huán)隊(duì)列：定義、存儲結(jié)構(gòu)和基本操作

3。鏈隊(duì)列

1）定義、特點(diǎn)和存儲結(jié)構(gòu)

2）基本操作

3。4隊(duì)列應(yīng)用舉例

22

教師授課教案

教學(xué)單元（章節(jié)）：第四章：串和數(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)算

定長串連接、求子串和串比較操作

教學(xué)方法：講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況：P78；2、3

課后分析與小結(jié)：

本節(jié)重點(diǎn)：串的定義、存儲結(jié)構(gòu)和基本運(yùn)算

本節(jié)難點(diǎn)：串連接、求子串和串比較算法

審批：教研室主任（簽字）年月日

抽查：系部主任(簽字）年月日

23

教學(xué)內(nèi)容及過程板書或旁注

第四章：串和數(shù)組

4.1串

4.1。1串的基本概念

1。串的定義

2。術(shù)語

4。1。2串的基本運(yùn)算

（1)求串長

（2)串賦值

（3)串連接

（4)求子串

（5）串比較

（6)串定位

（7)插入

（8)刪除

（9）串替換

4。1。2串的存儲結(jié)構(gòu)

1.串的定長順序存儲結(jié)構(gòu)

2。堆分配存儲結(jié)構(gòu)

3。定長順序串基本運(yùn)算的實(shí)現(xiàn)

（1）串連接

(2)子串

(3）串比較

24

教師授課教案

教學(xué)單元（章節(jié)):第四章：串和數(shù)組

4。2數(shù)組

教學(xué)目的：了解數(shù)組的邏輯存儲結(jié)構(gòu)和內(nèi)存映像

了解稀疏矩陣的定義及其數(shù)組實(shí)現(xiàn)

知識要點(diǎn)：數(shù)組與線性表、數(shù)組的邏輯存儲結(jié)構(gòu)和內(nèi)存映像

稀疏矩陣的定義、壓縮存儲方法、轉(zhuǎn)置

技能要點(diǎn):數(shù)組的內(nèi)存映像、數(shù)組元素地址的計(jì)算

稀疏矩陣的存儲、轉(zhuǎn)置

教學(xué)方法：講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況:P78；5、6

課后分析與小結(jié)：

本節(jié)重點(diǎn):數(shù)組的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、稀疏矩陣

本節(jié)難點(diǎn)：稀疏矩陣的壓縮方法

審批：教研室主任（簽字)年月日

抽查:系部主任（簽字)年月日

25

教學(xué)內(nèi)容及過程板書或旁注

第四章：串和數(shù)組

4。2數(shù)組

4。2。1數(shù)組的邏輯結(jié)構(gòu)

1）1維數(shù)組

2）2維數(shù)組

4。2。2數(shù)組的內(nèi)存映像

1.存儲方式

1）以行為主

2）以列為主

2。數(shù)組物理地址的計(jì)算

1）1維數(shù)組物理地址計(jì)算函數(shù)表達(dá)式

2）2維數(shù)組物理地址計(jì)算函數(shù)表達(dá)式

4。2。3稀疏矩陣

1。定義

2.特殊矩陣

3。稀疏矩陣的壓縮存儲

26

教師授課教案

教學(xué)單元(章節(jié)）:第五章：樹和二叉樹

5。1樹的概念和基本操作

5.2。1二叉樹的基本概念

5。2。2二叉樹的主要性質(zhì)

教學(xué)目的：掌握樹的定義、特點(diǎn)和相關(guān)術(shù)語

理解樹的基本操作

掌握二叉樹的定義、相關(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ì)

審批：教研室主任（簽字）年月日

抽查：系部主任（簽字）年月日

27

教學(xué)內(nèi)容及過程板書或旁注

28

第五章:樹和二叉樹

5。1樹的概念和基本操作

5。1.1樹的定義和相關(guān)術(shù)語

1.樹的定義

2。相關(guān)術(shù)語

5.1.2樹的基本操作

（1）Initiate（t）初始化一棵空樹t。

（2）Root（x)求結(jié)點(diǎn)x所在樹的根結(jié)點(diǎn)。

（3)Parent(t，x）求樹t中結(jié)點(diǎn)x的雙親結(jié)點(diǎn).

（4）Child（t，x,i）求樹t中結(jié)點(diǎn)x的第i個孩子結(jié)點(diǎn).

(5)RightSibling（t,x）求樹t中結(jié)點(diǎn)x的第一個右邊兄弟結(jié)

點(diǎn)。

(6)Insert（t，x,i，s）把以s為根結(jié)點(diǎn)的樹插入到樹t中作

為結(jié)點(diǎn)x的第i棵子樹。

（7）Delete(t，x，i）在樹t中刪除結(jié)點(diǎn)x的第i棵子樹。

（8）Traverse（t）是樹的遍歷操作，訪問每個結(jié)點(diǎn)。

5。2二叉樹

5.2。1二叉樹的基本概念

1．二叉樹

2。二叉樹的相關(guān)概念：滿二叉樹、完全二叉樹

5。2。2二叉樹的主要性質(zhì)

性質(zhì)1：層數(shù)與節(jié)點(diǎn)的關(guān)系

性質(zhì)2：深度與節(jié)點(diǎn)的關(guān)系

性質(zhì)3：非空二叉樹的度為2的結(jié)點(diǎn)與葉子節(jié)點(diǎn)的關(guān)系

性質(zhì)4：完全二叉樹的深度與節(jié)點(diǎn)的關(guān)系

性質(zhì)5：完全二叉樹的相關(guān)性質(zhì)

教師授課教案

29

教學(xué)單元（章節(jié)）：第五章：樹和二叉樹

5。2。3二叉樹的基本操作與存儲實(shí)現(xiàn)

5。2.4二叉樹的遍歷

教學(xué)目的:掌握二叉樹的2種存儲結(jié)構(gòu)

理解二叉樹的基本操作

掌握二叉樹的遍歷方法

知識要點(diǎn)：二叉樹的順序存儲、二叉鏈表存儲、三叉鏈表存儲

二叉樹的基本操作

先序遍歷、中序遍歷、后序遍歷、層次遍歷

技能要點(diǎn)：二叉樹的順序存儲、二叉樹鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)

先序遍歷、中序遍歷、后序遍歷、層次遍歷二叉樹的過程

教學(xué)方法：講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況：P107；3、4、5、6

課后分析與小結(jié)：

本節(jié)重點(diǎn)：二叉樹的存儲結(jié)構(gòu)和遍歷方法

本節(jié)難點(diǎn):先序、中序、后序遍歷二叉樹

審批：教研室主任（簽字）年月日

抽查：系部主任(簽字）年月日

教學(xué)內(nèi)容及過程板書或旁注

30

第五章：樹和二叉樹

5。2.3二叉樹的基本操作與存儲實(shí)現(xiàn)

1。二叉樹的順序存儲結(jié)構(gòu)

2.二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1）二叉鏈表存儲

2）三叉鏈表存儲

3。二叉樹的基本操作

（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)

5.2。4二叉樹的遍歷

1。先序遍歷

2。中序遍歷

3。后序遍歷

4。層次遍歷

教師授課教案

31

教學(xué)單元(章節(jié)）：第五章:樹和二叉樹

5。3樹和森林

教學(xué)目的:理解樹的3種存儲結(jié)構(gòu)

掌握樹、森林與二叉樹的轉(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)容及過程板書或旁注

32

第五章：樹和二叉樹

5。3樹和森林

5.3.1樹的存儲

1。雙親表示法

2.孩子鏈表示法

3。孩子兄弟表示法

5.3.2樹、森林與二叉樹的轉(zhuǎn)換

1.樹轉(zhuǎn)換為二叉樹

2。森林轉(zhuǎn)換為二叉樹

3。二叉樹轉(zhuǎn)換為樹和森林

5。3。3樹和森林的遍歷

1。樹的遍歷

1）先根遍歷

2）后根遍歷

2。森林的遍歷

(1）先序遍歷

(2）后序遍歷

教師授課教案

33

教學(xué)單元（章節(jié)）：第五章：樹和二叉樹

5。4最優(yōu)二叉樹-—哈夫曼樹

教學(xué)目的：理解哈夫曼樹的相關(guān)定義

掌握最優(yōu)二叉樹的構(gòu)建方法

掌握哈夫曼編碼的定義和實(shí)現(xiàn)過程

知識要點(diǎn)：哈夫曼樹、帶權(quán)路徑長度、哈夫曼編碼、

等長編碼、不等長編碼

技能要點(diǎn)：構(gòu)造哈夫曼樹

設(shè)計(jì)哈夫曼編碼

教學(xué)方法：講授+演示

教具及教學(xué)手段:投影

作業(yè)布置情況：P109；20、21

課后分析與小結(jié)：

本節(jié)重點(diǎn)：最優(yōu)二叉樹和哈夫曼編碼的構(gòu)造方法

本節(jié)難點(diǎn)：帶權(quán)路徑、哈夫曼編碼

審批：教研室主任（簽字）年月日

抽查:系部主任(簽字）年月日

教學(xué)內(nèi)容及過程板書或旁注

34

第五章：樹和二叉樹

5.4最優(yōu)二叉樹-—哈夫曼樹

5。4.1哈夫曼樹的基本概念

1。哈夫曼樹的概念

2。權(quán)值

3.帶權(quán)路徑長度

5。4。2哈夫曼樹的構(gòu)造算法

1.哈夫曼樹的構(gòu)造步驟

5.4。3哈夫曼編碼

1。等長編碼

2.不等長編碼

3。哈夫曼編碼的概念

4。哈夫曼編碼的構(gòu)造過程

5。4.4哈夫曼編碼的算法實(shí)現(xiàn)

1。哈夫曼編碼的算法思路

2.哈夫曼編碼的算法實(shí)現(xiàn)

教師授課教案

35

教學(xué)單元（章節(jié)）：第六章：圖

6。1圖的基本概念

6。2圖的存儲表示

教學(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、2、4

課后分析與小結(jié)：

本節(jié)重點(diǎn)：圖的相關(guān)術(shù)語和存儲表示

本節(jié)難點(diǎn)：鄰接矩陣、鄰接表

審批：教研室主任（簽字）年月日

抽查:系部主任（簽字）年月日

36

教學(xué)內(nèi)容及過程板書或旁注

第六章：圖

6。1圖的基本概念

6.1.1圖的定義和術(shù)語

1.定義

2。相關(guān)術(shù)語

1）有向圖、無向圖、完全圖

2）頂點(diǎn)、邊、弧、弧頭、弧尾

3)度、入度、出度

4）權(quán)和網(wǎng)

5）路徑和路徑長度、回路、簡單路徑、簡單回路

6）子圖、連通圖、強(qiáng)連通圖

7)連通的、連通分量、強(qiáng)連通分量

8)生成樹、生成森林

6.1.2圖的基本操作

（1)Creatgraph（G）（2）DestroyGraph（G）

（3)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圖的存儲表示

6。2。1鄰接矩陣

1。鄰接矩陣存儲結(jié)構(gòu)的定義

2。表示方法

6。2.2鄰接表

1。鄰接表存儲結(jié)構(gòu)的定義

2.表示方法

37

教師授課教案

教學(xué)單元（章節(jié))：第六章：圖

6。3圖的遍歷

6。4.1最小生成樹

教學(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)：圖的兩種遍歷、最小生成樹

本節(jié)難點(diǎn)：用Prim算法構(gòu)造最小生成樹

審批：教研室主任（簽字）年月日

抽查：系部主任（簽字)年月日

38

教學(xué)內(nèi)容及過程板書或旁注

第六章：圖

6。3圖的遍歷

6。3。1深度優(yōu)先搜索

1.深度優(yōu)先搜索的定義

2.深度優(yōu)先搜索的算法實(shí)現(xiàn)

6。3。2廣度優(yōu)先搜索

1.廣度優(yōu)先搜索的定義

2。廣度優(yōu)先搜索的算法實(shí)現(xiàn)

6。4圖的應(yīng)用

6.4.1最小生成樹

1.最小生成樹的基本概念

2。構(gòu)造最小生成樹的Prim算法

1)Prim算法的基本思想

2）Prim算法的基本步驟

3）Prim算法的C語言描述

39

教師授課教案

教學(xué)單元（章節(jié))：第六章：圖

6。4.2最短路徑

6。4.3拓?fù)渑判?/p>

教學(xué)目的：理解最短路徑問題和拓?fù)渑判虻囊饬x

了解用Dijkstra算法求單源最短路徑

了解拓?fù)渑判虻姆椒?/p>

知識要點(diǎn):最短路徑問題、Dijkstra算法的基本思想、

有向無環(huán)圖、AOV網(wǎng)、拓?fù)渑判虻牟襟E

技能要點(diǎn)：用Dijkstra算法求單元最短路徑

拓?fù)渑判蛩惴?/p>

教學(xué)方法:講授+演示

教具及教學(xué)手段:投影

作業(yè)布置情況:P139；6

課后分析與小結(jié)：

本節(jié)重點(diǎn):最短路徑問題和拓?fù)渑判?/p>

本節(jié)難點(diǎn)：Dijkstra算法、拓?fù)渑判蛩惴?/p>

審批：教研室主任(簽字）年月日

抽查：系部主任（簽字）年月日

40

教學(xué)內(nèi)容及過程板書或旁注

第六章:圖

6.4圖的應(yīng)用

6.4。2最短路徑

1。最短路徑問題

2.單源最短路徑

3.Dijkstra算法的思想

4。Dijkstra算法的C語言實(shí)現(xiàn)

6.4.3拓?fù)渑判?/p>

1.有向無環(huán)圖

2.AVO網(wǎng)

3.拓?fù)渑判?/p>

4.拓?fù)渑判虻幕静襟E

5.拓?fù)渑判虻乃惴ㄋ枷?/p>

41

教師授課教案

教學(xué)單元（章節(jié)）：第七章查找

7.1基本概念和術(shù)語

7.2靜態(tài)查找表

教學(xué)目的：了解查找的概念和靜態(tài)查找表結(jié)構(gòu)

理解順序查找和折半查找及其性能分析方法

知識要點(diǎn):關(guān)鍵碼、查找表、平均查找長度

順序查找、有序表的折半查找、分塊查找

技能要點(diǎn)：順序查找、有序表的折半查找和

分塊查找算法的基本思想

教學(xué)方法:講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況:P167：1、3

課后分析與小結(jié):

本節(jié)重點(diǎn):順序查找、折半查找和分塊查找算法

本節(jié)難點(diǎn):折半查找算法的基本思想

審批：教研室主任（簽字）年月日

抽查：系部主任（簽字）年月日

42

教學(xué)內(nèi)容及過程板書或旁注

第七章查找

7。1基本概念和術(shù)語

1。關(guān)鍵碼

2。查找表

3.查找

4.平均查找長度

7。2靜態(tài)查找表

7。2。1靜態(tài)查找表結(jié)構(gòu)

7。2。2順序查找

1）基本思想

2）算法實(shí)現(xiàn)

3）性能分析

7。2.3有序表的折半查找

1）基本思路

2）算法實(shí)現(xiàn)

3)性能分析

7.2.4分塊查找

1）基本思路

2）性能分析

43

教師授課教案

教學(xué)單元（章節(jié))：第七章查找

7.4哈希表

教學(xué)目的：理解哈希方法

理解沖突處理方法

知識要點(diǎn)：哈希表和哈希方法、常用的哈希函數(shù)

沖突處理方法、哈希表的查找和性能分析

技能要點(diǎn):哈希函數(shù)的比較、解決地址沖突的處理方法

教學(xué)方法：講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況：P167：6

課后分析與小結(jié):

本節(jié)重點(diǎn):常用的哈希函數(shù)、沖突處理方法

本節(jié)難點(diǎn):沖突處理方法、哈希表的查找和性能分析

審批:教研室主任（簽字）年月日

抽查：系部主任(簽字）年月日

44

教學(xué)內(nèi)容及過程板書或旁注

第七章查找

7.4哈希表

7。4。1哈希表和哈希方法

7。4。2常用的哈希函數(shù)

1。直接定址法

2。除留余數(shù)法

3。數(shù)字分析法

4。平方取中法

5.折疊法

7.4。3沖突處理方法

1。開放定址法

（1)線性探測法

(2）二次探測法

（3）雙哈希函數(shù)探測法

2.拉鏈法

3。建立公共溢出區(qū)

7。4。4哈希表的查找及其分析

1。哈希表的查找算法

2。哈希表的性能分析

45

教師授課教案

教學(xué)單元（章節(jié)）:第八章排序

8。1基本概念

8.2簡單排序方法

教學(xué)目的：理解排序的基本概念

掌握插入排序、簡單選擇排序的方法

知識要點(diǎn)：排序的基本概念和性能分析

直接插入排序、冒泡排序、簡單選擇排序

技能要點(diǎn)：直接插入排序、冒泡排序和

簡單選擇排序的性能分析

教學(xué)方法:講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況:P186：1

課后分析與小結(jié)：

本節(jié)重點(diǎn):冒泡排序算法、直接插入排序算法

本節(jié)難點(diǎn)：冒泡排序算法、簡單選擇排序算法

審批：教研室主任（簽字)年月日

抽查：系部主任（簽字)年月日

46

教學(xué)內(nèi)容及過程板書或旁注

第八章排序

8.1基本概念

1.排序

2。內(nèi)排序

3。外排序

8.2簡單排序方法

8。2。1直接插入排序

1。直接插入排序方法的思路

2.直接插入排序算法實(shí)現(xiàn)

3.直接插入排序效率分析

8。2。2冒泡排序

1。冒泡排序方法的思路

2.冒泡排序算法實(shí)現(xiàn)

3。冒泡排序效率分析

8。2。3簡單選擇排序

1。簡單選擇排序方法的思路

2.簡單選擇排序算法實(shí)現(xiàn)

3.簡單選擇排序效率分析

47

教師授課教案

教學(xué)單元(章節(jié)）：第八章排序

8。3快速排序

8。5歸并排序

8。7排序方法的比較和討論

教學(xué)目的：理解快速排序和歸并排序的方法及性能分析

了解主要排序方法各自的特點(diǎn)

知識要點(diǎn)：快速排序、兩路歸并的迭代算法

兩路歸并的遞歸算法、主要排序方法各自的特點(diǎn)

技能要點(diǎn):快速排序、兩路歸并的迭代算法

兩路歸并的遞歸算法、排序方法的比較

教學(xué)方法：講授+演示

教具及教學(xué)手段：投影

作業(yè)布置情況：P186:1、2

課后分析與小結(jié):

本節(jié)重點(diǎn)：兩路歸并算法、快速排序算法

本節(jié)難點(diǎn)：兩路歸并算法、快速排序算法

審批：教研室主任(簽字）年月日

抽查：系部主任(簽字）年月日

48

教學(xué)內(nèi)容及過程板書或旁注

第八章排序

8。3快速排序

1?？焖倥判虻幕舅悸?/p>

2。快速排序算法實(shí)現(xiàn)

3.快速排序的過程示意

4。快速排序效率分析

8.5歸并排序

1。歸并排序的基本思路

2。歸并排序算法實(shí)現(xiàn)

1）兩路歸并的迭代算法

2）兩路歸并的遞歸算法

3。歸并排序的過程示意

4。歸