《《大數(shù)據(jù)結(jié)構(gòu)》教案設(shè)計(jì)》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》教案設(shè)計(jì)（42頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word課程簡(jiǎn)介人們?cè)谶\(yùn)用程序設(shè)計(jì)語(yǔ)言編寫程序的過(guò)程中發(fā)現(xiàn)所有的數(shù)據(jù)都可以抽象為三種結(jié)構(gòu)，而對(duì)這些數(shù)據(jù)的所有操作都可以轉(zhuǎn)化為對(duì)這三種數(shù)據(jù)的幾種根本操作，而大多數(shù)的程序設(shè)計(jì)技巧都可以抽象為一些最根本的算法。于是人們逐步開(kāi)展了一門稱為數(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è)的核心根底課程之一。數(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à)的分析也要求有一定程度的了解和掌握。通過(guò)本課程的學(xué)習(xí)，使學(xué)生透徹地理解各種數(shù)據(jù)對(duì)象的特

2、點(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)要求逐步熟悉鏈表的表示，通過(guò)模仿實(shí)驗(yàn)教程中的例子，掌握編程技巧。強(qiáng)調(diào)類 C語(yǔ)言的書(shū)寫規(guī)X，特別注意參數(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)： 樹(shù)、二叉樹(shù)、圖。掌握它們的定義和特點(diǎn)

3、、表示和實(shí)現(xiàn)，特別注意與根本數(shù)據(jù)結(jié)構(gòu)的區(qū)別，掌握各種遍歷的遞歸和非遞歸算法，能熟練完成以下的應(yīng)用：最優(yōu)樹(shù)、Huffman編碼、拓?fù)渑判?、關(guān)鍵路徑和最短路徑問(wèn)題。 3數(shù)據(jù)結(jié)構(gòu)的應(yīng)用： 查找和內(nèi)部排序。熟練掌握靜態(tài)查找表的查找方法和實(shí)現(xiàn)，了解哈希表的構(gòu)造和查找方法。掌握各種內(nèi)部排序方法的根本思想、算法特點(diǎn)、排序過(guò)程以與它們的時(shí)間復(fù)雜度分析。42 / 42數(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)的綜合性課程，在計(jì)

4、算機(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è)根底課程，介紹計(jì)算機(jī)領(lǐng)域的常用數(shù)據(jù)結(jié)構(gòu)以與各種查找和排序的算法，是計(jì)算機(jī)專業(yè)學(xué)生必修的一門技術(shù)根底課程，也是計(jì)算機(jī)專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)根底課，主要解決數(shù)據(jù)的表示和數(shù)據(jù)的處理，系統(tǒng)介紹三大數(shù)據(jù)結(jié)構(gòu)與其實(shí)現(xiàn)，為操作系統(tǒng)等課程提供必要的知識(shí)根底，為計(jì)算機(jī)人員提供必要的根本技能。二、課程教學(xué)根本要求本課程介紹常用數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)其施加的運(yùn)算，如：線性表、棧、隊(duì)列、串、數(shù)

5、組、廣義表、樹(shù)、圖等。同時(shí)還介紹各種查找和排序的算法。通過(guò)本門課程的學(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í)各種分析問(wèn)題和解決問(wèn)題的能力。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ù)據(jù)元

6、素、數(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é)要求：理解棧和隊(duì)列的

7、定義、特點(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)過(guò)程。第五章：多維數(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ǔ)方法。 第六章：樹(shù)6.1 樹(shù)的定義和根本術(shù)語(yǔ)6.2 二叉樹(shù)6.2.1 二叉樹(shù)的

