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

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

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

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

3、樹、圖。掌握它們的定義和特點、表示和實現(xiàn)，特別注意與根本數(shù)據(jù)結(jié)構(gòu)的區(qū)別，掌握各種遍歷的遞歸和非遞歸算法，能熟練完成以下的應(yīng)用：最優(yōu)樹、Huffman編碼、拓?fù)渑判?、關(guān)鍵路徑和最短路徑問題。 3．?dāng)?shù)據(jù)結(jié)構(gòu)的應(yīng)用： 查找和內(nèi)部排序。熟練掌握靜態(tài)查找表的查找方法和實現(xiàn)，了解哈希表的構(gòu)造和查找方法。掌握各種內(nèi)部排序方法的根本思想、算法特點、排序過程以與它們的時間復(fù)雜度分析。 42 / 42 《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱 課程名稱：數(shù)據(jù)結(jié)構(gòu) 課程編號：014100028 適用專業(yè)：計算機(jī)、信息管理 總學(xué)時數(shù)：60 學(xué)分?jǐn)?shù)：

4、 4 一、課程的性質(zhì)、目的與任務(wù) 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)技術(shù)、信息管理等專業(yè)的核心課程之一，是一門理論與工程實踐密切相關(guān)的綜合性課程，在計算機(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ī)專業(yè)的專業(yè)根底課程，介紹計算機(jī)領(lǐng)域的常用數(shù)據(jù)結(jié)構(gòu)以與各種查找和排序的算法，是計算機(jī)專業(yè)學(xué)生必修的一門技術(shù)根底課程，也是計算機(jī)專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的一門重要的專業(yè)根底課，主要解決數(shù)據(jù)的表示和數(shù)據(jù)的處理，系統(tǒng)介紹三大數(shù)據(jù)結(jié)構(gòu)與其實現(xiàn)，為操作系統(tǒng)等課程提供必要

5、的知識根底，為計算機(jī)人員提供必要的根本技能。二、課程教學(xué)根本要求 本課程介紹常用數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對其施加的運(yùn)算，如：線性表、棧、隊列、串、數(shù)組、廣義表、樹、圖等。同時還介紹各種查找和排序的算法。 通過本門課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握以下幾個方面的知識： 1：系統(tǒng)學(xué)習(xí)常用根本數(shù)據(jù)結(jié)構(gòu)與其在不同存儲方式下的實現(xiàn)，掌握分析、選擇不同的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)的原如此和方法。 2：學(xué)習(xí)和掌握在各種存儲結(jié)構(gòu)上實現(xiàn)的各種算法與其設(shè)計思想，從而學(xué)習(xí)各種分析問題和解決問題的能力。 3：掌握各種算法的時空效率的分析方法，學(xué)會在實際應(yīng)用中選擇適宜的算法。 4：掌握各種查找和排序的算法以與效率，

6、并將其應(yīng)用在程序設(shè)計中。三、課程教學(xué)內(nèi)容體系 第一章：概論 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 根本概念和術(shù)語 1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實現(xiàn) 1.4 算法和算法分析 教學(xué)要求：理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的概念；掌握邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系；理解算法的根本概念；學(xué)會分析算法的時間復(fù)雜性和空間復(fù)雜性。 第二章：線性表 2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)〔靜態(tài)查找表不講〕 2.4 一元多項式的表示與相加 教學(xué)要求：理解線性表的定義和特點；掌握順序表和鏈表的特點，掌握在這兩種存儲結(jié)構(gòu)上各種根本運(yùn)算的實現(xiàn)算法以與效率的分析

7、，并學(xué)習(xí)在這兩種存儲結(jié)構(gòu)上進(jìn)展算法設(shè)計的方法；以達(dá)到利用根本算法進(jìn)展較復(fù)雜算法設(shè)計的目的。 第三章：棧、隊列 3.1 棧 3.2 棧的應(yīng)有和舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.3.4 迷宮求解 3.3 棧與遞歸的實現(xiàn) 3.4 隊列 教學(xué)要求：理解棧和隊列的定義、特點，學(xué)習(xí)它們的各種組織方式與算法；掌握它們的空和滿的判斷條件；并學(xué)會它們的簡單應(yīng)用。 第四章：串 4.1 串類型的定義 4.2 串的表示和實現(xiàn) 4.2.1 定長順序存儲表示 4.2.3 串的塊鏈存儲表示 4.3 串的模式匹配算法 4.3.1 求字串位置的定位函數(shù) 教學(xué)要求：了解串的概念，

