《數(shù)據(jù)結構》教案

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

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

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

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

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

6、；掌握邏輯結構和存儲結構的關系；理解算法的基本概念；學會分析算法的時間復雜性和空間復雜性。第二章：線性表2.1 線性表的類型定義2.2 線性表的順序表示和實現(xiàn)2.3 線性表的鏈式表示和實現(xiàn)（靜態(tài)查找表不講）2.4 一元多項式的表示及相加教學要求：理解線性表的定義和特點；掌握順序表和鏈表的特點，掌握在這兩種存儲結構上各種基本運算的實現(xiàn)算法以及效率的分析，并學習在這兩種存儲結構上進行算法設計的方法； 以達到利用基本算法進行較復雜算法設計的目的。第三章：棧、隊列3.1 棧3.2 棧的應有和舉例3.2.1 數(shù)制轉換3.3.4 迷宮求解3.3 棧與遞歸的實現(xiàn)3.4 隊列教學要求：理解棧和隊列的定義、特點

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

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

9、度優(yōu)先搜索7.3.2 廣度優(yōu)先搜索7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹7.4.3 最小生成樹7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序7.5.2 關鍵路徑7.6 最短路徑7.6.1 從某個源點到其余各頂點的最短路徑 教學要求：理解圖型結構的概念和術語，掌握圖的鄰接矩陣和鄰接表兩種存儲形式，理解圖的遍歷的基本思想，掌握圖的兩種遍歷的方法和其實現(xiàn)的過程，學會圖在最小生成樹、拓撲排序、最短路徑、關鍵路徑中的應用。第九章：查找9.1 靜態(tài)查找表9.1.1 順序表的查找9.1.2 有序表的查找9.1.4 索引順序表的查找9.3 哈希表9.3.1 什么是哈希表9.3.2 哈希函數(shù)

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

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

12、出版社，2001算法與數(shù)據(jù)結構C語言描述，張乃孝等，高等教育出版社，2002數(shù)據(jù)結構，殷人昆，清華大學出版社，2001計算機算法設計與分析，蘇德富，電子工業(yè)出版社，2001算法與數(shù)據(jù)結構，傅清祥，王嘵冬，電子工業(yè)出版社，1998數(shù)據(jù)結構C+與面向對象的途徑，張乃孝，裘宗燕，高等教育出版社，2001數(shù)據(jù)結構用面向對象方法與C+描述，殷人昆等清華大學出版社算法設計與分析，梁田貴，張鵬編著，冶金工業(yè)出版社，2004六、考核辦法和成績評定標準根據(jù)教學要求進行期末考試，由任課教師根據(jù)完成情況進行評定，并最終結合平時成績的考核給出綜合成績。 制定：制定日期：教案（首頁） 授課時間 教案編寫時間 課程名稱數(shù)

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

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

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

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

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

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

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

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

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

22、求） 算法的正確性 (1) 所設計的程序沒有語法錯誤； (2) 所設計的程序對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； (3) 所設計的程序對于精心選擇的典型、 苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結果。 (4) 程序對于一切合法的輸入數(shù)據(jù)都能產生滿足要求的結果。2） 可讀性 3） 健壯性 4） 高效率和低存儲量 、算法、 語言和程序的關系時間復雜度教學方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀、教科書作業(yè)1:圖1.5、P13：算法的5個特征；2:P15：兩段程序的語句的頻度的分析主要參考資料算法與數(shù)據(jù)結構（C語言版）， 范策，周世平，胡嘵琨 等編著，機械工業(yè)出版社，

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

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

25、周世平，胡嘵琨 等編著，機械工業(yè)出版社， 2004數(shù)據(jù)結構（C語言版）， 嚴蔚敏等編著， 清華大學出版社 2004數(shù)據(jù)結構與算法，許卓群，楊冬青，唐世渭，張銘，高等教育出版社，2004課后自我總結分析備注教案（分教案）課次：4 學時：2章 節(jié)第2章 ：2.3 線性表的鏈式表示和實現(xiàn)（1）教學目的和教學要求理解線性表的鏈表的特點，掌握在這種存儲結構上各種基本運算的實現(xiàn)算法以及效率的分析，并學習在這種存儲結構上進行算法設計的方法； 以達到利用基本算法進行較復雜算法設計的目的。教學重 點難 點教學重點：線性表的鏈式表示和實現(xiàn)；教學難點：單鏈表的插入、刪除、查找和歸并操作；教學進程（含章節(jié)教學內容、學

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

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

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

29、：2章 節(jié)第3章 棧和隊列：3.1 棧、3.2.1 數(shù)制轉換教學目的和教學要求理解棧的定義、特點，學習它的各種組織方式及算法；掌握它的空和滿的判斷條件；并學會它的簡單應用。教學重 點難 點教學重點： 棧的定義、特點，學習它的各種組織方式及算法；教學難點： 棧的簡單應用；教學進程（含章節(jié)教學內容、學時分配、教學方法、 輔助手段）教學進程：3.1 棧 3.1.1 棧的定義3.1.2 棧的表示和實現(xiàn) 1. 順序棧順序?；静僮鞯膶崿F(xiàn):(1) 初始化、(2) 取棧頂元素、(3) 入棧、(4) 出棧2. 鏈棧3.2 棧的應用舉例 1. 數(shù)制轉換教學方法、課堂講解、例題演示，課件演示輔助手段：電腦、投影儀

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

31、學難點： 漢諾塔算法及其過程；教學進程（含章節(jié)教學內容、學時分配、教學方法、 輔助手段）教學進程：4. 迷宮求解（拓展：填充算法） 3.3 棧與遞歸的實現(xiàn)1. 遞歸特性問題 1) 遞歸函數(shù) 2）漢諾塔算法三個盤子搬動時hanoi(3, A, B, C) 遞歸調用過程： 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

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

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

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

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

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

37、節(jié)教學內容、學時分配、教學方法、 輔助手段）教學進程：1：求N！的遞歸算法；2：求N！的棧的算法；3：數(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)：)

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

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

40、長順序存儲表示串1.串聯(lián)接Concat(& T , S1, S2) 2. 求子串SubString ( & Sub , S , pos , len )4.2.3串的塊鏈存儲表示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 ) return i - T 0

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

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

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

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

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

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

47、學內容、學時分配、教學方法、 輔助手段）教學進程：1：串的模式匹配算法；2：稀疏矩陣的轉置算法（一）；3：稀疏矩陣的轉置算法（二）；#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個位置。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