安徽大學本科教學課程教案課程代碼：ZJ36007課程名稱：數據結構授課專業(yè)：計算機科學與技術授課教師：鄒海職稱/學位：副教授/博士開課時間：二○一六至二○一七學年第二學期第1次課程教學方案周次1課時數2教學章節(jié)第一章、緒論1.1什么是數據結構1.2基本概念和術語1.3抽象數據類型的表示與實現1.4算法和算法分析目標要求（1）掌握數據、數據元素、數據對象、數據結構、存儲結構和數據類型等基本概念，特別是邏輯結構與存儲結構之間的關系；（2）了解抽象數據類型的定義、表示和實現方法；（3）理解算法的基本要素及含義；（4）掌握算法的時間復雜度和空間復雜度分析。重點難點（1）數據結構包含的邏輯結構、存儲結構和運算三方面的相互關系；（2）各種邏輯結構即線性結構、樹形結構和圖形結構之間的差別；（3）數據結構和數據類型的差別和聯系；（4）算法的時間復雜度和空間復雜度分析。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）數據的邏輯結構和存儲結構有什么不同？（2）數據類型和抽象數據類型有什么不同？（3）算法和程序有什么不同？（4）為什么要進行算法的時間復雜度分析？板書設計1、什么是數據結構指數據以及數據元素相互之間的聯系?？梢钥醋魇窍嗷ブg存在著某種特定關系的數據元素的集合。也可看成是帶結構的數據元素的集合。邏輯結構的類型：線性結構、樹型結構、圖狀結構、集合2、基本概念與術語1）數據；2）數據元素；3）數據對象3、抽象數據類型的表示與實現1）數據對象2）數據關系3）基本操作4、算法和算法分析（1）算法：對特定問題求解步驟的一種描述。（2）算法的5個重要特征：有窮性，確定性，可執(zhí)行性，輸入，輸出。（3）算法設計的目標：1）正確性；2）可讀性；3）健壯性；4）效率與低存儲量需求

第1次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課從計算機科學課程體系設置情況，導入數據結構這門課程所處的地位：承上啟下。先修課程：計算機基礎、高級語言程序設計、離散數學。后期課程：操作系統(tǒng)、編譯原理、數據庫原理、軟件工程等。數據結構課程的主要研究內容。學習和講授的方法：演譯法和歸納法。講授內容1、什么是數據結構指數據以及數據元素相互之間的聯系?？梢钥醋魇窍嗷ブg存在著某種特定關系的數據元素的集合。也可看成是帶結構的數據元素的集合。邏輯結構的類型：線性結構、樹型結構、圖狀結構、集合2、基本概念與術語1）數據；2）數據元素；3）數據對象4）邏輯結構與存儲結構的區(qū)別與聯系3、抽象數據類型的表示與實現1）數據對象2）數據關系3）基本操作4、算法和算法分析歸納總結1、數據結構的定義，數據結構包含的邏輯結構、存儲結構和運算三方面的相互關系。2、各種邏輯結構即線性結構、樹形結構和圖形結構之間的差別。3、數據結構和數據類型的差別和聯系。4、算法的定義及其特性。5、算法的時間復雜度和空間復雜度分析。第2次課程教學方案周次1課時數2教學章節(jié)第二章、線性表2.1線性表的基本概念2.2線性表的抽象類型定義2.3線性表的順序表示與實現目標要求（1）掌握線性表的邏輯特征；（2）掌握順序表的類型定義；（3）熟練掌握順序表基本操作的實現算法及其時間復雜度分析。重點難點（1）順序表的類型定義；（2）線性表（邏輯結構）到順序表（存儲結構）的具體映射方式；（3）順序表基本操作的實現算法及其時間復雜度分析。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）順序存儲結構下，線性表中數據關系是如何表示的？（2）設計一個算法，將一個順序存儲的線性表實現逆轉置？板書設計1、線性表的基本概念線性表：n（n>=0）個具有相同類型的數據元素所組成的有限序列。線性表的特征：1）除了第一個元素之外，每個元素有唯一的前驅元素；2）除了最后一個元素之外，每個元素有唯一的后繼元素。2、線性表的抽象類型定義1）數據對象：2）數據關系：3）基本操作：3、線性表的順序表示與實現（順序表）（1）順序表的類型定義與表示（2）順序表的主要特征：連續(xù)的存儲單元；邏輯相鄰則物理相鄰。（3）基本操作的實現1）初始化操作：2）插入操作：3）刪除操作：

第2次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課由前一講的數據的邏輯結構分類：線性結構、樹型結構、圖狀結構、集合。導入本章所要講述的主要內容：線性結構首先討論線性表的主要邏輯特征。其次，引導學生思考，這種邏輯結構在計算機中如何來表示、存儲及其操作？講授內容1、線性表的基本概念線性表：n（n>=0）個具有相同類型的數據元素所組成的有限序列。線性表的特征：1）除了第一個元素之外，每個元素有唯一的前驅元素；2）除了最后一個元素之外，每個元素有唯一的后繼元素。2、線性表的抽象類型定義1）數據對象：2）數據關系：3）基本操作：3、線性表的順序表示與實現（順序表）（1）順序表的類型定義（2）順序表的主要特征：連續(xù)的存儲單元；邏輯相鄰則物理相鄰。（3）基本操作的實現：1）初始化操作；2）插入操作；3）刪除操作等。歸納總結1、順序表的主要特征：采用一組地址連續(xù)的存儲單元依次的存儲從表頭到表尾的元素，邏輯上相鄰的兩個元素其物理上也相鄰。2、順序表的類型定義：1）*elem：一組地址連續(xù)的存儲單元；2）length：線性表的長度；3）listsize;線性表當前分配的存儲容量3、順序表中其插入和刪除操作，主要借助數據元素的移動來實現。對于插入操作，最好情況下，當i=n+1時，移動次數為0，最壞情況下，當i=1時，需要移動n次，平均移動次數為n/2。對于刪除操作，最好情況下，當i=n時，移動次數為0，最壞情況下，當i=1時，需要移動n-1次，平均移動次數為（n-1）/2。

第3次課程教學方案周次2課時數2教學章節(jié)第二章、線性表2.4線性表的鏈式表示與實現2.4.1線性表的鏈式存儲2.4.2單鏈表目標要求（1）掌握單鏈表的結點結構（2）掌握頭結點、頭指針和首元結點的概念；（3）單鏈表中數據關系的表示方法；（4）單鏈表的特點；（5）掌握線性表鏈式存儲結構下基本操作的實現。重點難點（1）單鏈表的類型定義；（2）頭指針與頭結點的概念；（3）單鏈表存儲結構下，線性表基本操作的實現。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）鏈表與順序表的區(qū)別？（2）采用帶頭結點的單鏈表與不帶頭結點的單鏈表相比，有哪些優(yōu)點？（3）設計算法，將單鏈表的尾結點修改為首元結點？板書設計1、線性表的鏈式存儲結點是構成鏈表的基本單位。結點的結構：數據域和指針域。其中數據域存儲元素本身的信息，指針域用來存儲數據元素之間的邏輯關系。存儲密度=結點數據本身占用的空間/結點占用的空間總量由于每個結點帶有指針域，導致存儲密度降低。2、單鏈表（1）什么是單鏈表由于順序表中的每個元素至多只有一個前驅元素和一個后繼元素，即數據元素之間是一對一的邏輯關系，所以當進行鏈式存儲時，一種最簡單也最常用的方法是:在每個節(jié)點中除包含有數據域外，只設置一個指針域，用以指向其后繼節(jié)點，這樣構成的鏈接表稱為線性單向鏈接表，簡稱單鏈表。（2）頭結點與頭指針：對于一個單鏈表頭結點不是必需的，但頭指針是必需的。帶頭結點的單鏈表與不帶頭結點的單鏈表，一般情況下，指帶頭結點。（3）單鏈表的類型定義（4）單鏈表的基本操作實現

