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

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

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

3、的各種遍歷算法，哈夫曼樹，最小生成樹，關(guān)鍵路徑，折半查找，二叉排序樹，平衡二叉樹，B-樹，哈希表，各種排序方法及性能分析。（四）與其他課程的關(guān)系數(shù)據(jù)結(jié)構(gòu)的先修課程有計(jì)算機(jī)導(dǎo)論、C語言程序設(shè)計(jì)、離散數(shù)學(xué)；后繼課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、人工智能等。數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)需要程序設(shè)計(jì)的基本知識(shí)和編程的經(jīng)驗(yàn)及能力，本課程的算法用C語言實(shí)現(xiàn)，因此要求學(xué)生較熟練地掌握C語言。（五）教材及教學(xué)參考書的選用1、數(shù)據(jù)結(jié)構(gòu)，劉振鵬，中國(guó)鐵道出版社，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é)時(shí)分配章課程內(nèi)容學(xué)時(shí) 1緒論22線型表83棧和隊(duì)列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ù)語，掌握算法描述和分析的方法。重點(diǎn)和難點(diǎn)：1、教學(xué)重點(diǎn)：了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)

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

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

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

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

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

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

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

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

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