數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程編號：課程名稱：數(shù)據(jù)結(jié)構(gòu)英文名稱：Data Structure學(xué)分：5學(xué)時：102，其中講授68學(xué)時，實驗34學(xué)時適用年級專業(yè)（學(xué)科類）：二年級 數(shù)學(xué)類、數(shù)電類一、課程概述（一）課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計算機(jī)及相關(guān)專業(yè)的一門綜合性的專業(yè)基礎(chǔ)課，是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件之間的一門計算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，同時數(shù)據(jù)結(jié)構(gòu)技術(shù)也被廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。本課程主要介紹如何合理的組織和表示數(shù)據(jù)、如何有效的存儲和處理數(shù)據(jù)、如何正確的設(shè)計算法以及對算法的優(yōu)劣作出分析和評價。（二）教學(xué)目標(biāo)與要求通過本課程的學(xué)習(xí)，使學(xué)生深透理解各種常用數(shù)據(jù)結(jié)構(gòu)的

2、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法的實現(xiàn)；全面掌握處理數(shù)據(jù)的理論和方法，培養(yǎng)學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)，編寫質(zhì)量高、風(fēng)格好的程序及初步評價算法的能力；使學(xué)生系統(tǒng)的科學(xué)的受到分析問題和解決問題的訓(xùn)練，提高運用數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力，為后續(xù)的軟件課程奠定良好的基礎(chǔ)。（三）重點和難點本課程的重點是：從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運算三個方面去掌握線性表、棧、隊列、串、數(shù)組、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)；掌握常用的各種查找方法和排序算法；并培養(yǎng)對算法的時間空間復(fù)雜性的分析能力。本課程的難點有：邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系，順序表和鏈表的區(qū)別與聯(lián)系，棧和隊列的特點，模式匹配，矩陣的壓縮存儲，二叉樹的性質(zhì)，二叉樹

3、的各種遍歷算法，哈夫曼樹，最小生成樹，關(guān)鍵路徑，折半查找，二叉排序樹，平衡二叉樹，B-樹，哈希表，各種排序方法及性能分析。（四）與其他課程的關(guān)系數(shù)據(jù)結(jié)構(gòu)的先修課程有計算機(jī)導(dǎo)論、C語言程序設(shè)計、離散數(shù)學(xué)；后繼課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、人工智能等。數(shù)據(jù)結(jié)構(gòu)中存儲結(jié)構(gòu)及基本運算的實現(xiàn)需要程序設(shè)計的基本知識和編程的經(jīng)驗及能力，本課程的算法用C語言實現(xiàn)，因此要求學(xué)生較熟練地掌握C語言。（五）教材及教學(xué)參考書的選用1、數(shù)據(jù)結(jié)構(gòu)，劉振鵬，中國鐵道出版社，2003年9月；2、數(shù)據(jù)結(jié)構(gòu)與算法，張曉莉，機(jī)械工業(yè)出版社，2002年9月； 3、數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，1997年4月；

4、4、Data Structures，Algorithms，and Applications in C，（美）Sartaj Sahni，機(jī)械工業(yè)出版社，1999年。5、數(shù)據(jù)結(jié)構(gòu)與算法，許卓群，高等教育出版社，2004年7月二、學(xué)時分配章課程內(nèi)容學(xué)時 1緒論22線型表83棧和隊列44串45數(shù)組、特殊矩陣和廣義表46二叉樹107樹和森林48圖129查找1010排序10三、課程內(nèi)容第一章 緒論教學(xué)目的和要求：本章的目的是介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義，要求了解本章介紹的各種基本概念和術(shù)語，掌握算法描述和分析的方法。重點和難點：1、教學(xué)重點：了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)

5、據(jù)運算等三方面的概念及相互關(guān)系，算法的性能評價。2、教學(xué)難點：抽象數(shù)據(jù)類型的概念的理解，算法時間復(fù)雜度的分析方法。主要內(nèi)容：1、數(shù)據(jù)結(jié)構(gòu)的概念；2、抽象數(shù)據(jù)類型；3、算法和算法分析。主要教學(xué)環(huán)節(jié)的組織：課堂講授。思考題：1、試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算這三方面的內(nèi)容。2、比較邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系。3、比較數(shù)據(jù)結(jié)構(gòu)的概念與程序設(shè)計語言中數(shù)據(jù)類型的概念的區(qū)別與聯(lián)系。第二章線性表教學(xué)目的和要求：本章目的是介紹線性表的邏輯結(jié)構(gòu)和各種存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運算在相應(yīng)的存儲結(jié)構(gòu)上的實現(xiàn)。要求在熟悉這些內(nèi)容的基礎(chǔ)上，能夠針對具體的應(yīng)用問題的要求和性質(zhì)，選擇

