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

1、歡迎關(guān)注作者！作者每天都會(huì)史新粘品文蘋(píng)!數(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é)目的與要求：1. 了解數(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è)及參考書(shū)：1、什

2、么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：自我介紹開(kāi)課引入展開(kāi)舉例小結(jié)作業(yè) 一、自我介紹和課程介紹約Smin課時(shí)：64二、引入 約2min由問(wèn)題的提出引入 三、 講課進(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ī)處理問(wèn)題編制一組指令集算法：處理問(wèn)題的策略數(shù)據(jù) 結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型1.1.2、當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)：約25min 1）所處理的數(shù)據(jù)量大且具有一定的關(guān)系；2）對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需要對(duì)其進(jìn)行組織、管理和檢索。舉例說(shuō)明：1）學(xué)生成績(jī)表2）井安棋對(duì)弈3）交通

3、管理結(jié)論計(jì)算機(jī)的操作對(duì)象的關(guān)系更加復(fù)雜， 操作形式不再是單純的數(shù)值計(jì)算，而更多地是對(duì)這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理；我們將此稱為非數(shù)值性處理。要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必 須弄清楚這些操作對(duì)象的特點(diǎn)，在汁算機(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)表所有能被輸入到計(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ù)的

4、一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。這種集合稱為結(jié) 構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類：種類特征示例集合元素間為松散的關(guān)系線 性結(jié)構(gòu)元素間為嚴(yán)格的一對(duì)一關(guān)系如上面的成績(jī)表中各元素樹(shù)形結(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)接诚?22、數(shù)據(jù)類型約5min數(shù)據(jù)類型是一個(gè)

5、值 的集合和定義在此集合上的一組操作的總稱。123、抽象數(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的 基本操作集。書(shū)中的定義格式：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é)：約3min 1.熟悉各名詞2.術(shù)語(yǔ)的含義3.掌握基本概念五、作業(yè)約2min

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