8、掌握串的根本運(yùn)算，學(xué)習(xí)串運(yùn)算在不同存儲結(jié)構(gòu)下的實現(xiàn)過程。 第五章：多維數(shù)組和廣義表 5.1 數(shù)組的定義 5.2 數(shù)組的順序表現(xiàn)和實現(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.

9、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)，掌握二叉樹的各種遍歷算法極其實現(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 無向圖的

10、連通分量和生成樹 　　7.4.3 最小生成樹 　　7.5 有向無環(huán)圖與其應(yīng)用 　　7.5.1 拓?fù)渑判? 　　7.5.2 關(guān)鍵路徑 7.6 最短路徑 　　7.6.1 從某個源點到其余各頂點的最短路徑 教學(xué)要求：理解圖型結(jié)構(gòu)的概念和術(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 什么是哈希

11、表 　　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 簡單項選擇擇排序 10.5 歸并排序 教學(xué)要求：熟練掌握各種排序方法的思想和特點，如：插入排序、交換排序、選擇排序、分配排序等，學(xué)會分析它們的優(yōu)點和缺點

12、以與時空性能，并學(xué)會選擇和應(yīng)用各種排序方法解決實際問題。 四、學(xué)時分配 章節(jié)內(nèi)容 講授學(xué)時 上機(jī)學(xué)時 習(xí)題學(xué)時 一 概論 4 0 0 二 線性表 6 1 1 三 棧、隊列 6 1 1 四 串 2 1 1 五 數(shù)組和廣義表 4 1 1 六 樹和二叉樹 8 1 1 七 圖 8 1 1 九 查找 2 1 1 十 內(nèi)部排序 4 1 1 總學(xué)時數(shù)：60課時 44 8 8 五、推薦教材與教學(xué)參考書 1. 教材 《數(shù)據(jù)結(jié)構(gòu)》；嚴(yán)蔚敏編著；清華大學(xué) 2. 教學(xué)參考書 《

13、算法與數(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)實用教程〔第二版〕》，徐孝凱編著，清華大學(xué) 2006 《數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實用教程〔第二版〕》，徐孝凱，清華大學(xué) 2003 《數(shù)據(jù)結(jié)構(gòu)》，謝楚屏等，人民郵電，2001 《算法與數(shù)據(jù)結(jié)構(gòu)－C語言描述》，X乃孝等，高等教育，2002 《數(shù)據(jù)結(jié)構(gòu)》，殷人昆，清華大學(xué)，2001 《計算機(jī)算法設(shè)計與分析》，蘇德富，電子工業(yè)，2001 《算法與數(shù)據(jù)結(jié)構(gòu)》，傅清祥，王嘵冬，電子工業(yè)，

14、1998 《數(shù)據(jù)結(jié)構(gòu)－C++與面向?qū)ο蟮耐緩健?，X乃孝，裘宗燕，高等教育，2001 《數(shù)據(jù)結(jié)構(gòu)－用面向?qū)ο蠓椒ㄅcC++描述》，殷人昆等清華大學(xué) 《算法設(shè)計與分析》，梁田貴，X鵬編著，冶金工業(yè)，2004 六、考核方法和成績評定標(biāo)準(zhǔn) 根據(jù)教學(xué)要求進(jìn)展期末考試，由任課教師根據(jù)完成情況進(jìn)展評定，并最終結(jié)合平時成績的考核給出綜合成績。 制定： ????????????????????????????????????????????????????????????????????

15、??????????????????????????????制定日期： 教案〔首頁〕 授課時間 教案編寫時間 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課程代碼 總學(xué)時 講課： 學(xué)時 上機(jī)： 學(xué)時 實習(xí)： 周 學(xué) 分 課程性質(zhì) 必修課〔√〕 選修課〔 〕 理論課〔√〕 實驗課〔 〕 任課教師 職稱 授課對象 專業(yè)： 年級： 　班級： 教材 和 主要參考資料 選用教材：《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏編著清華大學(xué) 主要參考

