word課程簡介人們在運(yùn)用程序設(shè)計(jì)語言編寫程序的過程中發(fā)現(xiàn)所有的數(shù)據(jù)都可以抽象為三種結(jié)構(gòu)，而對這些數(shù)據(jù)的所有操作都可以轉(zhuǎn)化為對這三種數(shù)據(jù)的幾種根本操作，而大多數(shù)的程序設(shè)計(jì)技巧都可以抽象為一些最根本的算法。于是人們逐步開展了一門稱為數(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ī)處理的對象，本課程研究的數(shù)據(jù)是非數(shù)值性、結(jié)構(gòu)性的數(shù)據(jù)。學(xué)習(xí)本課程要求掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、計(jì)算機(jī)內(nèi)的表示方法，以與處理數(shù)據(jù)的算法，對于算法所花費(fèi)的時(shí)間和空間代價(jià)的分析也要求有一定程度的了解和掌握。通過本課程的學(xué)習(xí)，使學(xué)生透徹地理解各種數(shù)據(jù)對象的特點(diǎn)，學(xué)會數(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)，對靜態(tài)結(jié)構(gòu)要求非常熟練的編程上機(jī)實(shí)現(xiàn)，對動態(tài)結(jié)構(gòu)要求逐步熟悉鏈表的表示，通過模仿實(shí)驗(yàn)教程中的例子，掌握編程技巧。強(qiáng)調(diào)類 C語言的書寫規(guī)X，特別注意參數(shù)的區(qū)別，輸入輸出的方式和錯(cuò)誤處理方式，以與抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。能熟練完成以下的應(yīng)用：多項(xiàng)式的計(jì)算、語法檢查、回朔算法、遞歸算法、表達(dá)式求值、離散事件模擬、文字的編輯和稀疏矩陣進(jìn)展矩陣運(yùn)算采用的處理方法。2復(fù)雜數(shù)據(jù)結(jié)構(gòu)： 樹、二叉樹、圖。掌握它們的定義和特點(diǎn)、表示和實(shí)現(xiàn)，特別注意與根本數(shù)據(jù)結(jié)構(gòu)的區(qū)別，掌握各種遍歷的遞歸和非遞歸算法，能熟練完成以下的應(yīng)用：最優(yōu)樹、Huffman編碼、拓?fù)渑判颉㈥P(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ù)雜度分析。42 / 42數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)課程編號：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ì)算機(jī)學(xué)科教學(xué)中具有十分重要的作用。大力加強(qiáng)數(shù)據(jù)結(jié)構(gòu)課程的建設(shè)，提高數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)質(zhì)量，有利于教學(xué)改革和教育創(chuàng)新，有利于高級應(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)等課程提供必要的知識根底，為計(jì)算機(jī)人員提供必要的根本技能。二、課程教學(xué)根本要求本課程介紹常用數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對其施加的運(yùn)算，如：線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹、圖等。同時(shí)還介紹各種查找和排序的算法。通過本門課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握以下幾個(gè)方面的知識：1：系統(tǒng)學(xué)習(xí)常用根本數(shù)據(jù)結(jié)構(gòu)與其在不同存儲方式下的實(shí)現(xiàn)，掌握分析、選擇不同的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)的原如此和方法。2：學(xué)習(xí)和掌握在各種存儲結(jié)構(gòu)上實(shí)現(xiàn)的各種算法與其設(shè)計(jì)思想，從而學(xué)習(xí)各種分析問題和解決問題的能力。3：掌握各種算法的時(shí)空效率的分析方法，學(xué)會在實(shí)際應(yīng)用中選擇適宜的算法。4：掌握各種查找和排序的算法以與效率，并將其應(yīng)用在程序設(shè)計(jì)中。三、課程教學(xué)內(nèi)容體系第一章：概論1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 根本概念和術(shù)語1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實(shí)現(xiàn)1.4 算法和算法分析教學(xué)要求：理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的概念；掌握邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系；理解算法的根本概念；學(xué)會分析算法的時(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)，掌握在這兩種存儲結(jié)構(gòu)上各種根本運(yùn)算的實(shí)現(xiàn)算法以與效率的分析，并學(xué)習(xí)在這兩種存儲結(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ì)列的定義、特點(diǎn)，學(xué)習(xí)它們的各種組織方式與算法；掌握它們的空和滿的判斷條件；并學(xué)會它們的簡單應(yīng)用。第四章：串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長順序存儲表示 4.2.3 串的塊鏈存儲表示4.3 串的模式匹配算法 4.3.1 求字串位置的定位函數(shù)教學(xué)要求：了解串的概念，掌握串的根本運(yùn)算，學(xué)習(xí)串運(yùn)算在不同存儲結(jié)構(gòu)下的實(shí)現(xiàn)過程。第五章：多維數(shù)組和廣義表5.1 數(shù)組的定義5.2 數(shù)組的順序表現(xiàn)和實(shí)現(xiàn)5.3 矩陣的壓縮存儲教學(xué)要求：領(lǐng)會數(shù)組的定義，數(shù)組的兩種順序存儲結(jié)構(gòu)，并領(lǐng)會幾種特殊矩陣和稀疏矩陣的壓縮存儲方法。 第六章：樹6.1 樹的定義和根本術(shù)語6.2 二叉樹6.2.1 二叉樹的定義6.2.2 二叉樹的性質(zhì)6.2.3 二叉樹的存儲結(jié)構(gòu)6.3 遍歷二叉樹和線索二叉樹6.3.1 遍歷二叉樹6.4 樹和森林6.4.1 樹的存儲結(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ù)語，領(lǐng)會二叉樹的定義、形態(tài)、性質(zhì)和存儲結(jié)構(gòu)，掌握二叉樹的各種遍歷算法極其實(shí)現(xiàn)過程，了解樹和森林與其相互轉(zhuǎn)換；掌握哈夫曼樹極其應(yīng)用。第七章：圖7.1 圖的定義和術(shù)語7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法7.2.2 鄰接表7.2.3 十字鏈表7.2.4 鄰接多重表7.3 圖的遍歷7.3.1 深度優(yōu)先搜索7.3.2 廣度優(yōu)先搜索7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹7.4.3 最小生成樹7.5 有向無環(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ù)語，掌握圖的鄰接矩陣和鄰接表兩種存儲形式，理解圖的遍歷的根本思想，掌握圖的兩種遍歷的方法和其實(shí)現(xiàn)的過程，學(xué)會圖在最小生成樹、拓?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 哈希函數(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 簡單項(xiàng)選擇擇排序10.5 歸并排序教學(xué)要求：熟練掌握各種排序方法的思想和特點(diǎn)，如：插入排序、交換排序、選擇排序、分配排序等，學(xué)會分析它們的優(yōu)點(diǎn)和缺點(diǎn)以與時(shí)空性能，并學(xué)會選擇和應(yīng)用各種排序方法解決實(shí)際問題。四、學(xué)時(shí)分配章節(jié)內(nèi)容講授學(xué)時(shí)上機(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語言版， X策等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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語言描述，X乃孝等，高等教育，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六、考核方法和成績評定標(biāo)準(zhǔn)根據(jù)教學(xué)要求進(jìn)展期末考試，由任課教師根據(jù)完成情況進(jìn)展評定，并最終結(jié)合平時(shí)成績的考核給出綜合成績。 制定：                                                                                                  制定日期：教案首頁 授課時(shí)間 教案編寫時(shí)間課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼總學(xué)時(shí)講課： 學(xué)時(shí)上機(jī)： 學(xué)時(shí)實(shí)習(xí)： 周學(xué) 分課程性質(zhì)必修課 選修課 理論課 實(shí)驗(yàn)課 任課教師職稱授課對象專業(yè)： 年級： 班級： 教材和主要參考資料選用教材：數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏編著清華大學(xué)主要參考書：算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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語言描述，X乃孝等，高等教育，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教學(xué)目的和教學(xué)要求通過本門課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握以下幾個(gè)方面的知識：1  系統(tǒng)學(xué)習(xí)常用根本數(shù)據(jù)結(jié)構(gòu)與其在不同存儲方式下的實(shí)現(xiàn)，掌握分析、選擇不同的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)的原如此和方法。2  學(xué)習(xí)和掌握在各種存儲結(jié)構(gòu)上實(shí)現(xiàn)的各種算法與其設(shè)計(jì)思想，從而學(xué)習(xí)各種分析問題和解決問題的能力。3  掌握各種算法的時(shí)空效率的分析方法，學(xué)會在實(shí)際應(yīng)用中選擇適宜的算法。4  掌握各種查找和排序的算法以與效率，并將其應(yīng)用在程序設(shè)計(jì)中。教學(xué)重點(diǎn)和教學(xué)難點(diǎn)重點(diǎn)掌握數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對其施加的運(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次課第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ù)語第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 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章 樹和二叉樹第6章 樹和二叉樹第6章 樹和二叉樹第6章 樹和二叉樹：綜合習(xí)題課2：樹的相關(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)部排序第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ù)語教學(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ù)語；掌握四類根本的數(shù)據(jù)關(guān)系。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語教學(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ù)值計(jì)算的處理工作。計(jì)算機(jī)加工處理的對象：數(shù)值，字符，表格，圖形聲音，圖象等具有一定結(jié)構(gòu)的數(shù)據(jù)。進(jìn)展程序設(shè)計(jì)時(shí)必須分析待處理的對象的特性與各對象之間存在的關(guān)系產(chǎn)生背景。1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 數(shù)據(jù)結(jié)構(gòu)的根本概念和術(shù)語1. 數(shù)據(jù)Data2. 數(shù)據(jù)元素Data Element3. 數(shù)據(jù)對象Data Object4. 結(jié)構(gòu)Data Structure存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (Abstract Data Type)ADT的定義格式不唯一, 我們采用下述格式定義一個(gè)ADT: ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象: <數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系: <結(jié)構(gòu)關(guān)系的定義>根本操作: <根本操作的定義> ADT 抽象數(shù)據(jù)類型名教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)圖1.5：要求理解和掌握四類根本的數(shù)據(jù)關(guān)系；并在日常生活中舉例進(jìn)展說明。主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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)；對算法、算法要求、算法效率的度量進(jìn)展有效的分析。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；算法、算法要求；教學(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ī)如此的有限集合，是為解決特定問題而規(guī)定的一系列操作。) 是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。2. 算法的特性3. 算法設(shè)計(jì)的要求算法的正確性 (1) 所設(shè)計(jì)的程序沒有語法錯(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高效率和低存儲量、算法、語言和程序的關(guān)系時(shí)間復(fù)雜度教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1:圖1.5、P13：算法的5個(gè)特征；2:P15：兩段程序的語句的頻度的分析主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，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è)元素均只有一個(gè)后繼。2.1 線性表的類型定義2.1.1 線性表的邏輯結(jié)構(gòu)2.1.2 線性表的抽象數(shù)據(jù)類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.2.1 線性表的順序存儲結(jié)構(gòu)2.2.2 線性表順序存儲結(jié)構(gòu)上的根本運(yùn)算1. 初始化操作 2. 插入操作 3. 刪除操作教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：4 學(xué)時(shí)：2章 節(jié)第2章 ：2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1教學(xué)目的和教學(xué)要求理解線性表的鏈表的特點(diǎn)，掌握在這種存儲結(jié)構(gòu)上各種根本運(yùn)算的實(shí)現(xiàn)算法以與效率的分析，并學(xué)習(xí)在這種存儲結(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)：單鏈表的插入、刪除、查找和歸并操作；教學(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)酱鎯Γ簣D2.6 單鏈表的邏輯狀態(tài)圖2.7 帶頭結(jié)點(diǎn)單鏈表圖示2.3.2 單鏈表上的根本運(yùn)算1. 建立單鏈表2. 查找3. 單鏈表插入操作4. 刪除5合并單鏈表：教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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)，掌握在這種存儲結(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. 雙向鏈表的前插操作2. 雙向鏈表的刪除操作2.3.6 順序表和鏈表的比擬1. 基于空間的考慮、2. 基于時(shí)間的考慮、3. 基于語言的考慮2.4 一元多項(xiàng)式的表示與相加教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：6 學(xué)時(shí)：2章 節(jié)第3章 棧和隊(duì)列：3.1 棧、3.2.1 數(shù)制轉(zhuǎn)換教學(xué)目的和教學(xué)要求理解棧的定義、特點(diǎn)，學(xué)習(xí)它的各種組織方式與算法；掌握它的空和滿的判斷條件；并學(xué)會它的簡單應(yīng)用。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 棧的定義、特點(diǎn)，學(xué)習(xí)它的各種組織方式與算法；教學(xué)難點(diǎ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é)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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é)中的種子填充蘇算法；掌握漢諾塔算法與其過程。教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 迷宮求解的算法思路、漢諾塔算法與其過程；教學(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è)盤子搬動時(shí)hanoi(3, A, B, C) 遞歸調(diào)用過程：hanoi(2,A,C,B): hanoi(1,A,B,C) move(A->C) 1號搬到C move(A->B) 2號搬到B hanoi(1,C,A,B) move(C->B) 1號搬到B move(A->c) 3號搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B->A) 1號搬到A move(B->c) 2號搬到C hanoi(1,A,B,C) move(A->C) 1號搬到C教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)2：算法3.5、種子填充算法、兩種算法求解n!主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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)程含章節(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ì)滿循環(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語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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)用與遞歸算法教學(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è)像素，并將該像素置成填充色；并判斷該像素相鄰的四連通像素是否為邊界色或已經(jīng)置成多邊形的填充色，假如不是，如此將該像素壓入棧；d轉(zhuǎn)b；e完畢。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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 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("請輸入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é)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析教案分教案課次：11 學(xué)時(shí)：2章 節(jié)第4章 串：4.1 串的定義、4.2.1 定長順序存儲表示 4.2.3 串的塊鏈存儲表示4.3.1 求子串位置的定位函數(shù)教學(xué)目的和教學(xué)要求掌握串的定義、定長順序存儲表示；了解串的塊鏈存儲表示；掌握求子串位置的定位函數(shù)模式匹配算法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 串的定義、定長順序存儲表示；串的塊鏈存儲表示；教學(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 定長順序存儲表示串1.串聯(lián)接Concat(& T , S1, S2)2. 求子串SubString ( & Sub , S , pos , len )串的塊鏈存儲表示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 ) if ( Si = = Tj) + i ; + j ; / 繼續(xù)比擬后續(xù)字符 else i = i j + 2 ; j = 1 ; / 指針后退重新開始匹配 if ( j> T 0 ) return i - T 0 ; else return 0 ; / Index 算法：教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：P73：串的操作；圖4.1；2：算法4.5：串的模式匹配算法、圖4.3；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，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ù)元素本身也是一種線性表。對于數(shù)組的操作一般只有兩類： (1獲得特定位置的元素值；(2修改特定位置的元素值。5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組一般不做插入和刪除操作，因此采用順序存儲結(jié)構(gòu)。由于存儲單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，如此用一組連續(xù)存儲單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定問題。數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，另一種是按列序存儲。Loci, j=Loc1, 1+n×(i-1)+(j-1)Loci, j, k=Loc1, 1, 1+(i-1)×m×n+(j-1)×n+(k-1)對于維數(shù)組A(c1d1, c2d2，, dn)，我們只要把上式推廣，就可以容易地得到維數(shù)組中任意元素aj1j2jn的存儲地址的計(jì)算公式: LOC(aj1j2jn)=LOC(a000)+(b2*b3*bn*j1+b3*bn*j2+bn*jn-1+jn)*lLOC(aj1j2jn)= LOC(a000)+( = LOC(a000)+其中 =L,ci-1=bi*ci教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)計(jì)算1-3維數(shù)組的任意元素的存儲地址；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：13 學(xué)時(shí)：2章 節(jié)第5章 數(shù)組和廣義表：5.3 矩陣的壓縮存儲 5.3.1 特殊矩陣、5.3.2 稀疏矩陣教學(xué)目的和教學(xué)要求掌握特殊矩陣和稀疏矩陣的存儲方法；掌握稀疏矩陣的轉(zhuǎn)置算法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)： 特殊矩陣和稀疏矩陣的存儲方法；稀疏矩陣的轉(zhuǎn)置算法；教學(xué)難點(diǎn)：稀疏矩陣的轉(zhuǎn)置算法；教學(xué)進(jìn)程含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jìn)程：5.3 矩陣的壓縮存儲壓縮存儲：為多個(gè)值一樣的元素只分配一個(gè)存儲空間，對零元素不分配空間。特殊矩陣：值一樣的元素或零元素在矩陣中的分布有一定的規(guī)律。稀疏矩陣：矩陣中元素分布沒有規(guī)律，但零元素較多。5.3.1 特殊矩陣三角矩陣大體分為三類：下三角矩陣、上三角矩陣和對稱矩陣Loci, j=Loc1, 1+i(i-1)/2+j-1帶狀矩陣5.3.2 稀疏矩陣方法一：按照中三元組的次序依次在中找到相應(yīng)的三元組進(jìn)展轉(zhuǎn)置。方法二：按照a.data 中三元組的次序進(jìn)展轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b 中的恰當(dāng)位置。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：下三角、對稱、帶狀矩陣的數(shù)據(jù)元素的下標(biāo)地址的計(jì)算方法；2：稀疏矩陣的兩個(gè)轉(zhuǎn)置算法；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(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í)現(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.h"void main() char sa7='a','b','c','d','e','f','g' char sb3='e','f','g'int i=0,j=0;while(i<=6 && j<=2) if(sai=sbj) +i;+j;else i=i-j+2; j=0;if(j>2) 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,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;j<=2;j+) printf(" %d ",Tij);printf("n");課后自我總結(jié)分析教案分教案課次：15 學(xué)時(shí)：2章 節(jié)第6章 樹：6.1 樹的定義和根本術(shù)語、6.2 二叉樹、6.2.1 二叉樹的定義、6.2.2 二叉樹的性質(zhì)；教學(xué)目的和教學(xué)要求熟練掌握樹的定義和根本術(shù)語、熟練掌握二叉樹的定義與二叉樹的性質(zhì)；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：樹的定義和根本術(shù)語、二叉樹的定義；教學(xué)難點(diǎn)：二叉樹的性質(zhì)；教學(xué)進(jìn)程含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jìn)程：6.1 樹的定義和根本術(shù)語樹是nn0個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n>0時(shí)，該集合滿足如下條件： (1) 其中必有一個(gè)稱為根root的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。 (2) 其余n-1個(gè)結(jié)點(diǎn)可以劃分成mm0個(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的位置序號分別與滿二叉樹的結(jié)點(diǎn)1n的位置序號一一對應(yīng)，如此為完全二叉樹。教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：圖6.3二叉樹的根本形態(tài)；2：二叉樹的五個(gè)性質(zhì)；主要參考資料算法與數(shù)據(jù)結(jié)構(gòu)C語言版， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004數(shù)據(jù)結(jié)構(gòu)C語言版， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，楊冬青，唐世渭，X銘，高等教育，2004課后自我總結(jié)分析備注教案分教案課次：16 學(xué)時(shí)：2章 節(jié)第6章樹和二叉樹：6.2.3 二叉樹的存儲結(jié)構(gòu)、6.3.1 遍歷二叉樹；教學(xué)目的和教學(xué)要求熟練掌握二叉樹的兩種存儲結(jié)構(gòu)；熟練掌握二叉樹的三種遍歷方法；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：二叉樹的兩種存儲結(jié)構(gòu)、二叉樹的三種遍歷方法； 教學(xué)難點(diǎn)：二叉樹的三種遍歷方法； 教學(xué)進(jìn)程含章節(jié)教學(xué)內(nèi)容、學(xué)時(shí)分配、教學(xué)方法、 輔助手段教學(xué)進(jìn)程：6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。二叉樹的存儲結(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1： 順序存儲結(jié)構(gòu)2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)對于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子：6.3.1 二叉樹的遍歷三種遍歷方法的遞歸定義。· 先序遍歷DLR操作過程：假如二叉樹為空，如此空操作，否如此依次執(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：對一些特殊樣式的二叉樹進(jìn)展順序存儲；2：對二叉樹進(jìn)展三種遍歷操作；課后自我總結(jié)分析備注教案分教案課次：17 學(xué)時(shí)：2章 節(jié)第6章 6.4 樹和森林：6.4.1 樹的存儲結(jié)構(gòu)、6.4.2 森林與二叉樹的轉(zhuǎn)換、6.4.3 樹和森林的遍歷教學(xué)目的和教學(xué)要求熟練掌握樹的三種存儲結(jié)構(gòu)；熟練掌握森林與二叉樹的轉(zhuǎn)換；熟練掌握樹和森林的遍歷；教學(xué)重 點(diǎn)難 點(diǎn)教學(xué)重點(diǎn)：樹的三種存儲結(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 樹的存儲結(jié)構(gòu)樹的主要存儲方法有以下三種：1. 雙親表示法、2. 孩子表示法、3. 孩子兄弟表示法6.4.2 森林與二叉樹的轉(zhuǎn)換1. 樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是： (1) 樹中所有相鄰兄弟之間加一條連線。 (2) 對樹中的每個(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第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。3. 二叉樹復(fù)原為樹或森林6.4.3 樹的遍歷1. 樹的遍歷：樹的遍歷方法主要有以下兩種： 1先根遍歷、2后根遍歷2. 森林的遍歷：森林的遍歷方法主要有以下三種：1先序遍歷、2中序遍歷、3后序遍歷教學(xué)方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1：把樹用三種方法存儲；2：把樹和森林與二叉樹進(jìn)展相互轉(zhuǎn)換；3：對樹和森林進(jìn)展遍歷；課后自我總結(jié)分析備注教案分教案課次：18 學(xué)時(shí)：2章 節(jié)第6章6.6 赫夫曼樹與其應(yīng)用、6.6.1 最優(yōu)二叉樹赫夫曼樹、6.6.2 赫夫曼編碼教學(xué)目的和教學(xué)要求熟練掌握哈夫