第3次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課針對上一講的線性表的順序存儲，引導學生總結順序存儲的優(yōu)點：結構簡單，易于理解；方便隨機訪問表中的每個元素；不需要再為表示元素間的邏輯關系而增加額外的存儲空間等。指出順序表的缺點：（1）順序表的存儲空間不易擴充；（2）順序表易造成存儲空間的利用率低，且不利于分散的存儲單元的使用；（3）順序表在插入和刪除操作時，需要大量的移動數據元素。針對順序表的上述缺點，導入線性表的另外一種存儲結構—鏈式存儲結構。講授內容1、線性表的鏈式存儲采用隨機的存儲單元，并利用指針域來存儲數據元素之間的邏輯關系。注意與順序表的主要區(qū)別。2、單鏈表（1）什么是單鏈表由于順序表中的每個元素至多只有一個前驅元素和一個后繼元素，即數據元素之間是一對一的邏輯關系，所以當進行鏈式存儲時，一種最簡單也最常用的方法是:在每個節(jié)點中除包含有數據域外，只設置一個指針域，用以指向其后繼節(jié)點，這樣構成的鏈接表稱為線性單向鏈接表，簡稱單鏈表。（2）頭結點與頭指針：對于一個單鏈表頭結點不是必需的，但頭指針是必需的。帶頭結點的單鏈表與不帶頭結點的單鏈表，一般情況下，指帶頭結點。（3）單鏈表的類型定義（4）單鏈表的基本操作實現歸納總結1、與順序表不同，鏈式存儲結構采用隨機的存儲單元來存儲線性表的元素，需要額外的存儲空間（指針域）來表示數據元素間的線性關系；2、單鏈表的頭指針非常重要，它是訪問單鏈表的入口，用來標識該鏈表。3、利用單鏈表來存儲線性表時，在進行插入和刪除操作時不再需要移動數據元素，而只要調整指針。在插入操作時，需要修改2個指針；在刪除操作時，需要修改1個指針。4、單鏈表的特點：在單鏈表中，由于每個節(jié)點只包含有一個指向后繼節(jié)點的指針，所以當訪問過一個節(jié)點后，只能接著訪問它的后繼節(jié)點，而無法訪問它的前驅節(jié)點。5、根據單鏈表的特點，往往在單鏈表操作時，一般將工作指針設置在待處理結點的前驅結點上。

第4次課程教學方案周次2課時數2教學章節(jié)2.4線性表的鏈式表示與實現2.4.3雙向鏈表目標要求（1）掌握雙向鏈表結點的結構；（2）掌握雙向鏈表的特點；（3）掌握雙向鏈表與單鏈表的區(qū)別與聯系；（4）掌握雙向鏈表基本操作的實現。重點難點（1）雙向鏈表的結構及其特征；（2）雙向鏈表與單向鏈表的異同及其適用條件；（3）雙向鏈表的類型定義；（4）雙向鏈表基本操作的實現。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）什么情況下使用雙向鏈表？（2）雙向鏈表與單鏈表相比有什么不同？（3）雙向鏈表的主要優(yōu)缺點是什么？板書設計1、什么是雙向鏈表在單鏈表中，當訪問過一個節(jié)點后，只能接著訪問它的后繼節(jié)點，而無法訪問它的前驅節(jié)點。為了解決上述問題：在每個節(jié)點中除包含有數值域外,設置有兩個指針域，分別用以指向其前驅節(jié)點和后繼節(jié)點，這樣構成的鏈接表稱之為線性雙向鏈接表，簡稱雙向鏈表。帶頭結點的雙向鏈表示意圖2、雙向鏈表的特點：1）在雙鏈表中，由于每個節(jié)點既包含有一個指向后繼節(jié)點的指針，又包含有一個指向前驅節(jié)點的指針，所以當訪問過一個節(jié)點后，既可以依次向后訪問每一個節(jié)點，也可以依次向前訪問每一個節(jié)點。2）求任意結點p的后繼操作的時間復雜度為O(1)，前驅操作操作的時間復雜度也為O(1)。3、雙向鏈表的類型定義typedefstructDNode｛//聲明雙鏈表節(jié)點類型 ElemTypedata;structDNode*prior;//指向前驅節(jié)點 structDNode*next;//指向后繼節(jié)點}DLinkList;4、雙向鏈表的基本操作

第4次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課簡要回顧上一講單向鏈表的主要特征：在單鏈表中，由于每個節(jié)點只包含有一個指向后繼節(jié)點的指針，所以當訪問過一個節(jié)點后，只能接著訪問它的后繼節(jié)點，而無法訪問它的前驅節(jié)點。在某些情況下，既需要進行求后繼操作，又要進行求前驅操作。為了便于訪問過一個節(jié)點后，既可以依次向后訪問每一個節(jié)點，也可以依次向前訪問每一個節(jié)點。需要修改鏈表中結點的結構，引入雙向鏈表的定義。講授內容1、什么是雙向鏈表在每個節(jié)點中除包含有數值域外，,設置有兩個指針域，分別用以指向其前驅節(jié)點和后繼節(jié)點，這樣構成的鏈接表稱之為線性雙向鏈接表，簡稱雙向鏈表。雙向鏈表與單向鏈表的區(qū)別與聯系？2、雙向鏈表的特點1）在雙鏈表中，由于每個節(jié)點既包含有一個指向后繼節(jié)點的指針，又包含有一個指向前驅節(jié)點的指針，所以當訪問過一個節(jié)點后，既可以依次向后訪問每一個節(jié)點，也可以依次向前訪問每一個節(jié)點。2）求任意結點p的后繼操作的時間復雜度為O(1)，前驅操作操作的時間復雜度也為O(1)。3、雙向鏈表的類型定義4、雙向鏈表的基本操作1）初始化操作2）插入操作3）刪除操作歸納總結1、雙向鏈表的結點結構包括一個數據域和兩個指針域，其中一個指向前驅結點，另一個指向后繼結點。2、雙向鏈表特征：由于每個節(jié)點既包含有一個指向后繼節(jié)點的指針，又包含有一個指向前驅節(jié)點的指針，所以當訪問過一個節(jié)點后，既可以依次向后訪問每一個節(jié)點，也可以依次向前訪問每一個節(jié)點。3、雙向鏈表的插入操作需要修改4個指針域，刪除操作需要修改2個指針域。