16、書： 《算法與數(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)實用教程〔第二版〕》，徐孝凱編著，清華大學(xué) 2006 《數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實用教程〔第二版〕》，徐孝凱，清華大學(xué) 2003 《數(shù)據(jù)結(jié)構(gòu)》，謝楚屏等，人民郵電，2001 《算法與數(shù)據(jù)結(jié)構(gòu)－C語言描述》，X乃孝等，高等教育，2002 《數(shù)據(jù)結(jié)構(gòu)》，殷人昆，清華大學(xué)，2001 《計算機(jī)算法設(shè)計與分析》，蘇德富，電子工業(yè)，2001 《算法與數(shù)據(jù)結(jié)構(gòu)》

17、，傅清祥，王嘵冬，電子工業(yè)，1998 《數(shù)據(jù)結(jié)構(gòu)－C++與面向?qū)ο蟮耐緩健?，X乃孝，裘宗燕，高等教育，2001 《數(shù)據(jù)結(jié)構(gòu)－用面向?qū)ο蠓椒ㄅcC++描述》，殷人昆等清華大學(xué) 《算法設(shè)計與分析》，梁田貴，X鵬編著，冶金工業(yè)，2004 教學(xué)目的和 教學(xué)要求 通過本門課程的學(xué)習(xí)，應(yīng)使學(xué)生掌握以下幾個方面的知識： 1．? 系統(tǒng)學(xué)習(xí)常用根本數(shù)據(jù)結(jié)構(gòu)與其在不同存儲方式下的實現(xiàn)，掌握分析、選擇不同的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)的原如此和方法。 2．? 學(xué)習(xí)和掌握在各種存儲結(jié)構(gòu)上實現(xiàn)的各種算法與其設(shè)計思想，從而學(xué)習(xí)各種分析問題和解決問題的能力。 3．? 掌握各種算法的時空效率的分析方法，學(xué)會在實

18、際應(yīng)用中選擇適宜的算法。 4．? 掌握各種查找和排序的算法以與效率，并將其應(yīng)用在程序設(shè)計中。 教學(xué)重點和 教學(xué)難點 重點掌握數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對其施加的運(yùn)算，如：線性表、棧、隊列、串、數(shù)組、廣義表、樹、圖等。應(yīng)掌握各種查找和排序的算法。 難點章節(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次課

19、 第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)與實現(xiàn)1.4 算法和算法分析 第2章 線性表：2.1 線性表的類型定義2.2 線性表的順序表示 第2章 ：2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)〔1〕 第2章 ：2.3 〔2〕2.4 一元多項式的表示與相加 第3章 棧和隊列 第3章 棧和隊列 第3章 棧和隊列 綜合習(xí)題課〔1〕：前3章的相關(guān)內(nèi)容 綜合實驗課〔1〕：前3章的相關(guān)內(nèi)容 第4章 串 第5

20、章 數(shù)組和廣義表 第5章 數(shù)組和廣義表 綜合實驗課〔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章 查找 綜合實驗課〔3〕：第9章的相關(guān)內(nèi)容 第10章 內(nèi)部排序 第10章 內(nèi)部排序 綜合習(xí)題課〔3〕：第9、10章的相關(guān)內(nèi)容 綜合實驗課〔4〕：第10章的相關(guān)內(nèi)容 學(xué) 時 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

21、 2 2 2 2 2 2 2 2 2 2 2 2 備 注 教案〔分教案〕 課次：1 學(xué)時：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é) 重 點 難 點 教學(xué)重點： 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念和術(shù)語 教學(xué)難點： 四類根本的數(shù)據(jù)關(guān)系 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 計算機(jī)的應(yīng)用不再局限于科學(xué)計算，更

22、多地用于控制，管理，數(shù)據(jù)處理等非數(shù)值計算的處理工作。計算機(jī)加工處理的對象：數(shù)值，字符，表格，圖形聲音，圖象等具有一定結(jié)構(gòu)的數(shù)據(jù)。進(jìn)展程序設(shè)計時必須分析待處理的對象的特性與各對象之間存在的關(guān)系———產(chǎn)生背景。 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)的根本概念和術(shù)語 1. 數(shù)據(jù)〔Data〕 2. 數(shù)據(jù)元素〔Data Element〕 3. 數(shù)據(jù)對象〔Data Object〕 4. 結(jié)構(gòu)〔Data Structure〕存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型 (Abstract Data Type) ADT的定義格式不唯一, 我們采用下述格式定義一個ADT:  ADT 抽象數(shù)據(jù)

