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

1、PAGE PAGE 49課程簡(jiǎn)介人們?cè)谶\(yùn)用程序設(shè)計(jì)語(yǔ)言編寫程序的過程中發(fā)現(xiàn)所有的數(shù)據(jù)都可以抽象為三種結(jié)構(gòu)，而對(duì)這些數(shù)據(jù)的所有操作都可以轉(zhuǎn)化為對(duì)這三種數(shù)據(jù)的幾種基本操作，而大多數(shù)的程序設(shè)計(jì)技巧都可以抽象為一些最基本的算法。于是人們逐步發(fā)展了一門稱為數(shù)據(jù)結(jié)構(gòu)（或數(shù)據(jù)結(jié)構(gòu)與算法）的計(jì)算機(jī)科學(xué)，它廣泛應(yīng)用于計(jì)算機(jī)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)是信息與計(jì)算專業(yè)的核心基礎(chǔ)課程之一。數(shù)據(jù)是計(jì)算機(jī)處理的對(duì)象，本課程研究的數(shù)據(jù)是非數(shù)值性、結(jié)構(gòu)性的數(shù)據(jù)。學(xué)習(xí)本課程要求掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、計(jì)算機(jī)內(nèi)的表示方法，以及處理數(shù)據(jù)的算法，對(duì)于算法所花費(fèi)的時(shí)間和空間代價(jià)的分析也要求有一定程度的了解和掌握。通過本課程的學(xué)習(xí)，使學(xué)生透徹地

2、理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)基本的良好的程序設(shè)計(jì)能力。本課程主要包括如下三個(gè)方面的內(nèi)容：1基本數(shù)據(jù)結(jié)構(gòu)： 線性表、棧、隊(duì)列、串、數(shù)組和廣義表，掌握它們的特點(diǎn)、表示和實(shí)現(xiàn)，對(duì)靜態(tài)結(jié)構(gòu)要求非常熟練的編程上機(jī)實(shí)現(xiàn)，對(duì)動(dòng)態(tài)結(jié)構(gòu)要求逐步熟悉鏈表的表示，通過模仿實(shí)驗(yàn)教程中的例子，掌握編程技巧。強(qiáng)調(diào)類 C語(yǔ)言的書寫規(guī)范，特別注意參數(shù)的區(qū)別，輸入輸出的方式和錯(cuò)誤處理方式，以及抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。能熟練完成以下的應(yīng)用：多項(xiàng)式的計(jì)算、語(yǔ)法檢查、回朔算法、遞歸算法、表達(dá)式求值、離散事件模擬、文字的編輯和稀疏矩陣進(jìn)行矩陣運(yùn)算采用的處理方法。2復(fù)雜數(shù)據(jù)結(jié)構(gòu)： 樹、二叉樹、圖。

3、掌握它們的定義和特點(diǎn)、表示和實(shí)現(xiàn)，特別注意與基本數(shù)據(jù)結(jié)構(gòu)的區(qū)別，掌握各種遍歷的遞歸和非遞歸算法，能熟練完成以下的應(yīng)用：最優(yōu)樹、Huffman編碼、拓?fù)渑判?、關(guān)鍵路徑和最短路徑問題。 3數(shù)據(jù)結(jié)構(gòu)的應(yīng)用： 查找和內(nèi)部排序。熟練掌握靜態(tài)查找表的查找方法和實(shí)現(xiàn)，了解哈希表的構(gòu)造和查找方法。掌握各種內(nèi)部排序方法的基本思想、算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)課程編號(hào)：014100028 適用專業(yè)：計(jì)算機(jī)、信息管理總學(xué)時(shí)數(shù)：60 學(xué)分?jǐn)?shù)： 4 一、課程的性質(zhì)、目的與任務(wù)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)技術(shù)、信息管理等專業(yè)的核心課程之一，是一門理論與工程實(shí)踐密切相關(guān)的綜合性課程

4、，在計(jì)算機(jī)學(xué)科教學(xué)中具有十分重要的作用。大力加強(qiáng)數(shù)據(jù)結(jié)構(gòu)課程的建設(shè)，提高數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)質(zhì)量，有利于教學(xué)改革和教育創(chuàng)新，有利于高級(jí)應(yīng)用型人才和創(chuàng)新人才的培養(yǎng)。數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課程，介紹計(jì)算機(jī)領(lǐng)域的常用數(shù)據(jù)結(jié)構(gòu)以及各種查找和排序的算法，是計(jì)算機(jī)專業(yè)學(xué)生必修的一門技術(shù)基礎(chǔ)課程，也是計(jì)算機(jī)專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)基礎(chǔ)課，主要解決數(shù)據(jù)的表示和數(shù)據(jù)的處理，系統(tǒng)介紹三大數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，為操作系統(tǒng)等課程提供必要的知識(shí)基礎(chǔ)，為計(jì)算機(jī)人員提供必要的基本技能。二、課程教學(xué)基本要求本課程介紹常用數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)其施加的運(yùn)算，如：線性表、棧、隊(duì)列、

5、串、數(shù)組、廣義表、樹、圖等。同時(shí)還介紹各種查找和排序的算法。通過本門課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握以下幾個(gè)方面的知識(shí)：1：系統(tǒng)學(xué)習(xí)常用基本數(shù)據(jù)結(jié)構(gòu)及其在不同存儲(chǔ)方式下的實(shí)現(xiàn)，掌握分析、選擇不同的數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的原則和方法。2：學(xué)習(xí)和掌握在各種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的各種算法及其設(shè)計(jì)思想，從而學(xué)習(xí)各種分析問題和解決問題的能力。3：掌握各種算法的時(shí)空效率的分析方法，學(xué)會(huì)在實(shí)際應(yīng)用中選擇合適的算法。4：掌握各種查找和排序的算法以及效率，并將其應(yīng)用在程序設(shè)計(jì)中。三、課程教學(xué)內(nèi)容體系第一章：概論1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語(yǔ)1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實(shí)現(xiàn)1.4 算法和算法分析教學(xué)要求：理解數(shù)據(jù)、數(shù)