7、類型的表示與實(shí)現(xiàn)131基本操作：約15min ASSignCOmPlex( Z, vl, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部 分別被賦 以參數(shù)Vl和v2的值。DestroyComplexC Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。GetRea1(乙realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。Getlmag(乙ImagPait)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add( zl,z2, SUm )初始條件：zl, z2是復(fù)數(shù)。操作結(jié)果：用SUm返回兩個(gè)復(fù)數(shù)zl, z2的和值。1.3.2對(duì)本書(shū)所采用的類C語(yǔ)言作簡(jiǎn)要說(shuō)明約18

8、min 1.預(yù)定義常量及類型2、數(shù)據(jù)結(jié) 構(gòu)的存儲(chǔ)結(jié)構(gòu)typedef3.算法描述為以下的函數(shù)形式：4. 在算法描述中可以使用的賦值語(yǔ)句形式有：5. 在算法描述中可以使用的選擇結(jié)構(gòu)語(yǔ)句形式有：6. 在算法描述中可以使用的循環(huán)結(jié)構(gòu)語(yǔ)句形式有：7. 在描述算法中可以使用的結(jié)束語(yǔ)句形式有：&在算法描述中可以使用的輸入輸出語(yǔ)句形式有：9. 在算法描述中使用的注釋格式為：10. 在算法描述中可以使用的擴(kuò)展函數(shù)有：11. 邏輯運(yùn)算約定14算法和算法分析1.4.1、算法 約IOmin算法是為了解決某類問(wèn) 題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1.有窮性2.確定性3.可行性4.有輸入5

9、.有輸出1.4.2、算法設(shè)計(jì)的原則約 IOmin設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1. 正確性2.可讀性3.健壯性4.高效率與低存儲(chǔ)量需求1.4.3、算法效率的衡量方 法和準(zhǔn)則約20min通常有兩種衡量算法效率的方法事后統(tǒng)計(jì)法缺點(diǎn)：1.必須執(zhí)行程序2. 其它因素掩蓋算法本質(zhì)事前分析估算法和算法執(zhí)行在計(jì)算算法的存儲(chǔ)量包括：1.輸入數(shù)據(jù)所占空間2.程序本身所占空間3.輔助變量所占空 間四、小結(jié)：約5min 1.理解算法五個(gè)要素的確切含義。2. 掌握計(jì)算語(yǔ)句頻度和估算算法五、作業(yè) 約5min 1、試編寫(xiě)算法求一元多項(xiàng)式Pn(X)=a+alx+a2x2+a3x3+.ax的值 Pn(xO),并確定算法

10、中的每一語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的試討論這兩種方法的優(yōu)缺點(diǎn)，并在本題算法中以你認(rèn)為較好的一種方式實(shí)現(xiàn)輸入和 輸出。課時(shí)授課計(jì)劃2020-2020學(xué)年第二學(xué)期第2周授課日期2月27日星期月 日星期月 日星期月 日星期月 日星期 班 級(jí) 信管10-1基本課題 線性表的類型定義 線性表的順序表示和實(shí)現(xiàn) 教學(xué)Ll的與要 求：1、掌握線性表的概念和類型定義2、掌握線性表的順序表示和實(shí)現(xiàn)方法教學(xué)重點(diǎn)：線性表的類型定義線性表的順序表示和實(shí)現(xiàn)方法教學(xué)難點(diǎn)：線性表的類型定義線性表的順序存儲(chǔ)的實(shí)現(xiàn)方法作業(yè)及參考書(shū)：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書(shū)課堂類型：講授教學(xué)過(guò)程：復(fù)習(xí)引入展開(kāi)舉例小結(jié)一、引

11、入約3min由順序 的算法引入二、講課進(jìn)程設(shè)計(jì)2. 1線性表的類型定義12.1.1線性表的定義約27min線 歡迎關(guān)注作者！作者每天都會(huì)史新粘品文克!性表是山n (n0)個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。抽象數(shù)據(jù)類型線性表的定義如下：ADT LiSt 數(shù)據(jù)對(duì)象 D= ai I ai ElemSet, i=l,2,.,n, nO 稱 n 為線性表的表長(zhǎng);稱n=O時(shí)的線性表為空表。數(shù)據(jù)關(guān)系Rl= ai-1 ,ai Iai-I ,aiD, i=2n )基本操作： 結(jié)構(gòu)初始化操作：InitList( L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。結(jié)構(gòu)銷毀操作：DestroyList( L )初始條件：線性表L

12、已存在。操作結(jié)果：銷毀線性表Lo 引用型操作ListEmptyC L )(線性表判空)LiStLength( L)(求線性表的長(zhǎng)度) PriorElem( L，cur_e, pre_e )(求數(shù)據(jù)元素的前驅(qū))NeXtEIem(L, cur_e, next_e )(求數(shù)據(jù)元 素的后繼)GetElem( L, i, e )(求線性表中某個(gè)數(shù)據(jù)元素)LOCateEIem( L, e, COmPare()(定位函數(shù))LiStTraVerse(L, visit()(遍歷線性表)加工型操作CIearList( L)(線性表置 空)PUtEIem( L, i, e )(改變數(shù)據(jù)元素的值)LiStInsert

13、( L, i, e )(插入數(shù)據(jù)元素)LiStDeIete(L, i, e)(刪除數(shù)據(jù)元素)2.1.2舉例約IOmin兩個(gè)線性表合并LA和LB 2.2線性表的順序 表示和實(shí)現(xiàn)221順序映象約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)初始化 LOCateElem(L, e, COmPareo) H 查找 LiStlnSert(L, i, e) / 插入元素 LiStDelete(L, i) / 刪除元素 2.1、線性表操作 約 20min Li

14、StlnSert(L, i, e)的實(shí)現(xiàn)：首先分析插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表操作LiStDeIete(U i, e)的實(shí)現(xiàn):首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表類型的實(shí)現(xiàn)2.1.2、線性表順 序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：約20min它是一種簡(jiǎn)單、方便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù) 的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜 態(tài)存儲(chǔ)形式。暴露的問(wèn)題(1)在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；(2) 對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常乂 得不到充分的利用；(3

15、) 線性表的容量難以擴(kuò)充。三、小結(jié)約5min 1.7解線性表的邏輯結(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基本課題線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一元多項(xiàng)式的表示及相加教學(xué)LI的 與要求：1、掌握線性鏈表、單鏈表、靜態(tài)鏈表的概念、表示及實(shí)現(xiàn)方法。2、掌握循環(huán)鏈表的概念3、掌握

16、雙向鏈表的表示與實(shí)現(xiàn)教學(xué)重點(diǎn)：1、線性鏈表之單鏈表的表示及實(shí)現(xiàn)方法。2、雙向鏈表的表示與實(shí)現(xiàn)教學(xué)難點(diǎn)：1、線性鏈表2、雙向鏈表的存儲(chǔ)表示作業(yè)及參考書(shū)：寫(xiě)一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同。數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：復(fù)習(xí)引入展開(kāi)舉例小結(jié)作業(yè)一、復(fù)習(xí)約5min復(fù)習(xí)線性表有的概念二、引入約2min由線性表的表示不方便引入三、講課進(jìn)程設(shè)計(jì)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線 性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：約IOmin它是一種簡(jiǎn)單、方 便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元 素的存儲(chǔ)順序表示相應(yīng)

17、的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。暴露的問(wèn)題(1)在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；(2)對(duì)于長(zhǎng)度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常乂得不到充分的利用；(3)線性表的容量難以擴(kuò)充。231、單鏈表約IOmin用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的也可以是 不連續(xù)的)。2.3.2、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述約IOmin 2.3.3、單鏈表操作的實(shí)現(xiàn)約13min因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過(guò)程。操作步驟：1、建立一個(gè)“空表”；2、輸入數(shù)據(jù)元素an,建立結(jié)點(diǎn)并插入：3、輸入數(shù)據(jù)元素an-l,建立結(jié)點(diǎn)并

18、插入；4、依次類推，直至輸入al為止。2.3.4、其它形式的鏈表約5min 1.循環(huán)鏈表2.雙向鏈表2.3.5、有丿了；表類型約5min 2.4 元多項(xiàng)式的表示2.4.1 一元多項(xiàng)式約20min在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示:P = (Po,pl,., Pn)抽象數(shù)據(jù)類型一元 多項(xiàng)式的定義如下：ADT POIynOmial 數(shù)據(jù)對(duì)象：D= ail aiTennSet,i=l,2,.,m, m0 TermSet 中的每個(gè) 元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：Rl=ai-l,ai Iai-I ,aiD, i=2n fiai-1中的指數(shù)值ai中的指數(shù)值基本操作：CreatPOIy

19、n ( P, m )操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式PoDeStrOyPOlyn ( P )初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式POPrintPOIyn ( P )初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式PoPolynLengtlX P )初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。歡迎關(guān)注作者！作者每天都會(huì)史新粘品文克!AddPOlyn ( Pa, Pb )初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：Pa = Pa+Pb,并銷毀一元多項(xiàng)式PboSUbtraCtPOlyIl ( Pa, Pb )

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