6、合適的存儲結(jié)構(gòu)設(shè)計出相應(yīng)的有效算法，解決與線性表相關(guān)的實際問題。重點和難點：1、教學(xué)重點：順序表和單鏈表上實現(xiàn)的各種基本算法及相關(guān)的時間性能分析。2、教學(xué)難點：用本章所學(xué)到的基本知識設(shè)計算法解決與線性表相關(guān)的實際應(yīng)用問題。主要內(nèi)容：1、線性表的邏輯結(jié)構(gòu)；2、線性表的順序存儲及運算實現(xiàn)；3、線性表的鏈?zhǔn)酱鎯斑\算實現(xiàn)；4、順序表和鏈表的比較。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、請比較順序表與鏈表的優(yōu)缺點。2、單鏈表具有隨機(jī)存取的性質(zhì)嗎？順序表呢？為什么？第三章棧和隊列教學(xué)目的和要求：本章的目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及其在兩種存儲結(jié)構(gòu)上如何實現(xiàn)棧和隊列的基本運算。要求在掌握棧和隊

7、列的特點的基礎(chǔ)上，懂得在什么樣的情況下使用?；蜿犃?，掌握在不同的存儲結(jié)構(gòu)上實現(xiàn)棧和隊列的方法。重點和難點：1、教學(xué)重點：棧和隊列在兩種存儲結(jié)構(gòu)上基本操作的實現(xiàn)。2、教學(xué)難點：循環(huán)隊列中對邊界條件的處理及棧和隊列的應(yīng)用。主要內(nèi)容：1、棧及其性質(zhì)；2、棧的應(yīng)用舉例；3、隊列及其性質(zhì)；4、隊列的應(yīng)用舉例。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、棧和隊列各有什么特點，什么情況下用到棧，什么情況下用到隊列？2、循環(huán)隊列是如何實現(xiàn)“循環(huán)”的？第四章串教學(xué)目的和要求：本章目的是介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其字符串上的基本運算，要求掌握串的各種存儲結(jié)構(gòu)、串的常用運算及模式匹配算法。重點和難點：1、教學(xué)

8、重點：串的存儲結(jié)構(gòu)及基本運算。2、教學(xué)難點：模式匹配。主要內(nèi)容：1、串及其基本運算；2、串的定長順序存儲及基本運算；3、串的堆存儲結(jié)構(gòu)。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、KMP算法與樸素的模式匹配算法相比有何優(yōu)越性？2、求模式串的next函數(shù)值有什么意義？第五章數(shù)組、特殊矩陣和廣義表教學(xué)目的和要求：本章的目的是介紹多維數(shù)組的邏輯結(jié)構(gòu)特征及存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念及存儲實現(xiàn)方法。重點和難點：1、教學(xué)重點：多維數(shù)組的存儲方式、矩陣的壓縮存儲方法、廣義表的定義及基本運算。2、教學(xué)難點：特殊矩陣的壓縮方法，稀疏矩陣的壓縮存儲及其運算的實現(xiàn)。主要內(nèi)容：1、多

9、維數(shù)組；2、特殊矩陣的壓縮存儲；3、稀疏矩陣；4、廣義表。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、如何用一維的空間表示多維的數(shù)組？2、為什么要對矩陣進(jìn)行壓縮存儲？ 3、廣義表和一般的線性表有和異同？第六章二叉樹教學(xué)目的和要求：本章目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、線索化及二叉樹的應(yīng)用等內(nèi)容，要求掌握二叉樹的性質(zhì)、存儲結(jié)構(gòu)，掌握二叉樹的各種遍歷算法及其應(yīng)用，哈夫曼樹等。重點和難點：1、教學(xué)重點：二叉樹的性質(zhì)，二叉樹的遍歷算法及其應(yīng)用，哈夫曼樹。2、教學(xué)難點：二叉樹性質(zhì)的證明，基于二叉樹遍歷解決實際問題，哈夫曼編碼。主要內(nèi)容：1、二叉樹的定義與性質(zhì)；2、二叉樹的存儲實現(xiàn)基本操作

