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

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱一、課程基本信息中文名稱數(shù)據(jù)結(jié)構(gòu)英文名稱Data Structure適用專業(yè)計算機科學(xué)與技術(shù)/信息管理與信息系統(tǒng)/信息工程先修課程C程序設(shè)計課程類別專業(yè)本科學(xué)科基礎(chǔ)課程修讀性質(zhì)必修學(xué)分/學(xué)時3.5學(xué)分/51學(xué)時（實踐學(xué)時:17）考核方式考試二、教學(xué)目標(biāo)本課程是為計算機科學(xué)與技術(shù)、信息管理與信息系統(tǒng)、信息工程的本科生開設(shè)的學(xué)科基礎(chǔ)課程之一，學(xué)習(xí)本課程能使學(xué)生掌握數(shù)據(jù)在計算機中的表示、存儲和處理。為以后學(xué)習(xí)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)打下基礎(chǔ)。掌握常用的數(shù)據(jù)結(jié)構(gòu)及內(nèi)在的邏輯關(guān)系，計算機軟件設(shè)計中的算法知識。提高軟件設(shè)計和編程技能。學(xué)會初步對不同的存儲結(jié)構(gòu)和相應(yīng)算法的對比，有一定的

2、算法改進能力。三、教學(xué)內(nèi)容及基本要求第一章 緒論（理論學(xué)時：3學(xué)時/實踐學(xué)時：1學(xué)時）（一）教學(xué)目標(biāo)1.了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展和地位；2.了解各種算法描述方法和算法設(shè)計的基本要求；3.理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念；4.掌握對算法的評價標(biāo)準(zhǔn)和算法效率的度量方法；（二）重點、難點重點：理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念；掌握對算法的評價標(biāo)準(zhǔn)和算法效率的度量方法；難點：算法的評價標(biāo)準(zhǔn)和算法效率的度量方法。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.什么是數(shù)據(jù)結(jié)構(gòu)2.基本概念和術(shù)語3.抽象數(shù)據(jù)類型的表示和實現(xiàn)4.算法和算法分析（1）算

3、法（2）算法設(shè)計要求（3）算法效率的度量（4）算法的存儲空間需求第二章 線性表（理論學(xué)時：8學(xué)時/實踐學(xué)時：3學(xué)時）（一）教學(xué)目標(biāo)1.理解線性表的概念、邏輯結(jié)構(gòu)特性以及兩種存儲結(jié)構(gòu)特性，針對實際應(yīng)用能從時間和空間復(fù)雜度的角度選用適當(dāng)?shù)拇鎯Y(jié)構(gòu)；2.熟練掌握線性表的順序存儲結(jié)構(gòu)及其各種基本運算；3.熟練掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（單鏈表、循環(huán)鏈表、雙向鏈表）及其各種基本運算，能在實際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)；（二）重點、難點重點：線性表的概念、邏輯結(jié)構(gòu)特性以及兩種存儲結(jié)構(gòu)特性，線性表順序存儲實現(xiàn)中的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法，線性表鏈?zhǔn)酱鎯崿F(xiàn)中單鏈表、循環(huán)鏈表和雙向鏈表的創(chuàng)建、查

4、找、插入和刪除等基本操作及相關(guān)算法。難點：線性表順序和鏈?zhǔn)酱鎯崿F(xiàn)中的某些操作及相關(guān)算法。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.線性表的類型定義2.線性表的順序表示和實現(xiàn)3.線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（1）線性鏈表（2）循環(huán)鏈表（3）雙向鏈表第三章 棧和隊列（理論學(xué)時：5學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo)1.掌握棧和隊列的定義、表示、實現(xiàn)和應(yīng)用；2.掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)；3.了解遞歸的概念和遞歸過程的實現(xiàn)；4.掌握隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）和鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)；（二）重點、難點重點：棧和隊列的定義、表示、實現(xiàn)和應(yīng)用；棧的順序存儲結(jié)