23、類型名{ 數(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é)分析

24、 備注 教案〔分教案〕 課次：2 學(xué)時：2 章 節(jié) 第1章：1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實現(xiàn)1.4 算法和算法分析 教學(xué)目的 和 教學(xué)要求 理解抽象數(shù)據(jù)類型的表示與實現(xiàn)； 對算法、算法要求、算法效率的度量進(jìn)展有效的分析。 教　學(xué) 重 點 難 點 教學(xué)重點： 抽象數(shù)據(jù)類型的表示與實現(xiàn)；算法、算法要求； 教學(xué)難點： 算法效率的度量與有效的分析； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 1.4 算法 1. 算法〔Algorithm〕的定義 Algorithm is a

25、finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是規(guī)如此的有限集合，是為解決特定問題而規(guī)定的一系列操作。) 是指令的有限序列，其中每一條指令表示一個或多個操作。 2. 算法的特性 3. 算法設(shè)計的要求 １〕算法的正確性 (1) 所設(shè)計的程序沒有語法錯誤； (2) 所設(shè)計的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； (3) 所設(shè)計的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要

26、求的結(jié)果。 (4) 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。 2〕可讀性 3〕健壯性 4〕高效率和低存儲量、算法、語言和程序的關(guān)系 時間復(fù)雜度 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè) 1:圖1.5、P13：算法的5個特征； 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 課后

27、自我總結(jié)分析 備注 教案〔分教案〕 課次：3 學(xué)時：2 章 節(jié) 第2章 線性表：2.1 線性表的類型定義2.2 線性表的順序表示 教學(xué)目的 和 教學(xué)要求 理解線性表的定義和特點；掌握順序表以達(dá)到利用根本算法進(jìn)展較復(fù)雜算法設(shè)計的目的。 教　學(xué) 重 點 難 點 教學(xué)重點：線性表的定義和特點；線性表的順序表示 教學(xué)難點：線性表的順序表示 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 線性結(jié)構(gòu)的特點： 在數(shù)據(jù)元素的非空有限集中， ? 存在唯一的一個被稱為“第一個〞的數(shù)據(jù)元素； ? 存在唯一

28、的一個被稱為“最后一個〞的數(shù)據(jù)元素； ? 除第一個元素之外，集合中的每個元素均只有一個前驅(qū)； ? 除最后一個元素之外，集合中的每個元素均只有一個后繼。 2.1 線性表的類型定義 2.1.1 線性表的邏輯結(jié)構(gòu) 2.1.2 線性表的抽象數(shù)據(jù)類型定義 2.2 線性表的順序表示和實現(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語言版〕

29、》， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004 《數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004 《數(shù)據(jù)結(jié)構(gòu)與算法》，許卓群，楊冬青，唐世渭，X銘，高等教育，2004 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：4 學(xué)時：2 章 節(jié) 第2章 ：2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)〔1〕 教學(xué)目的 和 教學(xué)要求 理解線性表的鏈表的特點，掌握在這種存儲結(jié)構(gòu)上各種根本運(yùn)算的實現(xiàn)算法以與效率的分析，并學(xué)習(xí)在這種存儲結(jié)構(gòu)上進(jìn)展算法設(shè)計的方法；以達(dá)到利用根本算法進(jìn)展較復(fù)雜算法設(shè)計的目的。 教　學(xué) 重 點 難 點 教學(xué)重

30、點：線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)； 教學(xué)難點：單鏈表的插入、刪除、查找和歸并操作； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 2.3.1 單鏈表 線性表的鏈?zhǔn)酱鎯Γ? 圖2.6 單鏈表的邏輯狀態(tài) 圖2.7 帶頭結(jié)點單鏈表圖示 2.3.2 單鏈表上的根本運(yùn)算 1. 建立單鏈表 2. 查找 3. 單鏈表插入操作 4. 刪除 5．合并單鏈表： 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè) 主要 參考資料 《算法與數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》，