6、據(jù)元素、數(shù)據(jù)項(xiàng)的概念；掌握邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系；理解算法的基本概念；學(xué)會(huì)分析算法的時(shí)間復(fù)雜性和空間復(fù)雜性。第二章：線性表2.1 線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（靜態(tài)查找表不講）2.4 一元多項(xiàng)式的表示及相加教學(xué)要求：理解線性表的定義和特點(diǎn)；掌握順序表和鏈表的特點(diǎn)，掌握在這兩種存儲(chǔ)結(jié)構(gòu)上各種基本運(yùn)算的實(shí)現(xiàn)算法以及效率的分析，并學(xué)習(xí)在這兩種存儲(chǔ)結(jié)構(gòu)上進(jìn)行算法設(shè)計(jì)的方法； 以達(dá)到利用基本算法進(jìn)行較復(fù)雜算法設(shè)計(jì)的目的。第三章：棧、隊(duì)列3.1 棧3.2 棧的應(yīng)有和舉例3.2.1 數(shù)制轉(zhuǎn)換3.3.4 迷宮求解3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列教學(xué)要求：理解

7、棧和隊(duì)列的定義、特點(diǎn)，學(xué)習(xí)它們的各種組織方式及算法；掌握它們的空和滿的判斷條件；并學(xué)會(huì)它們的簡(jiǎn)單應(yīng)用。第四章：串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長(zhǎng)順序存儲(chǔ)表示 4.2.3 串的塊鏈存儲(chǔ)表示4.3 串的模式匹配算法 4.3.1 求字串位置的定位函數(shù)教學(xué)要求：了解串的概念，掌握串的基本運(yùn)算，學(xué)習(xí)串運(yùn)算在不同存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)過程。第五章：多維數(shù)組和廣義表5.1 數(shù)組的定義5.2 數(shù)組的順序表現(xiàn)和實(shí)現(xiàn)5.3 矩陣的壓縮存儲(chǔ)教學(xué)要求：領(lǐng)會(huì)數(shù)組的定義，數(shù)組的兩種順序存儲(chǔ)結(jié)構(gòu)，并領(lǐng)會(huì)幾種特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法。 第六章：樹6.1 樹的定義和基本術(shù)語(yǔ)6.2 二叉樹6.2.1

8、 二叉樹的定義6.2.2 二叉樹的性質(zhì)6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)6.3 遍歷二叉樹和線索二叉樹6.3.1 遍歷二叉樹6.4 樹和森林6.4.1 樹的存儲(chǔ)結(jié)構(gòu)6.4.2 森林與二叉樹的轉(zhuǎn)換6.4.3 樹和森林的遍歷6.6 赫夫曼樹及其應(yīng)用6.6.1 最優(yōu)二叉樹（赫夫曼樹）6.6.2 赫夫曼編碼教學(xué)要求：理解樹型結(jié)構(gòu)的概念和術(shù)語(yǔ)，領(lǐng)會(huì)二叉樹的定義、形態(tài)、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，掌握二叉樹的各種遍歷算法極其實(shí)現(xiàn)過程，了解樹和森林及其相互轉(zhuǎn)換；掌握哈夫曼樹極其應(yīng)用。第七章：圖7.1 圖的定義和術(shù)語(yǔ)7.2 圖的存儲(chǔ)結(jié)構(gòu)7.2.1 數(shù)組表示法7.2.2 鄰接表7.2.3 十字鏈表7.2.4 鄰接多重表7.3 圖

9、的遍歷7.3.1 深度優(yōu)先搜索7.3.2 廣度優(yōu)先搜索7.4 圖的連通性問題7.4.1 無(wú)向圖的連通分量和生成樹7.4.3 最小生成樹7.5 有向無(wú)環(huán)圖及其應(yīng)用7.5.1 拓?fù)渑判?.5.2 關(guān)鍵路徑7.6 最短路徑7.6.1 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑 教學(xué)要求：理解圖型結(jié)構(gòu)的概念和術(shù)語(yǔ)，掌握?qǐng)D的鄰接矩陣和鄰接表兩種存儲(chǔ)形式，理解圖的遍歷的基本思想，掌握?qǐng)D的兩種遍歷的方法和其實(shí)現(xiàn)的過程，學(xué)會(huì)圖在最小生成樹、拓?fù)渑判颉⒆疃搪窂?、關(guān)鍵路徑中的應(yīng)用。第九章：查找9.1 靜態(tài)查找表9.1.1 順序表的查找9.1.2 有序表的查找9.1.4 索引順序表的查找9.3 哈希表9.3.1 什么是哈希表

10、9.3.2 哈希函數(shù)的構(gòu)造方法9.3.3 處理沖突的方法教學(xué)要求：掌握查找表的定義和分類，熟練掌握順序查找和二分查找的思想，了解二叉排序樹及其查找，了解散列查找的思想和有關(guān)方法。第十章：內(nèi)部排序10.1 概述10.2 插入排序10.2.1 直接插入排序10.2.2 其他插入排序（表的插入排序不講）10.2.3 希爾排序10.3 快速排序10.4 選擇排序10.4.1 簡(jiǎn)單選擇排序10.5 歸并排序教學(xué)要求：熟練掌握各種排序方法的思想和特點(diǎn)，如：插入排序、交換排序、選擇排序、分配排序等，學(xué)會(huì)分析它們的優(yōu)點(diǎn)和缺點(diǎn)以及時(shí)空性能，并學(xué)會(huì)選擇和應(yīng)用各種排序方法解決實(shí)際問題。四、學(xué)時(shí)分配章節(jié)內(nèi)容講授學(xué)時(shí)上

