教案學(xué)院:課程名稱:數(shù)據(jù)結(jié)構(gòu)任課教師:專業(yè)班級:課程學(xué)時(shí):64周學(xué)時(shí):4年月日教案紙（首頁）第1頁第1次課2學(xué)時(shí)授課時(shí)間_______教學(xué)主題數(shù)據(jù)結(jié)構(gòu)基本概念教學(xué)要求1、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念。2、掌握數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的映射關(guān)系。3、掌握數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的區(qū)別和聯(lián)系。4、掌握利用抽象數(shù)據(jù)類型表述求解問題的方法。教學(xué)重點(diǎn)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)運(yùn)算三方面的概念及相互關(guān)系、抽象數(shù)據(jù)類型教學(xué)難點(diǎn)利用抽象數(shù)據(jù)類型表述求解問題的方法教學(xué)方法講授教學(xué)手段多媒體+板書講授要點(diǎn)1、數(shù)據(jù)結(jié)構(gòu)的概念。2、數(shù)據(jù)邏輯結(jié)構(gòu)類型和存儲結(jié)構(gòu)類型。3、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型的關(guān)系。4、抽象數(shù)據(jù)類型的作用和描述方法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（首頁）第1頁教學(xué)內(nèi)容備注與后記首先自我介紹和課程介紹。數(shù)據(jù)結(jié)構(gòu)到底是什么，我們一起來看一看。1.1什么是數(shù)據(jù)結(jié)構(gòu)1.1.1、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：是對客觀事物的符號表示。所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號的集合。是計(jì)算機(jī)操作的對象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號表示形式。數(shù)據(jù)元素：是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。這種集合稱為結(jié)構(gòu)。舉例說明：學(xué)生成績表結(jié)論：數(shù)據(jù)結(jié)構(gòu)中討論的元素關(guān)系主要是指相鄰關(guān)系或鄰接關(guān)系。由此得出，一個(gè)數(shù)據(jù)結(jié)構(gòu)的構(gòu)成：數(shù)據(jù)的邏輯結(jié)構(gòu):集合松散線性結(jié)構(gòu)一對一樹型結(jié)構(gòu)一對多網(wǎng)狀結(jié)構(gòu)多對多每一種邏輯結(jié)構(gòu)舉實(shí)例進(jìn)行說明，幫助學(xué)生加深理解。數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式就是存儲結(jié)構(gòu)。常用的四種基本存儲類型有順序存儲、鏈?zhǔn)酱鎯?、順序存儲、哈希存儲等。?shù)據(jù)運(yùn)算：數(shù)據(jù)運(yùn)算是對數(shù)據(jù)的操作。1.1.2、數(shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱（一起復(fù)習(xí)C語言中已經(jīng)學(xué)過的數(shù)據(jù)類型。）1.1.3、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（ADT）指的是從求解問題的數(shù)學(xué)模型中抽象出來的數(shù)據(jù)邏輯結(jié)構(gòu)和運(yùn)算（抽象運(yùn)算），而不考慮計(jì)算機(jī)的具體實(shí)現(xiàn)。抽象數(shù)據(jù)類型=數(shù)據(jù)邏輯結(jié)構(gòu)+抽象運(yù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有兩個(gè)重要特征:數(shù)據(jù)抽象數(shù)據(jù)封裝本課小結(jié)：熟悉各名詞、術(shù)語的含義，掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，理解抽象數(shù)據(jù)類型的定義。

第2次課2學(xué)時(shí)授課時(shí)間__________教學(xué)主題算法的基本概念以及算法的分析教學(xué)要求1、掌握算法的特性和描述方法。2、掌握算法的分析方法，包括時(shí)間復(fù)雜度和空間復(fù)雜度分析。3、掌握從數(shù)據(jù)結(jié)構(gòu)的角度設(shè)計(jì)好的算法的過程。教學(xué)重點(diǎn)算法特性，算法的時(shí)間復(fù)雜度分析和空間復(fù)雜度分析，設(shè)計(jì)好的算法的過程教學(xué)難點(diǎn)算法的時(shí)間復(fù)雜度分析和空間復(fù)雜度分析教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、上機(jī)實(shí)操講授要點(diǎn)1、算法的特性，算法和程序的異同。2、算法的時(shí)間復(fù)雜度分析。3、算法的空間復(fù)雜度分析。4、設(shè)計(jì)好的算法的過程。作業(yè)完成學(xué)習(xí)通上的第一章測試題。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（首頁）第1頁教學(xué)內(nèi)容備注與后記回顧上節(jié)課有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念，引入算法：1.2算法及其描述1.2.1什么是算法算法是對特定問題求解步驟的一種描述，它是指令的有限序列。算法的五個(gè)重要特性：（1）有窮性（2）確定性（3）可行性（4）有輸入（5）有輸出舉例說明是否為算法，并說出原因。1.2.2算法的描述自然語言、偽代碼、C\C++語言描述課上舉例說明，課下練習(xí)學(xué)習(xí)通上的例題。1.3算法的分析算法分析目的：分析算法的時(shí)間和空間效率以便改進(jìn)算法性能。1.3.1時(shí)間復(fù)雜度分析事前估算分析法：算法的執(zhí)行時(shí)間是問題規(guī)模n的函數(shù)。一個(gè)算法由控制結(jié)構(gòu)和原操作構(gòu)成，求出算法所有原操作的執(zhí)行次數(shù)，用T(n)表示。算法執(zhí)行時(shí)間大致=原操作所需的時(shí)間×T(n)在算法分析時(shí)，原操作所需時(shí)間基本不變，僅僅考慮基本操作的運(yùn)算次數(shù)，所以算法的執(zhí)行時(shí)間用時(shí)間復(fù)雜度來表示O(f(n))=T(n)。記號“O”讀作“大O”，它表示隨問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同。T(T(n)nf(n)n0一般地，常用的有常數(shù)階O(1)、線性階O(n)、平方階O(n2)、立方階O(n3)、對數(shù)階O(log2n)、指數(shù)階O(2n)等。算法時(shí)間性能比較：假如求同一問題有兩個(gè)算法：A和B，如果算法A的平均時(shí)間復(fù)雜度為O(n)，而算法B的平均時(shí)間復(fù)雜度為O(n2)。一般情況下，認(rèn)為算法A的時(shí)間性能好比算法B。O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)補(bǔ)充：時(shí)間復(fù)雜性的運(yùn)算法則求和規(guī)則：求積規(guī)則：1.3.2空間復(fù)雜度分析用于量度一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲空間大小。一般也作為問題規(guī)模n的函數(shù)，采用數(shù)量級形式描述，記作：S(n)=O(g(n))1.4其他情況的算法分析1.4.1最好、最壞和平均復(fù)雜度分析注意：通常默認(rèn)情況下的時(shí)間復(fù)雜度是指平均復(fù)雜度。1.4.2遞歸算法的時(shí)空復(fù)雜度分析本課小結(jié)：介紹了算法的特性和描述方法，重點(diǎn)講解了算法的時(shí)間復(fù)雜度分析和空間復(fù)雜度分析，課下把學(xué)習(xí)通上的第一章的測驗(yàn)完成，掌握算法的時(shí)間復(fù)雜度分析。第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題線性表2.1線性表的基本概念；2.2線性表的順序存儲結(jié)構(gòu)教學(xué)要求1、掌握線性表的邏輯結(jié)構(gòu)特點(diǎn)，線性表抽象數(shù)據(jù)類型的描述方法。2、掌握線性表的順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)。教學(xué)重點(diǎn)線性表的邏輯結(jié)構(gòu)特點(diǎn)；線性表的順序存儲結(jié)構(gòu)特點(diǎn)及其實(shí)現(xiàn)。教學(xué)難點(diǎn)線性表的順序存儲結(jié)構(gòu)的特點(diǎn)及其實(shí)現(xiàn)教學(xué)方法講授教學(xué)手段多媒體+板書講授要點(diǎn)1、線性表的概念及其邏輯結(jié)構(gòu)特點(diǎn)。2、線性表抽象數(shù)據(jù)類型的描述方法。3、線性表的順序存儲結(jié)構(gòu)。作業(yè)完成學(xué)習(xí)通上第二章中有關(guān)順序表的作業(yè)。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記2.1線性表的基本概念1、線性表的定義線性表是一個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。三個(gè)特性：一致性；有窮性；序列性。線性表的邏輯表示：(a1，a2，…，ai，ai+1，…，an)ai（1≤i≤n）表示第i（i表示邏輯位序）個(gè)元素。舉實(shí)例說明，加深學(xué)生對線性表的認(rèn)識。2、線性表的基本運(yùn)算初始化線性表InitList(&L)：構(gòu)造一個(gè)空的線性表L。銷毀線性表DestroyList(&L)：釋放線性表L占用的內(nèi)存空間。判線性表是否為空表ListEmpty(L)：若L為空表，則返回真，否則返回假。求線性表的長度ListLength(L)：返回L中元素個(gè)數(shù)n。輸出線性表DispList(L)：線性表L不為空時(shí)，順序顯示L中各結(jié)點(diǎn)的值域。求線性表L中指定位置的某個(gè)數(shù)據(jù)元素GetElem(L，i，&e)：用e返回L中第i（1≤i≤n）個(gè)元素的值。定位查找LocateElem(L，e)：返回L中第一個(gè)值域與e相等的邏輯位序。若這樣的元素不存在，則返回值為0。插入一個(gè)數(shù)據(jù)元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）個(gè)元素位置插入新的元素e，L的長度增1。刪除數(shù)據(jù)元素ListDelete(&L，i，&e)：刪除L的第i（1≤i≤n）個(gè)元素，并用e返回其值，L的長度減1。3、線性表的抽象數(shù)據(jù)類型ADTList{數(shù)據(jù)對象：D={ai|1≤i≤n，n≥0，ai為ElemType類型}//ElemType是自定義類型標(biāo)識符數(shù)據(jù)關(guān)系：R={<ai，ai+1>|ai、ai+1∈D，i=1，…，n-1}基本運(yùn)算：9個(gè)運(yùn)算}2.2線性表的順序存儲結(jié)構(gòu)1、線性表的順序存儲——順序表線性表的順序存儲結(jié)構(gòu)：把線性表中的所有元素按照順序存儲方法進(jìn)行存儲。按邏輯順序依次存儲到存儲器中一片連續(xù)的存儲空間中。2、順序表的運(yùn)算的實(shí)現(xiàn)InitList(&L)//結(jié)構(gòu)初始化DestroyList(&L)//銷毀線性表ListEmpty(&L)//判定是否為空表ListLength(L)//線性表的長度DispList(L)//輸出線性表GetElem(L，i，e)//求某個(gè)數(shù)據(jù)元素值LocateElem(L,e)//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i，e)//刪除元素重點(diǎn)講解以下操作：ListInsert(&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)3、順序表的應(yīng)用示例刪除線性表中所有值為x的數(shù)據(jù)元素教學(xué)總結(jié)：本節(jié)課給大家介紹了線性表的基本定義，線性表的邏輯結(jié)構(gòu)特點(diǎn)以及線性表的順序存儲結(jié)構(gòu)，以上知識點(diǎn)是數(shù)據(jù)結(jié)構(gòu)中的非常重要的，大家必須要掌握。

第次課學(xué)時(shí)授課時(shí)間_________教學(xué)主題線性表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)教學(xué)要求通過本章節(jié)的學(xué)習(xí)，學(xué)生應(yīng)達(dá)到如下基本要求：1、掌握線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)設(shè)計(jì)方法及其優(yōu)缺點(diǎn)。2、掌握單鏈表、雙鏈表和循環(huán)鏈表算法設(shè)計(jì)方法。教學(xué)重點(diǎn)單鏈表的查找、插入和刪除操作過程及其實(shí)現(xiàn)；雙鏈表的查找、插入和刪除操作過程及其實(shí)現(xiàn)。雙鏈表的查找、插入和刪除操作過程及其實(shí)現(xiàn)。教學(xué)難點(diǎn)單鏈表的查找、插入和刪除操作過程及其實(shí)現(xiàn)。教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、板書、上機(jī)實(shí)操講授要點(diǎn)1、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2、單鏈表的算法設(shè)計(jì)方法。3、雙鏈表的算法設(shè)計(jì)方法。4、循環(huán)鏈表的算法設(shè)計(jì)方法。作業(yè)完成學(xué)習(xí)通上第二章作業(yè)中有關(guān)鏈表的練習(xí)題。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)——鏈表特點(diǎn)：線性表中每個(gè)結(jié)點(diǎn)有唯一的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。設(shè)計(jì)鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，每個(gè)邏輯結(jié)點(diǎn)存儲單獨(dú)存儲，為了表示邏輯關(guān)系，增加指針域。頭結(jié)點(diǎn)：單鏈表中增加一個(gè)頭結(jié)點(diǎn)的優(yōu)點(diǎn)如下：第一個(gè)結(jié)點(diǎn)的操作和表中其他結(jié)點(diǎn)的操作相一致，無需進(jìn)行特殊處理；無論鏈表是否為空，都有一個(gè)頭結(jié)點(diǎn)，因此空表和非空表的處理也就統(tǒng)一了。存儲密度是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲量和整個(gè)結(jié)點(diǎn)結(jié)構(gòu)中所占的存儲量之比。2、單鏈表單鏈表結(jié)點(diǎn)的定義typedefstructLNode//定義單鏈表結(jié)點(diǎn)類型{ElemTypedata;structLNode*next;//指向后繼結(jié)點(diǎn)}LinkNode;單鏈表的特點(diǎn)：當(dāng)訪問過一個(gè)結(jié)點(diǎn)后，只能接著訪問它的后繼結(jié)點(diǎn)，而無法訪問它的前驅(qū)結(jié)點(diǎn)。插入結(jié)點(diǎn)：只需修改相關(guān)結(jié)點(diǎn)的指針域，不需要移動結(jié)點(diǎn)。s->next=p->next;p->next=s;刪除結(jié)點(diǎn)：只需修改相關(guān)結(jié)點(diǎn)的指針域，不需要移動結(jié)點(diǎn)p->next=p->next->next;線性表的9種基本操作在單鏈表中的實(shí)現(xiàn)，重點(diǎn)講解插入和刪除一個(gè)結(jié)點(diǎn)的操作實(shí)現(xiàn)。3、雙鏈表雙鏈表的結(jié)點(diǎn)定義：typedefstructDNode //雙鏈表結(jié)點(diǎn)類型{ElemTypedata;structDNode*prior; //指向前驅(qū)結(jié)點(diǎn)structDNode*next; //指向后繼結(jié)點(diǎn)}DLinkNode;雙鏈表的特點(diǎn)：從任一結(jié)點(diǎn)出發(fā)可以快速找到其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)；從任一結(jié)點(diǎn)出發(fā)可以訪問其他結(jié)點(diǎn)。雙鏈表的插入操作操作語句：s->next=p->nextp->next->prior=ss->prior=pp->next=s雙鏈表的插入操作p->next->next->prior=pp->next=p->next->next4、循環(huán)鏈表循環(huán)單鏈表：將表中尾結(jié)點(diǎn)的指針域改為指向表頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此從表中任一結(jié)點(diǎn)出發(fā)均可找到鏈表中其他結(jié)點(diǎn)。循環(huán)雙鏈表：形成兩個(gè)環(huán)。教學(xué)總結(jié)：本章節(jié)主要介紹了線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)，單鏈表、雙鏈表和循環(huán)鏈表的特點(diǎn)和基本操作的實(shí)現(xiàn)，其中單鏈表的內(nèi)容是需要大家重點(diǎn)掌握的。