第5次課程教學方案周次3課時數2教學章節(jié)2.4線性表的鏈式表示與實現2.4.4循環(huán)鏈表目標要求（1）掌握循環(huán)鏈表的類型定義；（2）掌握循環(huán)鏈表為空的條件；（3）深刻理解循環(huán)鏈表的特征及與非循環(huán)鏈表之間的差異。重點難點（1）循環(huán)鏈表的結構及其特征；（2）循環(huán)鏈表與非循環(huán)鏈表的差異；（3）循環(huán)鏈鏈表的類型定義；（4）循環(huán)鏈表基本操作的實現。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）循環(huán)鏈表的主要特點是什么？（2）循環(huán)鏈表判空的條件是什么？（3）循環(huán)鏈表的操作與非循環(huán)的單鏈表在操作上相比，主要有什么不同？板書設計1、什么是循環(huán)鏈表循環(huán)鏈表是一種首尾相邊的鏈表。鏈表的最后一個結點的指針域指向頭指針，則使得鏈表的頭尾相邊，構成循環(huán)鏈表。2、循環(huán)鏈表特點在單鏈表中，只有單向指針（指向其直接后繼），從某個結點出發(fā)只能查找其后的那些結點。如果要查找它前面的結點，就必須從表頭結點開始搜索。而利用循環(huán)鏈表，在不增加存儲空間的同時，可以實現從表中任意結點出發(fā)，訪問表中其他所有結點，不必借助頭指針。3、循環(huán)鏈表的類型定義在循環(huán)鏈表中，結點的存儲結構與單鏈表中完全相同。因此，其類型定義與鏈表相同。typedefstructDLode｛//聲明雙鏈表節(jié)點類型 ElemTypedata;structLNode*prior;//指向前驅節(jié)點 structLNode*next;//指向后繼節(jié)點}CLinkList;4、循環(huán)鏈表的操作在循環(huán)鏈表中，結點的存儲結構與單鏈表中完全相同。其基本操作的實現也與單鏈表基本一致，其差別在于，判斷當前結點是否為表中最后結點的條件，由原來的看后繼指針是否為空，改為看其后繼指針是否等于頭指針。

第5次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課在單鏈表中，只有單向指針（指向其直接后繼），從某個結點出發(fā)只能查找其后的那些結點。如果要查找它前面的結點，就必須從表頭結點開始搜索。在單鏈表中，由于最后一個結點沒有后繼，因此，最后一個結點的指針域為空。在不增加存儲空間的同時，如果將其指向頭指針，則使得鏈表的頭尾相邊，構成循環(huán)鏈表。在循環(huán)鏈表中可以實現從表中任意結點出發(fā)，訪問表中其他所有結點，不必借助頭指針。講授內容1、什么是循環(huán)鏈表2、循環(huán)鏈表特點3、循環(huán)鏈表的類型定義4、循環(huán)鏈表的操作5、循環(huán)鏈表的應用歸納總結1、循環(huán)鏈表的特點：從表中任何一個結點開始都可以遍歷整個鏈表，而對于單鏈表只能從頭結點開始才能遍歷鏈表中的所有結點。2、循環(huán)鏈表的類型定義：在循環(huán)鏈表中，結點的存儲結構與單鏈表中完全相同。因此，其類型定義與鏈表相同，且不需要增加額外的存儲空間。3、循環(huán)鏈表的操作：其基本操作的實現也與單鏈表基本一致，其差別在于，判斷當前結點是否為表中最后結點的條件，由原來的看后繼指針是否為空，改為看其后繼指針是否等于頭指針。

第6次課程教學方案周次3課時數2教學章節(jié)2.4線性表的鏈式表示與實現2.4.5鏈表的應用目標要求（1）通過實例講解和討論，使學生掌握鏈表操作的技巧；（2）通過實例講解和討論，提高學生的算法設計技能；（3）算法的時間復雜度和空間復雜度分析。重點難點（1）如何讓學生掌握鏈表操作的一般步驟和使用技巧；（2）如何提高學生算法設計的技能；（4）如何讓學生掌握算法的時間復雜度和空間復雜度分析。教學方式√課堂講授□小組活動□實驗演示√難點答疑□提問√作業(yè)講評□實踐教學□考試測驗□其他活動習題課媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）設有一帶頭結點的單鏈表，編程將鏈表顛倒過來，要求不用另外的數組或結點完成。（2）給定(已生成)一個帶表頭結點的單鏈表，設head為頭指針，結點的結構為(data,next),data為整型元素，next為指針，試寫出算法:按遞增次序輸出單鏈表中各結點的數據元素，并釋放結點所占的存儲空間。(要求：不允許使用數組作輔助空間)。（3）設計算法將兩個有序的單鏈表合并為一個有序的單鏈表。板書設計實例1、設計一個算法采用頭插法構造一個帶頭結點的單鏈表。實例2、設計一個算法采用尾插法構造一個帶頭結點的單鏈表。實例3、已知一個帶有表頭節(jié)點的單鏈表，節(jié)點結構為：（data,link）假設該單鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的節(jié)點（k為正整數）。若查找成功，算法輸出該節(jié)點的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設計思想；（2）描述算法的詳細實現步驟；（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C語言實現），關鍵之處請給出簡要注釋。實例4、假定采用帶頭節(jié)點的單鏈表保存單詞，當兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間，例如，“l(fā)oading”和“being”，如下圖所示。設str1和str2分別指向兩個單詞所在單鏈表的頭節(jié)點，鏈表節(jié)點結構為：(data，next)。請設計一個時間上盡可能高效的算法，找出由str1和str2所指向兩個鏈表共同后綴的起始位置（如圖中字符i所在節(jié)點的位置p）。要求：（1）給出算法的基本設計思想。（2）根據設計思想，采用C或C++或JAVA語言描述算法，關鍵為之處給出注釋。（3）說明你所設計算法的時間復雜度。以上4個實例的算法，均采用PPT演示。

