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

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程編號(hào)：150116B3課程名稱：數(shù)據(jù)結(jié)構(gòu)（Data Structure）學(xué) 分：4學(xué)分總 學(xué) 時(shí)：72理論學(xué)時(shí)：36實(shí)驗(yàn)學(xué)時(shí)：36先修課程：計(jì)算機(jī)基礎(chǔ)、C語(yǔ)言程序設(shè)計(jì)適用專業(yè)：信息管理與信息系統(tǒng)四年制參考教材：1.譚浩強(qiáng)主編，C程序設(shè)計(jì)（第三版），清華大學(xué)出版社，20052.嚴(yán)蔚敏、嚴(yán)為民主編，數(shù)據(jù)結(jié)構(gòu)（第一版），清華大學(xué)出版社，20043.嚴(yán)蔚敏、嚴(yán)為民、米寧主編，數(shù)據(jù)結(jié)構(gòu)習(xí)題集（第一版），清華大學(xué)出版社，20044.周云靜主編，數(shù)據(jù)結(jié)構(gòu)（第一版），冶金工業(yè)出版社，20055.周云靜主編，數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機(jī)指導(dǎo)（第一版），冶金工業(yè)出版社，2004一、課程在培養(yǎng)方案中的

2、地位、目的和任務(wù)：數(shù)據(jù)結(jié)構(gòu)是信息的組織方式，對(duì)于相同的算法，用不同的數(shù)據(jù)結(jié)構(gòu)表示其中的抽象數(shù)據(jù)類型會(huì)造成不同的執(zhí)行效率。這就有必要研究各種抽象數(shù)據(jù)類型用不同的數(shù)據(jù)結(jié)構(gòu)表示的效率差異以及適用場(chǎng)合。數(shù)據(jù)結(jié)構(gòu)課程主要介紹和研究數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)和處理方法，旨在培養(yǎng)學(xué)生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，使學(xué)生深入了解數(shù)據(jù)結(jié)構(gòu)的邏輯思想和實(shí)現(xiàn)方法及應(yīng)用技術(shù)，告訴學(xué)生如何編寫效率高、結(jié)構(gòu)好的程序。它是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程，在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且對(duì)于學(xué)習(xí)計(jì)算杌專業(yè)的其他課程都是有益的。針對(duì)信息管理和信息系統(tǒng)的學(xué)生特點(diǎn)，通過(guò)課堂教學(xué)、上機(jī)實(shí)習(xí)，使學(xué)生

3、了解數(shù)據(jù)對(duì)象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實(shí)世界問(wèn)題在計(jì)算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計(jì)技能，培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)理論知識(shí)解決復(fù)雜實(shí)際問(wèn)題的實(shí)踐能力、研究性學(xué)習(xí)能力和團(tuán)隊(duì)合作能力。二、課程教學(xué)的基本要求：1.課程理論與基本知識(shí)（1）從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)方面去掌握線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹、圖和文件等常用的數(shù)據(jù)結(jié)構(gòu)。（2）掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)的排列和查找運(yùn)算。（3）對(duì)算法的時(shí)間和空間復(fù)雜性有一定的分析能力。2.基本技能（1）培養(yǎng)學(xué)生分析問(wèn)題、解決問(wèn)題的能力，學(xué)會(huì)對(duì)處理的數(shù)據(jù)建立抽象數(shù)據(jù)類型，掌握數(shù)據(jù)組織的基本方法