第次課學(xué)時(shí)授課時(shí)間_____教學(xué)主題線性表線性表的應(yīng)用、有序表教學(xué)要求通過本章節(jié)的學(xué)習(xí)，學(xué)生應(yīng)達(dá)到如下基本要求：1、掌握掌握順序表、單鏈表的算法設(shè)計(jì)方法。2、掌握有序表的特點(diǎn)和有序表的歸并算法設(shè)計(jì)方法。教學(xué)重點(diǎn)順序表、單鏈表的應(yīng)用算法設(shè)計(jì)；有序表的特點(diǎn)。雙鏈表的查找、插入和刪除操作過程及其實(shí)現(xiàn)。教學(xué)難點(diǎn)線性表的應(yīng)用算法設(shè)計(jì)實(shí)現(xiàn)；有序表的特點(diǎn)。教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、板書、上機(jī)實(shí)操講授要點(diǎn)1、利用線性表求解復(fù)雜問題的方法。2、有序表的特點(diǎn)和歸并算法設(shè)計(jì)。作業(yè)完成學(xué)習(xí)通上第二章作業(yè)中線性表的練習(xí)題。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（首頁）第1頁教學(xué)內(nèi)容備注與后記2.4線性表的應(yīng)用1、基于順序表基本操作的算法設(shè)計(jì)查找元素插入元素刪除元素例子：將整數(shù)順序表L以第一個(gè)元素為分界線（基準(zhǔn)）進(jìn)行劃分在順序表L中刪除所有值為x的元素……2、單鏈表算法設(shè)計(jì)查找結(jié)點(diǎn)插入結(jié)點(diǎn)刪除結(jié)點(diǎn)基于兩個(gè)建表方法的單鏈表算法設(shè)計(jì)：頭插法：相對次序相反尾插法：相對次序相同例子：設(shè)計(jì)一個(gè)算法，刪除一個(gè)單鏈表L中元素值最大的結(jié)點(diǎn)（假設(shè)最大值結(jié)點(diǎn)是唯一的）；有一個(gè)帶頭結(jié)點(diǎn)的單鏈表L（至少有一個(gè)數(shù)據(jù)結(jié)點(diǎn)），設(shè)計(jì)一個(gè)算法使其元素遞增有序排列。2.5有序表所謂有序表，是指這樣的線性表，其中所有元素以遞增或遞減方式有序排列從邏輯結(jié)構(gòu)看，有序表是線性表的一個(gè)子集，可以采用順序表或者鏈表存儲。利用二路歸并思路可以提高相關(guān)算法的效率。例題：已知一個(gè)有序單鏈表L（允許出現(xiàn)值域重復(fù)的結(jié)點(diǎn)），設(shè)計(jì)一個(gè)高效算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時(shí)間復(fù)雜度。教學(xué)總結(jié)：本章節(jié)主要介紹了線性表的應(yīng)用，單鏈表、雙鏈表的實(shí)現(xiàn)，還介紹了有序表的特點(diǎn)，希望同學(xué)們課下再認(rèn)真復(fù)習(xí)，把課上所講的內(nèi)容能夠消化吸收。第次課學(xué)時(shí)授課時(shí)間________教學(xué)主題棧和隊(duì)列棧的特點(diǎn)；棧的表示和實(shí)現(xiàn)；棧的典型應(yīng)用與實(shí)現(xiàn)教學(xué)要求通過本章的學(xué)習(xí)，學(xué)生應(yīng)達(dá)到如下基本要求：1、掌握棧的邏輯結(jié)構(gòu)特性，棧抽象數(shù)據(jù)類型的描述方法。2、掌握棧的先進(jìn)后出特點(diǎn)。3、掌握?；具\(yùn)算在兩類存儲結(jié)構(gòu)下的實(shí)現(xiàn)算法。4、掌握棧在實(shí)際求解問題中的應(yīng)用方法。教學(xué)重點(diǎn)棧的邏輯結(jié)構(gòu)特點(diǎn)；順序棧和鏈棧的基本算法設(shè)計(jì)。教學(xué)難點(diǎn)棧與線性表的異同；順序棧和鏈棧的基本算法設(shè)計(jì)教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、板書、上機(jī)實(shí)操講授要點(diǎn)1、棧的邏輯結(jié)構(gòu)特性。2、棧抽象數(shù)據(jù)類型的描述方法。3、順序棧的算法設(shè)計(jì)方法。4、鏈棧的算法設(shè)計(jì)方法。5、棧在表達(dá)式求值中的應(yīng)用。作業(yè)完成學(xué)習(xí)通上第三章中有關(guān)棧的練習(xí)作業(yè)。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第5頁教學(xué)內(nèi)容備注與后記3.1棧1、棧的定義棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。特點(diǎn)：后進(jìn)先出關(guān)于棧的幾個(gè)概念：允許進(jìn)行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。棧的插入操作通常稱為進(jìn)?；蛉霔?。棧的刪除操作通常稱為退?；虺鰲！Ｅe實(shí)例說明，加深學(xué)生對棧的理解和認(rèn)識。2、棧的存儲結(jié)構(gòu)順序存儲——順序棧鏈?zhǔn)酱鎯Α湕?、棧的基本運(yùn)算InitStack(&s)：初始化棧。構(gòu)造一個(gè)空棧s。DestroyStack(&s)：銷毀棧。釋放棧s占用的存儲空間。StackEmpty(s)：判斷棧是否為空:若棧s為空，則返回真；否則返回假。Push(&S，e)：進(jìn)棧。將元素e插入到棧s中作為棧頂元素。Pop(&s，&e)：出棧。從棧s中退出棧頂元素，并將其值賦給e。GetTop(s，&e)：取棧頂元素。返回當(dāng)前的棧頂元素，并將其值賦給e。4、順序棧的基本操作實(shí)現(xiàn)typedefstruct{ElemTypedata[MaxSize]；inttop； //棧頂指針}SqStack；順序棧的6種基本運(yùn)算實(shí)現(xiàn)。例3-4。5、鏈棧的基本操作實(shí)現(xiàn)typedefstructlinknode{ElemTypedata; //數(shù)據(jù)域structlinknode*next; //指針域}LinkStNode;順序棧的6種基本運(yùn)算實(shí)現(xiàn)。例3-5。3.2棧的典型應(yīng)用與實(shí)現(xiàn)1、簡單表達(dá)式求值這里限定的簡單表達(dá)式求值問題是：用戶輸入一個(gè)包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號的合法算術(shù)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。中綴表達(dá)式：1+2*3后綴表達(dá)式：123*+前綴表達(dá)式：+1*23利用棧的特點(diǎn)將表達(dá)式轉(zhuǎn)化成后綴表達(dá)式，再利用棧求出表達(dá)式的值。2、求解迷宮問題（選講內(nèi)容）給定一個(gè)M×N的迷宮圖、入口與出口、行走規(guī)則。求一條從指定入口到出口的路徑。利用棧后進(jìn)先出的特點(diǎn)求解上述問題并實(shí)現(xiàn)算法。教學(xué)總結(jié)：本章節(jié)給大家介紹了棧的基本定義，棧的特點(diǎn)是后進(jìn)先出。利用棧的這個(gè)特性可以解決實(shí)際生活中遇到的一些問題。

第次課學(xué)時(shí)授課時(shí)間______教學(xué)主題棧和隊(duì)列隊(duì)列的特點(diǎn)，表示和實(shí)現(xiàn)；隊(duì)列的應(yīng)用與實(shí)現(xiàn)教學(xué)要求1、掌握隊(duì)列的邏輯結(jié)構(gòu)特性，隊(duì)列抽象數(shù)據(jù)類型的描述方法。2、掌握隊(duì)列的先進(jìn)后出特點(diǎn)。3、掌握隊(duì)列基本運(yùn)算在兩類存儲結(jié)構(gòu)下的實(shí)現(xiàn)算法。4、掌握隊(duì)列在實(shí)際求解問題中的應(yīng)用方法教學(xué)重點(diǎn)順序隊(duì)的基本運(yùn)算算法設(shè)計(jì)；鏈隊(duì)的基本運(yùn)算算法設(shè)計(jì)；利用隊(duì)列求解復(fù)雜的應(yīng)用問題。雙鏈表的查找、插入和刪除操作過程及其實(shí)現(xiàn)。教學(xué)難點(diǎn)順序隊(duì)和鏈隊(duì)的基本運(yùn)算算法設(shè)計(jì)；利用隊(duì)列求解復(fù)雜的應(yīng)用問題。教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、板書、上機(jī)實(shí)操講授要點(diǎn)1、隊(duì)列的邏輯結(jié)構(gòu)特性。2、隊(duì)列抽象數(shù)據(jù)類型的描述方法。3、順序隊(duì)的算法設(shè)計(jì)方法。4、鏈隊(duì)的算法設(shè)計(jì)方法。作業(yè)完成學(xué)習(xí)通上第三章作業(yè)中有關(guān)隊(duì)列的練習(xí)題。參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（首頁）第1頁教學(xué)內(nèi)容備注與后記3.3隊(duì)列1、隊(duì)列的定義隊(duì)列簡稱隊(duì)，它也是一種運(yùn)算受限的線性表。。特點(diǎn)：先進(jìn)先出。隊(duì)列的幾個(gè)概念：進(jìn)行插入的一端稱做隊(duì)尾（rear）。進(jìn)行刪除的一端稱做隊(duì)首或隊(duì)頭（front）。向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素。從隊(duì)列中刪除元素稱為出隊(duì)或離隊(duì)，元素出隊(duì)后，其后繼元素就成為隊(duì)首元素。2、隊(duì)列的基本運(yùn)算InitQueue(&q)：初始化隊(duì)列。構(gòu)造一個(gè)空隊(duì)列q。DestroyQueue(&q)：銷毀隊(duì)列。釋放隊(duì)列q占用的存儲空間。QueueEmpty(q)：判斷隊(duì)列是否為空。若隊(duì)列q為空，則返回真；否則返回假。enQueue(&q，e)：進(jìn)隊(duì)列。將元素e進(jìn)隊(duì)作為隊(duì)尾元素。deQueue(&q，&e)：出隊(duì)列。從隊(duì)列q中出隊(duì)一個(gè)元素，并將其值賦給e。3、隊(duì)列的存儲結(jié)構(gòu)順序存儲——順序隊(duì)鏈?zhǔn)酱鎯Α滉?duì)4、順序隊(duì)的基本運(yùn)算實(shí)現(xiàn)typedefstruct{ElemTypedata[MaxSize]；intfront，rear；//隊(duì)首和隊(duì)尾指針}SqQueue;順序隊(duì)的四要素：隊(duì)空條件：front=rear隊(duì)滿條件：rear=MaxSize－1元素e進(jìn)隊(duì)：rear++;data[rear]=e;元素e出隊(duì)：front++;e=data[front];順序隊(duì)實(shí)現(xiàn)隊(duì)列中的基本運(yùn)算。5、循環(huán)隊(duì)列的基本運(yùn)算實(shí)現(xiàn)把數(shù)組的前端和后端連接起來，形成一個(gè)環(huán)形的順序表，即把存儲隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，稱為環(huán)形隊(duì)列或循環(huán)隊(duì)列。rear=(rear+1)%MaxSizefront=(front+1)%MaxSize循環(huán)隊(duì)列的四要素：隊(duì)空條件：front=rear隊(duì)滿條件：(rear+1)%MaxSize=front進(jìn)隊(duì)e操作：rear=(rear+1)%MaxSize;將e放在rear處出隊(duì)操作：front=(front+1)%MaxSize;取出front處元素e;6、鏈隊(duì)的基本運(yùn)算實(shí)現(xiàn)typedefstruct{DataNode*front; //指向單鏈表隊(duì)頭結(jié)點(diǎn)DataNode*rear; //指向單鏈表隊(duì)尾結(jié)點(diǎn)}LinkQuNode;鏈隊(duì)的四要素：隊(duì)空條件：rear=NULL隊(duì)滿條件：不考慮進(jìn)隊(duì)e操作：將包含e的結(jié)點(diǎn)插入到單鏈表表尾出隊(duì)操作：刪除單鏈表首數(shù)據(jù)結(jié)點(diǎn)鏈隊(duì)實(shí)現(xiàn)隊(duì)列中的基本運(yùn)算。3.4隊(duì)列的應(yīng)用與實(shí)現(xiàn)求解報(bào)數(shù)問題設(shè)有n個(gè)人站成一排，從左向右的編號分別為1～n，現(xiàn)在從左往右報(bào)數(shù)“1，2，1，2，…”，數(shù)到“1”的人出列，數(shù)到“2”的立即站到隊(duì)伍的最右端。報(bào)數(shù)過程反復(fù)進(jìn)行，直到n個(gè)人都出列為止。要求給出他們的出列順序。例如，當(dāng)n=8時(shí)，初始序列為12345678則出列順序?yàn)?3572648算法思想：先將n個(gè)人的編號進(jìn)隊(duì)，然后反復(fù)執(zhí)行如下操作，直到隊(duì)列為空：出隊(duì)一個(gè)的元素，輸出其編號—報(bào)數(shù)為1的人出列。若隊(duì)列不空，則再出隊(duì)一個(gè)元素，并將剛出列的元素進(jìn)隊(duì)—報(bào)數(shù)為2的人站到隊(duì)伍的最右端即隊(duì)尾。教學(xué)總結(jié)：本章節(jié)主要介紹了隊(duì)列的特點(diǎn)，順序隊(duì)、鏈隊(duì)及循環(huán)隊(duì)列的存儲結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)。第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題串的基本概念，串的存儲結(jié)構(gòu)教學(xué)要求1、掌握串的邏輯結(jié)構(gòu)特性和串抽象數(shù)據(jù)類型的描述方法。2、掌握串的兩類存儲結(jié)構(gòu)設(shè)計(jì)方法以及各自的優(yōu)缺點(diǎn)。3、掌握順序串算法設(shè)計(jì)方法。4、掌握鏈串算法設(shè)計(jì)方法。。4、掌握棧在實(shí)際求解問題中的應(yīng)用方法。教學(xué)重點(diǎn)串的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)；順序串運(yùn)算算法設(shè)計(jì)；鏈串運(yùn)算算法設(shè)計(jì)。教學(xué)難點(diǎn)串的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)；順序串運(yùn)算算法設(shè)計(jì)；鏈串運(yùn)算算法設(shè)計(jì)。教學(xué)方法講授教學(xué)手段多媒體、板書講授要點(diǎn)1、串的概念。2、串抽象數(shù)據(jù)類型的描述方法。3、串的順序存儲結(jié)構(gòu)及順序串算法設(shè)計(jì)方法。4、串的鏈?zhǔn)酱鎯Y(jié)構(gòu)及鏈串算法設(shè)計(jì)方法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記4.1串1、串的定義串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列。串線性表關(guān)于串的幾個(gè)概念：串中所含字符的個(gè)數(shù)稱為該串的長度（或串長）。含零個(gè)字符的串稱為空串，用Ф表示。非空串：通常用“a1a2…an”表示。其中，雙引號不是串的內(nèi)容，起標(biāo)識作用，ai（1≤i≤n）代表一個(gè)字符。串相等：兩個(gè)串的長度相等并且各個(gè)對應(yīng)位置上的字符都相同時(shí)字串：一個(gè)串中任意個(gè)連續(xù)字符組成的子序列（含空串）稱為該串的子串主串：是指包含子串的串舉實(shí)例說明，加深學(xué)生對串的理解和認(rèn)識。4.2串的存儲結(jié)構(gòu)1、串的存儲結(jié)構(gòu)順序存儲——順序串鏈?zhǔn)酱鎯Α湸?、串的基本運(yùn)算StrAssign(&s，cstr)：將字符串常量cstr賦給串s，即生成其值等于cstr的串s。StrCopy(&s，t)：串復(fù)制。將串t復(fù)制給串s。StrEqual(s，t)：判串相等。若兩個(gè)串s與t相等則返回真；否則返回假。StrLength(s)：求串長。返回串s中字符個(gè)數(shù)。Concat(s，t)：串連接:返回由兩個(gè)串s和t連接在一起形成的新串。SubStr(s，i，j)：求子串。返回串s中從第i（1≤i≤n）個(gè)字符開始的、由連續(xù)j個(gè)字符組成的子串。InsStr(s1，i，s2)：插入。將串s2插入到串s1的第i（1≤i≤n+1）個(gè)字符中，即將s2的第一個(gè)字符作為s1的第i個(gè)字符，并返回產(chǎn)生的新串。DelStr(s，i，j)：刪除。從串s中刪去從第i（1≤i≤n）個(gè)字符開始的長度為j的子串，并返回產(chǎn)生的新串。RepStr(s，i，j，t)：替換。在串s中，將第i（1≤i≤n）個(gè)字符開始的j個(gè)字符構(gòu)成的子串用串t替換，并返回產(chǎn)生的新串。DispStr(s)：串輸出。輸出串s的所有元素值。3、順序串的基本操作實(shí)現(xiàn)非緊縮格式#defineMaxSize100typedefstruct{chardata[MaxSize];intlength;}SqString;例4-1。4、鏈串的基本操作實(shí)現(xiàn)typedefstructsnode{chardata;structsnode*next;}LinkStrNode;例4-3。教學(xué)總結(jié)：本章節(jié)給大家介紹了串的基本定義，串的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本操作的實(shí)現(xiàn)。

第次課學(xué)時(shí)授課時(shí)間__________教學(xué)主題串的模式匹配算法教學(xué)要求1、掌握串的模式匹配算法設(shè)計(jì)方法教學(xué)重點(diǎn)簡單模式匹配算法設(shè)計(jì)，KMP算法設(shè)計(jì)，KMP算法是如何提高串匹配效率的。教學(xué)難點(diǎn)KMP算法設(shè)計(jì)，KMP算法是如何提高串匹配效率的。教學(xué)方法講授+練習(xí)教學(xué)手段多媒體、上機(jī)操作講授要點(diǎn)1、串的模式匹配的概念。2、串的簡單模式匹配算法。3、KMP算法及其提高串匹配效率的特點(diǎn)。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（首頁）第1頁教學(xué)內(nèi)容備注與后記4.3串的模式匹配1、簡單匹配算法Brute-Force簡稱為BF算法，亦稱簡單匹配算法。采用窮舉的思路。BF算法思路：從s的第一個(gè)字符開始和t的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從s的第二個(gè)字符開始和t的第一個(gè)字符進(jìn)行比較，重復(fù)上述過程，直到t中的字符全部比較完畢，則說明匹配成功；如果s中的字符全部比較完，則說明匹配失敗。B－F算法實(shí)現(xiàn)及分析。2、KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，簡稱KMP算法。KMP算法思路：基于BF算法，采用空間換時(shí)間的方式，提取保存有利于匹配的信息。S串不回溯，模式串t就需要像右滑動一段距離，利用已經(jīng)得到的“部分匹配”的信息，將模式串t向右滑動盡可能遠(yuǎn)的一段距離(j=next[j])后，繼續(xù)進(jìn)行比較。KMP算法實(shí)現(xiàn)及分析。3、例題講解教學(xué)總結(jié)：本章節(jié)主要介紹了簡單模式匹配算法和KMP算法。第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題數(shù)組的基本概念，數(shù)組的存儲結(jié)構(gòu)教學(xué)要求1、掌握數(shù)組的邏輯結(jié)構(gòu)特性，數(shù)組抽象數(shù)據(jù)類型的描述方法。2、掌握數(shù)組的順序存儲結(jié)構(gòu)及其特點(diǎn)。3、掌握對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲。4、掌握棧在實(shí)際求解問題中的應(yīng)用方法。教學(xué)重點(diǎn)數(shù)組的順序存儲結(jié)構(gòu)及其特點(diǎn)；對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲方法。教學(xué)難點(diǎn)數(shù)組的順序存儲結(jié)構(gòu)及其特點(diǎn)；對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲方法。。教學(xué)方法講授+練習(xí)教學(xué)手段多媒體、上機(jī)實(shí)操講授要點(diǎn)1、數(shù)組的邏輯結(jié)構(gòu)特性。2、數(shù)組的順序存儲結(jié)構(gòu)及其特點(diǎn)。3、對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記5.1數(shù)組1、數(shù)組的定義數(shù)組是所有高級編程語言中都已實(shí)現(xiàn)的固有數(shù)據(jù)類型，因此凡學(xué)習(xí)過高級程序設(shè)計(jì)語言的讀者對數(shù)組都不陌生。但它和其它諸如整數(shù)、實(shí)數(shù)等原子類型不同，它是一種結(jié)構(gòu)類型。換句話說，"數(shù)組"是一種數(shù)據(jù)結(jié)構(gòu)。數(shù)組的類型定義

ADTArray{

數(shù)據(jù)對象：D＝{aj1,j2,...,ji,...jN|=ji0,...,bi-1,i=1,2,..,N,

稱N(>0)為數(shù)組的維數(shù)，bi為數(shù)組第i維的長度，

ji為數(shù)組元素的第i維下標(biāo)，aj1,...,jN∈ElemSet}

數(shù)據(jù)關(guān)系：R＝{R1,R2,...,RN}

Ri＝{<aj1,...ji,...jN,aj1,...,ji+1,...,jN>|

0≤jk≤bk-1,1≤k≤N且ki,

0≤ji≤bi-2,

aj,...,j,...,j,aj,...j+1,...,j∈D,i=2,...,N}

基本操作：

InitArray(&A,n,bound1,...,boundn)

操作結(jié)果：若維數(shù)n和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A。

DestroyArray(&A)

初始條件：數(shù)組A已經(jīng)存在。

操作結(jié)果：銷毀數(shù)組A。

Value(A,&e,index1,...,indexn)

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值。

操作結(jié)果：若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK。

Assign(&A,e,index1,...,indexn)

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值。

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給A中指定下標(biāo)的元素。

}ADTArray2、數(shù)組的存儲結(jié)構(gòu)由于數(shù)組類型不作插入和刪除的操作，因此只需要通過"順序映象"得到它的存儲結(jié)構(gòu)，即借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

通常有兩種映象方法：即"以行(序)為主(序)"的映象方法和"以列(序)為主(序)"的映象方法。

以圖示的二維數(shù)組為例，"以行為主"的存儲結(jié)構(gòu)是對二維數(shù)組進(jìn)行"按行切分"，即將數(shù)組中的數(shù)據(jù)元素"按行依次排放"在存儲器中；"以列為主"的存儲結(jié)構(gòu)是對二維數(shù)組進(jìn)行"按列切分"，即將數(shù)組中的數(shù)據(jù)元素"按列依次排放"在存儲器中。

假設(shè)二維數(shù)組R[m][n]中每個(gè)數(shù)據(jù)元素占L個(gè)存儲地址，并以LOC(i,j)表示下標(biāo)為(i,j)的數(shù)據(jù)元素的存儲地址，則該數(shù)組中任何一對下標(biāo)(i,j)對應(yīng)的數(shù)據(jù)元素在"以行為主"的順序映象中的存儲地址為：

LOC(i,j)=LOC(0,0)+(in+j)L

在"以列為主"的順序映象中的存儲地址為：

LOC(i,j)=LOC(0,0)+(jm+i)L

其中LOC(0,0)是二維數(shù)組中第一個(gè)數(shù)據(jù)元素（下標(biāo)為(0,0)）的存儲地址，稱為數(shù)組的"基地址"或"基址"。類似地，假設(shè)三維數(shù)組R[p][m][n]中每個(gè)數(shù)據(jù)元素占L個(gè)存儲地址，并以LOC(i,j,k)表示下標(biāo)為(i,j,k)的數(shù)據(jù)元素的存儲地址，則該數(shù)組中任何一對下標(biāo)(i,j,k)對應(yīng)的數(shù)據(jù)元素在"以行為主"的順序映象中的存儲地址為：

LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L

推廣到N維數(shù)組，則得到

LOC(j1,j2,...jn,)=LOC+(b2×...×bn×j1＋b3×...×bn×j2＋...＋bn×jn-1+jn)×L

=LOC(0,0,...,0)+()×L

可縮寫成

LOC(j1,j2,...jn,)=LOC(0,0,...,0)+

其中Cn=L，Ci-1=bi×Ci,1<i≤N。5.2矩陣的壓縮存儲結(jié)構(gòu)特殊矩陣的壓縮存儲方法

如果矩陣中值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱之謂"特殊矩陣"。大致有這樣三類特殊矩陣：

1.對稱矩陣：若n階方陣A中的元滿足特性

aij=aji1≤i,j≤n

則稱為n階對稱矩陣；

2.三角矩陣：若n階方陣中下(上)三角(不包括對角線)中的元均為常量c或0，則稱為上(下)三角矩陣；

3.對角矩陣：若n階方陣中的非零值元都集中在以主對角線為中心的(由k條對角線組成的)帶狀區(qū)域中，則稱為k對角矩陣。

若為對稱矩陣中的每一對值相同的元素分配一個(gè)存儲空間，則可將矩陣中n2個(gè)元壓縮存儲到n(n+1)/2個(gè)存儲空間中。

假設(shè)以一維數(shù)組sa[n(n+1)/2]壓縮存儲n階對稱方陣A，則一維數(shù)組中的數(shù)據(jù)元素和方陣中的元之間存在著下列一一對應(yīng)的關(guān)系：

對于任意給定一對行列號(i,j)，均可在sa中找到方陣的元aij，反之，對于所有的k=0,1,…,n(n+1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i,j)。

三角矩陣示例

對角矩陣示例

由于特殊矩陣中的非零值元素在矩陣中的分布有著一定的規(guī)律，則可將這些非零值元連續(xù)存儲在一個(gè)一維數(shù)組中。即矩陣中的任何一個(gè)元和它們在一維數(shù)組中的位置之間存在著某種"轉(zhuǎn)換關(guān)系"，并且這種轉(zhuǎn)換關(guān)系可以用數(shù)學(xué)公式表示之。顯然，對于下(上)三角矩陣和對角矩陣也可得到類似對應(yīng)關(guān)系。教學(xué)總結(jié)：本章節(jié)介紹了數(shù)組的基本定義，數(shù)組的順序存儲結(jié)構(gòu)特點(diǎn)，對稱矩陣、上三角矩陣、下三角矩陣和三對角矩陣的壓縮存儲，重點(diǎn)掌握數(shù)組下標(biāo)的轉(zhuǎn)換。

第次課學(xué)時(shí)授課時(shí)間__________教學(xué)主題稀疏矩陣教學(xué)要求1、掌握稀疏矩陣的特點(diǎn)。2、掌握稀疏矩陣的兩種壓縮存儲方法。教學(xué)重點(diǎn)稀疏矩陣的特點(diǎn)；稀疏矩陣的三元組表示及其基本運(yùn)算算法設(shè)計(jì)。教學(xué)難點(diǎn)稀疏矩陣的三元組表示及其基本運(yùn)算算法設(shè)計(jì)。教學(xué)方法講授教學(xué)手段多媒體、板書講授要點(diǎn)1、稀疏矩陣的特點(diǎn)。2、稀疏矩陣的三元組和十字鏈表存儲結(jié)構(gòu)。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（首頁）第1頁教學(xué)內(nèi)容備注與后記稀疏矩陣的存儲如果矩陣中只有少量的非零值元，并且這些非零值元在矩陣中的分布沒有一定規(guī)律，則稱為隨機(jī)稀疏矩陣，簡稱為稀疏矩陣。至于矩陣中究竟含多少個(gè)零值元才被稱為是稀疏矩陣，目前還沒有一個(gè)確切的定義，它只是一個(gè)憑人的直覺來了解的概念。假設(shè)在mn的矩陣中有t個(gè)非零值元，令，稱§為矩陣的稀疏因子，則通常認(rèn)定§≤0.05的矩陣為稀疏矩陣。如何存儲稀疏矩陣中的非零值元？

由于壓縮存儲的基本宗旨是只存放矩陣中的非零值元，則在存儲非零元的值的同時(shí)必須記下它在矩陣中的位置(i,j)，反之，一個(gè)三元組(i,j,aij)唯一確定了矩陣A中的一個(gè)非零值元,由此可以"其數(shù)據(jù)元素為上述三元組的線性表"表示稀疏矩陣，并且非零元在三元組線性表中是"以行為主"有序排列的。相應(yīng)于線性表的兩種存儲結(jié)構(gòu)可得到稀疏矩陣的不同壓縮存儲方法。例如表示矩陣

的三元組線性表為：

((1,3,9),(1,5,-7),(3,4,8),(4,1,5),(4,6,2),(5,2,16))元組順序表

稀疏矩陣的三元組順序表的結(jié)構(gòu)定義

constMAXTERMS=12500;//假設(shè)非零元個(gè)數(shù)的最大值為12500

typedefstruct{

inti,j;//該非零元的行號和列號

ElemTypee;//該非零元的值

}Triple;//三元組

typedefstruct{

Tripledata[MAXTERMS+1];//非零元三元組表，data[0]未用

introws,cols,terms;//矩陣的行數(shù)、列數(shù)和非零元的個(gè)數(shù)

}TSMatrix;//三元組順序表算法實(shí)現(xiàn)，將稀疏矩陣轉(zhuǎn)換為三元組#include<stdio.h>#include<malloc.h>voidmain(){//定義一個(gè)二維數(shù)組 inta[10][10]; inti,j; intk=0; //構(gòu)造一個(gè)測試二維數(shù)組 for(i=0;i<10;i++) for(j=i;j<10;j++){ a[j][i]=a[i][j]=k++; if(j==i){ a[i][j]=0; } }//打印二維數(shù)組 printf("原矩陣\n"); for(i=0;i<10;i++){for(j=0;j<10;j++) printf("%3d",a[i][j]); printf("\n"); } printf("\n");//特殊矩陣為一維數(shù)組 intn=10; n=n*(n+1)/2;//首尾相加乘以個(gè)數(shù)除以2 int*b=(int*)malloc(n*sizeof(int)); for(i=0;i<10;i++) for(j=0;j<10;j++) if(j>=i) b[(j+1)*j/2+i]=a[i][j]; printf("轉(zhuǎn)化后矩陣(二維打印)\n"); k=1; for(i=0;i<n;i++){ printf("%3d",b[i]); if(i+1==k*(k+1)/2){//也可根據(jù)0換行 k++; printf("\n"); }} printf("\n"); printf("轉(zhuǎn)化后矩陣(一維打印)\n"); for(i=0;i<n;i++) printf("%3d",b[i]); printf("\n\n"); //根據(jù)一維矩陣轉(zhuǎn)換為二維矩陣 printf("數(shù)據(jù)還原\n"); inttemp[10][10]; for(i=0;i<10;i++) for(j=0;j<10;j++) if(i<=j) temp[i][j]=b[j*(j+1)/2+i]; else temp[i][j]=b[i*(i+1)/2+j]; //打印轉(zhuǎn)化后的矩陣 for(i=0;i<10;i++){ for(j=0;j<10;j++) printf("%3d",temp[i][j]);printf("\n"); }}教學(xué)總結(jié)：本章節(jié)主要介紹了稀疏矩陣的特點(diǎn)以及兩種壓縮存儲方式。5.3廣義表一、教學(xué)目標(biāo)理解廣義表的定義、特點(diǎn)及基本術(shù)語；掌握廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（頭尾表示法、孩子兄弟表示法）的C語言實(shí)現(xiàn)；掌握廣義表的基本運(yùn)算（求長度、求深度、遍歷、查找元素）的算法設(shè)計(jì)與代碼實(shí)現(xiàn)；培養(yǎng)基于鏈?zhǔn)浇Y(jié)構(gòu)的編程思維和問題解決能力。二、教學(xué)重難點(diǎn)重點(diǎn)：廣義表的存儲結(jié)構(gòu)、求深度/長度的算法、遍歷算法；難點(diǎn)：廣義表深度的遞歸求解、復(fù)雜廣義表的遍歷邏輯。三、教學(xué)過程（一）廣義表的定義1.核心概念廣義表（GeneralizedList）簡稱GList，是線性表的推廣，定義為：廣義表是n（n≥0）個(gè)元素的有限序列，記作LS=(a1,a2,...,an)。其中：ai可以是單個(gè)元素（稱為原子，Atom），也可以是另一個(gè)廣義表（稱為子表，SubList）；n為廣義表的長度，n=0時(shí)稱為空表；廣義表的深度指表中括號的最大嵌套層數(shù)（原子深度為0，空表深度為1）。2.示例解析（幫助理解）廣義表表示 說明A=()空表，長度0，深度1B=(a,b)原子表，長度2，深度1（元素均為原子）C=(a,(b,c))混合表，長度2（a和子表(b,c)），深度2D=(A,B,C)子表嵌套，長度3（A/B/C均為廣義表），深度3（C的深度2+外層1）E=(a,E)遞歸表（循環(huán)表），長度2，深度∞（嵌套無終止）3.核心特點(diǎn)層次性：元素可以是原子或子表，具有嵌套結(jié)構(gòu)；共享性：多個(gè)廣義表可共享同一個(gè)子表（如D共享A/B/C）；遞歸性：廣義表可以包含自身（如E）。（二）廣義表的存儲結(jié)構(gòu)（C語言實(shí)現(xiàn)）廣義表的元素類型不統(tǒng)一（原子/子表），因此無法用順序存儲，只能用鏈?zhǔn)酱鎯Α３Ｓ脙煞N方式：1.頭尾表示法（重點(diǎn)）（1）存儲思想廣義表可拆分為“表頭（Head）”和“表尾（Tail）”：表頭：廣義表的第一個(gè)元素（可以是原子或子表）；表尾：除去表頭后剩余元素構(gòu)成的廣義表（一定是子表）。例如：C=(a,(b,c))，表頭是a（原子），表尾是((b,c))（子表）。（2）節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)需要兩種節(jié)點(diǎn)：原子節(jié)點(diǎn)、表節(jié)點(diǎn)：c運(yùn)行#include<stdio.h>#include<stdlib.h>#include<string.h>//節(jié)點(diǎn)類型枚舉typedefenum{ATOM,//原子節(jié)點(diǎn)LIST//表節(jié)點(diǎn)}NodeType;//廣義表節(jié)點(diǎn)結(jié)構(gòu)體（頭尾表示法）typedefstructGListNode{NodeTypetype;//節(jié)點(diǎn)類型：原子/表union{//共用體：原子值或表的頭尾指針charatom;//原子節(jié)點(diǎn)：存儲字符型原子（如'a'、'b'）struct{//表節(jié)點(diǎn)：存儲表頭、表尾指針structGListNode*head;structGListNode*tail;}list;}data;}GListNode,*GList;（3）廣義表的創(chuàng)建（字符串解析）輸入格式示例：(a,(b,c))，遞歸創(chuàng)建廣義表：c運(yùn)行//輔助函數(shù)：跳過字符串中的空格voidskipSpace(char**str){while(**str=='')(*str)++;}//遞歸創(chuàng)建廣義表（輸入字符串如："(a,(b,c))"）intCreateGList(GList*L,char**str){skipSpace(str);if(**str==')'){//空表（如遇到"()"中的')'）(*str)++;*L=NULL;return1;}if(**str=='('){//表節(jié)點(diǎn)開始(*str)++;*L=(GListNode*)malloc(sizeof(GListNode));if(!*L)return0;//內(nèi)存分配失敗(*L)->type=LIST;//遞歸創(chuàng)建表頭if(!CreateGList(&((*L)->data.list.head),str))return0;skipSpace(str);if(**str==','){//有表尾，遞歸創(chuàng)建(*str)++;if(!CreateGList(&((*L)->data.list.tail),str))return0;}else{//無表尾，表尾置空(*L)->data.list.tail=NULL;}skipSpace(str);if(**str==')')(*str)++;//跳過表結(jié)束符}elseif((**str>='a'&&**str<='z')||(**str>='A'&&**str<='Z')){//原子節(jié)點(diǎn)*L=(GListNode*)malloc(sizeof(GListNode));if(!*L)return0;(*L)->type=ATOM;(*L)->data.atom=**str;(*str)++;}else{return0;//非法字符}return1;}//封裝創(chuàng)建函數(shù)（對外接口）GListCreateGListFromStr(char*str){GListL=NULL;char*p=str;if(*p=='('){CreateGList(&L,&p);}returnL;}2.孩子兄弟表示法（拓展）（1）存儲思想將廣義表視為樹形結(jié)構(gòu)：每個(gè)節(jié)點(diǎn)有兩個(gè)指針：child（指向第一個(gè)子元素）、next（指向同一層的下一個(gè)兄弟元素）；原子節(jié)點(diǎn)無child指針。（2）節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)c運(yùn)行//廣義表節(jié)點(diǎn)結(jié)構(gòu)體（孩子兄弟表示法）typedefstructCSNode{NodeTypetype;//節(jié)點(diǎn)類型：原子/表union{charatom;structCSNode*child;//表節(jié)點(diǎn)的第一個(gè)子元素}data;structCSNode*next;//指向兄弟節(jié)點(diǎn)}CSNode,*CSGList;（注：創(chuàng)建/運(yùn)算邏輯類似頭尾表示法，核心是“孩子+兄弟”的遍歷思路，本節(jié)重點(diǎn)講頭尾表示法）（三）廣義表的基本運(yùn)算（C語言實(shí)現(xiàn)）基于“頭尾表示法”實(shí)現(xiàn)核心運(yùn)算，所有運(yùn)算均基于遞歸（適配廣義表的嵌套特性）。1.求廣義表的長度定義：廣義表第一層元素的個(gè)數(shù)（空表長度為0）；思路：表尾是“除去表頭后的剩余元素”，因此長度=1+表尾的長度（遞歸）。c運(yùn)行//求廣義表的長度（第一層元素個(gè)數(shù)）intGListLength(GListL){if(L==NULL)return0;//空表長度0if(L->type==ATOM)return1;//單個(gè)原子（特殊情況：如廣義表是單個(gè)原子a）//表節(jié)點(diǎn)：長度=1+表尾的長度return1+GListLength(L->data.list.tail);}2.求廣義表的深度定義：括號的最大嵌套層數(shù)（空表深度1，原子深度0）；思路：深度=max(表頭深度，表尾深度)+1（表節(jié)點(diǎn)）；原子深度為0。c運(yùn)行//求廣義表的深度（括號最大嵌套層數(shù)）intGListDepth(GListL){if(L==NULL)return1;//空表深度1if(L->type==ATOM)return0;//原子深度0//表節(jié)點(diǎn)：遞歸求表頭、表尾的深度intdepth_head=GListDepth(L->data.list.head);intdepth_tail=GListDepth(L->data.list.tail);//深度=表頭/表尾深度的最大值+1return(depth_head>depth_tail?depth_head:depth_tail)+1;}3.遍歷廣義表（輸出）思路：遞歸遍歷，原子直接輸出，表節(jié)點(diǎn)輸出括號+遞歸遍歷表頭/表尾。c運(yùn)行//遍歷并輸出廣義表voidTraverseGList(GListL){if(L==NULL){//空表printf("()");return;}if(L->type==ATOM){//原子節(jié)點(diǎn)printf("%c",L->data.atom);return;}//表節(jié)點(diǎn)：輸出左括號+遍歷表頭+遍歷表尾printf("(");TraverseGList(L->data.list.head);//遍歷表頭GListNode*p=L->data.list.tail;while(p!=NULL){//遍歷表尾（多個(gè)元素用逗號分隔）printf(",");TraverseGList(p->data.list.head);//表尾的表頭是下一個(gè)元素p=p->data.list.tail;}printf(")");}4.查找元素是否存在思路：遞歸查找表頭，若不存在則查找表尾，原子節(jié)點(diǎn)直接比較值。c運(yùn)行//查找廣義表中是否存在指定原子元素intFindGListElem(GListL,charelem){if(L==NULL)return0;//空表，不存在if(L->type==ATOM){//原子節(jié)點(diǎn)，直接比較return(L->data.atom==elem)?1:0;}//表節(jié)點(diǎn)：遞歸查找表頭+表尾returnFindGListElem(L->data.list.head,elem)||FindGListElem(L->data.list.tail,elem);}5.釋放廣義表內(nèi)存（避免內(nèi)存泄漏）c運(yùn)行//釋放廣義表所有節(jié)點(diǎn)的內(nèi)存voidDestroyGList(GList*L){if(*L==NULL)return;if((*L)->type==LIST){//表節(jié)點(diǎn)：先釋放表頭、表尾DestroyGList(&((*L)->data.list.head));DestroyGList(&((*L)->data.list.tail));}free(*L);//釋放當(dāng)前節(jié)點(diǎn)*L=NULL;}（四）完整測試代碼c運(yùn)行intmain(){//測試用例：廣義表C=(a,(b,c))char*glist_str="(a,(b,c))";GListL=CreateGListFromStr(glist_str);//1.輸出廣義表printf("廣義表內(nèi)容：");TraverseGList(L);printf("\n");//2.求長度printf("廣義表長度：%d\n",GListLength(L));//輸出2//3.求深度printf("廣義表深度：%d\n",GListDepth(L));//輸出2//4.查找元素charelem='b';if(FindGListElem(L,elem)){printf("元素'%c'存在于廣義表中\(zhòng)n",elem);}else{printf("元素'%c'不存在于廣義表中\(zhòng)n",elem);}//5.釋放內(nèi)存DestroyGList(&L);return0;}測試輸出plaintext廣義表內(nèi)容：(a,(b,c))廣義表長度：2廣義表深度：2元素'b'存在于廣義表中四、課堂小結(jié)總結(jié)廣義表定義：線性表的推廣，元素可是原子或子表，具有層次性、共享性、遞歸性；長度是第一層元素個(gè)數(shù)，深度是括號最大嵌套層數(shù)。存儲結(jié)構(gòu)：僅能鏈?zhǔn)酱鎯?，重點(diǎn)掌握“頭尾表示法”（原子節(jié)點(diǎn)/表節(jié)點(diǎn)，共用體存儲不同數(shù)據(jù)）。核心運(yùn)算：基于遞歸實(shí)現(xiàn)，求長度（1+表尾長度）、求深度（max(表頭/表尾深度)+1）、遍歷/查找均需適配嵌套特性。第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題樹的基本定義和性質(zhì)；樹的遍歷方法和存儲結(jié)構(gòu)；教學(xué)要求1、掌握樹的定義及其邏輯結(jié)構(gòu)特性，數(shù)組抽象數(shù)據(jù)類型的描述方法。2、掌握樹的邏輯結(jié)構(gòu)表示方法和樹的性質(zhì)。3、掌握樹的遍歷方法和樹的存儲結(jié)構(gòu)。4、掌握棧在實(shí)際求解問題中的應(yīng)用方法。教學(xué)重點(diǎn)樹的遞歸特點(diǎn)；樹的性質(zhì)、樹的遍歷和樹的存儲結(jié)構(gòu)教學(xué)難點(diǎn)樹的性質(zhì)、樹的遍歷和樹的存儲結(jié)構(gòu)。教學(xué)方法講授教學(xué)手段多媒體、板書講授要點(diǎn)1、樹的邏輯結(jié)構(gòu)特性及樹抽象數(shù)據(jù)類型的描述。2、樹的邏輯表示方法及樹的基本術(shù)語。3、樹的性質(zhì)。4、樹的遍歷方法。5、樹的存儲結(jié)構(gòu)。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記7.1樹的概念樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)，正如在課前思考題所看到的，樹型結(jié)構(gòu)廣泛用于描述家族譜系以及其它社會組織結(jié)構(gòu)。在計(jì)算機(jī)領(lǐng)域中，如編譯程序中的語法結(jié)構(gòu)和數(shù)據(jù)庫中的信息組織也都需要借用樹來描述。本章將討論樹和二叉樹兩種樹型結(jié)構(gòu)。1、樹的定義樹：T={D，R}。D是包含n個(gè)結(jié)點(diǎn)的有限集合（n≥0）。當(dāng)n=0時(shí)為空樹，否則關(guān)系R滿足以下條件:有且僅有一個(gè)結(jié)點(diǎn)d0∈D，它對于關(guān)系R來說沒有前驅(qū)結(jié)點(diǎn)，結(jié)點(diǎn)d0稱作樹的根結(jié)點(diǎn)。除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。D中每個(gè)結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。2、樹的邏輯表示屬性表示法文氏圖表示法凹入表示法括號表示法3、樹的基本術(shù)語結(jié)點(diǎn)的度與樹的度：樹中一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹中各結(jié)點(diǎn)的度的最大值稱為樹的度，通常將度為m的樹稱為m次樹或者m叉樹。分支結(jié)點(diǎn)與葉結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)或葉結(jié)點(diǎn)（或葉子結(jié)點(diǎn)）。度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)，又叫分支結(jié)點(diǎn)。度為1的結(jié)點(diǎn)稱為單分支結(jié)點(diǎn)；度為2的結(jié)點(diǎn)稱為雙分支結(jié)點(diǎn)，依此類推。路徑與路徑長度：兩個(gè)結(jié)點(diǎn)di和dj的結(jié)點(diǎn)序列（di，di1，di2，…，dj）稱為路徑。其中<dx，dy>是分支。路徑長度等于路徑所通過的結(jié)點(diǎn)數(shù)目減1（即路徑上分支數(shù)目或邊的數(shù)目）。孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)和兄弟結(jié)點(diǎn)：在一棵樹中，每個(gè)結(jié)點(diǎn)的后繼，被稱作該結(jié)點(diǎn)的孩子結(jié)點(diǎn)（或子女結(jié)點(diǎn)）。相應(yīng)地，該結(jié)點(diǎn)被稱作孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)（或父母結(jié)點(diǎn)）。具有同一雙親的孩子結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。子孫結(jié)點(diǎn)和祖先結(jié)點(diǎn)：在一棵樹中，一個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。從根結(jié)點(diǎn)到達(dá)一個(gè)結(jié)點(diǎn)的路徑上經(jīng)過的所有結(jié)點(diǎn)被稱作該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。結(jié)點(diǎn)的層次和樹的高度：樹中的每個(gè)結(jié)點(diǎn)都處在一個(gè)層次上。結(jié)點(diǎn)的層次從樹根開始定義，根結(jié)點(diǎn)為第1層，它的孩子結(jié)點(diǎn)為第2層，以此類推，一個(gè)結(jié)點(diǎn)所在的層次為其雙親結(jié)點(diǎn)所在的層次加1。樹中結(jié)點(diǎn)的最大層次稱為樹的高度（或樹的深度）。有序樹和無序樹：若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨意變換的，則稱為有序樹，否則稱為無序樹。有序樹和無序樹：若樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨意變換的，則稱為有序樹，否則稱為無序樹。4、樹的性質(zhì)性質(zhì)1樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)之和加1。性質(zhì)2度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)3高度為h的m次樹至多有個(gè)結(jié)點(diǎn)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的m次樹的最小高度為logm(n(m-1)+1)。5、樹的基本運(yùn)算樹的運(yùn)算主要分為三大類：查找滿足某種特定關(guān)系的結(jié)點(diǎn)，如查找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)等。插入或刪除某個(gè)結(jié)點(diǎn)，如在樹的當(dāng)前結(jié)點(diǎn)上插入一個(gè)新結(jié)點(diǎn)或刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)等。遍歷樹中每個(gè)結(jié)點(diǎn)。6、樹的遍歷樹的遍歷運(yùn)算是指按某種方式訪問樹中的每一個(gè)結(jié)點(diǎn)且每一個(gè)結(jié)點(diǎn)只被訪問一次。主要遍歷方法：先根遍歷，若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。后跟遍歷，若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。層次遍歷，若樹不空，則自上而下、自左至右訪問樹中每個(gè)結(jié)點(diǎn)。7、樹的存儲結(jié)構(gòu)雙親存儲typedefstruct{ElemTypedata; //結(jié)點(diǎn)的值intparent; //指向雙親的位置}PTree[MaxSize];孩子鏈存儲結(jié)構(gòu)typedefstructnode{ElemTypedata; //結(jié)點(diǎn)的值structnode*sons[MaxSons]; //指向孩子結(jié)點(diǎn)}TSonNode;孩子兄弟鏈存儲typedefstructtnode{ElemTypedata; //結(jié)點(diǎn)的值structtnode*hp; //指向兄弟structtnode*vp; //指向孩子結(jié)點(diǎn)}TSBNode;教學(xué)總結(jié)：本章節(jié)介紹了樹的基本定義，樹的邏輯結(jié)構(gòu)，樹的性質(zhì)以及樹的存儲結(jié)構(gòu)。

第次課學(xué)時(shí)授課時(shí)間__________教學(xué)主題二叉樹教學(xué)要求1、掌握二叉樹的定義及其性質(zhì)。2、掌握二叉樹與樹、森林之間的轉(zhuǎn)換。教學(xué)重點(diǎn)二叉樹與樹、森林之間的轉(zhuǎn)換方法；二叉樹的遞歸特點(diǎn)、二叉樹的性質(zhì)和二叉樹的兩種存儲結(jié)構(gòu)。教學(xué)難點(diǎn)二叉樹與樹、森林之間的轉(zhuǎn)換方法；二叉樹的遞歸特點(diǎn)、二叉樹的性質(zhì)和二叉樹的兩種存儲結(jié)構(gòu)。5、完全二叉樹和滿二叉樹的特點(diǎn)。教學(xué)方法講授教學(xué)手段多媒體、板書講授要點(diǎn)1、二叉樹的遞歸定義和二叉樹的性質(zhì)。2、完全二叉樹和滿二叉樹的特點(diǎn)。3、二叉樹與樹、森林之間的轉(zhuǎn)換方法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記7.2二叉樹的概念和性質(zhì)二叉樹的定義二叉樹是有限的結(jié)點(diǎn)集合。這個(gè)集合或者是空(稱為空二叉樹)?；蛘哂梢粋€(gè)根結(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。二叉樹的結(jié)構(gòu)特點(diǎn)：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，即結(jié)點(diǎn)的度不大于2子樹有左右之分，子樹的次序(位置)不能顛倒即使結(jié)點(diǎn)只有一顆子樹，也有左右之分兩種特殊的二叉樹滿二叉樹:若二叉樹中所有的分支結(jié)點(diǎn)的度數(shù)都為2，且葉子結(jié)點(diǎn)都在同一層次上，則稱這類二叉樹為滿二叉樹。完全二叉樹:假如一棵包含n個(gè)結(jié)點(diǎn)的二叉樹中每個(gè)結(jié)點(diǎn)都可以和滿二叉樹中編號為1至n的結(jié)點(diǎn)一、一對應(yīng)，則稱這類二叉樹為完全二叉樹。3、二叉樹的性質(zhì)性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。即：n0=n2+1。性質(zhì)2非空二叉樹上第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)（h≥1）。性質(zhì)4完全二叉樹性質(zhì)（含n個(gè)結(jié)點(diǎn)）：n1=0或者n1=1。n1可由n的奇偶性確定。若i≤n/2，則編號為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉結(jié)點(diǎn)。4、二叉樹與樹、森林之間的轉(zhuǎn)換森林、樹轉(zhuǎn)換成二叉樹二叉樹還原為森林、樹教學(xué)總結(jié)：本章節(jié)主要介紹了二叉樹的定義，二叉樹的性質(zhì)，兩種特殊的二叉樹以及二叉樹與樹、森林之間的轉(zhuǎn)換。第次課學(xué)時(shí)授課時(shí)間___________教學(xué)主題二叉樹的兩種存儲結(jié)構(gòu)；二叉樹的基本運(yùn)算算法設(shè)計(jì)教學(xué)要求1、掌握二叉樹的兩種存儲結(jié)構(gòu)。2、掌握二叉樹的基本運(yùn)算算法設(shè)計(jì)。教學(xué)重點(diǎn)二叉樹的兩種存儲結(jié)構(gòu)；二叉樹的基本運(yùn)算算法教學(xué)難點(diǎn)二叉樹的存儲結(jié)構(gòu)及其特點(diǎn)；二叉樹的基本運(yùn)算算法教學(xué)方法講授、練習(xí)教學(xué)手段多媒體、上機(jī)實(shí)操講授要點(diǎn)1、二叉樹的兩種存儲結(jié)構(gòu)及其特點(diǎn)。2、二叉樹的基本運(yùn)算算法設(shè)計(jì)方法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學(xué)出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，嚴(yán)蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學(xué)內(nèi)容備注與后記二叉樹的存儲結(jié)構(gòu)1、二叉樹的順序存儲結(jié)構(gòu)用數(shù)組實(shí)現(xiàn)特點(diǎn)：對于完全二叉樹來說，其順序存儲是十分合適的。在順序存儲結(jié)構(gòu)中，找一個(gè)結(jié)點(diǎn)的雙親和孩子都很容易。2、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)用二叉鏈表實(shí)現(xiàn)特點(diǎn)：除了指針外，二叉鏈比較節(jié)省存儲空間。在二叉鏈中，找一個(gè)結(jié)點(diǎn)的孩子很容易，但找其雙親不方便。二叉樹的基本運(yùn)算及其實(shí)現(xiàn)1、二叉樹的基本運(yùn)算創(chuàng)建二叉樹CreateBTree(*b，*str)：根據(jù)二叉樹括號表示法字符串str生成對應(yīng)的二叉鏈存儲結(jié)構(gòu)b。銷毀二叉鏈存儲結(jié)構(gòu)DestroyBTree(*b)：銷毀二叉鏈b并釋放空間。查找結(jié)點(diǎn)FindNode(*b，x)：在二叉樹b中尋找data域值為x的結(jié)點(diǎn)，并返回指向該結(jié)點(diǎn)的指針。找孩子結(jié)點(diǎn)LchildNode(p)和RchildNode(p)：分別求二叉樹中結(jié)點(diǎn)p的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)