第6次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課1、本章小結。（1）理解線性表的邏輯結構特性。（2）深入掌握線性表的兩種存儲方法，即順序表和鏈表。體會這兩種存儲結構之間的差異。（3）重點掌握順序表和鏈表上各種基本運算的實現。（4）綜合運用線性表這種數據結構解決一些復雜的實際問題。2、通過實例講解線性表的應用，體會算法設計的規(guī)范及設計技巧。講授內容實例1、設計一個算法采用頭插法構造一個帶頭結點的單鏈表。實例2、設計一個算法采用尾插法構造一個帶頭結點的單鏈表。實例3、已知一個帶有表頭節(jié)點的單鏈表，節(jié)點結構為：（data,link）假設該單鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的節(jié)點（k為正整數）。若查找成功，算法輸出該節(jié)點的data域的值，并返回1；否則，只返回0。實例4、假定采用帶頭節(jié)點的單鏈表保存單詞，當兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間，例如，“l(fā)oading”和“being”，如下圖所示。設str1和str2分別指向兩個單詞所在單鏈表的頭節(jié)點，鏈表節(jié)點結構為：(data，next)。請設計一個時間上盡可能高效的算法，找出由str1和str2所指向兩個鏈表共同后綴的起始位置（如圖中字符i所在節(jié)點的位置p）。歸納總結本章小結：（1）理解線性表的邏輯結構特性。（2）深入掌握線性表的兩種存儲方法，即順序表和鏈表。體會這兩種存儲結構之間的差異。（3）重點掌握順序表和鏈表上各種基本運算的實現。（4）注意在單鏈表操作時，工作指針一般應設在待處理結點的前驅結點上。（5）綜合運用線性表這種數據結構解決一些復雜的實際問題。第7次課程教學方案周次4課時數2教學章節(jié)第三章：棧和隊列----棧目標要求棧的定義棧的存儲棧的基本操作的實現重點難點棧的基本操作的實現教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源√文字教材√電子教案□錄像材料□錄音材料□直播課堂□CAI課件□IP課件□其他資源：課后作業(yè)簡述現實生活中運用棧的實例，請至少找出3種實例。板書設計1.棧的基本概念棧(Stack)、棧頂(Top)、棧底(Bottom)、空棧。2.棧的抽象數據類型定義ADTStack{數據對象：D={ai|ai∈ElemSet,i=1,2,…,n，n≥0}數據關系：R={<ai-1,ai>|ai-1，ai∈D,i=2,3,…,n}，且約定：an端為棧頂，a1端為棧底基本操作：初始化、進棧、出棧、取棧頂元素等（pp.45）}ADTStack3.棧的動態(tài)順序存儲表示采用動態(tài)一維數組來存儲棧。所謂動態(tài)，指的是棧的大小可以根據需要增加?！粲胋ase表示棧底指針，棧底固定不變；棧頂則隨著進棧和退棧操作而變化。用top(稱為棧頂指針)指示當前棧頂?！粲胻op=base作為?？盏臉擞?。用top指向棧頂數組中的下一個存儲位置?！艚Y點進棧：首先將數據元素保存到棧頂(top所指的當前位置)，然后執(zhí)行top加1，使top指向棧頂的下一個存儲位置;◆結點出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲位置，然后將棧頂元素取出。4.動態(tài)順序棧的類型定義typedefstruct{SElemType*base;/*棧不存在時值為NULL*/SElemType*top;/*棧頂指針*/intstacksize;/*當前已分配空間，以元素為單位*/}SqStack;5.動態(tài)順序棧的基本操作和實現棧的初始化獲取棧頂元素壓棧(元素進棧)彈棧(元素出棧)6.棧的鏈式存儲表示簡述第7次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課通過棧在實際問題中的應用，引入學習棧的意義。講授內容1.棧的基本概念2.棧的抽象數據類型定義3.棧的動態(tài)順序存儲表示4.動態(tài)順序棧的類型定義5.動態(tài)順序棧的基本操作和實現6.棧的鏈式存儲表示簡述歸納總結總結棧的基本定義；棧的adt；棧的存儲結構；針對不同存儲結構，棧的基本操作的實現。第8次課程教學方案周次4課時數2教學章節(jié)第三章：棧和隊列----棧的應用目標要求應用棧實現數制轉換、括號匹配；利用棧理解遞歸。重點難點棧與遞歸的實現教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源√文字教材√電子教案□錄像材料□錄音材料□直播課堂□CAI課件□IP課件□其他資源：課后作業(yè)請給出求N！的非遞歸算法。板書設計1.數制轉換十進制整數N向其它進制數d(二、八、十六)的轉換是計算機實現計算的基本問題。轉換法則：該轉換法則對應于一個簡單算法原理:n=(ndivd)*d+nmodd//n是待轉換的十進制數，d=2，8,16。其中：div為整除運算,mod為求余運算采用靜態(tài)順序棧方式實現voidconversion(intn,intd)/*將十進制整數N轉換為d(2或8)進制數*/{SqStackS;S=Init_Stack();while(n>0){k=n%d;push(S,k);n=n/d;}/*求出所有的余數，進棧*/while(S.top!=0)/*棧不空時出棧，輸出*/{pop(S,e);printf(“%1d”,*e);}}2.括號匹配問題在文字處理軟件或編譯程序設計時，常常需要檢查一個字符串或一個表達式中的括號是否相匹配?匹配思想：從左至右掃描一個字符串(或表達式)，則每個右括號將與最近遇到的那個左括號相匹配。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個右括號時，就將它與棧頂的左括號(如果存在)相匹配，同時從棧頂刪除該左括號。算法思想：設置一個棧，當讀到左括號時，左括號進棧。當讀到右括號時，則從棧中彈出一個元素，與讀到的左括號進行匹配，若匹配成功，繼續(xù)讀入；否則匹配失敗，返回FLASE。#defineTRUE0#defineFLASE-1SqStackS;S=Init_Stack();/*堆棧初始化*/intMatch_Brackets(){charch,x;scanf(“%c”,&ch);while(asc(ch)!=13){//VT:垂直制表符if((ch==‘(’)||(ch==‘[’))push(S,ch);elseif(ch==‘]’){x=pop(S);if(x!=‘[’){printf(“‘[’括號不匹配”);returnFLASE;}}elseif(ch==‘)’){x=pop(S);if(x!=‘(’){printf(“’(’括號不匹配”);returnFLASE;}}}if(S.top!=0){printf(“括號數量不匹配!”);returnFLASE;}elsereturnTRUE;}3.棧與遞歸的實現棧的另一個重要應用是在程序設計語言中實現遞歸調用。遞歸調用：一個函數(或過程)直接或間接地調用自己本身，簡稱遞歸(Recursive)。遞歸是程序設計中的一個強有力的工具。因為遞歸函數結構清晰，程序易讀，正確性很容易得到證明。為了使遞歸調用不至于無終止地進行下去，實際上有效的遞歸調用函數(或過程)應包括兩部分：遞推規(guī)則(方法)；終止條件。Hanoi問題：voidhanoi(intn,charx,chary,charz)//算法3.5//將塔座x上按直徑由小到大且至上而下編號為1至n的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。//搬動操作move(x,n,z)可定義為：(c是初值為0的全局變量，對搬動計數)printf("%i.Movedisk%ifrom%cto%c\n",++c,n,x,z);1{2if(n==1)3move(x,1,z);//將編號為１的圓盤從x移到z4else{5hanoi(n-1,x,z,y);6move(x,n,z);//將編號為n的圓盤從x移到z7hanoi(n-1,y,x,z);//將y上編號為１至n-1的圓盤移到z,x作輔助塔8}9}

