《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》教案

1、數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）教案數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）教案2020至2020學(xué)年第一學(xué)期教案課程名稱數(shù)據(jù)結(jié)構(gòu)使用教材數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）教學(xué)時(shí)數(shù)56課程性質(zhì)必修任課班級(jí)（人數(shù)）信管（53人）信息系（部）信管教研室任課教師山東科技大學(xué)泰山科技學(xué)院課時(shí)授課計(jì)劃2020-2020學(xué)年第二學(xué)期第1周授課日期2月20日星期1月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題第1章緒論1.1-1.2教學(xué)目的與要求：了解數(shù)據(jù)結(jié)構(gòu)的基本概念2.理解常用術(shù)語(yǔ)教學(xué)重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)教學(xué)難點(diǎn)：數(shù)據(jù)元素之間的四種結(jié)構(gòu)關(guān)系作業(yè)及參考書：1、什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類

2、型：講授教學(xué)過程：自我介紹開課引入展開舉例小結(jié)作業(yè)一、自我介紹和課程介紹約8min課時(shí)：64二、引入約2min由問題的提出引入三、講課進(jìn)程設(shè)計(jì)1.1什么是數(shù)據(jù)結(jié)構(gòu)1.1.1、數(shù)據(jù)結(jié)構(gòu)與其它的關(guān)系約15min數(shù)據(jù)結(jié)構(gòu)+算法=程序程序設(shè)計(jì):為計(jì)算機(jī)處理問題編制一組指令集算法:處理問題的策略數(shù)據(jù)結(jié)構(gòu):問題的數(shù)學(xué)模型1.1.2、當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)：約25minl）所處理的數(shù)據(jù)量大且具有一定的關(guān)系；2）對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。舉例說明：1）學(xué)生成績(jī)表2）井安棋對(duì)弈3）交通管理結(jié)論計(jì)算機(jī)的操作對(duì)象的關(guān)系更加復(fù)雜，操作形式不再是單純的數(shù)值計(jì)算，而更多地是對(duì)這些

3、具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理；我們將此稱為非數(shù)值性處理。要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對(duì)象的特點(diǎn)，在計(jì)算機(jī)中的表示方式以及各個(gè)操作的具體實(shí)現(xiàn)手段。1.2基本概念和術(shù)語(yǔ)1.1.1、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)約20min數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表歡迎關(guān)注作者！作者每天都會(huì)更新精品文章！示。所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合。是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素：是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)

4、系的數(shù)據(jù)元素的集合。這種集合稱為結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:種類特征示例集合元素間為松散的關(guān)系線性結(jié)構(gòu)元素間為嚴(yán)格的一對(duì)一關(guān)系如上面的成績(jī)表中各元素樹形結(jié)構(gòu)元素間為嚴(yán)格的一對(duì)多關(guān)系圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）元素間為多對(duì)多關(guān)系數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像數(shù)據(jù)元素的映象方法：計(jì)算機(jī)中存儲(chǔ)信息的最小單位：位，8位為一字節(jié)，兩個(gè)字節(jié)為一字，字節(jié)、字或更多的二進(jìn)制位可稱為位串。在邏輯描述中，把位串稱為元素或結(jié)點(diǎn)。關(guān)系的映象方法：順序映象鏈?zhǔn)接诚?.2.2、數(shù)據(jù)類型約5min數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。1.2.3、抽象

5、數(shù)據(jù)類型約20min是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲(chǔ)方式。定義它的人同樣不必要關(guān)心它如何存儲(chǔ)。抽象數(shù)據(jù)類型表示法：三元組表示：（D,S,P）其中D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。書中的定義格式：ADT抽象數(shù)據(jù)類型名數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義基本操作：基本操作的定義ADT抽象數(shù)據(jù)類型名ADT有兩個(gè)重要特征:數(shù)據(jù)抽象數(shù)據(jù)封裝四、本次課小結(jié)：約3min1.熟悉各名詞2.術(shù)語(yǔ)的含義3.掌握基本概念五、作業(yè)約2min2、什么是數(shù)據(jù)結(jié)構(gòu)？課時(shí)授課計(jì)劃2020-2020學(xué)年第二學(xué)期第1周授課

6、日期2月24日星期5月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)算法和算法分析教學(xué)目的與要求：類C語(yǔ)言的各種句型及算法描述的規(guī)范教學(xué)重點(diǎn)：類C語(yǔ)言的各種句型及算法描述的規(guī)范教學(xué)難點(diǎn)：類C語(yǔ)言的各種句型及算法描述的規(guī)范作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：復(fù)習(xí)引入展開舉例小結(jié)作業(yè)一、復(fù)習(xí)：約5min1、數(shù)據(jù)結(jié)構(gòu)的基本概念2、一些基本術(shù)語(yǔ)二、引入約2min由程序設(shè)計(jì)過程遇到的問題引入三、講課進(jìn)程設(shè)計(jì)1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.3.1基本操作：約15minAssignComplex(Z,v1,v2)操作結(jié)果：

