《數(shù)據(jù)結(jié)構(gòu)(Java版)》教學(xué)大綱 孫愛香

《數(shù)據(jù)結(jié)構(gòu)(Java版)》教學(xué)大綱課程性質(zhì)與任務(wù)本課程是計(jì)算機(jī)科學(xué)中一門綜合性的基礎(chǔ)課程，是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)，它在計(jì)算機(jī)科學(xué)中具有承上啟下的核心地位，是計(jì)算機(jī)及相關(guān)專業(yè)學(xué)生必修的專業(yè)基礎(chǔ)課程。通過本課程的學(xué)習(xí)，學(xué)生能根據(jù)實(shí)際應(yīng)用研究的要求，對(duì)大量的表面上雜亂無章的數(shù)據(jù)進(jìn)行有效地組織、存儲(chǔ)和處理，編制出相應(yīng)的高效算法。學(xué)生必須熟練掌握計(jì)算機(jī)程序設(shè)計(jì)中常見的各種數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的運(yùn)算，掌握算法的時(shí)間分析和空間分析的技術(shù)，并能根據(jù)計(jì)算機(jī)加工的數(shù)據(jù)特性運(yùn)用數(shù)據(jù)結(jié)構(gòu)的知識(shí)和技巧設(shè)計(jì)出更好的算法和程序，培養(yǎng)良好的程序設(shè)計(jì)能力。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)先修《計(jì)算機(jī)文化基礎(chǔ)》、《高等數(shù)學(xué)》、《離散數(shù)學(xué)》、《JAVA程序設(shè)計(jì)》、《概率論與數(shù)理統(tǒng)計(jì)》，后續(xù)課程主要有《管理信息系統(tǒng)》《數(shù)據(jù)庫原理及應(yīng)用》《數(shù)據(jù)挖掘》，《網(wǎng)絡(luò)程序設(shè)計(jì)》等。與先修課程的關(guān)系：數(shù)據(jù)邏輯結(jié)構(gòu)的學(xué)習(xí)應(yīng)在《離散數(shù)學(xué)》課程中完成，這樣才會(huì)有充足的時(shí)間講解物理存儲(chǔ)結(jié)構(gòu)，并分析每一種不同存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在分析插入和刪除等操作的效率時(shí)，因?yàn)椴煌恢玫臄?shù)據(jù)操作概率不同，不結(jié)合概率論與數(shù)理統(tǒng)計(jì)的知識(shí)便無法分析。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)，沒有人機(jī)交流語言無法描述存儲(chǔ)結(jié)構(gòu)，所以必須先修高級(jí)語言《JAVA程序設(shè)計(jì)》，分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)需要用到《高等數(shù)學(xué)》與《概率論與數(shù)理統(tǒng)計(jì)》的知識(shí)。與后續(xù)課程的關(guān)系：數(shù)據(jù)結(jié)構(gòu)和算法分析可以為后續(xù)課程提供程序設(shè)計(jì)和系統(tǒng)開發(fā)方法論方面的指導(dǎo)與幫助。二、課程目標(biāo)1．知識(shí)目標(biāo)（1）知道《數(shù)據(jù)結(jié)構(gòu)與算法分析》這門學(xué)科的性質(zhì)、在計(jì)算機(jī)科學(xué)中的地位和獨(dú)立價(jià)值。知道這門學(xué)科的研究范圍、應(yīng)用領(lǐng)域、研究方法。（2）掌握與數(shù)據(jù)結(jié)構(gòu)有關(guān)的基本概念、明確數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的差別。（3）掌握各種主要數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、串、樹和圖的特點(diǎn)、計(jì)算機(jī)內(nèi)的表示方法，以及處理數(shù)據(jù)的算法實(shí)現(xiàn)。（4）會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并了解對(duì)算法的時(shí)間分析和空間分析技術(shù)。2．能力目標(biāo)（1）培養(yǎng)學(xué)生數(shù)據(jù)抽象能力，能為應(yīng)用涉及的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)。（2）培養(yǎng)學(xué)生理解計(jì)算機(jī)思維方式能力，能為各種邏輯結(jié)構(gòu)設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)。（3）培養(yǎng)學(xué)生進(jìn)一步提高程序設(shè)計(jì)質(zhì)量的能力。（4）培養(yǎng)學(xué)生理論聯(lián)系實(shí)際能力及自學(xué)能力。3．素質(zhì)目標(biāo)（1）具備運(yùn)用數(shù)據(jù)結(jié)構(gòu)的理論方法進(jìn)行高質(zhì)量程序設(shè)計(jì)的素質(zhì)。（2）具有良好的團(tuán)隊(duì)合作精神。