第8次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課回顧棧的基本定義和存儲結構，引入棧在實際問題中的應用。講授內容1.數制轉換2.括號匹配問題3.棧與遞歸的實現歸納總結數字轉換問題中，棧是如何應用的；棧在括號匹配問題的所扮演的角色；遞歸程序是如何借助棧來實現的。第9次課程教學方案周次5課時數2教學章節(jié)第三章：棧和隊列----隊列目標要求隊列及其基本概念；隊列的存儲結構及其實現重點難點循環(huán)隊列教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源√文字教材√電子教案□錄像材料□錄音材料□直播課堂□CAI課件□IP課件□其他資源：課后作業(yè)請給出循環(huán)隊列所涉及操作的C語言的代碼實現。板書設計1.隊列及其基本概念隊列(Queue)、隊首(front)、隊尾(rear)2.隊列的抽象數據類型定義ADTQueue{數據對象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}數據關系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}約定a1端為隊首，an端為隊尾?；静僮鳎簆p.59}ADTQueue3.隊列的鏈式表示和實現隊列的鏈式存儲表示:隊列的鏈式存儲結構簡稱為鏈隊列，它是限制僅在表頭進行；刪除操作和表尾進行插入操作的單鏈表。需要兩類不同的結點：數據元素結點，隊列的隊首指針和隊；尾指針的結點。數據元素結點類型定義：typedefstructQnode{QElemTypedata;structQnode*next;}QNode,*QueuePtr;指針結點類型定義：typedefstructlink_queue{QueuePtrfront;QueuePtrrear;}LinkQueue;鏈隊列的基本操作的實現：鏈隊列的初始化；鏈隊列的入隊操作；鏈隊列的出隊操作；鏈隊列的撤消。4.隊列的順序表示和實現利用一組連續(xù)的存儲單元(一維數組)依次存放從隊首到隊尾的各個元素，稱為順序隊列。對于隊列，和順序棧相類似，也有動態(tài)和靜態(tài)之分。本部分介紹的是靜態(tài)順序隊列，其類型定義如下：#defineMAX_QUEUE_SIZE100typedefstructqueue{ElemTypeQueue_array[MAX_QUEUE_SIZE];intfront;intrear;}SqQueue;設立一個隊首指針front，一個隊尾指針rear，分別指向隊首和隊尾元素.隊滿：rear=MAX_QUEUE_SIZE-1。順序隊列中存在“假溢出”現象。因為在入隊和出隊操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際元素個數可能遠遠小于數組大小，但可能由于隊尾巳不能做入隊操作。該現象稱為假溢出。設隊列大小為5=MAX_QUEUE_SIZE，即rear和front的變化范圍為0~MAX_QUEUE_SIZE-1（4）為充分利用向量空間，克服上述“假溢出”現象的方法是：將為隊列分配的向量空間看成為一個首尾相接的圓環(huán)，并稱這種隊列為循環(huán)隊列(CircularQueue)。在循環(huán)隊列中進行出隊、入隊操作時，隊首、隊尾指針仍要加1，朝前移動。只不過當隊首、隊尾指針指向向量上界(MAX_QUEUE_SIZE-1)時，其加1操作的結果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：if(i==MAX_QUEUE_SIZE-1)i=0;elsei++;其中：i代表隊首指針(front)或隊尾指針(rear)用模運算可簡化為：i=(i+1)%MAX_QUEUE_SIZE;循環(huán)隊列的基本操作循環(huán)隊列的初始化；入隊操作；出隊操作。

第9次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課介紹隊列在實際生活及編程中的應用，引入學習隊列的意義。講授內容1.隊列及其基本概念2.隊列的抽象數據類型定義3.隊列的鏈式表示和實現4.隊列的順序表示和實現歸納總結隊列的基本定義；隊列的兩種不同的存儲結構；循環(huán)隊列。

第10次課程教學方案周次5課時數2教學章節(jié)第四章串—串的定義及基本操作目標要求串的定義及基本操作串的存儲重點難點串的存儲教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源√文字教材√電子教案□錄像材料□錄音材料□直播課堂□CAI課件□IP課件□其他資源：課后作業(yè)請解釋OFFICE辦公軟件中WORD文字編輯器中所用到的串的操作。板書設計1.串的基本概念串(字符串)、串值、串長、空串、空格串(空白串)、子串(substring)、子串的序號。2.串的抽象數據類型定義ADTString{數據對象：D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}數據關系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}基本操作：pp.71}3.串的存儲表示和實現串是一種特殊的線性表，其存儲表示和線性表類似，但又不完全相同。串的存儲方式取決于將要對串所進行的操作。串在計算機中有3種表示方式：定長順序存儲表示：將串定義成字符數組，利用串名可以直接訪問串值。用這種表示方式，串的存儲空間在編譯時確定，其大小不能改變。堆分配存儲方式：仍然用一組地址連續(xù)的存儲單元來依次存儲串中的字符序列，但串的存儲空間是在程序運行時根據串的實際長度動態(tài)分配的。塊鏈存儲方式：是一種鏈式存儲結構表示。4.串的定長順序存儲表示及基本操作的實現這種存儲結構又稱為串的順序存儲結構。是用一組連續(xù)的存儲單元來存放串中的字符序列。所謂定長順序存儲結構，是直接使用定長的字符數組來定義，數組的上界預先確定。定長順序存儲結構定義為：#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//總共256個單元（0~255），可以存放的字符數為255，0號單元存放串的長度基本操作有：串的聯結操作；求子串操作；

第10次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課介紹串在實際生活及編程中的應用，引入學習串的意義。講授內容1.串的基本概念2.串的抽象數據類型定義3.串的存儲表示和實現4.串的定長順序存儲表示及基本操作的實現歸納總結串的基本定義；串的抽象數據類型定義；串的存儲結構及其基本操作的實現。

第11次課程教學方案周次6課時數2教學章節(jié)第四章串—模式匹配目標要求熟悉理解KMP算法重點難點KMP算法教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源√文字教材√電子教案□錄像材料□錄音材料□直播課堂□CAI課件□IP課件□其他資源：課后作業(yè)請用C語言編程實現KMP算法。板書設計串的定長順序存儲結構定義為：#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//總共256個單元（0~255），可以存放的字符數為255，0號單元存放串的長度1.樸素的模式匹配算法采用定長順序存儲結構，可以寫出不依賴于其他串操作的匹配算法：intIndex(SStringS,SStringT,intpos){//算法4.5：定長順序存儲//返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數值為0。//其中，T非空，1≤pos≤StrLength(S)。inti=pos;intj=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后繼字符else{//指針后退到原先主串i的位置是：i-j+1i=i-j+2;//原先主串i的位置的下一個位置為：i-j+2j=1;}}if(j>T[0])//每次S中的第i個字符和T中的第j個字符，比較相等后均+1；//故如果在S中找到和T相等的子串，則S和T在比較了最后一個相等的字符//后，均+1。此時j=T[0]+1(即存在子串的條件：j>T[0]))。returni-T[0];//由于i也+1，與T相等的子串在S中的位置:i-T[0]elsereturn0;}//Index具體模擬過程如下：此處假設pos=1該算法簡單，易于理解。在一些場合的應用里，如文字處理中的文本編輯，其效率較高。該算法的時間復雜度為O(n*m)，其中n、m分別是主串和模式串的長度。通常情況下，實際運行過程中，該算法的執(zhí)行時間近似于O(n+m)。理解該算法的關鍵點：每次匹配不成功時，都要將i退回到主串原先位置的下一個位置；將j退回到模式串的第1個位置。2.改進的模式匹配算法—KMP該改進算法是由D.E.Knuth，J.H.Morris和V.R.Pratt提出來的，簡稱為KMP算法。其改進在于：每當一趟匹配過程出現字符不相等時，主串指示器不用回溯，而是利用已經得到的“部分匹配”結果，將模式串的指示器向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。設主串S為：‘s1s2s3……sn’,模式串T為‘p1p2p3……pm’。為了實現改進算法，需要解決如下問題：當匹配過程中產生“失配”（即si≠pj）時，模式“向右滑動”可行的距離有多遠。換句話說，當主串的第i個字符與模式的第j個字符“失配”（即比較不相等）時，主串的第i個字符（i指針不回溯）應與模式中的哪個字符再比較?由以上分析可得KMP算法：(1)當匹配過程中產生失配時，指針i不變，指針j退回到next[j]所指示的位置上重新進行比較；(2)并且，當指針j退至0時，指針i和j同時加1。即若主串中的第i個字符和模式的第1個字符不相等，應從主串的第i+1個字符和模式的第1個字符重新進行匹配。intIndex_KMP(SStringS,SStringT,intpos){//T非空，1≤pos≤StrLength(S)。//利用模式串T的next函數求T在主串S中第pos個字符之后的位置的KMP算法。i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i;++j;}//繼續(xù)比較后繼字符elsej=next[j];//模式串向右移動}if(j>T[0])returni-T[0];//匹配成功elsereturn0;}//Index_KMP算法4.6,算法4.6是在模式串各個位置的next已知的情況下才能進行。故如何高效地求出next值呢？