31、 X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004 《數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004 《數(shù)據(jù)結(jié)構(gòu)與算法》，許卓群，楊冬青，唐世渭，X銘，高等教育，2004 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：5 學(xué)時：2 章 節(jié) 第2章 ：2.3 〔2〕2.4 一元多項式的表示與相加 教學(xué)目的 和 教學(xué)要求 理解線性表的鏈表的特點，掌握在這種存儲結(jié)構(gòu)上各種根本運(yùn)算的實現(xiàn)算法以與效率的分析；掌握一元多項式的表示與相加的方法與算法。 教　學(xué) 重 點 難 點 教學(xué)重點： 循環(huán)鏈表、雙向鏈表與其算法；一元多項

32、式的表示與相加的方法與算法； 教學(xué)難點：雙向鏈表與其算法、一元多項式相加的方法； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 2.3.3 循環(huán)鏈表 2.3.4 雙向鏈表 1. 雙向鏈表的前插操作 2. 雙向鏈表的刪除操作 2.3.6 順序表和鏈表的比擬 1. 基于空間的考慮、 2. 基于時間的考慮、 3. 基于語言的考慮 2.4 一元多項式的表示與相加 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè) 主要 參考資料 《算法與數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》， X策，周世平，胡嘵

33、琨 等編著，機(jī)械工業(yè)， 2004 《數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004 《數(shù)據(jù)結(jié)構(gòu)與算法》，許卓群，楊冬青，唐世渭，X銘，高等教育，2004 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：6 學(xué)時：2 章 節(jié) 第3章 棧和隊列：3.1 棧、3.2.1 數(shù)制轉(zhuǎn)換 教學(xué)目的 和 教學(xué)要求 理解棧的定義、特點，學(xué)習(xí)它的各種組織方式與算法；掌握它的空和滿的判斷條件；并學(xué)會它的簡單應(yīng)用。 教　學(xué) 重 點 難 點 教學(xué)重點： 棧的定義、特點，學(xué)習(xí)它的各種組織方式與算法； 教學(xué)難點： 棧的簡單應(yīng)用； 教學(xué)進(jìn)程

34、 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 3.1 棧 3.1.1 棧的定義 3.1.2 棧的表示和實現(xiàn) 1. 順序棧 順序棧根本操作的實現(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é)

35、構(gòu)與算法》，許卓群，楊冬青，唐世渭，X銘，高等教育，2004 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：7 學(xué)時：2 章 節(jié) 第3章 棧和隊列：3.2.4 迷宮求解、3.3 棧與遞歸的實現(xiàn) 教學(xué)目的和 教學(xué)要求 了解迷宮求解的算法思路、了解計算機(jī)圖形學(xué)中的種子填充蘇算法； 掌握漢諾塔算法與其過程。 教　學(xué) 重 點 難 點 教學(xué)重點： 迷宮求解的算法思路、漢諾塔算法與其過程； 教學(xué)難點： 漢諾塔算法與其過程； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 4. 迷宮求解〔拓展：填充算

36、法〕 3.3 棧與遞歸的實現(xiàn) 1. 遞歸特性問題 1) 遞歸函數(shù) 2〕漢諾塔算法 三個盤子搬動時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

37、,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)蔚敏等編著， 清華

38、大學(xué) 2004 《數(shù)據(jù)結(jié)構(gòu)與算法》，許卓群，楊冬青，唐世渭，X銘，高等教育，2004 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：8 學(xué)時：2 章 節(jié) 第3章 棧和隊列：3.4 隊列 教學(xué)目的和 教學(xué)要求 掌握隊列的數(shù)據(jù)結(jié)構(gòu)和鏈隊列的相關(guān)操作；掌握循環(huán)隊列的相關(guān)內(nèi)容； 教　學(xué) 重點、難點 教學(xué)重點： 列的數(shù)據(jù)結(jié)構(gòu)和鏈隊列的相關(guān)操作； 教學(xué)難點： 循環(huán)隊列的相關(guān)操作； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 3.4 隊列 3.4.1 隊列的定義 隊列 (Queue)是另一種