三、教學(xué)內(nèi)容及教學(xué)要求參考理論學(xué)時(shí)48參考實(shí)驗(yàn)學(xué)時(shí)16課程內(nèi)容及要求序號(hào)教學(xué)項(xiàng)目教學(xué)內(nèi)容和教學(xué)要求教學(xué)設(shè)計(jì)建議參考學(xué)時(shí)1緒論1.數(shù)據(jù)結(jié)構(gòu)的概念和術(shù)語；2.算法的描述與算法分析；3.數(shù)據(jù)結(jié)構(gòu)的地位。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。61.掌握數(shù)據(jù)結(jié)構(gòu)的概念和術(shù)語；2.理解算法的描述與算法分析；3.理解數(shù)據(jù)結(jié)構(gòu)的地位。2線性表1.線性表的類型定義；2.線性表的順序存儲(chǔ)與實(shí)現(xiàn)；3.性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)；4.線性表的應(yīng)用。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。61.掌握線性表的類型定義；2.掌握線性表的順序存儲(chǔ)與實(shí)現(xiàn)；3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與實(shí)現(xiàn)；4.了解線性表的應(yīng)用。實(shí)驗(yàn)1線性表的應(yīng)用1.利用線性表開發(fā)一元多項(xiàng)式運(yùn)算系統(tǒng)。43棧和隊(duì)列1.棧和隊(duì)列的定義；2.棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)；3.棧和隊(duì)列的應(yīng)用。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。61.掌握棧的定義、棧的存儲(chǔ)及其實(shí)現(xiàn)；2.掌握隊(duì)列的定義、存儲(chǔ)及其實(shí)現(xiàn)；3.了解棧和隊(duì)列的應(yīng)用。實(shí)驗(yàn)2棧和隊(duì)列的應(yīng)用1.編寫程序，從鍵盤輸入一個(gè)十進(jìn)制數(shù)，輸出與其等值的八進(jìn)制數(shù)。2.編寫程序，利用棧和隊(duì)列實(shí)現(xiàn)判斷一個(gè)字符串是否是回文。24串1串類型的定義，串的存儲(chǔ)；2.串的運(yùn)算實(shí)現(xiàn)。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。41.掌握串類型的定義，串的存儲(chǔ)；2.理解串的運(yùn)算實(shí)現(xiàn)。5數(shù)組與廣義表1.掌握：數(shù)組的定義、數(shù)據(jù)的順序存儲(chǔ)和實(shí)現(xiàn)，特殊矩陣的壓縮存儲(chǔ)，稀疏矩陣的三元組表存儲(chǔ)；2.理解：稀疏矩陣的十字鏈表；3.了解：廣義表的定義和廣義表的存儲(chǔ)結(jié)構(gòu)。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。61.掌握：數(shù)組的定義、數(shù)據(jù)的順序存儲(chǔ)和實(shí)現(xiàn)，特殊矩陣的壓縮存儲(chǔ)，稀疏矩陣的三元組表存儲(chǔ)；2.理解：稀疏矩陣的十字鏈表；3.了解：廣義表的定義和廣義表的存儲(chǔ)結(jié)構(gòu)。實(shí)驗(yàn)3特殊矩陣的運(yùn)算1.壓縮存儲(chǔ)下實(shí)現(xiàn)各種特殊矩陣的運(yùn)算。26樹與二叉樹1.樹的定義和基本術(shù)語、樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的概念、存儲(chǔ)及遍歷二叉樹、線索二叉樹、哈夫曼樹及其應(yīng)用；2.森林的概念、森林與樹的轉(zhuǎn)換及樹和森林的遍歷；樹的應(yīng)用1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。61.掌握樹的定義和基本術(shù)語、樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的概念、存儲(chǔ)及遍歷二叉樹、線索二叉樹、哈夫曼樹及其應(yīng)用；2.理解森林的概念、森林與樹的轉(zhuǎn)換及樹和森林的遍歷，樹的應(yīng)用；實(shí)驗(yàn)4樹的應(yīng)用1.從鍵盤接受n個(gè)字符的權(quán)值，輸出此n個(gè)字符的哈夫曼編碼，請(qǐng)嘗試基于二叉樹不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。2.從鍵盤接受某一集合s的r等價(jià)關(guān)系，即接受n個(gè)等價(jià)偶對(duì)，輸出s基于r的等價(jià)類。27圖1.圖的定義和術(shù)語、圖的存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)、圖的遍歷、最小生成樹；2.圖的連通性問題。3.有向無環(huán)圖的拓?fù)渑判?，關(guān)鍵路徑、最短路徑。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。61.掌握：圖的定義和術(shù)語、圖的存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)、圖的遍歷、最小生成樹；2.理解：圖的連通性問題；3.理解：有向無環(huán)圖的拓?fù)渑判蜿P(guān)鍵路徑、最短路徑。實(shí)驗(yàn)5圖的應(yīng)用1.從鍵盤接受圖的頂點(diǎn)和及邊的權(quán)值，輸出圖的最小生成樹，嘗試在不同的存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)。2.從鍵盤接受AOE圖的頂點(diǎn)和及邊的權(quán)值，輸出從源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑，嘗試在不同的存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)。3.從鍵盤接受圖的頂點(diǎn)和及邊的權(quán)值，輸出圖各對(duì)頂點(diǎn)之間的最短路徑，嘗試在不同的存儲(chǔ)結(jié)構(gòu)下實(shí)現(xiàn)。28查找1.順序查找法，折半查找法，二叉排序樹的查找，哈希表及其查找；2.分塊查找法，二叉平衡樹生成及其查找。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。41.掌握順序查找法，折半查找法，二叉排序樹的查找，哈希表及其查找；2.理解分塊查找法，二叉平衡樹生成及其查找。實(shí)驗(yàn)6查找1.從鍵盤接受一個(gè)整數(shù)序列，構(gòu)造一棵二叉排序樹并輸出。29排序1.直接插入排序、折半插入排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、歸并排序；2.希爾排序、堆排序；3.基數(shù)排序。1.多媒體教學(xué)，進(jìn)行啟發(fā)誘導(dǎo)，重點(diǎn)講解；2.課堂練習(xí)；3.布置課后作業(yè)。41.掌握直接插入排序、折半插入排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、歸并排序；2.理解希爾排序、堆排序。3.了解基數(shù)排序。實(shí)驗(yàn)7排序1.從鍵盤接受一個(gè)整數(shù)數(shù)據(jù)序列，嘗試用不同的排序方法，在屏幕輸出它的非遞減有序序列。2合計(jì)64