11、機(jī)學(xué)時(shí)習(xí)題學(xué)時(shí)一概 論400二線性表611三棧、隊(duì)列611四串211五數(shù)組和廣義表411六樹和二叉樹811七圖811九查找211十內(nèi)部排序411總學(xué)時(shí)數(shù)：60課時(shí)4488五、推薦教材及教學(xué)參考書1. 教材數(shù)據(jù)結(jié)構(gòu)；嚴(yán)蔚敏編著；清華大學(xué)出版社2. 教學(xué)參考書算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版），徐孝凱編著，清華大學(xué)出版社 2006數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實(shí)用教程（第二版），徐孝凱，清華大學(xué)出版社 2003數(shù)據(jù)結(jié)構(gòu)

12、，謝楚屏等，人民郵電出版社，2001算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述，張乃孝等，高等教育出版社，2002數(shù)據(jù)結(jié)構(gòu)，殷人昆，清華大學(xué)出版社，2001計(jì)算機(jī)算法設(shè)計(jì)與分析，蘇德富，電子工業(yè)出版社，2001算法與數(shù)據(jù)結(jié)構(gòu)，傅清祥，王嘵冬，電子工業(yè)出版社，1998數(shù)據(jù)結(jié)構(gòu)C+與面向?qū)ο蟮耐緩?，張乃孝，裘宗燕，高等教育出版社?001數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅcC+描述，殷人昆等清華大學(xué)出版社算法設(shè)計(jì)與分析，梁田貴，張鵬編著，冶金工業(yè)出版社，2004六、考核辦法和成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)根據(jù)教學(xué)要求進(jìn)行期末考試，由任課教師根據(jù)完成情況進(jìn)行評(píng)定，并最終結(jié)合平時(shí)成績(jī)的考核給出綜合成績(jī)。 制定：制定日期：教案（首頁(yè)） 授課時(shí)間 教案

13、編寫時(shí)間 課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼總學(xué)時(shí)講課： 學(xué)時(shí)上機(jī)： 學(xué)時(shí)實(shí)習(xí)： 周學(xué) 分課程性質(zhì)必修課（） 選修課（ ）理論課（） 實(shí)驗(yàn)課（ ）任課教師職稱授課對(duì)象專業(yè)： 年級(jí)： 班級(jí)： 教材和主要參考資料選用教材： 數(shù)據(jù)結(jié)構(gòu)， 嚴(yán)蔚敏編著 清華大學(xué)出版社主要參考書：算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版），徐孝凱編著，清華大學(xué)出版社 2006數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實(shí)用教程（第二版），徐孝凱，清華大學(xué)出

14、版社 2003數(shù)據(jù)結(jié)構(gòu)，謝楚屏等，人民郵電出版社，2001算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述，張乃孝等，高等教育出版社，2002數(shù)據(jù)結(jié)構(gòu)，殷人昆，清華大學(xué)出版社，2001計(jì)算機(jī)算法設(shè)計(jì)與分析，蘇德富，電子工業(yè)出版社，2001算法與數(shù)據(jù)結(jié)構(gòu)，傅清祥，王嘵冬，電子工業(yè)出版社，1998數(shù)據(jù)結(jié)構(gòu)C+與面向?qū)ο蟮耐緩?，張乃孝，裘宗燕，高等教育出版社?001數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅcC+描述，殷人昆等清華大學(xué)出版社算法設(shè)計(jì)與分析，梁田貴，張鵬編著，冶金工業(yè)出版社，2004教學(xué)目的和教學(xué)要求通過本門課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握以下幾個(gè)方面的知識(shí)：1 系統(tǒng)學(xué)習(xí)常用基本數(shù)據(jù)結(jié)構(gòu)及其在不同存儲(chǔ)方式下的實(shí)現(xiàn)，掌握分析、選擇不同的

15、數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的原則和方法。2 學(xué)習(xí)和掌握在各種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的各種算法及其設(shè)計(jì)思想，從而學(xué)習(xí)各種分析問題和解決問題的能力。3 掌握各種算法的時(shí)空效率的分析方法，學(xué)會(huì)在實(shí)際應(yīng)用中選擇合適的算法。4 掌握各種查找和排序的算法以及效率，并將其應(yīng)用在程序設(shè)計(jì)中。教學(xué)重點(diǎn)和教學(xué)難點(diǎn)重點(diǎn)掌握數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)其施加的運(yùn)算，如：線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹、圖等。應(yīng)掌握各種查找和排序的算法。難點(diǎn)章節(jié)：第六章：樹和第七章：圖。教學(xué)進(jìn)程第1次課第2次課第3次課第4次課第5次課第6次課第7次課第8次課第9次課第10次課第11次課第12次課第13次課第14次課第15次課第16次課第

16、17次課第18次課第19次課第20次課第21次課第22次課第23次課第24次課第25次課第26次課第27次課第28次課第29次課第30次課授課章節(jié)第1章 緒論：1.1 什么是數(shù)據(jù)結(jié)構(gòu)、1.2 基本概念和術(shù)語(yǔ)第1章：1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實(shí)現(xiàn)1.4 算法和算法分析第2章 線性表：2.1 線性表的類型定義2.2 線性表的順序表示第2章 ：2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（1）第2章 ：2.3 （2）2.4 一元多項(xiàng)式的表示及相加第3章 棧和隊(duì)列：3.1、3.2.1第3章 棧和隊(duì)列：3.2.4、3.2.5、3.3第3章 棧和隊(duì)列：3.4綜合習(xí)題課（1）：前3章的相關(guān)內(nèi)容綜合實(shí)驗(yàn)課（1）：前3章的

17、相關(guān)內(nèi)容第4章 串：4.1、4.2.1、4.2.2、4.2.3、4.3.1第5章 數(shù)組和廣義表：5.1、5.2第5章 數(shù)組和廣義表：5.3綜合實(shí)驗(yàn)課（2）：第4-5章的相關(guān)內(nèi)容第6章 樹和二叉樹：6.1、6.2第6章 樹和二叉樹：6.3、6.4.1第6章 樹和二叉樹：6.4.2、6.6第6章 樹和二叉樹：綜合習(xí)題課（2）：樹的相關(guān)內(nèi)容第7章 圖：7.1、7.2第7章 圖：7.3、7.4.1、7.4.3第7章 圖：7.6第7章 圖：綜合習(xí)題課（3）：圖的相關(guān)內(nèi)容第9章 查找：9.1、9.3綜合實(shí)驗(yàn)課（3）：第9章的相關(guān)內(nèi)容第10章 內(nèi)部排序：10.1、10.2第10章 內(nèi)部排序：10.3、10.

