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

《《大數(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ǔ)言編寫(xiě)程序的過(guò)程中發(fā)現(xiàn)所有的數(shù)據(jù)都可以抽象為三種結(jié)構(gòu)，而對(duì)這些數(shù)據(jù)的所有操作都可以轉(zhuǎn)化為對(duì)這三種數(shù)據(jù)的幾種根本操作，而大多數(shù)的程序設(shè)計(jì)技巧都可以抽象為一些最根本的算法。于是人們逐步開(kāi)展了一門(mén)稱為數(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é)生透徹地理解

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)要求逐步熟悉鏈表的表示，通過(guò)模仿實(shí)驗(yàn)教程中的例子，掌握編程技巧。強(qiáng)調(diào)類 C語(yǔ)言的書(shū)寫(xiě)規(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ù)、二叉

3、樹(shù)、圖。掌握它們的定義和特點(diǎn)、表示和實(shí)現(xiàn)，特別注意與根本數(shù)據(jù)結(jié)構(gòu)的區(qū)別，掌握各種遍歷的遞歸和非遞歸算法，能熟練完成以下的應(yīng)用：最優(yōu)樹(shù)、Huffman編碼、拓?fù)渑判?、關(guān)鍵路徑和最短路徑問(wèn)題。 3．?dāng)?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、 4 一、課程的性質(zhì)、目的與任務(wù) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)技術(shù)、信息管理等專業(yè)的核心課程之一，是一門(mén)理論與工程實(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)新，有利于高級(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é)生必修的一門(mén)技術(shù)根底課程，也是計(jì)算機(jī)專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門(mén)重要的專業(yè)根底課，主要解決數(shù)據(jù)的表示和數(shù)據(jù)的處理，系統(tǒng)介紹三大數(shù)據(jù)結(jié)構(gòu)與其實(shí)現(xiàn)，為操作系統(tǒng)等課程提供必要

5、的知識(shí)根底，為計(jì)算機(jī)人員提供必要的根本技能。二、課程教學(xué)根本要求 本課程介紹常用數(shù)據(jù)結(jié)構(gòu)之間的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)其施加的運(yùn)算，如：線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(shù)、圖等。同時(shí)還介紹各種查找和排序的算法。 通過(guò)本門(mén)課程的學(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：掌握各種查找和排序的算法以與效率，

6、并將其應(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ù)元素、數(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)算法以與效率的分析

7、，并學(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ì)列的定義、特點(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é)要求：了解串的概念，

8、掌握串的根本運(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ù)的定義 　　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.

9、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.1 深度優(yōu)先搜索　　7.3.2 廣度優(yōu)先搜索 7.4 圖的連通性問(wèn)題 　　7.4.1 無(wú)向圖的

10、連通分量和生成樹(shù) 　　7.4.3 最小生成樹(shù) 　　7.5 有向無(wú)環(huán)圖與其應(yīng)用 　　7.5.1 拓?fù)渑判? 　　7.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 什么是哈希

11、表 　　9.3.2 哈希函數(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)

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

13、算法與數(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 《算法與數(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è)計(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ī)。 制定： ????????????????????????????????????????????????????????????????????

15、??????????????????????????????制定日期： 教案〔首頁(yè)〕 授課時(shí)間 教案編寫(xiě)時(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é) 主要參考

16、書(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 《算法與數(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è)計(jì)與分析》，梁田貴，X鵬編著，冶金工業(yè)，2004 教學(xué)目的和 教學(xué)要求 通過(guò)本門(mén)課程的學(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í)

18、際應(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ù)組、廣義表、樹(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次課

19、 第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章 棧和隊(duì)列 第3章 棧和隊(duì)列 綜合習(xí)題課〔1〕：前3章的相關(guān)內(nèi)容 綜合實(shí)驗(yàn)課〔1〕：前3章的相關(guān)內(nèi)容 第4章 串 第5

20、章 數(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)部排序 第10章 內(nèi)部排序 綜合習(xí)題課〔3〕：第9、10章的相關(guān)內(nèi)容 綜合實(shí)驗(yàn)課〔4〕：第10章的相關(guān)內(nèi)容 學(xué) 時(shí) 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é)時(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ì)算，更

22、多地用于控制，管理，數(shù)據(jù)處理等非數(shù)值計(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ù)

23、類型名{ 數(shù)據(jù)對(duì)象: <數(shù)據(jù)對(duì)象的定義> 數(shù)據(jù)關(guān)系: <結(jié)構(gòu)關(guān)系的定義> 根本操作: <根本操作的定義> }ADT 抽象數(shù)據(jù)類型名 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(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é)分析

24、 備注 教案〔分教案〕 課次：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)；算法、算法要求； 教學(xué)難點(diǎn)： 算法效率的度量與有效的分析； 教學(xué)進(jìn)程 〔含章節(jié) 教學(xué)內(nèi)容、學(xué)時(shí)分配、 教學(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ī)如此的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。) 是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 2. 算法的特性 3. 算法設(shè)計(jì)的要求 １〕算法的正確性 (1) 所設(shè)計(jì)的程序沒(méi)有語(yǔ)法錯(cuò)誤； (2) 所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； (3) 所設(shè)計(jì)的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要