39、限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進(jìn)先出(Fist In Fist Out，縮寫為FIFO)的特性。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端如此稱為隊頭(front)。 3.4.2 隊列的表示和實現(xiàn) 鏈隊列: 〔1〕初始化操作、〔2〕銷毀隊列、〔3〕入隊操作、〔4〕出隊操作 ：循環(huán)隊列 如何區(qū)分隊列“空〞和“滿〞 1. 另設(shè)一個標(biāo)志位以區(qū)分隊列是空還是滿； 2. 少用一個元素空間，當(dāng)隊列頭指針在隊列尾指針的下一個位置上時為“滿〞。 當(dāng)時隊空；時隊滿 循環(huán)隊列滿足條件 (Q.rear+1)%MAXQSIZE

40、== Q.front 隊滿 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè) 1：圖3.8、圖3.10、圖3.11、圖3.14； 2：P62：隊列的根本操作算法、P64：循環(huá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é)分析 備注 教案〔分教案〕 課次：9 學(xué)時：2 章 節(jié) 綜合習(xí)

41、題課〔1〕：前3章的相關(guān)內(nèi)容 教學(xué)目的 和 教學(xué)要求 要求掌握棧的應(yīng)用與遞歸算法 教　學(xué) 重 點 難 點 教學(xué)重點： 教學(xué)難點： 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 1：求N！的遞歸算法； 2：求N！的棧的算法； 3：數(shù)制轉(zhuǎn)換算法的具體實現(xiàn)； 4：種子填充算法的具體過程： 四向連通填充算法： a〕種子像素壓入棧中； b〕如果棧為空，如此轉(zhuǎn)e)；否如此轉(zhuǎn)c)； c〕彈出一個像素，并將該像素置成填充色；并判斷該像素相鄰的四連通像素是否為邊界色或已經(jīng)置成多邊形的填充色，假如不是，如此將該像素壓入棧； d〕

42、轉(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é)時：2 章 節(jié) 綜合實驗課〔1〕：前3章的相關(guān)內(nèi)容 教學(xué)目的 和 教學(xué)要求 1：求N！的遞歸算法； 2：求N！的棧的算法； 3

43、：數(shù)制轉(zhuǎn)換算法的具體實現(xiàn)； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 1：求N！的遞歸算法； 2：求N！的棧的算法； 3：數(shù)制轉(zhuǎn)換算法的具體實現(xiàn)； #include "stdio.h" #include "stdlib.h" #define size 20 typedef struct { int *base; int *top; int ssize; }ss; void ist(ss &s) { s.base=(int *)malloc(size*sizeof(int)); s.top=s

44、.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(")8\n"); }

45、 教學(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é)時：2 章 節(jié) 第4章 串：4.1 串的定義、4.2.1 定長順序存儲表示 4.2.3 串的塊鏈存儲表示 4.3.1 求子串位置的定位函數(shù) 教學(xué)目的和 教學(xué)要求 掌握串的定義、定長順

46、序存儲表示；了解串的塊鏈存儲表示； 掌握求子串位置的定位函數(shù)〔模式匹配算法〕； 教　學(xué) 重 點 難 點 教學(xué)重點： 串的定義、定長順序存儲表示；串的塊鏈存儲表示； 教學(xué)難點：求子串位置的定位函數(shù)〔模式匹配算法〕； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 4.1 串的定義 串(String)是零個或多個字符組成的有限序列。一般記為： S= ′a1a2...an′ (n≥0) 4.2 串的表示和實現(xiàn) 4.2.1 定長順序存儲表示串 1.串聯(lián)接Concat(& T , S1, S2)2. 求子串SubString