18、4綜合習(xí)題課（3）：第9、10章的相關(guān)內(nèi)容綜合實(shí)驗(yàn)課（4）：第10章的相關(guān)內(nèi)容學(xué) 時(shí)222222222222222222222222222222備 注教案（分教案）課次：1 學(xué)時(shí)：2章 節(jié)第1章 緒論：1.1 什么是數(shù)據(jù)結(jié)構(gòu)、1.2 基本概念和術(shù)語(yǔ)教學(xué)目的和教學(xué)要求了解數(shù)據(jù)結(jié)構(gòu)的課程性質(zhì)、內(nèi)容、應(yīng)用領(lǐng)域及其與其他學(xué)科的關(guān)系；掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語(yǔ)；掌握四類基本的數(shù)據(jù)關(guān)系。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語(yǔ)教學(xué)難點(diǎn)： 四類基本的數(shù)據(jù)關(guān)系教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：計(jì)算機(jī)的應(yīng)用不再局限于科學(xué)計(jì)算，更多地用于控制，管理，數(shù)據(jù)處理等非數(shù)值

19、計(jì)算的處理工作。計(jì)算機(jī)加工處理的對(duì)象：數(shù)值，字符，表格，圖形聲音，圖象等具有一定結(jié)構(gòu)的數(shù)據(jù)。進(jìn)行程序設(shè)計(jì)時(shí)必須分析待處理的對(duì)象的特性及各對(duì)象之間存在的關(guān)系產(chǎn)生背景。1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 1. 數(shù)據(jù)（Data）2. 數(shù)據(jù)元素（Data Element）3. 數(shù)據(jù)對(duì)象（Data Object） 4. 結(jié)構(gòu)（Data Structure）存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (Abstract Data Type) ADT的定義格式不唯一, 我們采用下述格式定義一個(gè)ADT: ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象: 數(shù)據(jù)關(guān)系: 基本操作: ADT 抽象數(shù)據(jù)類型名教學(xué)方法、課

20、堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)圖1.5：要求理解和掌握四類基本的數(shù)據(jù)關(guān)系；并在日常生活中舉例進(jìn)行說明。主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：2 學(xué)時(shí)：2章 節(jié)第1章：1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實(shí)現(xiàn)1.4 算法和算法分析教學(xué)目的和教學(xué)要求理解抽象數(shù)據(jù)類型的表示及實(shí)現(xiàn)；對(duì)算法、算法要求、算法效率的度量進(jìn)行有效的分析。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)

21、重點(diǎn)： 抽象數(shù)據(jù)類型的表示及實(shí)現(xiàn)；算法、算法要求；教學(xué)難點(diǎn)： 算法效率的度量及有效的分析；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4 算 法 1. 算法（Algorithm）的定義 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是規(guī)則的有限集合， 是為解決特定問題而規(guī)定的一系列操作。) 是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。2. 算法的特

22、性3. 算法設(shè)計(jì)的要求） 算法的正確性 (1) 所設(shè)計(jì)的程序沒有語(yǔ)法錯(cuò)誤； (2) 所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； (3) 所設(shè)計(jì)的程序?qū)τ诰倪x擇的典型、 苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。 (4) 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。2） 可讀性 3） 健壯性 4） 高效率和低存儲(chǔ)量 、算法、 語(yǔ)言和程序的關(guān)系時(shí)間復(fù)雜度教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1:圖1.5、P13：算法的5個(gè)特征；2:P15：兩段程序的語(yǔ)句的頻度的分析主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著

23、，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：3 學(xué)時(shí)：2章 節(jié)第2章 線性表：2.1 線性表的類型定義2.2 線性表的順序表示教學(xué)目的和教學(xué)要求理解線性表的定義和特點(diǎn)；掌握順序表以達(dá)到利用基本算法進(jìn)行較復(fù)雜算法設(shè)計(jì)的目的。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：線性表的定義和特點(diǎn)；線性表的順序表示教學(xué)難點(diǎn)：線性表的順序表示教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中， 存在唯一的一個(gè)被稱為

24、“第一個(gè)”的數(shù)據(jù)元素； 存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素； 除第一個(gè)元素之外，集合中的每個(gè)元素均只有一個(gè)前驅(qū)； 除最后一個(gè)元素之外，集合中的每個(gè)元素均只有一個(gè)后繼。 2.1 線性表的類型定義2.1.1 線性表的邏輯結(jié)構(gòu)2.1.2 線性表的抽象數(shù)據(jù)類型定義2.2 線性表的順序表示和實(shí)現(xiàn) 2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.2 線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算1. 初始化操作 2. 插入操作 3. 刪除操作算法2.1算法2.3教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：算法2.1、圖2.2、算法2.42：算法2.5、算法2.6主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（

25、C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：4 學(xué)時(shí)：2章 節(jié)第2章 ：2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（1）教學(xué)目的和教學(xué)要求理解線性表的鏈表的特點(diǎn)，掌握在這種存儲(chǔ)結(jié)構(gòu)上各種基本運(yùn)算的實(shí)現(xiàn)算法以及效率的分析，并學(xué)習(xí)在這種存儲(chǔ)結(jié)構(gòu)上進(jìn)行算法設(shè)計(jì)的方法； 以達(dá)到利用基本算法進(jìn)行較復(fù)雜算法設(shè)計(jì)的目的。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)；教學(xué)難點(diǎn)：?jiǎn)捂湵淼牟迦?、刪除、查找和歸并操作；教學(xué)進(jìn)程

