數(shù)據(jù)結(jié)構(gòu)與算法（java語言版）-教學(xué)大綱、教案1-4 耿祥義（48+8）

《數(shù)據(jù)結(jié)構(gòu)與算法》(Java語言版)課程教學(xué)大綱教學(xué)大綱執(zhí)筆耿祥義頁《數(shù)據(jù)結(jié)構(gòu)與算法》(Java語言版)課程教學(xué)大綱一、課程性質(zhì)和教學(xué)目標(biāo)課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)科學(xué)的核心領(lǐng)域、是計(jì)算機(jī)程序的基礎(chǔ)。正確、恰當(dāng)?shù)厥褂脭?shù)據(jù)結(jié)構(gòu)和相應(yīng)的算法決定了程序的性能和效率。數(shù)據(jù)結(jié)構(gòu)和算法課程的重要性和意義不僅僅在于學(xué)習(xí)知識(shí)技能，同時(shí)涵蓋了提高編程能力、增強(qiáng)解決實(shí)際問題的能力、提高協(xié)作能力等諸多方面，一直是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程等專業(yè)的一門重要的專業(yè)必修課程。教學(xué)目標(biāo)通過本課程的學(xué)習(xí)，達(dá)到下列目標(biāo)。夯實(shí)基礎(chǔ)讓學(xué)習(xí)者掌握每種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，恰如其分的使用好相應(yīng)地?cái)?shù)據(jù)結(jié)構(gòu)和算法，熟悉基礎(chǔ)算法的特點(diǎn)、并能通透理解和正確使用這些基礎(chǔ)算法。注重能力該課程強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)和算法課程的重要性和意義不僅僅在于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法本身，同時(shí)注重訓(xùn)練、提高學(xué)習(xí)者的編程能力。教學(xué)目標(biāo)的重要目標(biāo)之一就是強(qiáng)調(diào)怎樣正確的使用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法、恰如其分的來解決問題，使用一些經(jīng)典和實(shí)用性強(qiáng)的算法思想并結(jié)合一些經(jīng)典的問題來使得學(xué)習(xí)者掌握如何設(shè)計(jì)和實(shí)現(xiàn)高效、優(yōu)秀的算法，提高解決實(shí)際問題的能力。強(qiáng)調(diào)實(shí)用數(shù)據(jù)結(jié)構(gòu)和算法與計(jì)算機(jī)科學(xué)緊密關(guān)聯(lián)，常常應(yīng)用于解決現(xiàn)實(shí)中的問題，課程注重結(jié)合一些經(jīng)典問題和某些實(shí)際問題，使得學(xué)習(xí)者通過學(xué)習(xí)該課程，能加深對(duì)實(shí)際問題的了解，并具有解決某些實(shí)際問題的能力。面向?qū)ο笳n程體現(xiàn)Java語言的面向?qū)ο筇厣?，即?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)體現(xiàn)Java的特色。二、教學(xué)內(nèi)容8.隊(duì)列與ArrayDeque8.隊(duì)列與ArrayDeque類9.二叉樹與TreeSet類10.散列結(jié)構(gòu)與HashMap類11.集合與HashSet類12.常用算法與Collections類13.圖論14.經(jīng)典算法思想1.數(shù)據(jù)結(jié)構(gòu)簡介2.算法復(fù)雜度3.遞歸算法4.數(shù)組與Arrays類5.鏈表與LinkedList類6.順序表與ArrayList類7.棧與Stack類三、教學(xué)環(huán)節(jié)教學(xué)環(huán)節(jié)包括：課堂講授、上機(jī)實(shí)踐、課外作業(yè)。通過本課程各個(gè)教學(xué)環(huán)節(jié)可以培養(yǎng)學(xué)生的自學(xué)能力、動(dòng)手能力、分析解決問題的能力。1．課堂講授(1)教學(xué)方法上盡量采用啟發(fā)式、討論式教學(xué)，在課堂上多提問題，安排一些自學(xué)內(nèi)容，鼓勵(lì)學(xué)生自學(xué)、培養(yǎng)學(xué)生的自學(xué)能力。結(jié)合實(shí)際問題，更新教學(xué)內(nèi)容，改進(jìn)教學(xué)方法，通過上機(jī)實(shí)踐，培養(yǎng)學(xué)生的動(dòng)手能力和創(chuàng)新能力。(2)利用多功能教室，結(jié)合黑板講解，演示較大程序的結(jié)構(gòu)及其運(yùn)行效果，以提高課堂信息量，增加教學(xué)的直觀性。2．實(shí)踐課根據(jù)教學(xué)需要，要適當(dāng)安排實(shí)踐課。3．考核采取期末考試和平時(shí)考核相結(jié)合的方式。四、學(xué)時(shí)分配本課程總學(xué)時(shí)是56學(xué)時(shí)，其中包含課內(nèi)上機(jī)8學(xué)時(shí)。上機(jī)學(xué)時(shí)的主要目的是針對(duì)教材相應(yīng)的知識(shí)點(diǎn)進(jìn)行基本訓(xùn)練。其中上機(jī)內(nèi)容安排的時(shí)間和內(nèi)容見學(xué)時(shí)分配建議。8次上機(jī)，教師可更具實(shí)際情況確定上機(jī)實(shí)踐的具體內(nèi)容（也可參考作者提供的上機(jī)參考教案）。通過上機(jī)實(shí)踐環(huán)節(jié)可以加深學(xué)生對(duì)理論知識(shí)的理解和掌握，同時(shí)提高學(xué)生分析問題、解決問題的能力，培養(yǎng)學(xué)生實(shí)踐能力與創(chuàng)新能力。整個(gè)知識(shí)架構(gòu)分成三大模塊-算法基礎(chǔ)（基礎(chǔ)模塊），結(jié)構(gòu)及其算法(重點(diǎn)模塊)，專項(xiàng)算法（難點(diǎn)模塊），如下列三大模塊圖（不含上機(jī)實(shí)踐）。算法基礎(chǔ)模塊（算法基礎(chǔ)模塊（8學(xué)時(shí)）數(shù)據(jù)結(jié)構(gòu)簡介算法復(fù)雜度遞歸算法專項(xiàng)算法模塊（8學(xué)時(shí)）常用算法圖論經(jīng)典算法思想結(jié)構(gòu)及其算法模塊（32學(xué)時(shí)）數(shù)組與Arrays類鏈表與LinkedList類順序表與ArrayList類棧與Stack類隊(duì)列與ArrayDeque類二叉樹與TreeSet類散列結(jié)構(gòu)與HashMap類集合與HashSet類圖三大模塊56學(xué)時(shí)（含上機(jī)實(shí)踐）和教案（見28個(gè)參考教案）分配細(xì)節(jié)如下列學(xué)時(shí)和教案分配表。學(xué)時(shí)和教案分配表序號(hào)內(nèi)容學(xué)時(shí)（56）參考教案（28個(gè)，含實(shí)踐）1數(shù)據(jù)結(jié)構(gòu)簡介，算法復(fù)雜度2教案12遞歸算法6教案2，教案3，教案43上機(jī)實(shí)踐2教案5（實(shí)踐）4數(shù)組與Arrays類6教案6，教案7，教案85鏈表與LinkedList類6教案9，教案10，教案116順序表與ArrayList類6教案12，教案13，教案147上機(jī)實(shí)踐2教案15（實(shí)踐）8棧與Stack類2教案169隊(duì)列與ArrayDeque類2教案177上機(jī)實(shí)踐2教案18（實(shí)踐）8二叉樹與TreeSet類4教案19，教案209散列結(jié)構(gòu)與HashMap類4教案21，教案2210集合與HashSet類2教案2311上機(jī)實(shí)踐2教案24（實(shí)踐）12常用算法與Collections類2教案2513圖論4教案26，教案2714經(jīng)典算法思想2教案28五、先修課程本課程的先修課程為Java程序設(shè)計(jì)。本課程特別需要Java語言中的一些基礎(chǔ)知識(shí)，例如，類，對(duì)象，接口以及常用的實(shí)用類等。六、教材與參考書1.教材《數(shù)據(jù)結(jié)構(gòu)與算法》（Java語言版），耿祥義張躍平，清華大學(xué)出版社2024.2.參考書［1］《數(shù)據(jù)結(jié)構(gòu)與算法》（Java語言版）,周翔，王建芬，黃小青，等譯.北京：機(jī)械工業(yè)出版社，2003.［2］《Java2實(shí)用教程(第6版)》,耿祥義張躍平，清華大學(xué)出版社，2021.參考教案1（2學(xué)時(shí)）主要內(nèi)容1.數(shù)據(jù)結(jié)構(gòu)簡介2.算法復(fù)雜度教材第1章和第2章數(shù)據(jù)結(jié)構(gòu)(教材第1章)算法與復(fù)雜度（教材第2章）基礎(chǔ)知識(shí)1.邏輯結(jié)構(gòu)，物理結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，算法與結(jié)構(gòu)（第1章）。2.算法以及算法的復(fù)雜度（教材2.2節(jié)）重點(diǎn)知識(shí)常見復(fù)雜度（教材2.3節(jié)）基礎(chǔ)算法1.找出1至n的連續(xù)多個(gè)自然數(shù)中缺失的某個(gè)數(shù)（例子2.5）2.起泡法重點(diǎn)算法二分法(例子2.9)，歐幾里得算法（例子2.10)難點(diǎn)算法給出包含若干個(gè)正整數(shù)的最短等差序列（例子2.12）。兩個(gè)學(xué)時(shí)可以根據(jù)實(shí)際講解情況，在時(shí)間的分配上有所調(diào)整。教學(xué)過程設(shè)計(jì)第1個(gè)學(xué)時(shí)結(jié)合24節(jié)氣，感性理解線性結(jié)構(gòu)，可以和學(xué)生交流，讓學(xué)生給出他自己熟悉的生活中的線性結(jié)構(gòu)。然后給出線性結(jié)構(gòu)的定義。結(jié)合年級(jí)結(jié)構(gòu)，感性理解樹結(jié)構(gòu)，可以和學(xué)生交流，讓學(xué)生給出他自己熟悉的生活中的樹結(jié)構(gòu)。然后給出樹結(jié)構(gòu)的定義，特別講解圖1.2示意的二叉樹的特點(diǎn)。結(jié)合焊接點(diǎn)形成的框架結(jié)構(gòu)，感性理解圖結(jié)構(gòu)，可以和學(xué)生交流，讓學(xué)生給出他自己熟悉的生活中的圖結(jié)構(gòu)。然后給出圖結(jié)構(gòu)的定義。簡單介紹集合，以及物理結(jié)構(gòu)和算法與結(jié)構(gòu)第2個(gè)學(xué)時(shí)1.介紹算法和復(fù)雜度時(shí)候，要特別強(qiáng)調(diào)什么是基本操作：耗時(shí)僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，即不會(huì)隨著n的增加而增大。2.結(jié)合對(duì)應(yīng)的例子講解常見復(fù)雜度、重點(diǎn)講解基礎(chǔ)算法：找出1至n的連續(xù)多個(gè)自然數(shù)中缺失的某個(gè)數(shù)（例子2.5）、起泡法（例子2.7）、重點(diǎn)算法：二分法，歐幾里得算法，特別注意分析二者的復(fù)雜度（例子2.9和例子2.10）、仔細(xì)分析難點(diǎn)算法：給出包含若干個(gè)正整數(shù)的最短等差序列（例子2.12）。多媒體輔助PPT電子講義。作業(yè)在習(xí)題1和習(xí)題2中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案2（2學(xué)時(shí)）主要內(nèi)容教材第3章（遞歸算法）3.1-3.4遞歸算法教材3.1線性與非線性遞歸教材3.2問題與子問題教材3.3遞歸與迭代教材3.4基礎(chǔ)知識(shí)遞歸算法。重點(diǎn)知識(shí)1.線性與非線性遞歸。2.問題與子問題基礎(chǔ)算法1.計(jì)算星期數(shù)（例子3.1）2.Fibonacci序列（例子3.2）3.反轉(zhuǎn)字符序列（例子3.4）4.計(jì)算圓周率重點(diǎn)算法判斷某個(gè)數(shù)是否是數(shù)組的元素值（例子3.6）難點(diǎn)算法求兩個(gè)正整數(shù)的最大公約數(shù)（例子3.7）兩個(gè)學(xué)時(shí)可以根據(jù)實(shí)際講解情況，在時(shí)間的分配上有所調(diào)整。教學(xué)過程設(shè)計(jì)第1個(gè)學(xué)時(shí)：結(jié)合圖3.1和3.2講解什么是遞歸以及特點(diǎn)，說明如何計(jì)算其復(fù)雜度。結(jié)合例子3.1（基礎(chǔ)算法，求星期數(shù)）講解線性遞歸，以及復(fù)雜度的計(jì)算。結(jié)合例子3.2（基礎(chǔ)算法Fibonacci序列）講解非線性遞歸，特別要結(jié)合圖3.6和3.7說明其空間復(fù)雜度是On（初學(xué)者容易誤解其空間復(fù)雜度是O2第2個(gè)學(xué)時(shí)：1.結(jié)合例子3.3，說明什么是問題與子問題，重點(diǎn)講解例子3.4，即基礎(chǔ)算法：反轉(zhuǎn)字符序列。2.結(jié)合例子3.5（計(jì)算圓周率），說明遞歸與迭代的特點(diǎn)和關(guān)系，重點(diǎn)講解例子3.6和例子3.7，即重點(diǎn)算法：判斷某個(gè)數(shù)是否是數(shù)組的元素值和難點(diǎn)算法：求兩個(gè)正整數(shù)的最大公約數(shù)。多媒體輔助PPT電子講義。作業(yè)在習(xí)題3中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案3（2學(xué)時(shí)）主要內(nèi)容教材第3章（遞歸算法）3.5-3.6多重遞歸教材3.5經(jīng)典遞歸教材3.6基礎(chǔ)知識(shí)遞歸算法。重點(diǎn)知識(shí)1.楊輝三角形。2.老鼠走迷宮基礎(chǔ)算法求n-位十進(jìn)制數(shù)中，出現(xiàn)含有偶數(shù)多個(gè)數(shù)字6的數(shù)的數(shù)量（例子3.8）重點(diǎn)算法輸出楊輝三角形（例子3.9）難點(diǎn)算法老鼠走迷宮（例子3.10）兩個(gè)學(xué)時(shí)可以根據(jù)實(shí)際講解情況，在時(shí)間的分配上有所調(diào)整。教學(xué)過程設(shè)計(jì)第1個(gè)學(xué)時(shí)：復(fù)習(xí)遞歸的基本知識(shí)，然后引出什么是多重遞歸。結(jié)合例子3.8（基礎(chǔ)算法：求n-位十進(jìn)制數(shù)中，出現(xiàn)含有偶數(shù)多個(gè)數(shù)字6的數(shù)的數(shù)量）講解多重遞歸，其復(fù)雜度留給學(xué)生自己思考。介紹經(jīng)典遞歸：楊輝三角形的兩個(gè)遞歸公式①和②，以及相應(yīng)的代碼，并強(qiáng)調(diào)二者的時(shí)間復(fù)雜度的不同，反復(fù)演示例子3.9的運(yùn)行效果。加深學(xué)生對(duì)這個(gè)重點(diǎn)算法的理解。第2個(gè)學(xué)時(shí)：1.敘述老鼠走迷宮的遞歸算法，并解釋其正確性。2.仔細(xì)分析例子3.10老鼠走迷宮的遞歸算法，并修改代碼，給出幾種迷宮，比如，迷宮有出口，老鼠能找到出口；迷宮有出口，但老鼠無法到達(dá)出口，即迷宮不通；迷宮無出口。演示運(yùn)行效果。多媒體輔助PPT電子講義。作業(yè)在習(xí)題3中挑選有關(guān)內(nèi)容布置相關(guān)作業(yè)。