5、構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)；隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）的實現(xiàn)；難點：棧和隊列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.棧（1）抽象數(shù)據(jù)類型棧的定義（2）棧的表示和實現(xiàn)2.棧的應(yīng)用舉例（1）數(shù)值轉(zhuǎn)換（2）括號匹配的檢驗（3）行編輯程序（4）迷宮求解（5）表達式求值3.隊列（1）抽象數(shù)據(jù)類型隊列的定義（2）鏈隊列-隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（3）循環(huán)隊列-隊列的順序表示和實現(xiàn)第四章 串（理論學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo)1.掌握串的基本概念、順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)；2.掌握串的各種基本運算；3.掌握順序存儲結(jié)構(gòu)上串的各種操作，

6、了解串的應(yīng)用；（二）重點、難點重點：串的基本概念、順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)及各種基本運算；難點：串的各種基本運算。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.串類型定義2.串的表示和實現(xiàn)（1）定長順序存儲表示（2）堆分配存儲表示（3）串的塊鏈存儲表示第五章 數(shù)組和廣義表（理論學(xué)時：3學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo)1.掌握數(shù)組的順序存儲和特殊矩陣的壓縮存儲。2.了解廣義表的概念和存儲結(jié)構(gòu)。（二）重點、難點重點：數(shù)組的存儲表示方法，順序存儲數(shù)組時數(shù)據(jù)元素之間的地址關(guān)系，特殊矩陣的壓縮存儲方法，稀疏矩陣的壓縮存儲方法，廣義表的定義、性質(zhì)和存儲結(jié)構(gòu)。難點：特殊矩陣和壓縮矩陣的存

7、儲表示（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.數(shù)組的定義2.數(shù)組的順序表示和實現(xiàn)3.矩陣的壓縮存儲（1）特殊矩陣（2）稀疏矩陣4.廣義表的定義5.廣義表的存儲結(jié)構(gòu)第六章 樹和二叉樹（理論學(xué)時：9學(xué)時/實踐學(xué)時：3學(xué)時）（一）教學(xué)目標(biāo)1.熟練掌握二叉樹的定義、性質(zhì)、各種存儲結(jié)構(gòu)的特點及適用范圍；2.熟練掌握二叉樹的各種遍歷算法；3.理解線索二叉樹的概念、存儲結(jié)構(gòu)及線索化算法；4理解樹的基本概念及其存儲結(jié)構(gòu)；掌握樹和森林與二叉樹間的轉(zhuǎn)換，掌握樹和森林的遍歷算法； 5.掌握哈夫曼樹的概念、存儲結(jié)構(gòu)；建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)路徑長度的計算；（二）重點、難點重點：二

8、叉樹的定義、結(jié)構(gòu)特點和性質(zhì)，二叉樹的設(shè)計和實現(xiàn)，二叉樹存儲結(jié)構(gòu)的特點，先序、中序、后序遍歷的遞歸和非遞歸算法，二叉樹的線索化過程，最優(yōu)二叉樹的特性及建立最優(yōu)二叉樹和構(gòu)造哈夫曼編碼的方法。樹和森林與二叉樹間的轉(zhuǎn)換。難點：二叉樹遍歷的非遞歸算法，二叉樹的線索化算法。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.樹的定義和基本術(shù)語2.二叉樹（1）二叉樹的定義（2）二叉樹的性質(zhì)（3）二叉樹的存儲結(jié)構(gòu)3.遍歷二叉樹和線索二叉樹（1）遍歷二叉樹（2）線索二叉樹4.樹和森林（1）樹的存儲結(jié)構(gòu)（2）森林與二叉樹的轉(zhuǎn)換（3）樹和森林的遍歷5.赫夫曼樹及其應(yīng)用（1）最優(yōu)二叉樹（赫夫曼樹）（2）