26、（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.3.1 單鏈表線性表的鏈?zhǔn)酱鎯?chǔ)：圖2.6 單鏈表的邏輯狀態(tài)圖2.7 帶頭結(jié)點(diǎn)單鏈表圖示2.3.2 單鏈表上的基本運(yùn)算 1. 建立單鏈表2. 查找3. 單鏈表插入操作4. 刪除5合并單鏈表：教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：圖2.5、圖2.8、圖2.92：算法2.8、算法2.9、算法2.10、算法2.11主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 20

27、04數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：5 學(xué)時(shí)：2章 節(jié)第2章 ：2.3 （2）2.4 一元多項(xiàng)式的表示及相加教學(xué)目的和教學(xué)要求理解線性表的鏈表的特點(diǎn)，掌握在這種存儲(chǔ)結(jié)構(gòu)上各種基本運(yùn)算的實(shí)現(xiàn)算法以及效率的分析；掌握一元多項(xiàng)式的表示及相加的方法與算法。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 循環(huán)鏈表、雙向鏈表及其算法；一元多項(xiàng)式的表示及相加的方法與算法；教學(xué)難點(diǎn)：雙向鏈表及其算法、一元多項(xiàng)式相加的方法；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：2.3.3 循環(huán)鏈表2.3.4 雙向鏈表1. 雙向鏈表的前插操作

28、2. 雙向鏈表的刪除操作2.3.6 順序表和鏈表的比較 1. 基于空間的考慮、2. 基于時(shí)間的考慮、3. 基于語(yǔ)言的考慮2.4 一元多項(xiàng)式的表示及相加教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：圖2.12、圖2.14、圖2.15、圖2.16、圖2.17、圖2.182：算法2.18、算法2.19、算法2.23主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分

29、教案）課次：6 學(xué)時(shí)：2章 節(jié)第3章 棧和隊(duì)列：3.1 棧、3.2.1 數(shù)制轉(zhuǎn)換教學(xué)目的和教學(xué)要求理解棧的定義、特點(diǎn)，學(xué)習(xí)它的各種組織方式及算法；掌握它的空和滿的判斷條件；并學(xué)會(huì)它的簡(jiǎn)單應(yīng)用。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 棧的定義、特點(diǎn)，學(xué)習(xí)它的各種組織方式及算法；教學(xué)難點(diǎn)： 棧的簡(jiǎn)單應(yīng)用；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：3.1 棧 3.1.1 棧的定義3.1.2 棧的表示和實(shí)現(xiàn) 1. 順序棧順序棧基本操作的實(shí)現(xiàn):初始化、(2) 取棧頂元素、(3) 入棧、(4) 出棧2. 鏈棧3.2 棧的應(yīng)用舉例 1. 數(shù)制轉(zhuǎn)換教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：

30、電腦、投影儀、教科書作業(yè)1：圖3.1、3.22：P47：?；静僮鞯乃惴枋?、算法3.1主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：7 學(xué)時(shí)：2章 節(jié)第3章 棧和隊(duì)列：3.2.4 迷宮求解、3.3 棧與遞歸的實(shí)現(xiàn)教學(xué)目的和教學(xué)要求了解迷宮求解的算法思路、了解計(jì)算機(jī)圖形學(xué)中的種子填充蘇算法；掌握漢諾塔算法及其過程。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 迷宮求解的算法思路、漢諾塔算法

31、及其過程；教學(xué)難點(diǎn)： 漢諾塔算法及其過程；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：4. 迷宮求解（拓展：填充算法） 3.3 棧與遞歸的實(shí)現(xiàn)1. 遞歸特性問題 1) 遞歸函數(shù) 2）漢諾塔算法三個(gè)盤子搬動(dòng)時(shí)hanoi(3, A, B, C) 遞歸調(diào)用過程： hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1號(hào)搬到C move(A-B) 2號(hào)搬到B hanoi(1,C,A,B) move(C-B) 1號(hào)搬到B move(A-c) 3號(hào)搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B-A) 1號(hào)搬到A mo

32、ve(B-c) 2號(hào)搬到C hanoi(1,A,B,C) move(A-C) 1號(hào)搬到C教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：圖3.72：算法3.5、種子填充算法、兩種算法求解n!主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：8 學(xué)時(shí)：2章 節(jié)第3章 棧和隊(duì)列：3.4 隊(duì)列教學(xué)目的和教學(xué)要求掌握隊(duì)列的數(shù)據(jù)結(jié)構(gòu)和鏈隊(duì)列的相關(guān)操作；掌握循

33、環(huán)隊(duì)列的相關(guān)內(nèi)容；教學(xué)重點(diǎn)、難點(diǎn)教學(xué)重點(diǎn)： 列的數(shù)據(jù)結(jié)構(gòu)和鏈隊(duì)列的相關(guān)操作；教學(xué)難點(diǎn)： 循環(huán)隊(duì)列的相關(guān)操作；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：3.4 隊(duì) 列3.4.1 隊(duì)列的定義 隊(duì)列 (Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出(Fist In Fist Out， 縮寫為FIFO)的特性。在隊(duì)列中，允許插入的一端叫做隊(duì)尾(rear)，允許刪除的一端則稱為隊(duì)頭(front)。3.4.2 隊(duì)列的表示和實(shí)現(xiàn) 鏈隊(duì)列: （1） 初始化操作、（2）銷毀隊(duì)列、（3） 入隊(duì)操作、（4） 出隊(duì)操作3.4.3：循環(huán)

34、隊(duì)列如何區(qū)分隊(duì)列“空”和“滿”另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列是空還是滿；少用一個(gè)元素空間，當(dāng)隊(duì)列頭指針在隊(duì)列尾指針的下一個(gè)位置上時(shí)為“滿”。當(dāng)Q.front=Q.rear時(shí)隊(duì)空；Q.front+1=Q.rear時(shí)隊(duì)滿 循環(huán)隊(duì)列滿足條件 (Q.rear+1)%MAXQSIZE= Q.front 隊(duì)滿教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：圖3.8、圖3.10、圖3.11、圖3.14；2：P62：隊(duì)列的基本操作算法、P64：循環(huán)隊(duì)列的基本操作算法；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），

35、嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：9 學(xué)時(shí)：2章 節(jié)綜合習(xí)題課（1）：前3章的相關(guān)內(nèi)容教學(xué)目的和教學(xué)要求要求掌握棧的應(yīng)用及遞歸算法教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 教學(xué)難點(diǎn)： 教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：1：求N！的遞歸算法；2：求N！的棧的算法；3：數(shù)制轉(zhuǎn)換算法的具體實(shí)現(xiàn)；4：種子填充算法的具體過程：四向連通填充算法：a） 種子像素壓入棧中；b） 如果棧為空，則轉(zhuǎn)e)；否則轉(zhuǎn)c)；c） 彈出一個(gè)像素，并將該像素置成填充色；并判斷該像素相鄰的四連

