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

1、歡迎關(guān)注作者！作者每天都會史新粘品文蘋!數(shù)據(jù)結(jié)構(gòu)（C語言版）教案數(shù)據(jù)結(jié)構(gòu)（C語言版）教案2020至2020學(xué)年第一學(xué)期教 案課程名稱 數(shù)據(jù)結(jié)構(gòu) 使用教材數(shù)據(jù)結(jié)構(gòu) （C語言版）教學(xué)時數(shù)56課程性質(zhì) 必修任課班級（人數(shù)）信管（53人）信息 系（部）信管 教研室任課教師山東科技大學(xué)泰山科技學(xué)院課時授課計劃2020-2020學(xué)年笫二學(xué)期第1周授課日期2月20日星期1月 日星期月 日星期月 日星期月 日星 期班級信管10-1基本課題第1章緒論1.1-1.2教學(xué)目的與要求：1. 了解數(shù)據(jù)結(jié)構(gòu)的基本概念2.理解常用術(shù)語教學(xué)重點：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語教學(xué)難點：數(shù)據(jù)元素之間的四種結(jié)構(gòu)關(guān)系作業(yè)及參考書：1、什

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

3、管理結(jié)論計算機(jī)的操作對象的關(guān)系更加復(fù)雜， 操作形式不再是單純的數(shù)值計算，而更多地是對這些具有一定關(guān)系的數(shù)據(jù)進(jìn)行組織管理；我們將此稱為非數(shù)值性處理。要使計算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必 須弄清楚這些操作對象的特點，在汁算機(jī)中的表示方式以及各個操作的具體實現(xiàn)手段。1.2基本概念和術(shù)語1.1.1、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu) 約20min數(shù)據(jù)：是對客觀事物的符號表所有能被輸入到計算機(jī)中，且能被訃算機(jī)處理的符號的集合。是計算機(jī)操作的對象的 總稱。是計算機(jī)處理的信息的某種特定的符號表示形式。數(shù)據(jù)元素：是數(shù)據(jù)（集合）中的一個“個體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的

4、一個子集。數(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)格的一對一關(guān)系如上面的成績表中各元素樹形結(jié)構(gòu)元素間為嚴(yán)格 的一對多關(guān)系圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）元素間為多對多關(guān)系數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù) 據(jù)結(jié)構(gòu)是一個二元組數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器中的映像數(shù)據(jù)元素的映 象方法：計算機(jī)中存儲信息的最小單位：位，8位為一字節(jié)，兩個字節(jié)為一字，字節(jié)、字 或更多的二進(jìn)制位可稱為位串。在邏輯描述中，把位串稱為元素或結(jié)點。關(guān)系的映象方法：順序映象鏈?zhǔn)接诚?22、數(shù)據(jù)類型約5min數(shù)據(jù)類型是一個

5、值 的集合和定義在此集合上的一組操作的總稱。123、抽象數(shù)據(jù)類型約20min是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操 作。關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲方式。定義它的人 同樣不必要關(guān)心它如何存儲。抽象數(shù)據(jù)類型表示法：三元組表示：（D, S, P） 其中D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的 基本操作集。書中的定義格式：ADT抽象數(shù)據(jù)類型名數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義基本操作：基本操作的定義ADT抽象數(shù)據(jù)類型名ADT有兩個重要特征：數(shù)據(jù)抽象數(shù)據(jù)封裝四、本次課小結(jié)：約3min 1.熟悉各名詞2.術(shù)語的含義3.掌握基本概念五、作業(yè)約2min

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

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

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

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

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

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