21、的應(yīng)用舉例教學(xué)目的與要求：1、棧的數(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è)及參考書(shū)：1、棧定義的應(yīng)用2、棧的特點(diǎn)數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具： 多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：引入展開(kāi)舉例小結(jié)一作業(yè)一、引入約IOmin 1.什么是線性結(jié)構(gòu)？2.以餐館中一疊一疊的盤(pán)子的使用為例，引出棧的特點(diǎn)。二、講課進(jìn)程設(shè)計(jì)3.1棧的類型定義3.1、棧、棧頂(top)、棧底(bottom)的定義約IOmin 3.2棧的類型定義約IO

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

23、，用以接受用戶輸入的一行字符，然后逐行存入 用戶數(shù)據(jù)區(qū),并假設(shè)“# ”為退格符，“ ”為退行符。例四、迷宮求解約IOmin假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”?！凹{入路徑”的操作即為“當(dāng)前位置入棧；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出棧“。例五、表達(dá)式求值約IOmin任何一個(gè)表達(dá)式都是由操作數(shù)(OPerand)、運(yùn)算符(OPeratOr)和界限符(delimiter)組成。例六、實(shí)現(xiàn)遞歸約IOmin遞歸函數(shù)的實(shí)現(xiàn)一個(gè)遞歸函數(shù)的運(yùn)行過(guò)程類似于多個(gè)函數(shù)的嵌套調(diào)用，差別僅在于“調(diào)用函數(shù)和 被調(diào)用函數(shù)是同一個(gè)函數(shù)”。為了保證“每一層的遞歸調(diào)用”都是對(duì)“本層”