36、通像素是否為邊界色或已經(jīng)置成多邊形的填充色，若不是，則將該像素壓入棧；d） 轉(zhuǎn)b）；e） 結(jié)束。 教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：10 學(xué)時(shí)：2章 節(jié)綜合實(shí)驗(yàn)課（1）：前3章的相關(guān)內(nèi)容教學(xué)目的和教學(xué)要求1：求N！的遞歸算法；2：求N！的棧的算法；3：數(shù)制轉(zhuǎn)換算法的具體實(shí)現(xiàn)；教學(xué)進(jìn)程（含章

37、節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：1：求N！的遞歸算法；2：求N！的棧的算法；3：數(shù)制轉(zhuǎn)換算法的具體實(shí)現(xiàn)；#include stdio.h#include stdlib.h#define size 20typedef struct int *base; int *top; int ssize;ss;void ist(ss &s) s.base=(int *)malloc(size*sizeof(int); s.top=s.base; s.ssize=size;void main() long n,m; ss w;ist(w);printf(請(qǐng)輸入N的值(1-32768)：)

38、; scanf(%d,&n);m=n; while(n) *w.top+=n%8; n=n/8; printf(轉(zhuǎn)換為8進(jìn)制以后的值：n(%d)10=(,m); while(w.top!=w.base) printf(%d,*-w.top); printf()8n); 教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析教案（分教案）

39、課次：11 學(xué)時(shí)：2章 節(jié)第4章 串：4.1 串的定義、4.2.1 定長(zhǎng)順序存儲(chǔ)表示 4.2.3 串的塊鏈存儲(chǔ)表示4.3.1 求子串位置的定位函數(shù)教學(xué)目的和教學(xué)要求掌握串的定義、定長(zhǎng)順序存儲(chǔ)表示；了解串的塊鏈存儲(chǔ)表示；掌握求子串位置的定位函數(shù)（模式匹配算法）；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 串的定義、定長(zhǎng)順序存儲(chǔ)表示；串的塊鏈存儲(chǔ)表示；教學(xué)難點(diǎn)：求子串位置的定位函數(shù)（模式匹配算法）；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：4.1 串的定義 串(String)是零個(gè)或多個(gè)字符組成的有限序列。 一般記為： S= a1a2.an (n0)4.2 串的表示和實(shí)現(xiàn) 4.2.1 定

40、長(zhǎng)順序存儲(chǔ)表示串1.串聯(lián)接Concat(& T , S1, S2) 2. 求子串SubString ( & Sub , S , pos , len )4.2.3串的塊鏈存儲(chǔ)表示4.3 串的模式匹配算法 4.3.1 求子串位置的定位函數(shù) Index( S, T ,pos)int Index （SString S, SString T, int pos ） /返回子串T在主串中第 pos個(gè)字符之后的位置。如不存在，則函數(shù)值為0。其中：T 非空，1=pos=Strlength( S )。 i = pos ; j = 1 ; while ( i=S 0 & j T 0 ) return i - T 0

41、 ; else return 0 ; / Index 算法：4.5教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：P73：串的鏈接操作；圖4.1；2：算法4.5：串的模式匹配算法、圖4.3；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：12 學(xué)時(shí)：2章 節(jié)第5章 數(shù)組和廣義表：5.1 數(shù)組的定義、5.2 數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)目的和教學(xué)要求掌