10、的實現(xiàn)；3、二叉樹的遍歷；4、線索二叉樹；5、二叉樹的應(yīng)用。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、一棵度為2的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)別？2、在結(jié)點數(shù)多于1的哈夫曼樹中存在度為1的結(jié)點嗎？3、遍歷二叉樹的方法有哪些？遍歷二叉樹的實質(zhì)是什么？第七章樹和森林教學(xué)目的和要求：本章介紹樹和森林的定義、存儲結(jié)構(gòu)、和二叉樹之間的轉(zhuǎn)換、遍歷及樹的應(yīng)用等內(nèi)容，要求掌握樹與二叉樹之間的轉(zhuǎn)換及其樹的應(yīng)用等。重點和難點：1、教學(xué)重點：樹和森林的存儲結(jié)構(gòu)、遍歷，樹、森林和二叉樹之間的轉(zhuǎn)換。2、教學(xué)難點：樹和森林的遍歷及由遍歷序列恢復(fù)樹或森林，用相關(guān)知識解決與樹的實際應(yīng)用問題。主要內(nèi)容：1

11、、樹的概念與表示；2、樹的基本操作與存儲；3、樹、森林與二叉樹的轉(zhuǎn)換；4、樹或森林的遍歷；5、樹的應(yīng)用。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、樹、森林和二叉樹之間有什么關(guān)系？2、已知一棵度為m的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？有多少個非終端結(jié)點？第八章教學(xué)目的和要求：教學(xué)目的和要求：本章的目的是介紹圖的基本概念、兩種常用的存儲結(jié)構(gòu)、兩種遍歷算法以及圖的應(yīng)用算法，在熟悉這些內(nèi)容的基礎(chǔ)上，重點和難點：1、教學(xué)重點：圖的存儲結(jié)構(gòu)，圖的遍歷算法，圖的幾種應(yīng)用算法。2、教學(xué)難點：最小生成樹，最短路徑，拓?fù)渑判?，關(guān)鍵路徑。主要內(nèi)容：1

12、、圖的基本概念 ；2、圖的存儲表示；3、圖的遍歷；4、生成樹與最小生成樹；5、最短路徑；6、有向無環(huán)圖及其應(yīng)用。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、比較Prim算法和Kruskal算法，當(dāng)邊數(shù)較少時用哪一個方法較好？2、用哪些方法可以判斷有向圖中有環(huán)路存在？3、加快一個關(guān)鍵活動，一定能縮短工期嗎？第九章查找教學(xué)目的和要求：本章目的是介紹各種存儲方式下的查找表的查找方法，以及各種查找方法的時間性能分析，重點和難點：1、教學(xué)重點：順序查找、二分查找、二叉樹排序樹、平衡二叉樹，B-樹以及哈希表上的查找思想、算法實現(xiàn)及查找性能的分析。2、教學(xué)難點：二叉排序樹的刪除，平衡二叉樹的調(diào)整，B-樹

13、的插入和刪除，哈希表中處理沖突的方法。主要內(nèi)容：1、基本概念；2、靜態(tài)查找表；3、動態(tài)查找表；4、哈希表查找(雜湊法) 。主要教學(xué)環(huán)節(jié)的組織：課堂教學(xué)與實踐。思考題：1、試推導(dǎo)含有12個結(jié)點的平衡二叉樹的最大深度，并畫出一棵這樣的樹。2、含有9個葉子結(jié)點的3階B樹中至少有多少個非葉子結(jié)點？含有10個葉子結(jié)點的3階B樹中至少有多少個非葉子結(jié)點？3、比較哈希查找方法與其他查找方法的區(qū)別。第十章排序教學(xué)目的和要求：本章目的介紹5類內(nèi)部排序方法的基本思想、排序過程、算法事現(xiàn)、時間和空間性能的分析以及各種排序方法的比較和選擇。重點和難點：1、教學(xué)重點：各種排序的思想、算法實現(xiàn)、穩(wěn)定性、適用情況、時間空間復(fù)雜度分析。2、教學(xué)難點：希爾排序，快速排序，堆排序。主要內(nèi)容：1、基本概念；2、插入排序；3、交換排序；4、選擇排