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

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

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

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