四、教學(xué)方法在教學(xué)過程中，應(yīng)立足于加強(qiáng)學(xué)生實(shí)際編程能力的培養(yǎng)，采用項(xiàng)目教學(xué)，以工作任務(wù)引領(lǐng)提高學(xué)生學(xué)習(xí)興趣，激發(fā)學(xué)生的成就動(dòng)機(jī)。通過對(duì)項(xiàng)目的課外分析與編程和課堂總結(jié)，培養(yǎng)學(xué)生利用計(jì)算機(jī)編程解決實(shí)際問題的能力，綜合分析能力，創(chuàng)新能力。增設(shè)數(shù)據(jù)結(jié)構(gòu)與算法分析課程主頁，實(shí)現(xiàn)網(wǎng)上交互式教學(xué)，在每一章的教學(xué)內(nèi)容之后配備相關(guān)的編程題目，倡導(dǎo)“問題導(dǎo)向”，引導(dǎo)學(xué)生對(duì)相關(guān)題目進(jìn)行編程，以掌握程序設(shè)計(jì)的基本原理：數(shù)據(jù)結(jié)構(gòu)+算法=程序編程開發(fā)：編程開發(fā)是數(shù)據(jù)結(jié)構(gòu)與算法分析教學(xué)聯(lián)系實(shí)際的特色形式，應(yīng)引起教師高度重視。本課程所選編程題目，應(yīng)是較為典型的、學(xué)生有能力完成的。教師的指導(dǎo)重點(diǎn)要放在指導(dǎo)學(xué)生如何進(jìn)行程序設(shè)計(jì)以及提高程序的質(zhì)量上，而不是代替他們進(jìn)行程序設(shè)計(jì)，鼓勵(lì)學(xué)生課下自己根據(jù)編譯器的錯(cuò)誤提示信息，找出所編制程序的錯(cuò)誤，逐步提高程序調(diào)試水平。作業(yè)評(píng)講：制作學(xué)生作業(yè)錯(cuò)誤匯總PPT，收集學(xué)生平時(shí)作業(yè)中的常見問題,以圖片展示、關(guān)鍵點(diǎn)解釋、計(jì)算技巧講解的方式教會(huì)學(xué)生如何自己發(fā)現(xiàn)錯(cuò)誤、如何自行糾正錯(cuò)誤的方法與技巧。鼓勵(lì)學(xué)生上網(wǎng)查閱中國學(xué)術(shù)期刊，萬方數(shù)據(jù)庫、中宏數(shù)據(jù)庫等電子資源。向?qū)W生推薦數(shù)據(jù)結(jié)構(gòu)與算法分析理論與應(yīng)用成果較多的1.軟件學(xué)報(bào)2.計(jì)算機(jī)學(xué)報(bào)3.計(jì)算機(jī)研究與發(fā)展4.系統(tǒng)仿真學(xué)報(bào)5.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)6.自動(dòng)化學(xué)報(bào)7.控制與決策8.中國圖象圖形學(xué)報(bào)9.計(jì)算機(jī)集成制造系統(tǒng)10.中文信息學(xué)報(bào)11.控制理論與應(yīng)用12.計(jì)算機(jī)應(yīng)用13.計(jì)算機(jī)應(yīng)用研究14計(jì)算機(jī)科學(xué)15.信息與控制16.模式識(shí)別與人工智能等國內(nèi)高水平科技期刊。讓學(xué)生主動(dòng)查閱、了解數(shù)據(jù)結(jié)構(gòu)與算法分析的發(fā)展現(xiàn)狀和新理論、新方法、新概念、