4、，利用抽象數(shù)據(jù)類型進(jìn)行程序設(shè)計(jì)。（2）通過(guò)不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的不同算法及其設(shè)計(jì)思想，掌握結(jié)構(gòu)選擇和算法設(shè)計(jì)的思維方式。通過(guò)綜合性的實(shí)驗(yàn)題目，提升學(xué)生分析和解決問(wèn)題的思維邏輯，培養(yǎng)學(xué)生的系統(tǒng)化程序設(shè)計(jì)能力，激發(fā)學(xué)生的創(chuàng)造性。（3）能夠應(yīng)用一門程序設(shè)計(jì)語(yǔ)言進(jìn)行各種應(yīng)用系統(tǒng)的設(shè)計(jì)、開發(fā)及維護(hù)。三、課程學(xué)時(shí)分配：授課內(nèi)容總學(xué)時(shí)理論學(xué)時(shí)實(shí)驗(yàn)（見習(xí)）時(shí)數(shù)備注緒論633線性表1266棧和隊(duì)列1266串633樹和二叉樹1299圖1266內(nèi)部排序633小計(jì)723636四、考核： 1.考核方式：理論考核（筆試）、實(shí)驗(yàn)考核（機(jī)試）、平時(shí)考核。 2.成績(jī)構(gòu)成：理論考核80%+平時(shí)考核20%。五、課程基本內(nèi)容：【理論課

5、部分】第一章 緒論（一）目的要求：1.熟悉各名詞術(shù)語(yǔ)及基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)間的關(guān)系；2.了解抽象數(shù)據(jù)類型的定義，表示和實(shí)現(xiàn)方法；3.熟悉類C語(yǔ)言的書寫規(guī)范，掌握C語(yǔ)言語(yǔ)法。 （二）教學(xué)時(shí)數(shù)：3學(xué)時(shí)（三）教學(xué)內(nèi)容：1.什么是數(shù)據(jù)結(jié)構(gòu)2.基本概念和術(shù)語(yǔ)3.抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)4.算法和算法分析重點(diǎn)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和抽象數(shù)據(jù)類型、算法等概念術(shù)語(yǔ)的確切含義；及算法的時(shí)間復(fù)雜度分析。 難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、ADT、算法等重要概念；算法的概念，評(píng)價(jià)標(biāo)準(zhǔn)及從時(shí)間和空間角度分析算法的方法。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法。（五）

6、教學(xué)手段：多媒體+板書。第二章 線性表（一）目的要求：1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；2.掌握線性表順序存儲(chǔ)結(jié)構(gòu)的基本操作：查找、插入和刪除的算法；3.掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法；4.熟練掌握在各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線性表基本操作的方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。（二）教學(xué)時(shí)數(shù)：6學(xué)時(shí)（三）教學(xué)內(nèi)容：1.線性表的類型定義2.線性表的順序表示和實(shí)現(xiàn)3.線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)重點(diǎn)：線性表的存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法及基本操作。難點(diǎn)：順序表的描述方法及插入、刪除等基本操作的實(shí)現(xiàn)；各

7、種鏈表的特點(diǎn)及在其上實(shí)現(xiàn)線性表基本操作的方法。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法。（五）教學(xué)手段：多媒體+板書。第三章 棧和隊(duì)列（一）目的要求：1.掌握棧這種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法；3.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程；4.掌握隊(duì)列這種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；5.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。（二）教學(xué)時(shí)數(shù)：6學(xué)時(shí)（三）教學(xué)內(nèi)容： 1.棧2.棧的應(yīng)用舉例3.棧與遞歸的實(shí)現(xiàn)4.隊(duì)列重點(diǎn)：棧的存儲(chǔ)結(jié)構(gòu)、特點(diǎn)、基本操作算法實(shí)現(xiàn)；隊(duì)列的存儲(chǔ)結(jié)構(gòu)、特點(diǎn)、基本操作算法

8、實(shí)現(xiàn)。難點(diǎn)：棧的基本操作，尤其是棧滿和?？盏呐袛?；循環(huán)隊(duì)列的鏈隊(duì)列的應(yīng)用。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，PBL教學(xué)法。（五）教學(xué)手段：多媒體+板書第四章 串（一）目的要求：1.掌握串的基本操作的定義，并能利用這些操作實(shí)現(xiàn)串的其他各種操作；2.熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。（二）教學(xué)時(shí)數(shù)：3學(xué)時(shí)（三）教學(xué)內(nèi)容： 1.串類型的定義2.串的表示和實(shí)現(xiàn) 3.串的模式匹配算法4.串操作應(yīng)用舉例重點(diǎn)：串的基本操作及定長(zhǎng)順序存儲(chǔ)的實(shí)現(xiàn)。難點(diǎn)：定長(zhǎng)順序存儲(chǔ)的實(shí)現(xiàn)。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法。（五）教學(xué)手段：多媒體+