8、定義6.2.2 二叉樹(shù)的性質(zhì)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)6.3.1 遍歷二叉樹(shù)6.4 樹(shù)和森林6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4.2 森林與二叉樹(shù)的轉(zhuǎn)換6.4.3 樹(shù)和森林的遍歷6.6 赫夫曼樹(shù)與其應(yīng)用6.6.1 最優(yōu)二叉樹(shù)赫夫曼樹(shù)6.6.2 赫夫曼編碼教學(xué)要求：理解樹(shù)型結(jié)構(gòu)的概念和術(shù)語(yǔ)，領(lǐng)會(huì)二叉樹(shù)的定義、形態(tài)、性質(zhì)和存儲(chǔ)結(jié)構(gòu)，掌握二叉樹(shù)的各種遍歷算法極其實(shí)現(xiàn)過(guò)程，了解樹(shù)和森林與其相互轉(zhuǎn)換；掌握哈夫曼樹(shù)極其應(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 圖的遍歷7.3.

9、1 深度優(yōu)先搜索7.3.2 廣度優(yōu)先搜索7.4 圖的連通性問(wèn)題7.4.1 無(wú)向圖的連通分量和生成樹(shù)7.4.3 最小生成樹(shù)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)的過(guò)程，學(xué)會(huì)圖在最小生成樹(shù)、拓?fù)渑判颉⒆疃搪窂?、關(guān)鍵路徑中的應(yīng)用。第九章：查找9.1 靜態(tài)查找表9.1.1 順序表的查找9.1.2 有序表的查找9.1.4 索引順序表的查找9.3 哈希表9.3.1 什么是哈希表9.3.2 哈

10、希函數(shù)的構(gòu)造方法9.3.3 處理沖突的方法教學(xué)要求：掌握查找表的定義和分類，熟練掌握順序查找和二分查找的思想，了解二叉排序樹(shù)與其查找，了解散列查找的思想和有關(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)單項(xiàng)選擇擇排序10.5 歸并排序教學(xué)要求：熟練掌握各種排序方法的思想和特點(diǎn)，如：插入排序、交換排序、選擇排序、分配排序等，學(xué)會(huì)分析它們的優(yōu)點(diǎn)和缺點(diǎn)以與時(shí)空性能，并學(xué)會(huì)選擇和應(yīng)用各種排序方法解決實(shí)際問(wèn)題。四、學(xué)時(shí)分配章節(jié)內(nèi)容講授學(xué)時(shí)上機(jī)學(xué)時(shí)習(xí)題學(xué)時(shí)

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

12、等教育，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ū)ο蟮耐緩?，X乃孝，裘宗燕，高等教育，2001數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅcC+描述，殷人昆等清華大學(xué)算法設(shè)計(jì)與分析，梁田貴，X鵬編著，冶金工業(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í)間 教案編寫時(shí)間課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼總學(xué)時(shí)講課： 學(xué)時(shí)上機(jī)： 學(xué)時(shí)實(shí)習(xí)： 周學(xué) 分課程性質(zhì)必修課 選修課 理論課 實(shí)驗(yàn)課 任

13、課教師職稱授課對(duì)象專業(yè)： 年級(jí)： 班級(jí)： 教材和主要參考資料選用教材：數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏編著清華大學(xué)主要參考書(shū)：算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004數(shù)據(jù)結(jié)構(gòu)實(shí)用教程第二版，徐孝凱編著，清華大學(xué) 2006數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實(shí)用教程第二版，徐孝凱，清華大學(xué) 2003數(shù)據(jù)結(jié)構(gòu)，謝楚屏等，人民郵電，2001算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述，X乃孝等，高等教育，2002數(shù)據(jù)結(jié)構(gòu)，殷人昆，清華大學(xué)，2001計(jì)算機(jī)算法設(shè)計(jì)與分析，蘇德富，電子工業(yè)，2001算法與

14、數(shù)據(jù)結(jié)構(gòu)，傅清祥，王嘵冬，電子工業(yè)，1998數(shù)據(jù)結(jié)構(gòu)C+與面向?qū)ο蟮耐緩?，X乃孝，裘宗燕，高等教育，2001數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅcC+描述，殷人昆等清華大學(xué)算法設(shè)計(jì)與分析，梁田貴，X鵬編著，冶金工業(yè)，2004教學(xué)目的和教學(xué)要求通過(guò)本門課程的學(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í)各種分析問(wèn)題和解決問(wèn)題的能力。3 掌握各種算法的時(shí)空效率的分析方法，學(xué)會(huì)在實(shí)際應(yīng)用中選擇適宜的算法。4 掌握各種查找和排序的算法以與效率，并將其