24、的數(shù)據(jù)進(jìn)行操作， 在執(zhí)行遞歸函數(shù)的過(guò)程中需要一個(gè)“遞歸?！?。三、小結(jié)約5min 1.掌握棧和隊(duì)列類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)注意棧滿和棧空的條件以及它們的描述 方法。四、作業(yè) 約5min 1. 4個(gè)元素al, a2, a3和a4依次通過(guò)一個(gè)棧，在“4進(jìn)棧前，棧的狀態(tài)，則不可歡迎關(guān)注作者！作者每天都會(huì)史新粘品文克!能的出棧序是()(A)a4, a3, a2, al (B)a3, a2, a4, al (C)a3, al, a4, a2 (D)a3,a4, a2, al 2、棧的特點(diǎn)是()。課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第3周

25、授課日期9月27日三星期月 日星期月 日星期月 日星期月 日星 期班級(jí)信管10-1基本課題隊(duì)列教學(xué)目的與要求：1. 熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。2. 理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。教學(xué)重點(diǎn)：1.鏈隊(duì)的表示與實(shí)現(xiàn)教學(xué)難點(diǎn)：.1。鏈隊(duì)的表示與實(shí)現(xiàn)作業(yè)及參考書(shū)：1.棧與隊(duì)列的比較2.讀程序段數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具： 多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：引入展開(kāi)舉例小結(jié)一作業(yè)一、引入約5min在日常生活中，為了維持正常的社會(huì)秩序而出現(xiàn)的常見(jiàn)現(xiàn)象是什么？是“排隊(duì)“。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是“隊(duì)列“。二、講課進(jìn)程設(shè)計(jì)3.4隊(duì)列1隊(duì)列的定義約IOmin