42、握數(shù)組的定義、數(shù)組的順序表示和實(shí)現(xiàn)；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 數(shù)組的定義、數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)難點(diǎn)： 數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：5.1 數(shù)組的定義數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。對(duì)于數(shù)組的操作一般只有兩類： (1） 獲得特定位置的元素值； (2） 修改特定位置的元素值。5.2 數(shù)組的順序表示和實(shí)現(xiàn) 數(shù)組一般不做插入和刪除操作，因此采用順序存儲(chǔ)結(jié)構(gòu)。由于存儲(chǔ)單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，則用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問題。 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：一

43、種是按行序存儲(chǔ)，另一種是按列序存儲(chǔ)。Loci, j=Loc1, 1+n(i-1)+(j-1)Loci, j, k=Loc1, 1, 1+(i-1)mn+(j-1)n+(k-1)對(duì)于維數(shù)組A(c1d1, c2d2，, cndn)，我們只要把上式推廣，就可以容易地得到維數(shù)組中任意元素aj1j2jn的存儲(chǔ)地址的計(jì)算公式: LOC(aj1j2jn)=LOC(a000)+(b2*b3*bn*j1+b3*bn*j2+bn*jn-1+jn)*lLOC(aj1j2jn)= LOC(a000)+( = LOC(a000)+其中 cn=L,ci-1=bi*ci教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、

44、投影儀、教科書作業(yè)計(jì)算1-3維數(shù)組的任意元素的存儲(chǔ)地址；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：13 學(xué)時(shí)：2章 節(jié)第5章 數(shù)組和廣義表：5.3 矩陣的壓縮存儲(chǔ) 5.3.1 特殊矩陣、5.3.2 稀疏矩陣教學(xué)目的和教學(xué)要求掌握特殊矩陣和稀疏矩陣的存儲(chǔ)方法；掌握稀疏矩陣的轉(zhuǎn)置算法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 特殊矩陣和稀疏矩陣的存儲(chǔ)方法；稀疏矩陣的轉(zhuǎn)置算法；教學(xué)難點(diǎn)：

45、稀疏矩陣的轉(zhuǎn)置算法；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：5.3 矩陣的壓縮存儲(chǔ) 壓縮存儲(chǔ)：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配空間。特殊矩陣：值相同的元素或零元素在矩陣中的分布有一定的規(guī)律。稀疏矩陣：矩陣中元素分布沒有規(guī)律，但零元素較多。 5.3.1 特殊矩陣 三角矩陣大體分為三類：下三角矩陣、上三角矩陣和對(duì)稱矩陣Loci, j=Loc1, 1+i(i-1)/2+j-1帶狀矩陣5.3.2 稀疏矩陣方法一：按照b.data中三元組的次序依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。方法二：按照a.data 中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組

46、置入b 中的恰當(dāng)位置。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：下三角、對(duì)稱、帶狀矩陣的數(shù)據(jù)元素的下標(biāo)地址的計(jì)算方法；2：稀疏矩陣的兩個(gè)轉(zhuǎn)置算法；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：14 學(xué)時(shí)：2章 節(jié)綜合實(shí)驗(yàn)課（2）：第4、5章的相關(guān)內(nèi)容教學(xué)目的和教學(xué)要求要求編程實(shí)現(xiàn)串的模式匹配算法、稀疏矩陣的兩個(gè)轉(zhuǎn)置算法；教學(xué)進(jìn)程（含章節(jié)教

47、學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：1：串的模式匹配算法；2：稀疏矩陣的轉(zhuǎn)置算法（一）；3：稀疏矩陣的轉(zhuǎn)置算法（二）；#include stdio.hvoid main() char sa7=a,b,c,d,e,f,g; char sb3=e,f,g; int i=0,j=0;while(i=6 & j2) printf(找到了!在第%d個(gè)位置。n,i-3+1); else printf(抱歉,沒有找到!n);#include stdio.h#define mu 3#define nu 8#define tu 8void main() int M83=1,2,12,1,3,9,3

48、,1,-3,3,6,14,4,3,24,5,2,18,6,1,15,6,4,-7; int T83; int q=0,col,p,i,j; printf(轉(zhuǎn)換之前的矩陣為：n);for(i=0;i=7;i+) for(j=0;j=2;j+) printf( %d ,Mij);printf(n) for(col=1;col=nu;+col)for(p=0;p=tu-1;+p)if(Mp1=col) Tq0=Mp1;Tq1=Mp0; Tq2=Mp2;+q; printf(轉(zhuǎn)換之后的矩陣為：n);for(i=0;i=7;i+) for(j=0;j0時(shí)， 該集合滿足如下條件： (1) 其中必有一個(gè)稱為

49、根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成m（m0）個(gè)互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵樹，稱為根root的子樹。 每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。6.2 二叉樹的定義 6.2.1 二叉樹的定義 定義：我們把滿足以下兩個(gè)條件的樹形結(jié)構(gòu)叫做二叉樹（Binary Tree）： （1） 每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即度都不大于2）； （2）二叉樹的子樹有左右之分，其次序不能任意顛倒。 6.2.2 二叉樹的性質(zhì)滿二叉樹：完全二叉樹：深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1n的位置序號(hào)分別與滿

50、二叉樹的結(jié)點(diǎn)1n的位置序號(hào)一一對(duì)應(yīng)，則為完全二叉樹。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：圖6.3二叉樹的基本形態(tài)；2：二叉樹的五個(gè)性質(zhì)；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：16 學(xué)時(shí)：2章 節(jié)第6章 樹和二叉樹：6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)、6.3.1 遍歷二叉樹；教學(xué)目的和教學(xué)要求熟練掌握二叉樹的兩種存儲(chǔ)結(jié)構(gòu)；熟練掌握二

51、叉樹的三種遍歷方法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：二叉樹的兩種存儲(chǔ)結(jié)構(gòu)、二叉樹的三種遍歷方法； 教學(xué)難點(diǎn)：二叉樹的三種遍歷方法； 教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹的結(jié)構(gòu)是非線性的， 每一結(jié)點(diǎn)最多可有兩個(gè)后繼。 二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種： 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 1： 順序存儲(chǔ)結(jié)構(gòu)2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)于任意的二叉樹來(lái)說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、 左孩子域和右孩子： 二叉樹的遍歷三種遍歷方法的遞歸定義。 先序遍歷（DLR）操作過程： 若二叉樹為空， 則空操作， 否則依次

52、執(zhí)行如下3個(gè)操作： (1) 訪問根結(jié)點(diǎn)； (2) 按先序遍歷左子樹； (3) 按先序遍歷右子樹。 中序遍歷（LDR）操作過程： 若二叉樹為空， 則空操作， 否則依次執(zhí)行如下3個(gè)操作： (1) 按中序遍歷左子樹； (2) 訪問根結(jié)點(diǎn)； (3) 按中序遍歷右子樹。 后序遍歷（LRD）操作過程： 若二叉樹為空， 則空操作， 否則依次執(zhí)行如下3個(gè)操作： (1) 按后序遍歷左子樹； (2) 按后序遍歷右子樹； (3) 訪問根結(jié)點(diǎn)。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：對(duì)一些特殊樣式的二叉樹進(jìn)行順序存儲(chǔ)；2：對(duì)二叉樹進(jìn)行三種遍歷操作；課后自我總結(jié)分析備注教案（分教案）

53、課次：17 學(xué)時(shí)：2章 節(jié)第6章 6.4 樹和森林：6.4.1 樹的存儲(chǔ)結(jié)構(gòu)、6.4.2 森林與二叉樹的轉(zhuǎn)換、6.4.3 樹和森林的遍歷教學(xué)目的和教學(xué)要求熟練掌握樹的三種存儲(chǔ)結(jié)構(gòu)；熟練掌握森林與二叉樹的轉(zhuǎn)換；熟練掌握樹和森林的遍歷；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：樹的三種存儲(chǔ)結(jié)構(gòu)、森林與二叉樹的轉(zhuǎn)換； 教學(xué)難點(diǎn)：樹和森林的遍歷； 教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：6.4 樹和森林6.4.1 樹的存儲(chǔ)結(jié)構(gòu)樹的主要存儲(chǔ)方法有以下三種： 雙親表示法、2. 孩子表示法、3. 孩子兄弟表示法6.4.2 森林與二叉樹的轉(zhuǎn)換 1. 樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是： (

54、1) 樹中所有相鄰兄弟之間加一條連線。 (2) 對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線， 刪去其與其它孩子結(jié)點(diǎn)之間的連線。 (3) 以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度， 使之結(jié)構(gòu)層次分明。2. 森林轉(zhuǎn)換為二叉樹 森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹， 森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下： （1） 將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 （2） 第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子， 當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹

55、。3. 二叉樹還原為樹或森林6.4.3 樹的遍歷 1. 樹的遍歷：樹的遍歷方法主要有以下兩種： 1） 先根遍歷、2） 后根遍歷2. 森林的遍歷：森林的遍歷方法主要有以下三種： 1） 先序遍歷、2） 中序遍歷、3） 后序遍歷教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：把樹用三種方法存儲(chǔ)；2：把樹和森林與二叉樹進(jìn)行相互轉(zhuǎn)換；3：對(duì)樹和森林進(jìn)行遍歷；課后自我總結(jié)分析備注教案（分教案）課次：18 學(xué)時(shí)：2章 節(jié)第6章6.6 赫夫曼樹及其應(yīng)用、6.6.1 最優(yōu)二叉樹（赫夫曼樹）、6.6.2 赫夫曼編碼教學(xué)目的和教學(xué)要求熟練掌握哈夫曼樹的構(gòu)造方法；熟練掌握哈夫曼編碼的編碼方

56、法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：哈夫曼樹的構(gòu)造方法； 教學(xué)難點(diǎn)：哈夫曼編碼的編碼方法； 教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：6.6 赫夫曼樹及其應(yīng)用 6.6.1 最優(yōu)二叉樹 1. 路徑和路徑長(zhǎng)度2. 結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度3. 樹的帶權(quán)路徑長(zhǎng)度構(gòu)造赫夫曼算法的步驟如下： （1）用給定的n個(gè)權(quán)值w1, w2, , wn對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森林F=T1, T2, , Tn，其中每一棵二叉樹Ti(1in)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空。 （2）在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左

57、右子樹的根結(jié)點(diǎn)權(quán)值之和。 （3）從F中刪除被選中的那兩棵二叉樹， 同時(shí)把新構(gòu)成的二叉樹加入到森林F中。 （4）重復(fù)（2）、（3）操作， 直到森林中只含有一棵二叉樹為止， 此時(shí)得到的這棵二叉樹就是赫夫曼樹。6.6.2 赫夫曼編碼前綴編碼：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，可利用二叉樹設(shè)計(jì)前綴編碼。6.6.3 赫夫曼編碼算法的實(shí)現(xiàn)教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：構(gòu)造哈夫曼樹；2：生成哈夫曼編碼；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 范策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)出版社， 2004數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）， 嚴(yán)蔚敏等編著， 清華大學(xué)出版社

58、 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結(jié)分析備注教案（分教案）課次：19 學(xué)時(shí)：2章 節(jié)綜合習(xí)題（三）：樹與二叉樹的相關(guān)內(nèi)容；教學(xué)目的和教學(xué)要求要求熟練掌握樹、二叉樹、森林的相關(guān)存儲(chǔ)、遍歷、轉(zhuǎn)換的知識(shí)；能夠構(gòu)造哈夫曼樹、哈夫曼編碼；教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：1：已知某二叉樹的先序遍歷和中序遍歷分別為：先序：18 14 7 3 11 22 35 27中序：3 7 11 14 18 22 27 35；求該二叉樹。2：已知某二叉樹的先序遍歷和中序遍歷分別為：先序：E B A D C F H G I K J中

59、序：A B C D E F G H I J K；畫出該二叉樹。3已知某樹的先根遍歷和后根遍歷分別為：先根：G F K D A I E B C H J后根：D I A E K F C J H B G、畫出該樹。4：數(shù)據(jù)傳輸中的二進(jìn)制編碼：要傳送數(shù)據(jù)state、seat、act、tea、cat、set、a、eat；如何使傳送的長(zhǎng)度最短。（構(gòu)造哈夫曼樹、求出各個(gè)數(shù)據(jù)的哈夫曼編碼。）5：假設(shè)有一臺(tái)機(jī)器共有7種不同的指令，其使用頻率如表所示：求出各個(gè)指令的哈夫曼編碼。6：求出滿足下列條件的所有二叉樹：1：先序和后序相同；2：中序和后序相同；3：先序和中序相同；7：假設(shè)用于用于通訊的電文由8個(gè)字母組成，字

60、母在電文中出現(xiàn)的頻率分別為： 0.07、0.19、0.02、0.06 0.32、0.03、0.21、0.10；請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。8：畫出和下列數(shù)對(duì)應(yīng)的二叉樹：9：已知某二叉樹的先序建立時(shí)讀入的數(shù)據(jù)為：A B C D E F G H ；請(qǐng)求出該二叉樹。課后自我總結(jié)分析教案（分教案）課次：20 學(xué)時(shí)：2章 節(jié)第7章 圖：7.1 圖的定義和術(shù)語(yǔ)教學(xué)目的和教學(xué)要求熟練掌握和理解有關(guān)圖的各種定義和術(shù)語(yǔ)；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：圖的各種定義和術(shù)語(yǔ)； 教學(xué)難點(diǎn)：圖的生成樹、圖的連通性； 教學(xué)進(jìn)程（含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段）教學(xué)進(jìn)程：7.1 圖的定義與基本術(shù)語(yǔ) 7.1.1