47、 ( & Sub , S , pos , len ) 串的塊鏈存儲表示 4.3 串的模式匹配算法 4.3.1 求子串位置的定位函數(shù) Index( S, T ,pos) int Index 〔SString S, SString T, int pos 〕 { //返回子串T在主串中第 pos個字符之后的位置。如不存在，如此函數(shù)值為0。其中：T 非空，1<=pos<=Strlength( S )。 i = pos ; j = 1 ; while ( i<=S[ 0 ] && j<= T[ 0 ] ) {if ( S[i] = = T[j]

48、) { ++ 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語言版〕》

49、， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004 《數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》， 嚴(yán)蔚敏等編著， 清華大學(xué) 2004 《數(shù)據(jù)結(jié)構(gòu)與算法》，許卓群，楊冬青，唐世渭，X銘，高等教育，2004 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：12 學(xué)時：2 章 節(jié) 第5章 數(shù)組和廣義表：5.1 數(shù)組的定義、5.2 數(shù)組的順序表示和實現(xiàn) 教學(xué)目的和 教學(xué)要求 掌握數(shù)組的定義、數(shù)組的順序表示和實現(xiàn)； 教　學(xué) 重 點 難 點 教學(xué)重點： 數(shù)組的定義、數(shù)組的順序表示和實現(xiàn) 教學(xué)難點： 數(shù)組的順序表示和實現(xiàn) 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容

50、、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 5.1 數(shù)組的定義 數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。 對于數(shù)組的操作一般只有兩類： (1〕獲得特定位置的元素值；(2〕修改特定位置的元素值。 5.2 數(shù)組的順序表示和實現(xiàn) 數(shù)組一般不做插入和刪除操作，因此采用順序存儲結(jié)構(gòu)。由于存儲單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，如此用一組連續(xù)存儲單元存放數(shù)組的數(shù)據(jù)元素就有個次序約定問題。 數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，另一種是按列序存儲。 Loc［i, j］=Loc［1, 1］+n×(i-1)+(j-1) Lo

51、c［i, j, k］=Loc［1, 1, 1］+(i-1)×m×n+(j-1)×n+(k-1) 對于ｎ維數(shù)組A(c1∶d1, c2∶d2，…, ∶dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲地址的計算公式: LOC(aj1j2…jn)=LOC(a00…0)+(b2*b3*…*bn*j1+b3*…*bn*j2+…+bn*jn-1+jn)*l LOC(aj1j2…jn)= LOC(a00…0)+( = LOC(a00…0)+ 其中 =L,ci-1=bi*ci 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè)

52、 計算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é)時：2 章 節(jié) 第5章 數(shù)組和廣義表：5.3 矩陣的壓縮存儲 5.3.1 特殊矩陣、5.3.2 稀疏矩陣 教學(xué)目的和 教學(xué)要求 掌握特殊矩陣和稀疏矩陣的存儲方法；掌握稀疏矩陣的轉(zhuǎn)置算法； 教　學(xué) 重 點

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

54、 方法一：按照中三元組的次序依次在中找到相應(yīng)的三元組進(jìn)展轉(zhuǎn)置。 方法二：按照a.data 中三元組的次序進(jìn)展轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b 中的恰當(dāng)位置。 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè) 1：下三角、對稱、帶狀矩陣的數(shù)據(jù)元素的下標(biāo)地址的計算方法； 2：稀疏矩陣的兩個轉(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 課后自

55、我總結(jié)分析 備注 教案〔分教案〕 課次：14 學(xué)時：2 章 節(jié) 綜合實驗課〔2〕：第4、5章的相關(guān)內(nèi)容 教學(xué)目的和 教學(xué)要求 要求編程實現(xiàn)串的模式匹配算法、稀疏矩陣的兩個轉(zhuǎn)置算法； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 1：串的模式匹配算法； 2：稀疏矩陣的轉(zhuǎn)置算法〔一〕； 3：稀疏矩陣的轉(zhuǎn)置算法〔二〕； #include "stdio.h" void main() { char sa[7]={'a','b','c','d','e','f','g'}; char sb[

56、3]={'e','f','g'};int i=0,j=0; while(i<=6 && j<=2) { if(sa[i]==sb[j]) {++i;++j;} else {i=i-j+2; j=0;}} if(j>2) printf("找到了!在第%d個位置。\n",i-3+1); else printf("抱歉,沒有找到!\n"); } #include "stdio.h" #define mu 3 #define nu 8 #define tu 8 void main() { int M[8][3]={{1,2,12},{1,3,9},{3,

57、1,-3},{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}}; int T[8][3];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 ",M[i][j]); printf("\n")} for(col=1;col<=nu;++col) for(p=0;p<=tu-1;++p) if(M[p][1]==col) { T[q][0]=M[p][1];T[q][1]=M[p][