26、2隊(duì)列的抽象類型定義約15min 3.隊(duì)列的基本操作:約 20min InitQUeUe(Q)操作結(jié) 果：構(gòu)造一個(gè)空隊(duì)列Q。DeStrOyQUeUe(Q)初始條件:隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。QUeUeEnlPty(Q)初始條件:隊(duì)列Q已存在。操作結(jié)果:若Q為空隊(duì)列,則返回TRUE,否則返回FALSEOQUeUeLength(Q)初始條件:隊(duì)列Q已存在。操作結(jié)果:返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q, e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。CIearQUeUe(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。EnQUeUe(Q, e

27、)初始條件:隊(duì)列Q已存在。操作結(jié)果:插入元素e為Q的新的隊(duì)尾元素。DeQUeUe(Q, e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并Hle返回其值。QUeUeTraVers(Q, ViSito)隊(duì)列類型的實(shí)現(xiàn)4.鏈隊(duì)列鏈?zhǔn)接诚蠹s15min 5.循環(huán)隊(duì)列順序映象約20 min隊(duì)列在程序設(shè)汁中的一個(gè)典型應(yīng)用例子是作業(yè)排隊(duì)問(wèn)題。三、小結(jié)約5min 1.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述 方法。2.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。四、作業(yè)約IOminK線性表、棧和隊(duì)列都是()結(jié)構(gòu),可以在線性表的()位置插入和刪除元素， 對(duì)于棧只能在()插入和刪除

28、元素，對(duì)于隊(duì)列只能在()插入元素和()刪除元素。2、指出下述程序段的功能是什么？(1) VOid Demol(SeqStaCk *S)int i;arr64 ; n=0 ;While ( StaCkEmPty(S) arrn+=Pop(S);for (i=0, i i+)PUSh(S, arri); /Demol課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第4周授課日期月 日星期月 日星期月 日星期月 日星期月 日星期班 級(jí)信管10-1基本課題實(shí)驗(yàn)二 棧和隊(duì)列的總結(jié)復(fù)習(xí)教學(xué)目的與要求：1、深入了解棧和隊(duì)列的特征，以便在實(shí)際問(wèn)題背景下靈活運(yùn)用它們；2、鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問(wèn)題的遞歸

29、算法設(shè)計(jì)。教學(xué)重點(diǎn)：鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問(wèn)題的遞歸算法設(shè)計(jì)乙教學(xué)難點(diǎn)：鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問(wèn)題的遞歸算法設(shè)汁。作業(yè)及參考書(shū)：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：課堂類型：教學(xué)過(guò)程：停車場(chǎng)管理問(wèn)題描述設(shè)停車場(chǎng)內(nèi)只有一個(gè)的停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)測(cè)試數(shù)據(jù)設(shè) n=2,輸入數(shù)據(jù)為：(tA, 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)。其中宀表示到達(dá)；Tr表示離去，

30、表示輸入結(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)或便道上的停車位置；若是車離去；則輸出汽車在停車場(chǎng)內(nèi)停留的實(shí)現(xiàn)提示需另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退出來(lái)的汽車，也用順序存儲(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)開(kāi)辟數(shù)組的空間是多少？(2)

31、汽車可有不同種類，則它們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如1輛客車和15輛小汽 車的占地面積相同，1輛十輪卡車占地面積相當(dāng)于3輛小汽車的占地面積。(3) 汽車可以直接從便道上開(kāi)走，此時(shí)派在它前面的汽車要先開(kāi)走讓路，然后再依 次排到隊(duì)尾。(4) 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場(chǎng)的車低，請(qǐng)思考如何修 改結(jié)構(gòu)以滿足這種要求。課時(shí)授課計(jì)劃2020-2020學(xué)年第一學(xué)期第4周授課日期10月8日日星期月 日星期月 日星期月 日星期月曰星 期班 級(jí)信管10-1基本課題串教學(xué)目的與要求：1、熟悉串七種基本操作的定義，并能利用這些基本操作實(shí)現(xiàn)傳的其他各種操作的方 法。2、熟悉掌握在串的定長(zhǎng)順序存

32、儲(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è)及參考書(shū)：對(duì)串的操作的應(yīng)用數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：引入展開(kāi)舉例小結(jié)作業(yè)一、引入約5min計(jì)算機(jī)上的非數(shù)值處理的對(duì)象基本上都是字符串?dāng)?shù)據(jù)。二、講課進(jìn)程設(shè)計(jì)4.1串的抽象數(shù)據(jù)類型的定義1.定義約IOmin 串、串長(zhǎng)、空串、子串、主串、位置、相等、空格串2.串的抽象數(shù)據(jù)類型 的定義約 1 Omin StrASSign(T, Char

33、S) StrCOPy (T, S) DeStrOyString (S) StrEmPty(S) StrCOmPare(S,T) StrLength(S) COnCat(T,S 1 ,S2) SUbString (Sub,S,pos,len) IndeX(S,T,pos) RePIaCe(S,T,V) StrlnSert (S, pos, T) StrDelete (S, pos, Ien) ClearString(S) 4.2串的表示和實(shí)現(xiàn)4.2.1、串的定長(zhǎng)順序存儲(chǔ)表示 約15min 1.串聯(lián)接2.求子串422、串的堆分配存儲(chǔ)表示約20min通常,C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的