參考教案4（2學(xué)時(shí)）主要內(nèi)容教材第3章（遞歸算法）3.6-3.7經(jīng)典遞歸教材3.6優(yōu)化遞歸教材3.7基礎(chǔ)知識(shí)遞歸算法，漢諾塔重點(diǎn)知識(shí)優(yōu)化遞歸基礎(chǔ)算法漢諾塔的遞歸算法和迭代算法（例子3.11，例子3.12）重點(diǎn)算法優(yōu)化遞歸，計(jì)算Fibonacci數(shù)列（例子3.13）難點(diǎn)算法優(yōu)化遞歸，輸出楊輝三角形（例子3.14）兩個(gè)學(xué)時(shí)可以根據(jù)實(shí)際講解情況，在時(shí)間的分配上有所調(diào)整。教學(xué)過程設(shè)計(jì)第1個(gè)學(xué)時(shí)：復(fù)習(xí)遞歸的基本知識(shí)，然后講解漢諾塔的遞歸算法（例子3.11）。結(jié)合表3.1，介紹漢諾塔的一些規(guī)律，引出漢諾塔的迭代算法。然后講解例子3.2，最后總結(jié)遞歸和迭代算法各自的優(yōu)缺點(diǎn)：遞歸優(yōu)缺點(diǎn)：優(yōu)點(diǎn)是代碼簡練，容易理解解決問題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，具有很好的可讀性。缺點(diǎn)是可能導(dǎo)致運(yùn)行時(shí)刻的棧溢出。迭代優(yōu)缺點(diǎn)：優(yōu)點(diǎn)是同一問題的