7、構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex(Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。GetReal(Z,realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。GetImag(Z,ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add(z1,z2,sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。1.3.2對(duì)本書所采用的類C語(yǔ)言作簡(jiǎn)要說明約18min1.預(yù)定義常量及類型2、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)typedef3、算法描述為以下的函數(shù)形式：在算法描述中可以使用的賦值語(yǔ)

8、句形式有：在算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句形式有：在算法描述中可以使用的循環(huán)結(jié)構(gòu)語(yǔ)句形式有：在描述算法中可以使用的結(jié)束語(yǔ)句形式有：在算法描述中可以使用的輸入輸出語(yǔ)句形式有：在算法描述中使用的注釋格式為：在算法描述中可以使用的擴(kuò)展函數(shù)有：11.邏輯運(yùn)算約定1.4算法和算法分析1.4.1、算法約10min算法是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1有窮性2確定性3可行性4有輸入5有輸出1.4.2、算法設(shè)計(jì)的原則約10min設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性2.可讀性3健壯性4高效率與低存儲(chǔ)量需求1.4.3、算法效率的衡量方法和準(zhǔn)則約20min

9、通常有兩種衡量算法效率的方法事后統(tǒng)計(jì)法缺點(diǎn)：1必須執(zhí)行程序2其它因素掩蓋算法本質(zhì)事前分析估算法和算法執(zhí)行在計(jì)算算法的存儲(chǔ)量包括:1輸入數(shù)據(jù)所占空間2程序本身所占空間3輔助變量所占空間四、小結(jié)：約5min1.理解算法五個(gè)要素的確切含義。掌握計(jì)算語(yǔ)句頻度和估算算法五、作業(yè)約5min1、試編寫算法求一元多項(xiàng)式Pn(x)=a0+alx+a2x2+a3x3+.anxn的值Pn(xO)，并確定算法中的每一語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的試討論這兩種方法的優(yōu)缺點(diǎn)，并在本題算法中以你認(rèn)為較好的一種方式實(shí)現(xiàn)輸入和輸出。課時(shí)授課計(jì)劃2020-2020學(xué)年第二學(xué)期第2周授課日期2月27日星期月日星期月日星期月日星期月日星

10、期班級(jí)信管10-1基本課題線性表的類型定義線性表的順序表示和實(shí)現(xiàn)教學(xué)目的與要求：1、掌握線性表的概念和類型定義2、掌握線性表的順序表示和實(shí)現(xiàn)方法教學(xué)重點(diǎn)：線性表的類型定義線性表的順序表示和實(shí)現(xiàn)方法教學(xué)難點(diǎn)：線性表的類型定義線性表的順序存儲(chǔ)的實(shí)現(xiàn)方法作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：復(fù)習(xí)引入展開舉例小結(jié)一、引入約3min由順序的算法引入二、講課進(jìn)程設(shè)計(jì)2.1線性表的類型定義12.1.1線性表的定義約27min線性表是由n(nNO)個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。抽象數(shù)據(jù)類型線性表的定義如下：ADTList數(shù)據(jù)對(duì)象D=aiIaiGElemS

11、et,i=l,2,.,n,n0稱n為線性表的表長(zhǎng)；稱n=0時(shí)的線性表為空表。數(shù)據(jù)關(guān)系Rl=ai-1,ailai-1,ai$D,i=2,.,n基本操作：結(jié)構(gòu)初始化操作：InitList(L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。結(jié)構(gòu)銷毀操作：DestroyList(L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。引用型操作ListEmpty(L)(線性表判空)ListLength(L)(求線性表的長(zhǎng)度)PriorElem(L,cur_e,pre_e)(求數(shù)據(jù)元素的前驅(qū))NextElem(L,cur_e,next_e)(求數(shù)據(jù)元素的后繼)GetElem(L,i,e)(求線性表中某個(gè)數(shù)據(jù)元素)Loc

12、ateElem(L,e,compare()(定位函數(shù))ListTraverse(L,visit()(遍歷線性表)加工型操作ClearList(L)(線性表置空)PutElem(L,i,e()改變數(shù)據(jù)元素的值)ListInsert(L,i,e()插入數(shù)據(jù)元素)ListDelete(L,i,e)(刪除數(shù)據(jù)元素)2.1.2舉例約lOmin兩個(gè)線性表合并LA和LB2.2線性表的順序表示和實(shí)現(xiàn)2.2.1順序映象約15min以x的存儲(chǔ)位置和y的存儲(chǔ)位置之間某種關(guān)系表示邏輯關(guān)系x,y。最簡(jiǎn)單的一種順序映象方法是：令y的存儲(chǔ)位置和x的存儲(chǔ)位置相鄰。線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(L)/結(jié)構(gòu)初

13、始化LocateElem(L,e,compare()/查找ListInsert(L,i,e)/插入元素ListDelete(L,i)/刪除元素2.1.1、線性表操作約20minListInsert(L,i,e)的實(shí)現(xiàn)：首先分析插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表操作ListDelete(L,i,e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表類型的實(shí)現(xiàn)2.1.2、線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：約2Omin它是一種簡(jiǎn)單、方便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。暴露的

14、問題(1)在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；(2)對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用；(3)線性表的容量難以擴(kuò)充。三、小結(jié)約5min1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實(shí)現(xiàn)。課時(shí)授課計(jì)劃2020-2020學(xué)年第二學(xué)期第2周授課日期3月3日星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題線性表的

15、鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一元多項(xiàng)式的表示及相加教學(xué)目的與要求：1、掌握線性鏈表、單鏈表、靜態(tài)鏈表的概念、表示及實(shí)現(xiàn)方法。2、掌握循環(huán)鏈表的概念3、掌握雙向鏈表的表示與實(shí)現(xiàn)教學(xué)重點(diǎn)：1、線性鏈表之單鏈表的表示及實(shí)現(xiàn)方法。2、雙向鏈表的表示與實(shí)現(xiàn)教學(xué)難點(diǎn)：1、線性鏈表2、雙向鏈表的存儲(chǔ)表示作業(yè)及參考書：寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同。數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：復(fù)習(xí)引入展開舉例小結(jié)作業(yè)一、復(fù)習(xí)約5min復(fù)習(xí)線性表有的概念二、引入約2min由線性表的表示不方便引入三、講課進(jìn)程設(shè)計(jì)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表順序存儲(chǔ)結(jié)構(gòu)的

16、特點(diǎn)：約10min它是一種簡(jiǎn)單、方便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。暴露的問題(1)在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；(2)對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用；(3)線性表的容量難以擴(kuò)充。2.3.1、單鏈表約10min用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的也可以是不連續(xù)的)。2.3.2、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述約10min2.3.3、單鏈表操作的實(shí)現(xiàn)約13min因此生成鏈表的過程是一

17、個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過程。操作步驟：1、建立一個(gè)“空表”；2、輸入數(shù)據(jù)元素an,建立結(jié)點(diǎn)并插入；3、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；4、依次類推,直至輸入a1為止。2.3.4、其它形式的鏈表約5min1.循環(huán)鏈表2.雙向鏈表2.3.5、有序表類型約5min2.4一元多項(xiàng)式的表示2.4.1一元多項(xiàng)式約20min在計(jì)算機(jī)中,可以用一個(gè)線性表來表示:P=(p0,p1,pn)抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：ADTPolynomial數(shù)據(jù)對(duì)象：D=ailaiGTermSet,i=l,2,.,m,m0TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：Rl=ai-1,aila

18、i-1,ai$D,i=2,.,n且ai-1中的指數(shù)值Vai中的指數(shù)值基本操作：CreatPolyn(P,m)操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù),建立一元多項(xiàng)式P。DestroyPolyn(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。PrintPolyn(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式P。PolynLength(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。AddPolyn(Pa,Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：Pa=Pa+Pb，并銷毀一元多項(xiàng)式Pb。SubtractPolyn(P

19、a,Pb)ADTPolynomial2.4.2一元多項(xiàng)式的實(shí)現(xiàn)：約10mintypedefOrderedLinkListpolynomial;/用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式四、小結(jié)約5min1.能夠從五、本章作業(yè)：約5min寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同。本題可以這樣考慮，先取開始結(jié)點(diǎn)中的值，將它與其后的所有結(jié)點(diǎn)值一一比較，發(fā)現(xiàn)相同的就刪除掉，然后再取第二結(jié)點(diǎn)的值，重復(fù)上述過程直到最后一個(gè)結(jié)點(diǎn)。課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第3周授課日期9月22日五星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題棧棧的應(yīng)用舉例教學(xué)目的與要求：1

20、、棧的數(shù)據(jù)類型定義2、棧的順序存儲(chǔ)與實(shí)現(xiàn)3、掌握棧的應(yīng)用方法，理解棧的重要作用教學(xué)重點(diǎn)：1、棧的順序存儲(chǔ)表示與實(shí)現(xiàn)方法2、利用棧實(shí)現(xiàn)行編輯、利用棧實(shí)現(xiàn)表達(dá)式求值教學(xué)難點(diǎn)：1、棧的定義2、利用棧實(shí)現(xiàn)表達(dá)式求值作業(yè)及參考書：1、棧定義的應(yīng)用2、棧的特點(diǎn)數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約10min1.什么是線性結(jié)構(gòu)？2.以餐館中一疊一疊的盤子的使用為例，引出棧的特點(diǎn)二、講課進(jìn)程設(shè)計(jì)3.1棧的類型定義3.1.1、棧、棧頂(top)、棧底(bottom)的定義約10min3.1.2棧的類型定義約10min3.2棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)

21、換約10min十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，個(gè)簡(jiǎn)單算法基于下列原理：N=(Ndivd)xd+Nmodd(其中：div為整除運(yùn)算，mod為求余運(yùn)算)例二、括號(hào)匹配的檢驗(yàn)約10min檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。三種情況對(duì)應(yīng)到棧的操作即為：1和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?棧中并沒有左括弧等在哪里；3棧中還有左括弧沒有等到和它相匹配的右括弧。例三、行編輯程序問題約10min在用戶輸入一行的過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。合理的作法是：設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū),并假設(shè)“#”為退格

22、符，“”為退行符。例四、迷宮求解約10min假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”?！凹{入路徑”的操作即為“當(dāng)前位置入棧；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出?！啊＠?、表達(dá)式求值約10min任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成。例六、實(shí)現(xiàn)遞歸約10min遞歸函數(shù)的實(shí)現(xiàn)一個(gè)遞歸函數(shù)的運(yùn)行過程類似于多個(gè)函數(shù)的嵌套調(diào)用，差別僅在于“調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)”。為了保證“每一層的遞歸調(diào)用”都是對(duì)“本層”的數(shù)據(jù)進(jìn)行操作，在執(zhí)行遞歸函數(shù)的過程中需要一個(gè)“遞歸?！?。三、小結(jié)約5min1.

23、掌握棧和隊(duì)列類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)注意棧滿和棧空的條件以及它們的描述方法。四、作業(yè)約5min1、4個(gè)元素a1，a2，a3和a4依次通過一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)，則不可能的出棧序是()(A)a4，a3，a2，a1(B)a3，a2，a4，a1(C)a3，a1，a4，a2(D)a3，a4，a2，a12、棧的特點(diǎn)是()。課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第3周授課日期9月27日三星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題隊(duì)列教學(xué)目的與要求：1.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。理解遞歸算法執(zhí)行過程中

24、棧的狀態(tài)變化過程。教學(xué)重點(diǎn)：1鏈隊(duì)的表示與實(shí)現(xiàn)教學(xué)難點(diǎn)：.1。鏈隊(duì)的表示與實(shí)現(xiàn)作業(yè)及參考書：1棧與隊(duì)列的比較2讀程序段數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約5min在日常生活中，為了維持正常的社會(huì)秩序而出現(xiàn)的常見現(xiàn)象是什么？是“排隊(duì)“。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是“隊(duì)列“。二、講課進(jìn)程設(shè)計(jì)3.4隊(duì)列1隊(duì)列的定義約10min2隊(duì)列的抽象類型定義約15min3.隊(duì)列的基本操作：約20minInitQueue(Q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在

25、。QueueEmpty(Q)初始條件:隊(duì)列Q已存在。操作結(jié)果:若Q為空隊(duì)列,則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件:隊(duì)列Q已存在。操作結(jié)果:返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q,e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。ClearQueue(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。EnQueue(Q,e)初始條件:隊(duì)列Q已存在。操作結(jié)果:插入元素e為Q的新的隊(duì)尾元素。DeQueue(Q,e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。QueueTravers(Q,visit()隊(duì)列類型的實(shí)現(xiàn)

26、4.鏈隊(duì)列鏈?zhǔn)接诚蠹s15min5.循環(huán)隊(duì)列順序映象約20min隊(duì)列在程序設(shè)計(jì)中的一個(gè)典型應(yīng)用例子是作業(yè)排隊(duì)問題。三、小結(jié)約5min1.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法。2.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。四、作業(yè)約10min1、線性表、棧和隊(duì)列都是()結(jié)構(gòu),可以在線性表的()位置插入和刪除元素，對(duì)于棧只能在()插入和刪除元素，對(duì)于隊(duì)列只能在()插入元素和()刪除元素。2、指出下述程序段的功能是什么?(1)voidDemo1(SeqStack*S)inti;arr64;n=0;while(StackEmpty(S)arrn+=Pop(S);for(

27、i=0,ii+)Push(S,arri);/Demo1課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第4周授課日期月日星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題實(shí)驗(yàn)二棧和隊(duì)列的總結(jié)復(fù)習(xí)教學(xué)目的與要求：1、深入了解棧和隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它們；2、鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。教學(xué)重點(diǎn)：鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。教學(xué)難點(diǎn)：鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計(jì)。作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：課堂類型：教學(xué)過程：停車場(chǎng)管理問題描述設(shè)停車場(chǎng)內(nèi)只有一個(gè)的停放n輛汽車的狹長(zhǎng)通

28、道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)測(cè)試數(shù)據(jù)設(shè)n=2,輸入數(shù)據(jù)為：(A,1,5)，(A，,2,10)，(D,1,15),(A，,3，20)，(A，4，25)，(A，5，30)，(D，2，35)，(D，4，40)，(E，0，0)。其中，A，表示到達(dá)；D，表示離去，E，表示輸入結(jié)束?；疽笠詶ＤM停車場(chǎng),以隊(duì)列模擬車場(chǎng)外的便道,按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻,對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá),則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停

29、車場(chǎng)內(nèi)停留的實(shí)現(xiàn)提示需另設(shè)一個(gè)棧,臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來的汽車,也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。棧中每個(gè)元素表示一輛汽車,包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。選作內(nèi)容(1)兩個(gè)棧共享空間,思考應(yīng)開辟數(shù)組的空間是多少？(2)汽車可有不同種類,則它們的占地面積不同,收費(fèi)標(biāo)準(zhǔn)也不同,如1輛客車和1.5輛小汽車的占地面積相同,1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。汽車可以直接從便道上開走,此時(shí)派在它前面的汽車要先開走讓路,然后再依次排到隊(duì)尾。停放在便道上的汽車也收費(fèi),收費(fèi)標(biāo)準(zhǔn)比停放在停車場(chǎng)的車低,請(qǐng)思考如何修改結(jié)構(gòu)以滿足這種要求。課時(shí)

30、授課計(jì)劃2020-2020學(xué)年第一學(xué)期第4周授課日期10月8日日星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題串教學(xué)目的與要求：1、熟悉串七種基本操作的定義,并能利用這些基本操作實(shí)現(xiàn)傳的其他各種操作的方法。2、熟悉掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。3、掌握串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串的各種操作的基本方法。教學(xué)重點(diǎn)：1、串七種基本操作的定義2、串的定長(zhǎng)順序存儲(chǔ)3、串的堆存儲(chǔ)結(jié)構(gòu)教學(xué)難點(diǎn)：1、串七種基本操作的定義2、串的堆存儲(chǔ)結(jié)構(gòu)作業(yè)及參考書：對(duì)串的操作的應(yīng)用數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約5

31、min計(jì)算機(jī)上的非數(shù)值處理的對(duì)象基本上都是字符串?dāng)?shù)據(jù)。二、講課進(jìn)程設(shè)計(jì)4.1串的抽象數(shù)據(jù)類型的定義1.定義約10min串、串長(zhǎng)、空串、子串、主串、位置、相等、空格串2.串的抽象數(shù)據(jù)類型的定義約10minStrAssign(T,chars)StrCopy(T,S)DestroyString(S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(T,S1,S2)SubString(Sub,S,pos,len)Index(S,T,pos)Replace(S,T,V)StrInsert(S,pos,T)StrDelete(S,pos,len)ClearStrin

32、g(S)4.2串的表示和實(shí)現(xiàn)4.2.1、串的定長(zhǎng)順序存儲(chǔ)表示約15min1.串聯(lián)接2.求子串4.2.2、串的堆分配存儲(chǔ)表示約20min通常,C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc()和free()進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”。4.2.3、串的塊鏈存儲(chǔ)表示約10min也可用鏈表來存儲(chǔ)串值,由于串的數(shù)據(jù)元素是一個(gè)字符,它只有8位二進(jìn)制數(shù),因此用鏈表存儲(chǔ)時(shí),通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符,而是一個(gè)子串。4.4串操作應(yīng)用舉例4.4.1文本編輯約20min可用于文本編輯的程序很多,功能強(qiáng)弱差別很大,但基本操作是一

33、致的：都包括串的查找,插入和刪除等基本操作。對(duì)用戶來講,一個(gè)文本(文件)可以包括若干頁(yè),每頁(yè)包括若干行,每行包括若干文字。對(duì)文本編輯程序來講，可把整個(gè)文本看成一個(gè)長(zhǎng)字符串，稱文本串，頁(yè)是文本串的子串，行又是頁(yè)的子串。為簡(jiǎn)化程序復(fù)雜程度，可簡(jiǎn)單地把文本分成若干行。三、小結(jié)約5min1.熟悉串的七種基本操作的定義，并能利用這些基本操作來實(shí)現(xiàn)串的其它各種操作的方法。熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。了解串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法。了解串操作的應(yīng)用方法和特點(diǎn)。四、作業(yè)約5min假設(shè)有如下的串說明：charsl30=“Stocktom,CA“，s230=“Marc

34、h51999”，s330,*p;(1)在執(zhí)行下列語(yǔ)句后，s3的值是什么？strcopy(s3,s1);concat(s3,“,“);concat(s3,s2);(2)調(diào)用函數(shù)strcompare(sl,s2)的返回值是什么？(3)調(diào)用函數(shù)strcompare(s15,“ton“)的返回值是什么？調(diào)用函數(shù)strlength(concat(s1,s2)的返回值是什么？課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第5周授課日期10月11日三星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題數(shù)組教學(xué)目的與要求：1、掌握數(shù)組的定義2、掌握數(shù)組的順序表示方法教學(xué)重點(diǎn)：1、數(shù)組的定義2、數(shù)組的順序表

35、示方法教學(xué)難點(diǎn)：數(shù)組的順序表示方法作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例一一小結(jié)一、引入約5min由前幾章討論的線性結(jié)構(gòu)中的數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型引入數(shù)組。二、講課進(jìn)程設(shè)計(jì)5.1數(shù)組的類型定義抽象數(shù)據(jù)類型定義約5minADTArray數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：ADTArray二維數(shù)組的定義：約10min數(shù)據(jù)對(duì)象:D=aij|0ib1-1,0jb2-1數(shù)據(jù)關(guān)系：R=ROW,COLROW=ai,j,ai+l,j|0ib1-2,0jb2-1COL=ai,j,ai,j+ll0ib1-1,0j1)性質(zhì)2:深度為k的二叉樹上至多含2k-l個(gè)結(jié)點(diǎn)

36、(k1)o性質(zhì)3:對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)(0度結(jié)點(diǎn))、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+l。兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為l至n的結(jié)點(diǎn)一一對(duì)應(yīng)。(編號(hào)的規(guī)則為，由上到下，從左到右。)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為elog2nu+1。性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：(1)如i=1，則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)；如訂，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為。(2)如2xin，則序號(hào)為i的結(jié)

37、點(diǎn)無左孩子；如2xin，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2xi。(3)如2xi+1n，則序號(hào)為i的結(jié)點(diǎn)無右孩子；如2xi+ln，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2xi+16.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)約25min1、二叉樹的順序存儲(chǔ)表示2、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1）.二叉鏈表2）三叉鏈表3）雙親鏈表4）線索鏈表三、小結(jié)約5min1、樹、二叉樹的定義2、二叉樹的性質(zhì)3、存儲(chǔ)結(jié)構(gòu)四、作業(yè)約5min1.一棵度為2的樹與一棵二叉樹有何區(qū)別？2.試分別畫出具有3個(gè)結(jié)點(diǎn)的二叉樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第7周授課日期10月25日三星期月日星期月日星期月日

38、星期月日星期班級(jí)信管10-1基本課題遍歷二叉樹和線索二叉樹教學(xué)目的與要求：遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。2.理解二叉樹線索化的實(shí)質(zhì).熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。教學(xué)重點(diǎn)：1.遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。2各種遍歷策略的遞歸算法，運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。教學(xué)難點(diǎn)：各種遍歷策略的遞歸算法，運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。作業(yè)及參考書：寫出所給二叉樹的前、中、后序的序列數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡

39、編著教具：/、多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約3min由二叉樹的結(jié)構(gòu)引出對(duì)每個(gè)結(jié)點(diǎn)的遍歷。二、講課進(jìn)程設(shè)計(jì)6.3遍歷二叉樹和線索二叉樹6.3.1二叉樹的遍歷一、問題的提出約7min順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。（將樹線性化）對(duì)“二叉樹”而言，可以有三條搜索路徑：01.先上后下的按層次遍歷；02.先左（子樹）后右（子樹）的遍歷；03先右（子樹）后左（子樹）的遍歷。二、先左后右的遍歷算法約10min先（根）序的遍歷算法若二叉樹為空樹，則空操作；否則（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。中（根

40、）序的遍歷算法若二叉樹為空樹，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。后（根）序的遍歷算法若二叉樹為空樹，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。三、算法的遞歸描述約10min總結(jié)：無論先序、中序、后序遍歷二叉樹，遍歷時(shí)的搜索路線是相同的：從根結(jié)點(diǎn)出發(fā)，逆時(shí)針延二叉樹外緣移動(dòng)對(duì)每個(gè)結(jié)點(diǎn)均途徑三次。先序遍歷：第一次經(jīng)過結(jié)點(diǎn)時(shí)訪問。中序遍歷：第二次經(jīng)過結(jié)點(diǎn)時(shí)訪問。后序遍歷：第三次經(jīng)過結(jié)點(diǎn)時(shí)訪問。四、中序遍歷算法的非遞歸描述約10min五、遍歷算法的應(yīng)用舉例約30min1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)（先序遍歷）先序（或中序或后序

41、）遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。2、求二叉樹的深度（后序遍歷）算法基本思想:首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。3、復(fù)制二叉樹（后序遍歷）其基本操作為：生成一個(gè)結(jié)點(diǎn)。4、建立二叉樹的存儲(chǔ)結(jié)構(gòu)p不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法按給定的表達(dá)式建相應(yīng)二叉樹由先綴表示式建樹由原表達(dá)式建樹我們已經(jīng)知道二叉樹結(jié)構(gòu)和它的某個(gè)遍歷序列不存在一一對(duì)應(yīng)的關(guān)系，但若已知一個(gè)二叉樹的前序序列和中序序列，卻一定可以惟一確定一個(gè)二叉樹的結(jié)構(gòu)。6.3.2線索二叉樹約20min何謂

42、線索二叉樹？遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。如何保存這種在遍歷過程中得到的信息？最簡(jiǎn)單的方法是在每個(gè)結(jié)點(diǎn)上增加二個(gè)指針域：fwd和bkwd用來指示此結(jié)點(diǎn)在遍歷中的前驅(qū)和后繼結(jié)點(diǎn)。線索鏈表的遍歷算法由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。如何建立線索鏈表？結(jié)索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時(shí)才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。為了記下遍歷過程中訪問結(jié)點(diǎn)的先后關(guān)系，附設(shè)一個(gè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，若指針p指向當(dāng)前訪問的結(jié)點(diǎn)，則pre指向它的前驅(qū)。由此在中

43、序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。三、小結(jié)約7min1、遍歷的總結(jié)2、線索化的總結(jié)四、作業(yè)1、對(duì)所給出的二叉樹寫出前、中、后序的遍歷序列。課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第7周授課日期11月1日三星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題樹和森林教學(xué)目的與要求：1熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹、森林與二叉樹的轉(zhuǎn)換方法。2學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。教學(xué)重點(diǎn)：1、樹、森林與二叉樹的轉(zhuǎn)換方法2學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。教學(xué)難

44、點(diǎn)：1、樹、森林與二叉樹的轉(zhuǎn)換方法2學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。作業(yè)及參考書：樹和森林的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約5min由前面樹、二叉樹的回顧引入二、講課進(jìn)程設(shè)計(jì)6.4樹和森林641樹的存儲(chǔ)結(jié)構(gòu)約25min1、雙親表示法以一組連續(xù)的存儲(chǔ)空間存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指針指示其雙親結(jié)點(diǎn)在這連續(xù)的存儲(chǔ)空間中的位置（下標(biāo)，這種結(jié)構(gòu)屬靜態(tài)鏈表）,可形式表示如下：typrdefstructtnodedatatypedata;intparent;treen2、孩子表示法用多重鏈表表示。有兩種方法：同構(gòu)：按最大度的

45、結(jié)點(diǎn)設(shè)置各結(jié)點(diǎn)結(jié)構(gòu)，即一個(gè)數(shù)據(jù)域和d個(gè)指針域，這容易造成空間浪費(fèi)；異構(gòu)：結(jié)點(diǎn)有幾棵子樹設(shè)幾個(gè)指針，這樣操作困難。可將其子女鏈在一個(gè)單鏈表中。其形式描述如下：typrdefstructtagnode/*表結(jié)點(diǎn)*/intchild;structtagnode*next;node,*link;typedefstruct/*頭結(jié)點(diǎn)*/datatypedata;linkheadptr;headnode;typedefheadnodechildlinkmaxnode;/*表頭數(shù)組*/帶雙親的孩子鏈表表示法：typedefstruct/*頭結(jié)點(diǎn)*/datatypedata;intparent;linkhea

46、dptr;headnode1;3、孩子兄弟表示法該方法又稱二叉樹表示法，或二叉鏈表表示法，即以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟，分別命名為fch和nsib?？尚问矫枋鋈缦拢簍ypedefstructtreenodedatatypedata;structtreenode*fch,*nsib;treenode,*tree;樹的這種表示本質(zhì)上是二叉樹的二叉鏈表表示。由于二叉樹和樹這種存儲(chǔ)結(jié)構(gòu)的一致性，從而導(dǎo)致樹和二叉樹可以相互轉(zhuǎn)換。642森林與二叉樹的相互轉(zhuǎn)換約30min1、森林轉(zhuǎn)為二叉樹樹（樹林）轉(zhuǎn)換成二叉樹時(shí)結(jié)果是唯一的。其轉(zhuǎn)換可以遞歸的描述如下：若樹（樹

47、林）為空，則二叉樹為空；否則，樹（樹林）中第一棵樹的根是二叉樹的根，第一棵樹除去根結(jié)點(diǎn)后的子樹林是二叉樹的左子樹，樹林中除去第一棵樹后的樹林形成二叉樹的右子樹。形象的說轉(zhuǎn)換過程可用下面的“三步曲”來說明：三步曲：連線切線旋轉(zhuǎn)連線：將兄弟結(jié)點(diǎn)連接起來切線：保留雙親到第一個(gè)子女的連線，將雙親到其它子女的連線切掉。旋轉(zhuǎn)：以根為軸，平面向下順時(shí)針方向旋轉(zhuǎn)450。2、二叉樹轉(zhuǎn)為樹林二叉樹轉(zhuǎn)換成樹（樹林）時(shí)結(jié)果也是唯一的。其轉(zhuǎn)換可以遞歸的描述，若二叉樹為空，則樹（樹林）為空；否則，二叉樹的根是樹（樹林）中第一棵樹的根，二叉樹的左子樹構(gòu)成樹（樹林）中第一棵樹除去根結(jié)點(diǎn)后的子樹林，二叉樹的右子樹構(gòu)成樹林中除去

48、第一棵樹后的樹林。形象的說是上面三步曲的逆。643樹和森林的遍歷約30min樹的遍歷方法也可分為“寬度優(yōu)先法”和“深度優(yōu)先法”兩類。前者指從（根）第一層開始，由上到下，從左往右逐個(gè)結(jié)點(diǎn)的遍歷；后者又可分為先根次序和后根次序。（1）先根次序的遍歷（相當(dāng)于對(duì)其相應(yīng)的二叉樹的先序遍歷）若樹（森林）為空則空操作，否則：訪問左面第一棵樹的根；按先根次序從左到右遍歷此根下的子樹；按先根次序從左到右遍歷除第一棵樹外的樹（森林）。（2）后根次序的遍歷（相當(dāng)于對(duì)其相應(yīng)的二叉樹的中序遍歷）若樹（森林）為空則空操作，否則：按后根次序從左到右遍歷最左面的樹下的子樹；訪問最左面樹的根；按后根次序從左到右遍歷除第一棵樹外

49、的樹（森林）；三、小結(jié)約7min1、樹的存儲(chǔ)2、樹與森林之間的轉(zhuǎn)換3、樹和森林的遍歷四、作業(yè)約3min1完成由樹和森的轉(zhuǎn)換課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第8周授課日期11月3日五星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題哈夫曼樹教學(xué)目的與要求：1、掌握哈夫曼樹的構(gòu)造方法2、掌握哈夫曼編碼3、帶權(quán)路徑的計(jì)算4、了解最優(yōu)樹的特性教學(xué)重點(diǎn)：1、哈夫曼樹的構(gòu)造2、掌握建立最優(yōu)樹和哈夫曼編碼的方法。教學(xué)難點(diǎn)：1、建立最優(yōu)樹和哈夫曼編碼的方法2、帶權(quán)路徑的計(jì)算作業(yè)及參考書：1、構(gòu)造一棵哈夫曼樹并且計(jì)算其權(quán)值數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：/、多媒體板書課堂類型：講授教

50、學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約5min由最優(yōu)樹概念的提出引入哈夫曼樹二、講課進(jìn)程設(shè)計(jì)66哈夫曼樹及其應(yīng)用661最優(yōu)二叉樹（哈夫曼樹-帶權(quán)路徑長(zhǎng)度最短的樹）1、哈夫曼樹的基本概念約20min（1）路徑從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支。（2）路徑長(zhǎng)度路徑上的分支數(shù)目稱為路徑長(zhǎng)度。（3）樹的路徑長(zhǎng)度從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，稱為樹的路徑長(zhǎng)度，完全二叉樹是路徑長(zhǎng)度最短的二叉樹。（4）結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度和結(jié)點(diǎn)上權(quán)的乘積。（5）樹的帶權(quán)路徑長(zhǎng)度樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為WPL=wili，（6）哈夫曼樹（最優(yōu)二叉樹）帶權(quán)路徑長(zhǎng)度之和最小的二叉樹

51、稱為哈夫曼樹（最優(yōu)二叉樹）（7）哈夫曼編碼在哈夫曼樹上，左分枝為0，右分枝為1，從根結(jié)點(diǎn)開始，直到葉子結(jié)點(diǎn)所組成的編碼序列，稱為葉子結(jié)點(diǎn)的哈夫曼編碼。2、哈夫曼樹在判定問題中的應(yīng)用約15min將百分制轉(zhuǎn)為五級(jí)記分制的例子。說明哈夫曼樹判定次數(shù)最少的樹（即帶權(quán)路徑長(zhǎng)度最短、最節(jié)省計(jì)算（2）在F中刪除這兩棵子樹，同時(shí)將新得到的二叉樹加入F中。（3）重復(fù)（2）和（3），直到F中只剩一棵樹（即哈夫曼樹）為止。舉例說明這一過程：應(yīng)該說明，哈夫曼樹的形態(tài)不是唯一的，但對(duì)具有一組權(quán)值的各哈夫曼樹的WPL是唯一的。662哈夫曼編碼1、哈夫曼編碼提出的背景約lOmin(1)如何使電報(bào)編碼變短，非前綴編碼出現(xiàn)二義

52、性。(2)用二叉樹可以構(gòu)造前綴編碼。(3)由哈夫曼樹得到最優(yōu)編碼。2、構(gòu)造哈夫曼樹和哈夫曼編碼的算法約2Omin前綴編碼：任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。如ABCD四個(gè)字符的使用率由高到低，編碼為A-0B-10C-110D-111利用赫夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。哈夫曼編碼算法的實(shí)現(xiàn)：由于哈夫曼樹中沒有度為1的結(jié)點(diǎn)，則一棵有n個(gè)葉子的哈夫曼樹共有2xn1個(gè)結(jié)點(diǎn)，可以用一個(gè)大小為2xn1的一維數(shù)組存放哈夫曼樹的各個(gè)結(jié)點(diǎn)。由于每個(gè)結(jié)點(diǎn)同時(shí)還包含其雙親信息和孩子結(jié)點(diǎn)的信息，所以構(gòu)成一個(gè)靜態(tài)三叉

53、鏈表。三、小結(jié)約5min1、構(gòu)造哈夫曼樹2、哈夫曼編碼四、作業(yè)約5min1、求由帶權(quán)9、1、3、5、6的5個(gè)葉子節(jié)點(diǎn)生成的哈夫曼樹的帶權(quán)路徑長(zhǎng)度。2、設(shè)哈夫曼樹的葉節(jié)點(diǎn)數(shù)為nO，則它的節(jié)點(diǎn)總數(shù)為多少？課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第8周授課日期10月27日五星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題樹與二叉樹復(fù)習(xí)習(xí)題課教學(xué)目的與要求：1熟悉二叉樹結(jié)點(diǎn)的結(jié)構(gòu)和對(duì)二叉樹的基本操作。2掌握對(duì)二叉樹每一種操作的具體實(shí)現(xiàn)。3學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。教學(xué)重點(diǎn)：1學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。教學(xué)難點(diǎn)：1、利用遞

54、歸方法編寫對(duì)二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：課堂類型：總結(jié)復(fù)習(xí)教學(xué)過程：提出問題對(duì)問題提示完成問題檢查二叉樹基本操作復(fù)習(xí)目的4熟悉二叉樹結(jié)點(diǎn)的結(jié)構(gòu)和對(duì)二叉樹的基本操作。5掌握對(duì)二叉樹每一種操作的具體實(shí)現(xiàn)。6學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。復(fù)習(xí)內(nèi)容該程序的功能是實(shí)現(xiàn)二叉樹結(jié)點(diǎn)的類型定義和對(duì)二叉樹的基本操作。該程序包括二叉樹結(jié)構(gòu)類型以及每一種操作的具體的函數(shù)定義和主函數(shù)。/*定義DataType為char類型*/typedefcharDataType;/*二叉樹的結(jié)點(diǎn)類型*/typedefstructBitNo

55、deDataTypedata;structBitNode*lchild,*rchild;BitNode,*BitTree;/*初始化二叉樹，即把樹根指針置空*/voidBinTreeInit(BitTree*BT)/*按先序次序建立一個(gè)二叉樹*/voidBinTreeCreat(BitTree*BT)/*檢查二叉樹是否為空*/intBinTreeEmpty(BitTree*BT)/*按任一種遍歷次序(包括按先序、中序、后序、按層次)輸出二叉樹中的所有結(jié)點(diǎn)*/voidBinTraverse(BitTree*BT)/*求二叉樹的深度*/intBinTreeDepth(BitTreeBT)/*求二叉

56、樹中所有結(jié)點(diǎn)數(shù)*/intBinTreeCount(BitTreeBT)/*清除二叉樹，使之變?yōu)榭諛?/voidBinTreeClear(BitTree*課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第11周授課日期11月8日三星期月日星期月日星期月日星期月日星期班級(jí)信管10-1基本課題圖的定義和術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)教學(xué)目的與要求：1、掌握?qǐng)D的定義及常用術(shù)語(yǔ)2、掌握?qǐng)D的二種存儲(chǔ)表示法教學(xué)重點(diǎn)：1、圖的常用術(shù)語(yǔ)2、圖的數(shù)組表示及鄰接表表示法教學(xué)難點(diǎn)：1、圖的常用術(shù)語(yǔ)2、鄰接表表示法作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約5min

57、由各城市之間的通信引出圖二、講課進(jìn)程設(shè)計(jì)第七章圖對(duì)圖進(jìn)行概述約5min圖是一種比線性表和樹都復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)元素之間都可能有關(guān)系。圖的應(yīng)用非常廣泛。7.1圖的定義和術(shù)語(yǔ)1、圖的定義約5min圖是一種數(shù)據(jù)結(jié)構(gòu)，其形式化定義可寫為Graph=(V,R)其中，V=x|xdatatypeR=VRVR=x,ylP(x,y)(x,yV)在圖中，數(shù)據(jù)元素常稱為頂點(diǎn)，V是頂點(diǎn)的有窮集合；R是邊(弧)的有窮集合。2、抽象數(shù)據(jù)類型圖的定義約5minADTGraph數(shù)據(jù)對(duì)象V：數(shù)據(jù)關(guān)系R：基本操作P：ADTGraph3、圖的術(shù)語(yǔ)概念約15min(1)有向圖、無向圖?。?/p>

58、x,y邊(x,y)。有(無)向完全圖稀疏圖稠密圖子圖無向完全圖：n個(gè)頂點(diǎn)n(n-1)/2條邊；有向完全圖：n個(gè)頂點(diǎn)n(n-l)條??；權(quán)、網(wǎng)和邊(弧)相關(guān)的數(shù)叫權(quán)，帶權(quán)的圖稱網(wǎng)。鄰接、鄰接點(diǎn)無向圖：一條邊連起來的兩個(gè)頂點(diǎn)，互稱鄰接點(diǎn)；有向圖：若從頂點(diǎn)x到頂點(diǎn)y有一條弧，則說頂點(diǎn)x鄰接到頂點(diǎn)y,而頂點(diǎn)y鄰接自頂點(diǎn)x。度、出度、入度無向圖中和頂點(diǎn)相關(guān)的邊(e)的個(gè)數(shù)叫頂點(diǎn)的度。e=有向圖中從頂點(diǎn)出發(fā)的弧的個(gè)數(shù)叫該頂點(diǎn)的出度，入到該頂點(diǎn)的弧的個(gè)數(shù)叫該頂點(diǎn)的入度。TD(v)=ID(v)+OD(v)(6)路徑、路徑長(zhǎng)度、回路(環(huán))、簡(jiǎn)單路徑(7)連通、連通圖、連通分量無向圖頂點(diǎn)vl到頂點(diǎn)v2有路徑，則說v

59、l和v2連通。若任意兩個(gè)頂點(diǎn)都連通，則說該圖是連通的。連通分量是無向圖中的極大連通子圖。(8)強(qiáng)連通圖、強(qiáng)連通分量(9)生成樹、有向樹、生成森林一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-l條邊。若有向圖中只有一個(gè)頂點(diǎn)的入度為0其余頂點(diǎn)的入度均為1，則該有向圖稱為有向樹。有向圖的生成森林由若干棵有向樹組成，含有圖的全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。72圖的存儲(chǔ)結(jié)構(gòu)721圖的順序存儲(chǔ)結(jié)構(gòu)-數(shù)組表示法約20min1、數(shù)組表示法用兩個(gè)數(shù)組分別表示數(shù)據(jù)元素的(頂點(diǎn))的信息和邊(弧)的信息若頂點(diǎn)只有編號(hào)信息，邊(弧)只是有無，則可用下面的鄰接矩陣來

60、表示。2、鄰接矩陣的定義有n個(gè)頂點(diǎn)的圖G=(V,VR)的鄰接矩陣為n階方陣，其定義為：0若(vi,vj)或vi,vjVR3、無向圖鄰接矩陣的性質(zhì)(1)無向圖的鄰接矩陣是對(duì)稱矩陣；（2）頂點(diǎn)vi的度是鄰接矩陣中第i行（或第i列）的元素（1）之和。4、有向圖鄰接矩陣的性質(zhì)（1）有向圖的鄰接矩陣不一定是對(duì)稱矩陣；（2）頂點(diǎn)vi的出度是鄰接矩陣中第i行元素之和，入度是鄰接矩陣中第i列的元素之和5、網(wǎng)的鄰接矩陣將鄰接矩陣中的0、1換成權(quán)值，就是網(wǎng)的鄰接矩陣。6、鄰接矩陣的優(yōu)缺點(diǎn)容易實(shí)現(xiàn)圖的前4個(gè)操作。容易判定頂點(diǎn)間有無邊（弧），容易計(jì)算頂點(diǎn)的度（出度、入度）；缺點(diǎn)是所占空間只和頂點(diǎn)個(gè)數(shù)有關(guān)，和邊數(shù)無關(guān)，