9、赫夫曼編碼第七章 圖（理論學(xué)時：9學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo)1.理解圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)；2.熟練掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法；3. 掌握構(gòu)造最小生成樹的方法及其算法；4.掌握求拓撲排序和關(guān)鍵路徑的方法，理解其算法；5.理解帶權(quán)最短路徑的概念，掌握用Dijkstra方法求最短路徑的算法； （二）重點、難點重點：圖的定義、術(shù)語、結(jié)構(gòu)特點和性質(zhì)，圖的鄰接矩陣、鄰接表的存儲結(jié)構(gòu)及其構(gòu)造方法，圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法，構(gòu)造連通圖的最小生成樹算法，有向無環(huán)圖的拓撲排序算法、關(guān)鍵路徑的算法，最短路徑求解中的Dijkstra算法和Floyed算法。難點

10、：圖的存儲結(jié)構(gòu)及圖的各種應(yīng)用的算法。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.圖的定義和術(shù)語2.圖的存儲結(jié)構(gòu)（1）數(shù)組表示法（2）鄰接表（3）十字鏈表（4）鄰接多重表3.圖的遍歷（1）深度優(yōu)先搜索（2）廣度優(yōu)先搜索4.圖的連通性問題（1）無向圖的連通分量和生成樹（2）最小生成樹5.有向無環(huán)圖及其應(yīng)用（1）拓撲排序（2）關(guān)鍵路徑6.最短路徑（1）從某個源點到其余各頂點的最短路徑（2）每一對頂點之間的最短路徑第九章 查找（理論學(xué)時：6學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo)1.理解查找及其算法的時間復(fù)雜度，靜態(tài)查找表的概念；2.熟練掌握順序查找、折半查找和分塊查找算法，能對其

11、性能進行分析；3.掌握二叉排序樹查找算法；理解二叉平衡樹，B樹的概念；4.理解哈希表的含義；掌握哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法；（二）重點、難點重點：順序查找、折半查找和分塊查找算法，哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法；難點：哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法，各種查找算法的性能進行分析。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.靜態(tài)查找表（1）順序表的查找（2）有序表的查找（3）索引順序表的查找2.動態(tài)查找表（1）二叉排序樹和平衡二叉樹（2）B-樹和B+樹3.哈希表（1）什么是哈希表（2

12、）哈希函數(shù)的構(gòu)造方法（3）處理沖突的方法（4）哈希表的查找及其分析第十章 內(nèi)部排序（理論學(xué)時：6學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo)1.了解內(nèi)部排序的概念；2.掌握插入類排序的算法，直接插入排序、希爾排序；3. 掌握交換類排序的算法，冒泡排序、快速排序；4. 掌握選擇類排序的算法，簡單選擇排序、堆排序；5.了解歸并排序、基數(shù)排序的算法；6.掌握各種排序方法的特點，能夠?qū)Ω鞣N排序算法進行評價，并能加以靈活應(yīng)用；（二）重點、難點重點：插入類排序的算法，直接插入排序、希爾排序； 掌握交換類排序的算法，冒泡排序、快速排序，掌握選擇類排序的算法，簡單選擇排序、堆排序；難點：各種排序方法的特點，能夠?qū)Ω?/p>

13、種排序算法進行評價，并能加以靈活應(yīng)用。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容1.概述2.插入排序（1）直接插入排序（2）其他插入排序（3）希爾排序3.快速排序4.選擇排序（1）簡單選擇排序（2）樹形選擇排序（3）堆排序5.歸并排序6.基數(shù)排序（1）多關(guān)鍵字的排序（2）鏈?zhǔn)交鶖?shù)排序7.各種內(nèi)部排序方法的比較討論四、考核形式及成績評定（一）考核形式：期末考試為閉卷考試，考試范圍和要求應(yīng)符合本教學(xué)大綱對各章教學(xué)內(nèi)容的基本要求。（二）成績評定：課程考核由平時作業(yè)及聽課情況和期末考試成績兩部分組成，分別占課程總成績的30%和70%。五、教材與參考書教 材：嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言）.（第三版）.北京：清華大學(xué)出版社，2007參考書：