15、應(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ù)組、廣義表、樹(shù)、圖等。應(yīng)掌握各種查找和排序的算法。難點(diǎn)章節(jié)：第六章：樹(shù)和第七章：圖。教學(xué)進(jìn)程第1次課第2次課第3次課第4次課第5次課第6次課第7次課第8次課第9次課第10次課第11次課第12次課第13次課第14次課第15次課第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)與

16、實(shí)現(xiàn)1.4 算法和算法分析第2章 線性表：2.1 線性表的類型定義2.2 線性表的順序表示第2章 ：2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1第2章 ：2.3 22.4 一元多項(xiàng)式的表示與相加第3章 棧和隊(duì)列第3章 棧和隊(duì)列第3章 棧和隊(duì)列綜合習(xí)題課1：前3章的相關(guān)內(nèi)容綜合實(shí)驗(yàn)課1：前3章的相關(guān)內(nèi)容第4章 串第5章 數(shù)組和廣義表第5章 數(shù)組和廣義表綜合實(shí)驗(yàn)課2：第4-5章的相關(guān)內(nèi)容第6章 樹(shù)和二叉樹(shù)第6章 樹(shù)和二叉樹(shù)第6章 樹(shù)和二叉樹(shù)第6章 樹(shù)和二叉樹(shù)：綜合習(xí)題課2：樹(shù)的相關(guān)內(nèi)容第7章 圖第7章 圖第7章 圖第7章 圖：綜合習(xí)題課3：圖的相關(guān)內(nèi)容第9章 查找綜合實(shí)驗(yàn)課3：第9章的相關(guān)內(nèi)容第10章 內(nèi)部排

17、序第10章 內(nèi)部排序綜合習(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ù)

18、值計(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ù)Data2. 數(shù)據(jù)元素Data Element3. 數(shù)據(jù)對(duì)象Data Object4. 結(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é)方法、課堂講解、例題演示，課

19、件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)圖1.5：要求理解和掌握四類根本的數(shù)據(jù)關(guān)系；并在日常生活中舉例進(jìn)展說(shuō)明。主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，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é)重點(diǎn)： 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；算法、算法要求；

20、教學(xué)難點(diǎn)： 算法效率的度量與有效的分析；教學(xué)進(jìn)程含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jì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ī)如此的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。) 是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。2. 算法的特性3. 算法設(shè)計(jì)的要求算法的正確性 (1) 所設(shè)計(jì)的程序沒(méi)有語(yǔ)法錯(cuò)誤； (2) 所設(shè)計(jì)的程序?qū)?/p>

21、于幾組輸入數(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é)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)1:圖1.5、P13：算法的5個(gè)特征；2:P15：兩段程序的語(yǔ)句的頻度的分析主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高

22、等教育，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è)被稱為“第一個(gè)的數(shù)據(jù)元素； 存在唯一的一個(gè)被稱為“最后一個(gè)的數(shù)據(jù)元素； 除第一個(gè)元素之外，集合中的每個(gè)元素均只有一個(gè)前驅(qū)； 除最后一個(gè)元素之外，集合中的每個(gè)元素

23、均只有一個(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. 刪除操作教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：4 學(xué)時(shí)：2章 節(jié)第2章 ：2

24、.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)程含章節(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é)

25、方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：5 學(xué)時(shí)：2章 節(jié)第2章 ：2.3 22.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)式的表示與相加的方

26、法與算法；教學(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. 雙向鏈表的前插操作2. 雙向鏈表的刪除操作2.3.6 順序表和鏈表的比擬1. 基于空間的考慮、2. 基于時(shí)間的考慮、3. 基于語(yǔ)言的考慮2.4 一元多項(xiàng)式的表示與相加教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等

27、教育，2004課后自我總結(jié)分析備注教案分教案課次：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):(1) 初始化、(2) 取棧頂元素、(3) 入棧、(4) 出棧2. 鏈棧3.2 棧的應(yīng)用舉例1. 數(shù)制轉(zhuǎn)換教學(xué)方法、課