9、板書第六章 樹和二叉樹（一）目的要求：1.掌握樹及二叉樹的結(jié)構(gòu)特征，了解相應(yīng)的證明方法；2.熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)；3.熟悉掌握二叉樹的遍歷算法；4.理解二叉樹的線索化的實(shí)質(zhì)；5.熟練掌握二叉樹的線索化過(guò)程；6.掌握樹的存儲(chǔ)結(jié)構(gòu)；7.熟練掌握樹和森林與二叉樹的轉(zhuǎn)換方法；8.掌握樹和森林的遍歷；9.掌握建立最優(yōu)樹和哈夫曼編碼的方法。（二）教學(xué)時(shí)數(shù)：9學(xué)時(shí)（三）教學(xué)內(nèi)容： 1.樹的定義和基本術(shù)語(yǔ)2.二叉樹3.遍歷二叉樹和線索二叉樹4.赫夫曼樹及其應(yīng)用重點(diǎn)：二叉樹的的定義和性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的遍歷、線索算法；樹的存儲(chǔ)結(jié)構(gòu)，樹和森林的定義及與二叉樹的轉(zhuǎn)換方法；建立最優(yōu)樹和哈夫曼編碼的方法

10、。難點(diǎn)：二叉樹的性質(zhì)及其證明、二叉樹的遍歷、線索算法；樹的存儲(chǔ)結(jié)構(gòu)，森林與二叉樹的轉(zhuǎn)換方法；建立最優(yōu)樹和哈夫曼編碼的方法。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法。（五）教學(xué)手段：多媒體+板書第七章 圖（一）目的要求：1.熟悉圖的定義和術(shù)語(yǔ)；2.熟悉圖的鄰接矩陣和鄰接表表示法及其構(gòu)造算法；3.了解圖的十字鏈表表示法和鄰接多重表表示法及其構(gòu)造算法；4.掌握?qǐng)D的兩種搜索路徑的遍歷；5.理解掌握?qǐng)D的連通性問(wèn)題的方法；6.掌握最小生成樹的構(gòu)造方法；7.理解有向無(wú)環(huán)圖及其應(yīng)用；8.掌握求關(guān)鍵路徑的方法。（二）教學(xué)時(shí)數(shù)：6學(xué)時(shí) （三）教學(xué)內(nèi)容： 1.圖的定義和術(shù)語(yǔ)2.圖的存儲(chǔ)結(jié)

11、構(gòu)3.圖的遍歷4.圖的連通性問(wèn)題5.有向無(wú)環(huán)圖及其應(yīng)用重點(diǎn)：圖的鄰接矩陣表示法和鄰接表表示法；圖的兩種搜索路徑的遍歷；最小生成樹的構(gòu)造方法；拓?fù)渑判?、關(guān)鍵路徑。難點(diǎn)：圖的鄰接表表示法；深度優(yōu)先和廣度優(yōu)先算法；最小生成樹的構(gòu)造方法、關(guān)鍵路徑。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法，PBL教學(xué)法。（五）教學(xué)手段：多媒體+板書第十章 內(nèi)部排序（一）目的要求：1.掌握插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序的基本思想;2.算法特點(diǎn)和排序過(guò)程及其時(shí)間復(fù)雜度分析。（二）教學(xué)時(shí)數(shù)：3學(xué)時(shí)（三）教學(xué)內(nèi)容： 1.概述2.插入排序3.快速排序4.選擇排序5.歸并排序6.基數(shù)排