第11次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課模式匹配(模范匹配)：子串在主串中的定位稱為模式匹配或串匹配(字符串匹配)。其中：子串稱為模式串。模式匹配成功：是指在主串S中能夠找到模式串T，否則，稱模式串T在主串S中不存在。模式匹配的應用在非常廣泛。例如，在文本編輯程序中，我們經常要查找某一特定單詞在文本中出現的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應性能。講授內容1.樸素的模式匹配算法2.改進的模式匹配算法—KMP歸納總結next的自動化求解：next[1]=0;若next[j]=k;則next[j+1]:若:pj=pk,則next[j+1]=next[j]+1否則:next[j+1]=next[k]+1

第12次課程教學方案周次6課時數2教學章節(jié)第五章、數組與廣義表5.1數組的定義5.2數組的順序表示和實現目標要求1.了解數組的兩種存儲表示方法。2.掌握數組在以行為主序的存儲結構中的地址計算方法。重點難點1.多維數組和廣義表的邏輯結構特征：它們是復雜的非線性結構。一個數據元素可能有多個直接前趨和多個直接后繼。2.多維數組的兩種順序存儲方式：行優(yōu)先順序和列優(yōu)先順序。這兩種存儲方式下的地址計算方法。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)(1)C中二維數組floata[5][4]的起始地址為2000，且每個數組元素長度為32位（即4個字節(jié)），求數組元素a[3][2]的內存地址。（2）數據A[1..8,-2..6,0..6]以行為主序存儲，設第一個元素的首地址是78，每個元素的長度為4個字節(jié)，試求元素A[4,2,3]的存儲首地址。板書設計5.1數組的定義5.1.1數組的定義數組的特點是每個數據元素可以又是一個線性表結構。數組定義：若線性表中的數據元素為非結構的簡單元素，則稱為一維數組，即為向量；若一維數組中的數據元素又是一維數組結構，則稱為二維數組；依次類推，若二維數組中的元素又是一個一維數組結構，則稱作三維數組二維數組可以看成是這樣一個定長線性表：它的每個數據元素也是一個定長的線性表。5.1.2數組的基本操作數組結構一般在創(chuàng)建時就確定了組成該結構的行向量數目和列向量數目，因此，在數組結構中不存在插入、刪除元素的操作。給定一組下標，修改該位置元素的內容Assign(A,item,index1,index2)給定一組下標，返回該位置的元素內容Value(A,item,index1,index2)5.2數組的順序表示和實現數組一般采用順序存儲結構。從理論上講，數組結構也可以使用兩種存儲結構，即順序存儲結構和鏈式存儲結構。一般的數組結構不使用鏈式存儲結構。數組的存儲表示：組成數組結構的元素可以是多維的，但存儲數據元素的內存單元地址是一維的，因此，在存儲數組結構之前，需要解決將多維關系映射到一維關系的問題。對于數組，一旦規(guī)定了它的維數和各維的長度，便可為它分配存儲空間。反之，只要給出一組下標便可求得相應數組元素的存儲位置。在C語言中數組的存儲采用以行序為主序的存儲結構。假設每個數據元素占L個存儲單元，則上述二維數組A中任一元素aij的存儲位置可由下式確定：LOC(i,j)=LOC(0,0)+(n*i+j)*L

第12次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課前面幾章中，討論的線性表中的元素主要為簡單數據類型。當線性表中的元素又為一個線性表時，如何處理？導入新課：線性表的推廣：數組和廣義表。講授內容5.1數組的定義5.1.1數組的定義5.1.2數組的基本操作5.2數組的順序表示和實現歸納總結（1）理解數組和一般線性表之間的差異。（2）重點掌握數組的順序存儲結構和元素地址計算方法。對一個已知以行序為主序的計算機系統(tǒng)中,當二維數組第一個數據元素a1,1的存儲地址LOC(a1,1)和每個數據元素所占用的存儲單元k確定后,則該二維數組中任一數據元素ai,j的存儲地址可由下式確定：LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k其中n為列數。同理可推出在以列序為主序的計算機系統(tǒng)中有：LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k其中m為行數。

第13次課程教學方案周次7課時數2教學章節(jié)第五章數組和廣義表5.3特殊矩陣的壓縮存儲5.4稀疏矩陣的壓縮存儲目標要求（1）掌握各種特殊矩陣如對稱矩陣、上、下三角矩陣和對角矩陣的壓縮存儲方法；（2）掌握稀疏矩陣的各種存儲結構以及基本運算實現算法。重點難點（1）幾種特殊矩陣的特征及其壓縮存儲地址對應關系。（2）稀疏矩陣的三元組存儲表示方法；（3）稀疏矩陣的壓縮存儲及以及矩陣轉置運算的實現算法。。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）為什么特殊矩陣可以采用壓縮存儲？（2）對于一個m╳m的對稱，若采用壓縮存儲，則需要多少個存儲單元？（3）已知b對角矩陣（aij）m*n，以行為主序將b對角線上的非零元存儲在一維數組中，每個數據元素占L個存儲單元，存儲基地址為S，請用i，j表示出aij的存儲位置。板書設計5.3矩陣的壓縮存儲5.3.1特殊矩陣1.對稱矩陣:對稱矩陣的特點是aij=aji2.下（上）三角矩陣特點是以主對角線為界的上（下）半部分是一固定值，下（上）半部分元素值沒有任何規(guī)律。3.對角矩陣:特點是所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。5.3.2特殊矩陣壓縮方法（1）對稱矩陣在對稱矩陣中有n(n-1)/2個元素可以通過其他獲得。壓縮方法是將二維關系映射成一維關系，并存儲其中必要的n(n+1)/2個（主對角線和下三角）元素，這些元素的存儲順序以行為主序。（2）下（上）三角矩陣下三角矩陣的壓縮存儲與上面講述的對稱矩陣的壓縮存儲一樣，只是將上三角部分的常量值存儲在0單元，下三角和主對角上的元素從1號單元開始存放。（3）對角矩陣對于對角矩陣，壓縮存儲的主要思路是只存儲非零元素。這些非零元素按以行為主序的順序，從下標為1的位置開始依次存放在一維數組中，而0位置存放數值0。5.4稀疏矩陣的壓縮存儲若一個m×n的矩陣含有t個非零元素，且t遠遠小于m*n，則我們將這個矩陣稱為稀疏矩陣。(1)稀疏矩陣的壓縮存儲方法——三元組表示法。矩陣中的每個元素都是由行序號和列序號唯一確定的。因此，我們需要用三項內容表示稀疏矩陣中的每個非零元素，即形式為：(i,j,value)其中，i表示行序號，j表示列序號，value表示非零元素的值，通常將它稱為三元。(2)矩陣的轉置：兩種轉置實現算法。