28、堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：7 學(xué)時(shí)：2章 節(jié)第3章 棧和隊(duì)列：3.2.4 迷宮求解、3.3 棧與遞歸的實(shí)現(xiàn)教學(xué)目的和教學(xué)要求了解迷宮求解的算法思路、了解計(jì)算機(jī)圖形學(xué)中的種子填充蘇算法；掌握漢諾塔算法與其過(guò)程。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 迷宮求解的算法思路、漢諾塔算法與其過(guò)程；教學(xué)難點(diǎn)： 漢諾塔算法與其過(guò)程；教學(xué)進(jìn)程含章節(jié)教

29、學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jìn)程：4. 迷宮求解拓展：填充算法3.3 棧與遞歸的實(shí)現(xiàn)1. 遞歸特性問(wèn)題1) 遞歸函數(shù) 2漢諾塔算法三個(gè)盤子搬動(dòng)時(shí)hanoi(3, A, B, C) 遞歸調(diào)用過(guò)程：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 move(B-c) 2號(hào)搬到C hanoi(1,A,B,C) move(A-C

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

31、含章節(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ì)操作：循環(huán)隊(duì)列如何區(qū)分隊(duì)列“空和“滿1. 另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列是空還是滿；2. 少用一個(gè)元素空間，當(dāng)隊(duì)列頭指針在隊(duì)列尾指針的下一個(gè)位置上時(shí)為“滿。當(dāng)時(shí)隊(duì)空；時(shí)隊(duì)滿循

32、環(huán)隊(duì)列滿足條件 (Q.rear+1)%MAXQSIZE= Q.front 隊(duì)滿教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)1：圖3.8、圖3.10、圖3.11、圖3.14；2：P62：隊(duì)列的根本操作算法、P64：循環(huán)隊(duì)列的根本操作算法；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：9 學(xué)時(shí)：2章 節(jié)綜合習(xí)題課1：前3章的相關(guān)內(nèi)容教學(xué)目的和教學(xué)要求要求掌握棧的應(yīng)用與遞歸算法教

33、學(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：種子填充算法的具體過(guò)程：四向連通填充算法：a種子像素壓入棧中；b如果棧為空，如此轉(zhuǎn)e)；否如此轉(zhuǎn)c)；c彈出一個(gè)像素，并將該像素置成填充色；并判斷該像素相鄰的四連通像素是否為邊界色或已經(jīng)置成多邊形的填充色，假如不是，如此將該像素壓入棧；d轉(zhuǎn)b；e完畢。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C

34、語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，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)程含章節(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 ssi

35、ze;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)：); 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é)方法、課堂講解、例題演示，課件演示

36、輔助手段：電腦、投影儀、教科書(shū)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析教案分教案課次：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)

37、：求子串位置的定位函數(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 定長(zhǎng)順序存儲(chǔ)表示串1.串聯(lián)接Concat(& T , S1, S2)2. 求子串SubString ( & Sub , S , pos , len )串的塊鏈存儲(chǔ)表示4.3 串的模式匹配算法4.3.1 求子串位置的定位函數(shù) Index( S, T ,pos)int Index SString S, SString T, int pos /返回子串T在主串中第

38、 pos個(gè)字符之后的位置。如不存在，如此函數(shù)值為0。其中：T 非空，1=pos=Strlength( S )。 i = pos ; j = 1 ; while ( i=S 0 & j T 0 ) return i - T 0 ; else return 0 ; / Index 算法：教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)1：P73：串的操作；圖4.1；2：算法4.5：串的模式匹配算法、圖4.3；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊

39、冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：12 學(xué)時(shí)：2章 節(jié)第5章 數(shù)組和廣義表：5.1 數(shù)組的定義、5.2 數(shù)組的順序表示和實(shí)現(xiàn)教學(xué)目的和教學(xué)要求掌握數(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ù)組一般不做

40、插入和刪除操作，因此采用順序存儲(chǔ)結(jié)構(gòu)。由于存儲(chǔ)單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，如此用一組連續(xù)存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問(wèn)題。數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：一種是按行序存儲(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，, dn)，我們只要把上式推廣，就可以容易地得到維數(shù)組中任意元素aj1j2jn的存儲(chǔ)地址的計(jì)算公式: LOC(aj1j2jn)=LOC(a000)+(b2*b3*bn*j1+b3*bn*j2+bn*jn-1+jn)*lL