26、求的結(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銘，高等教育，2004 課后

27、自我總結(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ù)元素； ? 存在唯一

28、的一個(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. 刪除操作 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(shū) 作　業(yè) 主要 參考資料 《算法與數(shù)據(jù)結(jié)構(gòu)〔C語(yǔ)言版〕

29、》， 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.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é)重

30、點(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é)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(shū) 作　業(yè) 主要 參考資料 《算法與數(shù)據(jù)結(jié)構(gòu)〔C語(yǔ)言版〕》，

31、 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 〔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)

32、式的表示與相加的方法與算法； 教學(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策，周世平，胡嘵

33、琨 等編著，機(jī)械工業(yè)， 2004 《數(shù)據(jù)結(jié)構(gòu)〔C語(yǔ)言版〕》， 嚴(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é)會(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)程

34、 〔含章節(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é)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(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é)

35、構(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é) 教學(xué)內(nèi)容、學(xué)時(shí)分配、 教學(xué)方法、 輔助手段〕 教學(xué)進(jìn)程： 4. 迷宮求解〔拓展：填充算

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

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

38、大學(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)是另一種

39、限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出(Fist In Fist Out，縮寫(xiě)為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

40、== 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í)

41、題課〔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：種子填充算法的具體過(guò)程： 四向連通填充算法： a〕種子像素壓入棧中； b〕如果棧為空，如此轉(zhuǎn)e)；否如此轉(zhuǎn)c)； c〕彈出一個(gè)像素，并將該像素置成填充色；并判斷該像素相鄰的四連通像素是否為邊界色或已經(jīng)置成多邊形的填充色，假如不是，如此將該像素壓入棧； d〕

42、轉(zhuǎn)b〕； e〕完畢。 教學(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é)分析 備注 教案〔分教案〕 課次：10 學(xué)時(shí)：2 章 節(jié) 綜合實(shí)驗(yàn)課〔1〕：前3章的相關(guān)內(nèi)容 教學(xué)目的 和 教學(xué)要求 1：求N！的遞歸算法； 2：求N！的棧的算法； 3

43、：數(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 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("請(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(")8\n"); }

45、 教學(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 課后自我總結(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)順

46、序存儲(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′ (n≥0) 4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長(zhǎng)順序存儲(chǔ)表示串 1.串聯(lián)接Concat(& T , S1, S2)2. 求子串SubString

47、 ( & Sub , S , pos , len ) 串的塊鏈存儲(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 ] ) {if ( S[i] = = T[j]

48、) { ++ i ; ++ j ;} // 繼續(xù)比擬后續(xù)字符 else { i = i – j + 2 ; j = 1 ;} // 指針后退重新開(kāi)始匹配 } if ( 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ǔ)言版〕》

49、， X策，周世平，胡嘵琨 等編著，機(jī)械工業(yè)， 2004 《數(shù)據(jù)結(jié)構(gòu)〔C語(yǔ)言版〕》， 嚴(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)容

50、、學(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è)次序約定問(wèn)題。 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：一種是按行序存儲(chǔ)，另一種是按列序存儲(chǔ)。 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) 對(duì)于ｎ維數(shù)組A(c1∶d1, c2∶d2，…, ∶dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲(chǔ)地址的計(jì)算公式: 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é)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(shū) 作　業(yè)

52、 計(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é)要求 掌握特殊矩陣和稀疏矩陣的存儲(chǔ)方法；掌握稀疏矩陣的轉(zhuǎn)置算法； 教　學(xué) 重 點(diǎn)

53、 難 點(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ì)稱矩陣 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é)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(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 課后自

55、我總結(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 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個(gè)位置。\n",i-3+1); else printf("抱歉,沒(méi)有找到!\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é)時(shí)：2 章 節(jié) 第6章 樹(shù)：6.1 樹(shù)的定義和根本術(shù)語(yǔ)、6.2 二叉樹(shù)、 6.2.1 二叉樹(shù)的定義、6.2.2 二叉樹(shù)的性質(zhì)； 教學(xué)目的和 教學(xué)要求 熟練掌握樹(shù)的定義和根本術(shù)語(yǔ)、熟練掌握二叉樹(shù)的定義與二叉樹(shù)的性質(zhì)； 教　學(xué) 重

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

60、或多個(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)1~n的位置序號(hào)分別與滿二叉樹(shù)的結(jié)點(diǎn)1~n的位置序號(hào)一一對(duì)應(yīng)，如此為完全二叉樹(shù)。 教學(xué)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、教科書(shū) 作　業(yè) 1：圖6.3二叉樹(shù)的根本形態(tài)； 2：二叉樹(shù)的五個(gè)性質(zhì)

61、； 主要 參考資料 《算法與數(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é) 重 點(diǎn) 難 點(diǎn) 教學(xué)重點(diǎn)：二叉樹(shù)的兩種存儲(chǔ)結(jié)構(gòu)、二叉

62、樹(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í)行如

63、下3個(gè)操作： (1) 訪問(wèn)根結(jié)點(diǎn)； (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é)方法、課堂講解、例題演示，課件演示 輔助手段：電腦、投影儀、

64、教科書(shū) 作　業(yè) 1：對(duì)一些特殊樣式的二叉樹(shù)進(jìn)展順序存儲(chǔ)； 2：對(duì)二叉樹(shù)進(jìn)展三種遍歷操作； 課后自我總結(jié)分析 備注 教案〔分教案〕 課次：17 學(xué)時(shí)：2 章 節(jié) 第6章 6.4 樹(shù)和森林：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í)分

65、配、 教學(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ù)中的每個(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)換為

66、二叉樹(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é)要求 熟練掌握哈夫