第13次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課在大量的工程應用中，涉及到矩陣及其運算。對于特殊矩陣，在計算機中如何來進行存儲？根據矩陣的特殊性，能否采用壓縮存儲？如何對特殊矩陣進行壓縮存儲？對矩陣的運算又會帶來哪些影響？講授內容5.3矩陣的壓縮存儲5.3.1特殊矩陣1.對稱矩陣:對稱矩陣的特點是aij=aji2.下（上）三角矩陣3.對角矩陣:特點是所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。5.3.2特殊矩陣壓縮方法（1）對稱矩陣（2）下（上）三角矩陣（3）對角矩陣5.4稀疏矩陣的壓縮存儲(1)稀疏矩陣的壓縮存儲方法——三元組表示法。(2)矩陣的轉置：兩種轉置實現算法。歸納總結（1）各種特殊矩陣如對稱矩陣、上、下三角矩陣和對角矩陣的壓縮存儲方法；（2）稀疏矩陣的各種存儲結構（三元組表示方法）以及基本運算（稀疏矩陣的轉置運算）實現算法。

第14次課程教學方案周次7課時數2教學章節(jié)第五章數組和廣義表5.5廣義表的定義5.6廣度表的存儲結構目標要求（1）掌握廣義表的定義和廣義表的鏈式存儲結構；（2）掌握廣義表的基本運算，包括創(chuàng)建廣義表、輸出廣義表、求廣義表的長度和深度。重點難點（1）廣義表的定義和廣義表的鏈式存儲結構；（2）掌握廣義表的二種重要運算，取頭和取尾操作。（3）能畫出廣義表的圖形表示法。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)（1）假設采用以下兩種結點的鏈表作為廣義表的存儲結構，表結點：（tag=1,hp,tp），元素結點：(tag=0,data)。請畫了下列廣義表的存儲結構圖，并求出它的深度和長度。（（），（（（）），（（（）））））。（2）GetHead(GetTail(GetHead(((a,b,c),(d,e)))))。板書設計5.5廣義表1.廣義表的定義廣義表是線性表的推廣的概念。廣義表一般記作：LS=(a1,a2,…,an)其中LS為廣義表的名稱，n是長度。在線性表的定義中，ai只限于是單個元素，而在廣義表的定義中，ai可是單個元素，也可廣義表，分別稱為LS的原子和子表。當廣義表非空時，第一個元素稱為LS的表頭，稱其余元素組成的表為LS的表尾。2.廣義表的特點（1）廣義表的元素可以是子表，而子表的元素還可以是子表。廣義表是一個多層次的結構。（2）廣義表可以其他廣義表所共享，其可以通過子表的名稱來引用。（3）廣義表可以是一個遞歸的表，即廣義表也可以是其本身的一個子表。（4）任何一個非空的廣義表其表頭可能是原子，也可能是子表，而其表尾必定為子表。5.6廣義表的存儲結構(1)廣義表的鏈式存儲結構由于廣義表中的元素可具有不同的結構，因此難以采用順序存儲結構表示，而通常采用鏈式存儲結構，每個元素可用一個結點表示。(2)結點結構=1\*GB3①表結點 =2\*GB3②原子結點 (3)類型定義

第14次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課復習舊課：簡要的回顧解特殊矩陣的壓縮存儲和稀疏矩陣的壓縮及矩陣的轉置運算。討論的線性表中的元素主要為簡單數據類型。當線性表中的元素又為一個線性表時，如何處理？導入新課：線性表的推廣：廣義表。廣義表在計算機中如何表示與存儲？講授內容5.5廣義表1.廣義表的定義2.廣義表的特點（1）廣義表的元素可以是子表，而子表的元素還可以是子表。廣義表是一個多層次的結構。（2）廣義表可以其他廣義表所共享，其可以通過子表的名稱來引用。（3）廣義表可以是一個遞歸的表，即廣義表也可以是其本身的一個子表。（4）任何一個非空的廣義表其表頭可能是原子，也可能是子表，而其表尾必定為子表。5.6廣義表的存儲結構(1)廣義表的鏈式存儲結構(2)結點結構(3)類型定義歸納總結本章小結：（1）理解數組和一般線性表之間的差異。（2）重點掌握數組的順序存儲結構和元素地址計算方法。（3）掌握各種特殊矩陣如對稱矩陣、上、下三角矩陣和對角矩陣的壓縮存儲方法。（4）掌握稀疏矩陣的各種存儲結構以及基本運算實現算法。（5）掌握廣義表的定義和廣義表的鏈式存儲結構。（6）掌握廣義表的基本運算,包括創(chuàng)建廣義表、輸出廣義表、求廣義表的長度和深度。第15次課程教學方案周次8課時數2教學章節(jié)第六章樹和二叉樹6.1樹的定義和基本術語6.2.1目標要求（1）掌握樹的定義和基本術語；（2）掌握二叉樹的定義和性質。重點難點（1）二叉樹的性質教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)數據結構習題集6.1，6.2，6.3，6.5板書設計1.樹的概念樹是一個有n個節(jié)點的有限集合。在任意一棵非空樹中：有且僅有一個根節(jié)點；其余節(jié)點可以分為若干個互不相交的有限集合；每個集合本身也是一棵樹。（畫出幾個圖，判斷是否是樹）樹的特點：連通：各個節(jié)點之間均可以沿著邊互達；無環(huán)：從任何一個節(jié)點出發(fā)，沿著樹的邊最多經過其它節(jié)點一次，不會回到出發(fā)點。一個有n個節(jié)點的樹，一共有n-1條邊。2.樹的基本術語畫圖介紹樹的基本術語3.二叉樹的定義：二叉樹是一棵樹，每個節(jié)點的度不超過2，并且二叉樹的子樹有左右之分。畫出幾種樹，判斷是否是二叉樹。4.二叉樹的性質：性質1.在二叉樹的第i層上至多有2i-1個節(jié)點(i>=1)性質2.深度為k的二叉樹至多有2k-1個節(jié)點性質3.對任何二叉樹，如果終端節(jié)點數為n0，度為2的節(jié)點數為n2，則n0=n2+1。性質4.具有n個節(jié)點的完全二叉樹的深度為[log2n]+1

第15次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課我們已經學習了線性表等結構，這些都是線性結構。今天我們學習一種非線性結構：樹型結構。講授內容樹的基本概念和術語：二叉樹的概念二叉樹的性質歸納總結樹的基本定義和相關術語二叉樹的定義二叉樹的性質

第16次課程教學方案周次8課時數2教學章節(jié)第六章樹和二叉樹6.2.3二叉樹的存儲結構6.3.1遍歷二叉樹目標要求（1）掌握二叉樹的存儲結構；（2）掌握二叉樹的遍歷算法重點難點（1）二叉鏈表；（2）二叉樹的遍歷算法及其非遞歸實現。教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)數據結構習題集6.12，6.14，板書設計1.順序存儲結構如何把非線性的邏輯結構映射到線性的物理地址空間？把一個任意二叉樹補足為一棵完全二叉樹，對完全二叉樹進行遍歷可以得到線性序列。（畫出6.4所示二叉樹的補足結果以及線性存儲結果）2.鏈式存儲結構除葉子節(jié)點之外，每個節(jié)點都有最多兩個孩子節(jié)點每個節(jié)點保存兩個指針域，分別指向兩個孩子節(jié)點二叉鏈表（畫出圖6.8所示二叉樹的二叉鏈表）（寫出二叉鏈表的ADT）3.二叉樹的遍歷按照某種規(guī)則依次訪問二叉樹的每一個節(jié)點。先序遍歷（畫出6.8所示二叉樹的先序遍歷結果）（寫出先序遍歷的遞歸算法）中序遍歷（畫出6.8所示二叉樹的中序遍歷結果）（寫出中序遍歷的非遞歸算法）后序遍歷（畫出6.8所示二叉樹的后序遍歷結果）（寫出后序遍歷的非遞歸算法）

