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

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