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

《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱一、課程基本信息二、教學(xué)目標(biāo)中文名稱數(shù)據(jù)結(jié)構(gòu)英文名稱DataStructure適用專業(yè)計算機科學(xué)與技術(shù)/信息管理與信息系統(tǒng)/信息工程先修課程C程序設(shè)計課程類別專業(yè)本科學(xué)科基礎(chǔ)課程修讀性質(zhì)必修學(xué)分/學(xué)時3.5學(xué)分/51學(xué)時（實踐學(xué)時：17）考核方式考試本課程是為計算機科學(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)算法的比照，有一定的算法改進能力。三、教學(xué)內(nèi)容及基本要求第一章緒論（理論學(xué)時：3學(xué)時/實踐學(xué)時：1學(xué)時）（一）教學(xué)目標(biāo)1,了解數(shù)據(jù)結(jié)構(gòu)的開展和地位；.了解各種算法描述方法和算法設(shè)計的基本要求；.理解數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念；.掌握對算法的評價標(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)容.什么是數(shù)據(jù)結(jié)構(gòu).基本概念和術(shù)語.抽象數(shù)據(jù)類型的表示和實現(xiàn).算法和算法分析（1）算法（2）算法設(shè)計要求（3）算法效率的度量（4）算法的存儲空間需求第二章線性表（理論學(xué)時：8學(xué)時/實踐學(xué)時：3學(xué)時）（一）教學(xué)目標(biāo).理解線性表的概念、邏輯結(jié)構(gòu)特性以及兩種存儲結(jié)構(gòu)特性，針對實際應(yīng)用能從時間和空間復(fù)雜度的角度選用適當(dāng)?shù)拇鎯Y(jié)構(gòu)；.熟練掌握線性表的順序存儲結(jié)構(gòu)及其各種基本運算；.熟練掌握線性表的鏈?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)立、查找、插入和刪除等基本操作及相關(guān)算法。難點：線性表順序和鏈?zhǔn)酱鎯崿F(xiàn)中的某些操作及相關(guān)算法。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容.線性表的類型定義.線性表的順序表示和實現(xiàn).線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（1）線性鏈表（2）循環(huán)鏈表（3）雙向鏈表第三章棧和隊列（理論學(xué)時：5學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo).掌握棧和隊列的定義、表示、實現(xiàn)和應(yīng)用；.掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)以及相應(yīng)操作的實現(xiàn)；,了解遞歸的概念和遞歸過程的實現(xiàn)；.掌握隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）和鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)；（二）重點、難點重點：棧和隊列的定義、表示、實現(xiàn)和應(yīng)用；棧的順序存儲結(jié)構(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）抽象數(shù)據(jù)類型棧的定義（2）棧的表示和實現(xiàn).棧的應(yīng)用舉例（1）數(shù)值轉(zhuǎn)換（2）括號匹配的檢驗（3）行編輯程序（4）迷宮求解（5）表達式求值.隊列（1）抽象數(shù)據(jù)類型隊列的定義（2）鏈隊列-隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（3）循環(huán)隊列-隊列的順序表示和實現(xiàn)第四章串（理論學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo).掌握串的基本概念、順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)；.掌握串的各種基本運算；.掌握順序存儲結(jié)構(gòu)上串的各種操作，了解串的應(yīng)用；.（二）重點、難點重點：串的基本概念、順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)及各種基本運算；難點：串的各種基本運算。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容.串類型定義.串的表示和實現(xiàn)（1）定長順序存儲表示（2）堆分配存儲表示（3）串的塊鏈存儲表示第五章數(shù)組和廣義表（理論學(xué)時：3學(xué)時/實踐學(xué)時：2學(xué)時）（一）教學(xué)目標(biāo).掌握數(shù)組的順序存儲和特殊矩陣的壓縮存儲。.了解廣義表的概念和存儲結(jié)構(gòu)。（二）重點、難點重點：數(shù)組的存儲表示方法，順序存儲數(shù)組時數(shù)據(jù)元素之間的地址關(guān)系，特殊矩陣的壓縮存儲方法，稀疏矩陣的壓縮存儲方法，廣義表的定義、性質(zhì)和存儲結(jié)構(gòu)。難點：特殊矩陣和壓縮矩陣的存儲表示（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容.數(shù)組的定義.數(shù)組的順序表示和實現(xiàn).矩陣的壓縮存儲（1）特殊矩陣（2）稀疏矩陣.廣義表的定義.廣義表的存儲結(jié)構(gòu)第六章樹和二叉樹（理論學(xué)時：9學(xué)時/實踐學(xué)時：3學(xué)時）（一）教學(xué)目標(biāo).熟練掌握二叉樹的定義、性質(zhì)、各種存儲結(jié)構(gòu)的特點及適用范圍；.熟練掌握二叉樹的各種遍歷算法；.理解線索二叉樹的概念、存儲結(jié)構(gòu)及線索化算法；.理解樹的基本概念及其存儲結(jié)構(gòu)；掌握樹和森林與二叉樹間的轉(zhuǎn)換，掌握樹和森林的遍歷算法；.掌握哈夫曼樹的概念、存儲結(jié)構(gòu)；建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)路徑長度的計算;（二）重點、難點重點：二叉樹的定義、結(jié)構(gòu)特點和性質(zhì)，二叉樹的設(shè)計和實現(xiàn)，二叉樹存儲結(jié)構(gòu)的特點,先序、中序、后序遍歷的遞歸和非遞歸算法，二叉樹的線索化過程，最優(yōu)二叉樹的特性及建立最優(yōu)二叉樹和構(gòu)造哈夫曼編碼的方法。樹和森林與二叉樹間的轉(zhuǎn)換。難點：二叉樹遍歷的非遞歸算法，二叉樹的線索化算法。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容.樹的定義和基本術(shù)語.二叉樹（1）二叉樹的定義（2）二叉樹的性質(zhì)（3）二叉樹的存儲結(jié)構(gòu).遍歷二叉樹和線索二叉樹（1）遍歷二叉樹（2）線索二叉樹.樹和森林（1）樹的存儲結(jié)構(gòu)（2）森林與二叉樹的轉(zhuǎn)換（3）樹和森林的遍歷.赫夫曼樹及其應(yīng)用（1）最優(yōu)二叉樹（赫夫曼樹）（2）赫夫曼編碼第七章圖（理論學(xué)時：9學(xué)時/實踐學(xué)時：2學(xué)時）（-）教學(xué)目標(biāo).理解圖的基本概念，掌握圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)；.熟練掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法；.掌握構(gòu)造最小生成樹的方法及其算法；.掌握求拓?fù)渑判蚝完P(guān)鍵路徑的方法，理解其算法；.理解帶權(quán)最短路徑的概念，掌握用Dijkstra方法求最短路徑的算法；（二）重點、難點重點：圖的定義、術(shù)語、結(jié)構(gòu)特點和性質(zhì)，圖的鄰接矩陣、鄰接表的存儲結(jié)構(gòu)及其構(gòu)造方法，圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法，構(gòu)造連通圖的最小生成樹算法，有向無環(huán)圖的拓?fù)渑判蛩惴ā㈥P(guān)鍵路徑的算法，最短路徑求解中的Dijkstra算法和Floyed算法。難點：圖的存儲結(jié)構(gòu)及圖的各種應(yīng)用的算法。.（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容.圖的定義和術(shù)語.圖的存儲結(jié)構(gòu)(1)數(shù)組表示法(2)鄰接表(3)十字鏈表(4)鄰接多重表.圖的遍歷(1)深度優(yōu)先搜索(2)廣度優(yōu)先搜索.圖的連通性問題(1)無向圖的連通分量和生成樹(2)最小生成樹.有向無環(huán)圖及其應(yīng)用(1)拓?fù)渑判?2)關(guān)鍵路徑.最短路徑(1)從某個源點到其余各頂點的最短路徑(2)每一對頂點之間的最短路徑第九章查找(理論學(xué)時：6學(xué)時/實踐學(xué)時：2學(xué)時)(-)教學(xué)目標(biāo).理解查找及其算法的時間復(fù)雜度，靜態(tài)查找表的概念；.熟練掌握順序查找、折半查找和分塊查找算法，能對其性能進行分析；.掌握二叉排序樹查找算法；理解二叉平衡樹，B樹的概念；.理解哈希表的含義；掌握哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法；(二)重點、難點重點：順序查找、折半查找和分塊查找算法，哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法；難點：哈希函數(shù)的構(gòu)造方法，哈希表的建立和查找以及處理沖突的基本方法，各種查找算法的性能進行分析。(三)教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合(四)教學(xué)內(nèi)容.靜態(tài)查找表(1)順序表的查找(2)有序表的查找(3)索引順序表的查找.動態(tài)查找表(1)二叉排序樹和平衡二叉樹B-樹和B+樹.哈希表(1)什么是哈希表(2)哈希函數(shù)的構(gòu)造方法（3）處理沖突的方法（4）哈希表的查找及其分析第十章內(nèi)部排序（理論學(xué)時：6學(xué)時/實踐學(xué)時：2學(xué)時）（-）教學(xué)目標(biāo),了解內(nèi)部排序的概念；.掌握插入類排序的算法，直接插入排序、希爾排序;.掌握交換類排序的算法，冒泡排序、快速排序；.掌握選擇類排序的算法，簡單項選擇擇排序、堆排序;.了解歸并排序、基數(shù)排序的算法；.掌握各種排序方法的特點，能夠?qū)Ω鞣N排序算法進行評價，并能加以靈活應(yīng)用;（二）重點、難點重點：插入類排序的算法，直接插入排序、希爾排序；掌握交換類排序的算法，冒泡排序、快速排序，掌握選擇類排序的算法，簡單項選擇擇排序、堆排序；難點：各種排序方法的特點，能夠?qū)Ω鞣N排序算法進行評價，并能加以靈活應(yīng)用。（三）教學(xué)方法多媒體課件輔助教學(xué)，理論和實踐結(jié)合（四）教學(xué)內(nèi)容.概述.插入排序（1）直接插入排序（2）其他插入排序（3）希爾排序,快速排序.選擇排序（1）簡單項選擇擇排序（2）樹形選擇排序（3）堆排序.歸并排序.基數(shù)排序（1）多關(guān)鍵字的排序（2）鏈?zhǔn)交鶖?shù)排序.各種內(nèi)部排序方法的比擬討論四、考核形式及成績評定（一）考核形式：期末考試為閉卷考試，考試范圍和要求應(yīng)符合本教學(xué)大綱對各章教學(xué)內(nèi)容的基本要求。（二）成績評定：課程考核由平時作業(yè)及聽課情況和期末考試成績兩局部組成，分別占課程總成績的30%和70%0五、教材與參考書教材：嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言）.（第三版）.北京：清華大學(xué)出版社，2007參考書：