41、OC(aj1j2jn)= LOC(a000)+( = LOC(a000)+其中 =L,ci-1=bi*ci教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)計(jì)算1-3維數(shù)組的任意元素的存儲(chǔ)地址；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：13 學(xué)時(shí)：2章 節(jié)第5章 數(shù)組和廣義表：5.3 矩陣的壓縮存儲(chǔ) 5.3.1 特殊矩陣、5.3.2 稀疏矩陣教學(xué)目的和教學(xué)要求掌握特殊矩陣和稀

42、疏矩陣的存儲(chǔ)方法；掌握稀疏矩陣的轉(zhuǎn)置算法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 特殊矩陣和稀疏矩陣的存儲(chǔ)方法；稀疏矩陣的轉(zhuǎn)置算法；教學(xué)難點(diǎn)：稀疏矩陣的轉(zhuǎn)置算法；教學(xué)進(jìn)程含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jìn)程：5.3 矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ)：為多個(gè)值一樣的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配空間。特殊矩陣：值一樣的元素或零元素在矩陣中的分布有一定的規(guī)律。稀疏矩陣：矩陣中元素分布沒(méi)有規(guī)律，但零元素較多。5.3.1 特殊矩陣三角矩陣大體分為三類：下三角矩陣、上三角矩陣和對(duì)稱矩陣Loci, j=Loc1, 1+i(i-1)/2+j-1帶狀矩陣5.3.2 稀疏矩陣方法一：按照中三元組的次序依次在

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

44、現(xiàn)串的模式匹配算法、稀疏矩陣的兩個(gè)轉(zhuǎn)置算法；教學(xué)進(jìn)程含章節(jié)教學(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(抱歉,沒(méi)有找到!n);#include stdio.h#define mu 3#define nu 8#define tu 8void main(

45、) int M83=1,2,12,1,3,9,3,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í)，該集合滿

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

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

48、 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的三種遍歷方法； 教學(xué)難點(diǎn)：二叉樹(shù)的三種遍歷方法； 教學(xué)進(jìn)程含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jìn)程：6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。二叉樹(shù)的存儲(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ì)于任意的二叉樹(shù)來(lái)說(shuō)，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子：6.3.1 二叉樹(shù)的遍歷三種遍歷方法的遞歸定義。 先序遍歷DLR操作過(guò)程：假如二叉樹(shù)為空，如此空操作，否如此依次執(zhí)行如下3個(gè)操作： (1) 訪問(wèn)根結(jié)點(diǎn)

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

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

51、中的每個(gè)結(jié)點(diǎn)，只保存其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。 (3) 以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次清楚。2. 森林轉(zhuǎn)換為二叉樹(shù)森林是假如干棵樹(shù)的集合。樹(shù)可以轉(zhuǎn)換為二叉樹(shù)，森林同樣也可以轉(zhuǎn)換為二叉樹(shù)。因此，森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹(shù)的方法如下：1將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。2第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。3. 二叉樹(shù)復(fù)原為樹(shù)或森林6.4.3 樹(shù)的遍歷1. 樹(shù)的遍歷：樹(shù)的遍歷方法主要有以下兩種： 1先根遍歷、2后根遍歷2. 森林的遍歷：森林的遍歷方法主要有以下三種：1先序遍歷、2中序遍歷、3后序遍歷教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書(shū)作業(yè)1：把樹(shù)用三種方法存儲(chǔ)；2：把樹(shù)和森林與二叉樹(shù)進(jìn)展相互轉(zhuǎn)換；3：對(duì)樹(shù)和森林進(jìn)展遍歷；課后自我總結(jié)分析備注教案分教案課次：18 學(xué)時(shí)：2章 節(jié)第6章6.6 赫夫曼樹(shù)與其應(yīng)用、6.6.1 最優(yōu)二叉樹(shù)赫夫曼樹(shù)、6.6.2 赫夫曼編碼教學(xué)目的和教學(xué)要求熟練掌握哈夫