34、。系統(tǒng)利用函數(shù)malloc() 和free()進(jìn)行吊值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的 存儲(chǔ)空間為“堆”。423、串的塊鏈存儲(chǔ)表示約IOmin也可用鏈表來(lái)存儲(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)弱差別很大，但基本操作是一致的：都包括 串的查找，插入和刪除等基本操作。對(duì)用戶來(lái)講，一個(gè)文本(文件)可以包括若干頁(yè)，每頁(yè)包括若干行，每行包括若干文 字。歡迎關(guān)注作者！作者毎天都會(huì)史新粘品文蘋(píng)!對(duì)文本編輯程序來(lái)

35、講，可把整個(gè)文本看成一個(gè)長(zhǎng)字符串，稱文本串，頁(yè)是文本串的子 串，行乂是頁(yè)的子串。為簡(jiǎn)化程序復(fù)雜程度，可簡(jiǎn)單地把文本分成若干行。三、小結(jié)約5min 1.熟悉串的七種基本操作的定義，并能利用這些基本操作來(lái)實(shí)現(xiàn)吊的其它各種操 作的方法。2. 熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。3. 了解串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法。4. 了解串操作的應(yīng)用方法和特點(diǎn)。四、作業(yè)約5min假設(shè)有如下的串說(shuō)明：chai* sl30=tStocktom,CA, s230=MMarCh 5 1999, s330, *p; (1)在執(zhí)行下列語(yǔ)句后， s3 的值是什么？StrCOPy(S3,si

36、); COnCat(S3,u,u); ColICat(S3,s2);(2)調(diào)用函數(shù)StrCOmPare(S 1 ,s2)的返回值是什么？(3)調(diào)用函數(shù)StrCOmPaIe(Sl5,tonu)的返回值是什么？調(diào)用函數(shù)Strlength(ConCat(Sl,s2)fiJ返回值是什么?課時(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ù)組的順序表示方法教學(xué)難點(diǎn)：數(shù)組的順序表示方法作業(yè)及參考書(shū)：數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編

37、著教具：多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：引入展開(kāi)舉例小結(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)系：)ADT Array 二維數(shù)組的定義：約 IOmin 數(shù)據(jù)對(duì): D= aij 0ibl-l, 0 jb2-l數(shù) 據(jù)關(guān)系:R = ROW, COL ROW= ai,j,ail,j 0ibl-2, 0jb2-l） COL= ai,j,ai,j+ll 0ibl-l,0jl)性質(zhì)2 :深度為k的二叉樹(shù)上至多含2k-l個(gè)結(jié)點(diǎn)(1)。性質(zhì)3 :對(duì)任何一棵二叉樹(shù)，若它含

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

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

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

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

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

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

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

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

46、學(xué)重點(diǎn)：1、樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法2.學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。教學(xué)難點(diǎn)：1、樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換方法2.學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法。歡迎關(guān)注作者！作者每天都會(huì)史新粘品文克!作業(yè)及參考書(shū)：樹(shù)和森林的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析/高一凡編著教具：多媒體板書(shū)課堂類型：講授 教學(xué)過(guò)程：引入展開(kāi)舉例小結(jié)作業(yè)一、引入約5min由前面樹(shù)、二叉樹(shù)的回顧引入 二、講課進(jìn)程設(shè)Ii 6.4樹(shù)和森林641樹(shù)的存儲(chǔ)結(jié) 構(gòu)約25min 1 雙親表示法以一組連續(xù)的存儲(chǔ)空間存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指針指示其雙親結(jié)點(diǎn)在 這連續(xù)的存儲(chǔ)空間中的位置（下標(biāo)，這種結(jié)構(gòu)屬靜態(tài)鏈表），可形式表示如下：typrdef StrUCt tnode datatype