12、已存在。操作結(jié)果：銷毀線性表Lo 引用型操作ListEmptyC L )(線性表判空)LiStLength( L)(求線性表的長度) PriorElem( L，cur_e, pre_e )(求數(shù)據(jù)元素的前驅(qū))NeXtEIem(L, cur_e, next_e )(求數(shù)據(jù)元 素的后繼)GetElem( L, i, e )(求線性表中某個數(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兩個線性表合并LA和LB 2.2線性表的順序 表示和實現(xiàn)221順序映象約15min以X的存儲位置和y的存儲位置之間某種關(guān) 系表示邏輯關(guān)系x,y。最簡單的一種順序映象方法是：令y的存儲位置和X的存儲位置相鄰。線性表的基本操作在順序表中的實現(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)的實現(xiàn)：首先分析插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表操作LiStDeIete(U i, e)的實現(xiàn):首先分析：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？線性表類型的實現(xiàn)2.1.2、線性表順 序存儲結(jié)構(gòu)的特點：約20min它是一種簡單、方便的存儲方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù) 的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應(yīng)的邏輯順序，這種存儲方式屬于靜 態(tài)存儲形式。暴露的問題(1)在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；(2) 對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常乂 得不到充分的利用；(3

15、) 線性表的容量難以擴(kuò)充。三、小結(jié)約5min 1.7解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在 計算機(jī)中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。用前者表 示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。2. 熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實現(xiàn)。課時授課計劃2020-2020學(xué)年第二學(xué)期第2周授課日期3月3日星期月 日星期月 日星期月 日星期月 日星期 班級信管10-1基本課題線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)一元多項式的表示及相加教學(xué)LI的 與要求：1、掌握線性鏈表、單鏈表、靜態(tài)鏈表的概念、表示及實現(xiàn)方法。2、掌握循環(huán)鏈表的概念3、掌握

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

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

18、插入；4、依次類推，直至輸入al為止。2.3.4、其它形式的鏈表約5min 1.循環(huán)鏈表2.雙向鏈表2.3.5、有丿了；表類型約5min 2.4 元多項式的表示2.4.1 一元多項式約20min在計算機(jī)中，可以用一個線性表來表示:P = (Po,pl,., Pn)抽象數(shù)據(jù)類型一元 多項式的定義如下：ADT POIynOmial 數(shù)據(jù)對象：D= ail aiTennSet,i=l,2,.,m, m0 TermSet 中的每個 元素包含一個表示系數(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項的系數(shù)和指數(shù)，建立一元多項式PoDeStrOyPOlyn ( P )初始條件：一元多項式P已存在。操作結(jié)果：銷毀一元多項式POPrintPOIyn ( P )初始條件：一元多項式P已存在。操作結(jié)果：打印輸出一元多項式PoPolynLengtlX P )初始條件：一元多項式P已存在。操作結(jié)果：返回一元多項式P中的項數(shù)。歡迎關(guān)注作者！作者每天都會史新粘品文克!AddPOlyn ( Pa, Pb )初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相加運算，即：Pa = Pa+Pb,并銷毀一元多項式PboSUbtraCtPOlyIl ( Pa, Pb )

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

21、的應(yīng)用舉例教學(xué)目的與要求：1、棧的數(shù)據(jù)類型定義2、棧的順序存儲與實現(xiàn)3、掌握棧的應(yīng)用方法，理解棧的 重要作用教學(xué)重點：1、棧的順序存儲表示與實現(xiàn)方法2、利用棧實現(xiàn)行編輯、利用棧實現(xiàn)表達(dá)式求值教 學(xué)難點：1、棧的定義2、利用棧實現(xiàn)表達(dá)式求值作業(yè)及參考書：1、棧定義的應(yīng)用2、棧的特點數(shù)據(jù)結(jié)構(gòu)算法實現(xiàn)及解析/高一凡編著教具： 多媒體板書課堂類型：講授 教學(xué)過程：引入展開舉例小結(jié)一作業(yè)一、引入約IOmin 1.什么是線性結(jié)構(gòu)？2.以餐館中一疊一疊的盤子的使用為例，引出棧的特點。二、講課進(jìn)程設(shè)計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ī)實現(xiàn)訃算的基本問題，個簡單算法基于下列原理：N = (N div d)d + N mod d (其中：div為整除運算，mod為求余運算)例二、括號匹 配的檢驗約IOmin檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。三種悄況對應(yīng)到棧的操作即為：1. 和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?. 棧中并沒有左括弧等在哪里；3. 棧中還有左括弧沒有等到和它相匹配的右括弧。例三、行編輯程序問題約1 Omin在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。合理的作法是：設(shè)立一個輸入緩沖區(qū)

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

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

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

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

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

28、元素，對于隊列只能在()插入元素和()刪除元素。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課時授課計劃2020-2020學(xué)年第一學(xué)期第4周授課日期月 日星期月 日星期月 日星期月 日星期月 日星期班 級信管10-1基本課題實驗二 棧和隊列的總結(jié)復(fù)習(xí)教學(xué)目的與要求：1、深入了解棧和隊列的特征，以便在實際問題背景下靈活運用它們；2、鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸

29、算法設(shè)計。教學(xué)重點：鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)計乙教學(xué)難點：鞏固這兩種結(jié)構(gòu)的構(gòu)造方法，接觸較復(fù)雜問題的遞歸算法設(shè)汁。作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實現(xiàn)及解析/高一凡編著教具：課堂類型：教學(xué)過程：停車場管理問題描述設(shè)停車場內(nèi)只有一個的停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)測試數(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停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽 車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛 到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的實現(xiàn)提示需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。棧中每個元素表示一 輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進(jìn)入停車場的時刻。選作內(nèi)容(1)兩個棧共享空間，思考應(yīng)開辟數(shù)組的空間是多少？(2)

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

32、儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。3、掌握串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串的各種操作的基本方法。教學(xué)重點：1、串七種基本操作的定義2、串的定長順序存儲3、串的堆存儲結(jié)構(gòu)教學(xué)難點：1、串七種基本操作的定義2、串的堆存儲結(jié)構(gòu)作業(yè)及參考書：對串的操作的應(yīng)用數(shù)據(jù)結(jié)構(gòu)算法實現(xiàn)及解析/高一凡編著教具：多媒體板書課堂類型：講授 教學(xué)過程：引入展開舉例小結(jié)作業(yè)一、引入約5min計算機(jī)上的非數(shù)值處理的對象基本上都是字符串?dāng)?shù)據(jù)。二、講課進(jìn)程設(shè)計4.1串的抽象數(shù)據(jù)類型的定義1.定義約IOmin 串、串長、空串、子串、主串、位置、相等、空格串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串的表示和實現(xiàn)4.2.1、串的定長順序存儲表示 約15min 1.串聯(lián)接2.求子串422、串的堆分配存儲表示約20min通常,C語言中提供的串類型就是以這種存儲方式實現(xiàn)的

34、。系統(tǒng)利用函數(shù)malloc() 和free()進(jìn)行吊值空間的動態(tài)管理，為每一個新產(chǎn)生的串分配一個存儲區(qū)，稱串值共享的 存儲空間為“堆”。423、串的塊鏈存儲表示約IOmin也可用鏈表來存儲串值，由于串的數(shù)據(jù)元素是一個字符，它只有8位二進(jìn)制數(shù)， 因此用鏈表存儲時，通常一個結(jié)點中存放的不是一個字符，而是一個子串。4.4串操作應(yīng)用舉例4.4.1文本編輯約20min可用于文本編輯的程序很多，功能強(qiáng)弱差別很大，但基本操作是一致的：都包括 串的查找，插入和刪除等基本操作。對用戶來講，一個文本(文件)可以包括若干頁，每頁包括若干行，每行包括若干文 字。歡迎關(guān)注作者！作者毎天都會史新粘品文蘋!對文本編輯程序來

35、講，可把整個文本看成一個長字符串，稱文本串，頁是文本串的子 串，行乂是頁的子串。為簡化程序復(fù)雜程度，可簡單地把文本分成若干行。三、小結(jié)約5min 1.熟悉串的七種基本操作的定義，并能利用這些基本操作來實現(xiàn)吊的其它各種操 作的方法。2. 熟練掌握在串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。3. 了解串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。4. 了解串操作的應(yīng)用方法和特點。四、作業(yè)約5min假設(shè)有如下的串說明：chai* sl30=tStocktom,CA, s230=MMarCh 5 1999, s330, *p; (1)在執(zhí)行下列語句后， 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返回值是什么?課時授課計劃2020-2020學(xué)年 第一學(xué)期第5周授課日期10月11日三星期月 日星期月 日星期月曰星期月曰星期班級信管 10-1基本課題數(shù)組教學(xué)的與要求：1、掌握數(shù)組的定義2、掌握數(shù)組的順序表示方法教學(xué)重點：1、數(shù)組的定義2、數(shù)組的順序表示方法教學(xué)難點：數(shù)組的順序表示方法作業(yè)及參考書：數(shù)據(jù)結(jié)構(gòu)算法實現(xiàn)及解析/高一凡編

37、著教具：多媒體板書課堂類型：講授 教學(xué)過程：引入展開舉例小結(jié)一、引入約5min山前兒章討論的線性結(jié)構(gòu)中的數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型引入數(shù)組。二、講課進(jìn)程設(shè)計5.1數(shù)組的類型定義抽象數(shù)據(jù)類型定義約5minADTArray 數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：)ADT Array 二維數(shù)組的定義：約 IOmin 數(shù)據(jù)對: 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的二叉樹上至多含2k-l個結(jié)點(1)。性質(zhì)3 :對任何一棵二叉樹，若它含

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

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

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

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

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

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

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

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

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