58、0];T[q][2]=M[p][2];++q;} printf("轉(zhuǎn)換之后的矩陣為：\n"); for(i=0;i<=7;i++) { for(j=0;j<=2;j++) printf(" %d ",T[i][j]); printf("\n");} } 課后自我總結(jié)分析 教案〔分教案〕 課次：15 學(xué)時：2 章 節(jié) 第6章 樹：6.1 樹的定義和根本術(shù)語、6.2 二叉樹、 6.2.1 二叉樹的定義、6.2.2 二叉樹的性質(zhì)； 教學(xué)目的和 教學(xué)要求 熟練掌握樹的定義和根本術(shù)語、熟練掌握二叉樹的定義與二叉樹的性質(zhì)； 教　學(xué) 重

59、 點 難 點 教學(xué)重點：樹的定義和根本術(shù)語、二叉樹的定義； 教學(xué)難點：二叉樹的性質(zhì)； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 6.1 樹的定義和根本術(shù)語 樹是n〔n≥0〕個結(jié)點的有限集合T。當(dāng)n=0時，稱為空樹；當(dāng)n>0時，該集合滿足如下條件： (1) 其中必有一個稱為根〔root〕的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼。 (2) 其余n-1個結(jié)點可以劃分成m〔m≥0〕個互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但有零個

60、或多個直接后繼。 6.2 二叉樹的定義 6.2.1 二叉樹的定義 定義：我們把滿足以下兩個條件的樹形結(jié)構(gòu)叫做二叉樹〔Binary Tree〕： 〔1〕每個結(jié)點至多只有二棵子樹〔即度都不大于2〕； 〔2〕二叉樹的子樹有左右之分，其次序不能任意顛倒。 6.2.2 二叉樹的性質(zhì) 滿二叉樹： 完全二叉樹： 深度為k，結(jié)點數(shù)為n的二叉樹，如果其結(jié)點1~n的位置序號分別與滿二叉樹的結(jié)點1~n的位置序號一一對應(yīng)，如此為完全二叉樹。 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書 作　業(yè) 1：圖6.3二叉樹的根本形態(tài)； 2：二叉樹的五個性質(zhì)

61、； 主要 參考資料 《算法與數(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é)時：2 章 節(jié) 第6章樹和二叉樹：6.2.3 二叉樹的存儲結(jié)構(gòu)、6.3.1 遍歷二叉樹； 教學(xué)目的和 教學(xué)要求 熟練掌握二叉樹的兩種存儲結(jié)構(gòu)；熟練掌握二叉樹的三種遍歷方法； 教　學(xué) 重 點 難 點 教學(xué)重點：二叉樹的兩種存儲結(jié)構(gòu)、二叉

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

63、下3個操作： (1) 訪問根結(jié)點； (2) 按先序遍歷左子樹； (3) 按先序遍歷右子樹。 · 中序遍歷〔LDR〕操作過程： 假如二叉樹為空，如此空操作，否如此依次執(zhí)行如下3個操作： (1) 按中序遍歷左子樹； (2) 訪問根結(jié)點； (3) 按中序遍歷右子樹。 · 后序遍歷〔LRD〕操作過程： 假如二叉樹為空，如此空操作，否如此依次執(zhí)行如下3個操作： (1) 按后序遍歷左子樹； (2) 按后序遍歷右子樹； (3) 訪問根結(jié)點。 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、

64、教科書 作　業(yè) 1：對一些特殊樣式的二叉樹進(jìn)展順序存儲； 2：對二叉樹進(jìn)展三種遍歷操作； 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：17 學(xué)時：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é) 重 點 難 點 教學(xué)重點：樹的三種存儲結(jié)構(gòu)、森林與二叉樹的轉(zhuǎn)換； 教學(xué)難點：樹和森林的遍歷； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時分

65、配、 教學(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) 對樹中的每個結(jié)點，只保存其與第一個孩子結(jié)點之間的連線，刪去其與其它孩子結(jié)點之間的連線。 (3) 以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次清楚。 2. 森林轉(zhuǎn)換為二叉樹 森林是假如干棵樹的集合。樹可以轉(zhuǎn)換為

66、二叉樹，森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下： 〔1〕將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。 〔2〕第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(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é)時：2 章 節(jié) 第6章6.6 赫夫曼樹與其應(yīng)用、6.6.1 最優(yōu)二叉樹〔赫夫曼樹〕、 6.6.2 赫夫曼編碼 教學(xué)目的和 教學(xué)要求 熟練掌握哈夫