第16次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課上次課討論了二叉樹的概念與性質，本次課我們研究如何在物理上實現二叉樹的存儲，以及如何遍歷二叉樹的各個元素。講授內容二叉樹的存儲結構順序存儲結構、二叉鏈表結構二叉樹的遍歷算法先序遍歷、中序遍歷、后序遍歷歸納總結二叉樹的順序存儲二叉樹的鏈式存儲二叉樹的遍歷算法

第17次課程教學方案周次9課時數2教學章節(jié)第六章樹和二叉樹6.3.2線索二叉樹目標要求（1）掌握線索鏈表存儲結構；（2）掌握二叉樹線索化方法。重點難點（1）二叉樹的線索化方法教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)數據結構習題集6.15，6.16板書設計1.二叉樹的線索畫出圖6.11中的二叉樹，講解什么是線索。2.線索鏈表結構寫出線索鏈表的結構3.線索化算法書寫并講解算法6.5，6.6

第17次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課回顧二叉樹的遍歷引入：如何把遍歷結果記錄在二叉樹中？講授內容二叉樹的線索線索鏈表存儲結構線索化算法歸納總結二叉樹的線索線索鏈表存儲結構線索化算法第18次課程教學方案周次9課時數2教學章節(jié)第六章樹和二叉樹6.4樹和森林目標要求（1）掌握樹的存儲結構；（2）掌握森林與二叉樹的轉換；（3）掌握樹和森林的遍歷算法。重點難點（1）樹的存儲結構；（2）森林與二叉樹的轉換教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)數據結構習題集6.19，6.20，6.21，6.22。板書設計1.樹的存儲結構1）雙親表示法：每個節(jié)點記錄雙親節(jié)點。（畫出6.13，介紹雙親表示法）（寫出雙親表示法的結構體）2）孩子表示法：每個節(jié)點記錄孩子節(jié)點。（畫出6.14，介紹孩子鏈表表示法）3）孩子兄弟表示法：把樹轉換為二叉樹，用二叉鏈表存儲。（畫出6.15，講解樹轉換為二叉樹的過程）2.森林與二叉樹的轉換引入一個虛擬的根節(jié)點，把森林變成一棵樹轉換為二叉樹去掉根節(jié)點，得到森林的二叉樹表示。（畫出圖6.16，6.17，演示森林與二叉樹之間的轉換）3.樹和森林的遍歷1）先序遍歷森林：訪問森林中第一棵樹的根節(jié)點先序遍歷第一個樹根的子樹森林先序遍歷剩余的樹構成的森林（畫出圖6.17的先序遍歷結果）2）中序遍歷森林：中序遍歷森林中第一棵樹根的子樹森林訪問第一棵樹的根節(jié)點中序遍歷剩余的樹構成的森林（畫出圖6.17的中序遍歷結果）

第18次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課復習二叉樹的基本概念講授內容1.樹的存儲結構2.森林與二叉樹的轉換3.樹與森林的遍歷歸納總結1.樹的存儲結構2.森林與二叉樹的轉換3.樹與森林的遍歷

第19次課程教學方案周次10課時數2教學章節(jié)第六章樹和二叉樹6.6哈夫曼樹及其應用目標要求（1）掌握路徑、路徑長度、帶權路徑長度的概念（2）掌握最優(yōu)二叉樹的構建方法（3）理解前綴編碼的定義與性質，掌握哈夫曼編碼的算法（4）掌握哈夫曼樹和哈夫曼編碼的存儲結構（5）學會編寫哈夫曼編碼算法重點難點（1）哈夫曼樹的構造方法（1）哈夫曼編碼算法（2）用c語言實現哈夫曼編碼算法教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)數據結構習題集第六章6.26板書設計6.6.1.最優(yōu)二叉樹1.路徑長度（畫出圖6.22的二叉樹），講解路徑、路徑長度、帶權路徑長度的概念2.最優(yōu)二叉樹（哈夫曼樹）由n個權值構造一個帶有n個葉子節(jié)點的二叉樹，每個葉子節(jié)點的權值為wi，其中帶權路徑長度最小的二叉樹。3.如何構造一個哈夫曼樹？通過實例講解。6.6.2哈夫曼編碼1.前綴編碼例：假設需要傳送的電文只有A、B、Ｃ、Ｄ四個字符，如何設計這四個字符的編碼？可能的設計方案：Ａ:00,B:01,C:11,D:10;特點：任何一個字符的編碼都不會構成另一個字符的前綴，在接收端可以正確解碼。符合這種特點的編碼叫做前綴編碼。2.編碼長度第i個字符的編碼長度為li，某電文中第i個字符出現的次數為ni,則電文的總編碼長度為L=sum_i{ni*li};按照上述編碼方案，電文“AACCDBBBBB”的編碼長度為L=20;如何設計合適的編碼方案使得電文的平均編碼長度最??？平均編碼長度L=sum_i{wi*li},wi是第i個字符在電文中出現的概率。3.哈夫曼編碼把li看作是一棵二叉樹的樹根到第i個葉子節(jié)點的路徑長度，wi表示這個葉子節(jié)點的權重，則平均編碼長度恰好是樹的帶權路徑長度。最小平均編碼長度最小帶權路徑長度最短二進制前綴編碼方案以字符出現概率wi做權，設計一個哈夫曼樹稱這樣得到的二進制前綴編碼為哈夫曼編碼（舉例）課本例6-2在黑板上逐步構造出哈夫曼樹，并設計出哈夫曼編碼；4.哈夫曼編碼的程序實現定義哈夫曼樹結構：typedefstruct_HTNode{unsignedintw;unsignedinparent,lchild,rchild;}HTNode,*HuffmanTree;講解算法6.12,6.13

第19次教學活動設計教學環(huán)節(jié)內容設計與手段導入新課回顧二叉樹的有關概念。引入新課：二叉樹的應用？講授內容1.路徑長度2.哈夫曼樹3.哈夫曼樹的構造方法4.前綴編碼前綴編碼的特點，及其原因。5.編碼長度編碼長度的概念，如何計算編碼長度，平均編碼長度的概念。6.哈夫曼編碼平均編碼長度與二叉樹的帶權路徑長度之間的對應關系；最短平均編碼長度與哈夫曼樹的帶權路徑長度之間的對應關系；利用哈夫曼樹構造哈夫曼編碼；同一個字符集，可以有多種不同的哈夫曼編碼7.編寫哈夫曼編碼程序歸納總結1.哈夫曼樹的概念和構造方法；2.前綴編碼的特點；3.平均編碼長度的概念和計算4.哈夫曼編碼的原理5.哈夫曼編碼程序第20次課程教學方案周次10課時數2教學章節(jié)第六章樹和二叉樹6.7回溯法與樹的遍歷目標要求（1）理解回溯法的思想（2）學會利用回溯法解決簡單的搜索問題重點難點（1）理解回溯法教學方式√課堂講授□小組活動□實驗演示□難點答疑□提問□作業(yè)講評□實踐教學□考試測驗□其他活動媒體資源□文字教材√電子教案□錄像材料□錄音材料□直播課堂√CAI課件□IP課件□其他資源：課后作業(yè)編寫程序求解八皇后問題板書設計1.冪集（