12、序7.各種內(nèi)部排序的比較討論重點(diǎn)：插入排序的基本思想、算法特點(diǎn)。難點(diǎn)：希爾排序。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法。（五）教學(xué)手段：多媒體+板書【實(shí)驗(yàn)課部分】實(shí)驗(yàn)一 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)（一）目的要求：1.熟悉各名詞術(shù)語(yǔ)及基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)間的關(guān)系；2.了解抽象數(shù)據(jù)類型的定義，表示和實(shí)現(xiàn)方法；3.掌握各種數(shù)據(jù)類型。（二）教學(xué)內(nèi)容：1.熟悉Turbo C 基本操作環(huán)境2.將抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)轉(zhuǎn)化為C語(yǔ)言，并驗(yàn)證3.編程序?qū)崿F(xiàn)數(shù)組數(shù)據(jù)的插入和刪除實(shí)驗(yàn)二 線性表的順序存儲(chǔ)結(jié)構(gòu)（一）目的要求：1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存

13、在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；2.掌握線性表順序存儲(chǔ)結(jié)構(gòu)的基本操作：查找、插入和刪除的算法。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)線性表順序存儲(chǔ)結(jié)構(gòu)中的基本操作的實(shí)現(xiàn)（線性表的創(chuàng)建、插入、刪除和查找）2.用線性表順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)將兩個(gè)有序線性表合并為一個(gè)有序線性表實(shí)驗(yàn)三 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（一）目的要求：1.掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法；2.熟練掌握在各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線性表基本操作的方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)線性表順序鏈?zhǔn)浇Y(jié)構(gòu)中的基本操作的實(shí)現(xiàn)（線性表的創(chuàng)建、插入、刪除和查找）2.用線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)

14、現(xiàn)將兩個(gè)有序線性表合并為一個(gè)有序線性表實(shí)驗(yàn)四 棧（一）目的要求：1.掌握棧這種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法、理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)棧在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作（棧的初始化、判?？?、進(jìn)棧、出棧）2.編程實(shí)現(xiàn)一個(gè)表達(dá)式的計(jì)算3.編程實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)化為其它進(jìn)制數(shù)實(shí)驗(yàn)五 隊(duì)列（一）目的要求：1.掌握隊(duì)列這種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；2.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作（隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列

15、、出隊(duì)列實(shí)驗(yàn)六 串（一）目的要求：1.掌握串的基本操作的定義，并能利用這些操作實(shí)現(xiàn)串的其他各種操作；2.熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)串的基本操作和串的匹配實(shí)驗(yàn)七 樹和二叉樹（一）目的要求：1.掌握樹及二叉樹的結(jié)構(gòu)特征；2.熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)；3.熟悉掌握二叉樹的遍歷算法。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)二叉樹的建立2.編程實(shí)現(xiàn)二叉樹的先序、后序遞歸遍歷3.編程實(shí)現(xiàn)二叉樹的中序非遞歸遍歷實(shí)驗(yàn)八 樹和森林（一）目的要求：1.掌握森林的結(jié)構(gòu)特征；2.熟悉樹和森林遍歷算法；3.掌握森林和二叉樹的轉(zhuǎn)換。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)樹的存儲(chǔ)2.編程實(shí)現(xiàn)樹和森林的遍歷3.完成森林和二叉樹的轉(zhuǎn)換實(shí)驗(yàn)九 哈夫曼編碼（一）目的要求：1.掌握建立最優(yōu)樹；2.掌握哈夫曼編碼的方法。（二）教學(xué)內(nèi)容：1.根據(jù)已知的字符及其權(quán)值，編程實(shí)現(xiàn)建立哈夫曼樹，并輸出哈夫曼編碼實(shí)驗(yàn)十 圖（一）（一）目的要求：1.熟悉圖的鄰接矩陣和鄰接表表示法及其構(gòu)造算法；2.掌握?qǐng)D的兩種搜索路徑的遍歷；3.理解掌握?qǐng)D的連通性問(wèn)題的方法；4.掌握最小生成樹的構(gòu)造方法。（二）教學(xué)內(nèi)容：1.在鄰接鏈表存儲(chǔ)