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

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程編號(hào)：150115X3課程名稱：數(shù)據(jù)結(jié)構(gòu)（Data Structure）學(xué) 分：3學(xué)分總 學(xué) 時(shí)：54理論學(xué)時(shí)：36實(shí)驗(yàn)學(xué)時(shí)：18先修課程：計(jì)算機(jī)基礎(chǔ)、C語(yǔ)言程序設(shè)計(jì)適用專業(yè)：生物醫(yī)學(xué)工程四年制參考教材：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)課程主要介紹和研究數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)和處理方法，它是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)核心課程，在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且對(duì)于學(xué)習(xí)計(jì)算杌專業(yè)的其他課程都是有益的。針對(duì)生物醫(yī)學(xué)工程專業(yè)學(xué)生，注重培養(yǎng)學(xué)生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，能根據(jù)實(shí)際問(wèn)題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)與算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，并能設(shè)計(jì)出解決問(wèn)題的有效算法，提高程序設(shè)計(jì)和調(diào)試能力。通過(guò)課堂教學(xué)、上機(jī)實(shí)習(xí)，使學(xué)生了解數(shù)據(jù)對(duì)象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實(shí)世界問(wèn)題在計(jì)算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計(jì)技能，

3、為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。二、課程教學(xué)的基本要求：1.課程理論與基本知識(shí)（1）從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)方面去掌握線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(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ù)組織的基本方法，利用抽象數(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)題的思維

4、邏輯，培養(yǎng)學(xué)生的系統(tǒng)化程序設(shè)計(jì)能力，激發(fā)學(xué)生的創(chuàng)造性。（3）能夠應(yīng)用一門(mén)程序設(shè)計(jì)語(yǔ)言進(jìn)行各種應(yīng)用系統(tǒng)的設(shè)計(jì)、開(kāi)發(fā)及維護(hù)。三、課程學(xué)時(shí)分配：授課內(nèi)容總學(xué)時(shí)理論學(xué)時(shí)實(shí)驗(yàn)（見(jiàn)習(xí)）時(shí)數(shù)備注緒論330線性表963棧和隊(duì)列1266串330樹(shù)和二叉樹(shù)1293圖963內(nèi)部排序633小計(jì)543618四、考核：1.考核方式：理論考核（筆試）、實(shí)驗(yàn)考核（機(jī)試）、平時(shí)考核。2.成績(jī)構(gòu)成：理論考核80%+平時(shí)考核20%。五、課程基本內(nèi)容：【理論課部分】第一章 緒論（一）目的要求：1.熟悉各名詞術(shù)語(yǔ)及基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)間的關(guān)系；2.了解抽象數(shù)據(jù)類型的定義，表示和實(shí)現(xiàn)方法；3.熟悉類C語(yǔ)言的書(shū)寫(xiě)規(guī)范，

5、掌握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ā)式），舉例法，演示法。（五）教學(xué)手段：多媒體+板書(shū)。第二章 線性表（一）目的要求：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)

6、；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)；各種鏈表的特點(diǎn)及在其上實(shí)現(xiàn)線性表基本操作的方法。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法。（五）教學(xué)手段：多媒體+板書(shū)。第三章 棧和隊(duì)列（一）目的要求：1.掌握棧這種抽

7、象數(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)、基本操作算法實(shí)現(xiàn)。難點(diǎn)：棧的基本操作，尤其是棧滿和棧空的判斷；循環(huán)隊(duì)列的鏈隊(duì)列的應(yīng)用。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，PBL教學(xué)法。（五）教學(xué)手段：多媒體+板書(shū)第四章 串

8、（一）目的要求：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é)手段：多媒體+板書(shū)第六章 樹(shù)和二叉樹(shù)（一）目的要求：1.掌握樹(shù)及二叉樹(shù)的結(jié)構(gòu)特征，了解相應(yīng)的證明方法；2.熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)；3.熟悉掌握二叉樹(shù)的遍歷算法；4.理解二叉樹(shù)的線索化的實(shí)質(zhì)；5.熟練掌

9、握二叉樹(shù)的線索化過(guò)程；6.掌握樹(shù)的存儲(chǔ)結(jié)構(gòu)；7.熟練掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法；8.掌握樹(shù)和森林的遍歷；9.掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。（二）教學(xué)時(shí)數(shù)：9學(xué)時(shí)（三）教學(xué)內(nèi)容：1.樹(shù)的定義和基本術(shù)語(yǔ)2.二叉樹(shù)3.遍歷二叉樹(shù)和線索二叉樹(shù)4.赫夫曼樹(shù)及其應(yīng)用重點(diǎn)：二叉樹(shù)的的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、二叉樹(shù)的遍歷、線索算法；樹(shù)的存儲(chǔ)結(jié)構(gòu)，樹(shù)和森林的定義及與二叉樹(shù)的轉(zhuǎn)換方法；建立最優(yōu)樹(shù)和哈夫曼編碼的方法。難點(diǎn)：二叉樹(shù)的性質(zhì)及其證明、二叉樹(shù)的遍歷、線索算法；樹(shù)的存儲(chǔ)結(jié)構(gòu)，森林與二叉樹(shù)的轉(zhuǎn)換方法；建立最優(yōu)樹(shù)和哈夫曼編碼的方法。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法

10、。（五）教學(xué)手段：多媒體+板書(shū)第七章 圖（一）目的要求：1.熟悉圖的定義和術(shù)語(yǔ)；2.熟悉圖的鄰接矩陣和鄰接表表示法及其構(gòu)造算法；3.了解圖的十字鏈表表示法和鄰接多重表表示法及其構(gòu)造算法；4.掌握?qǐng)D的兩種搜索路徑的遍歷；5.理解掌握?qǐng)D的連通性問(wèn)題的方法；6.掌握最小生成樹(shù)的構(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é)構(gòu)3.圖的遍歷4.圖的連通性問(wèn)題5.有向無(wú)環(huán)圖及其應(yīng)用重點(diǎn)：圖的鄰接矩陣表示法和鄰接表表示法；圖的兩種搜索路徑的遍歷；最小生成樹(shù)的構(gòu)造方法；拓?fù)渑判?、關(guān)鍵路徑。難點(diǎn)：圖的鄰接表表示法；深度優(yōu)先

11、和廣度優(yōu)先算法；最小生成樹(shù)的構(gòu)造方法、關(guān)鍵路徑。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法，PBL教學(xué)法。（五）教學(xué)手段：多媒體+板書(shū)第十章 內(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ù)排序7.各種內(nèi)部排序的比較討論重點(diǎn)：插入排序的基本思想、算法特點(diǎn)。難點(diǎn)：希爾排序。（四）教學(xué)方法：講授法（引導(dǎo)式、啟發(fā)式），舉例法，演示法，案例教學(xué)法。（五）教學(xué)手段：多媒體+板書(shū)【實(shí)驗(yàn)課部分】實(shí)

12、驗(yàn)一 線性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（一）目的要求：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)上實(shí)現(xiàn)線性表基本操作的方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)線性表順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的基本操作的實(shí)現(xiàn)（線性表的創(chuàng)建、插入、刪除和查找）2.用線性表的兩種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)將兩個(gè)有序線性表合并為一個(gè)有序線性表實(shí)驗(yàn)二 棧和隊(duì)列（一）目的要求：1.掌握棧這種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們

13、；2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法、理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程；3.掌握隊(duì)列這種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；4.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。（二）教學(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ù)4.編程實(shí)現(xiàn)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作（隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、出隊(duì)列）實(shí)驗(yàn)三 串和數(shù)組（一）目的要求：1.掌握串的基本操作的定義，并能利用這些操作實(shí)現(xiàn)串的其他各種操作；2.熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法；3.掌握數(shù)組的類型定義和表示方法；4.特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法及運(yùn)算的實(shí)現(xiàn)。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)串的基本操作2.編程實(shí)現(xiàn)兩個(gè)矩陣相乘實(shí)驗(yàn)四 二叉樹(shù)和哈夫曼編碼（一）目的要求：1.熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)；2.熟悉掌握二叉樹(shù)的遍歷算法；3.掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。（二）教學(xué)內(nèi)容：1.編程實(shí)現(xiàn)二叉樹(shù)的先序、后序遞歸遍歷2.根據(jù)已知的字符及其權(quán)值，編程實(shí)現(xiàn)建立哈夫曼樹(shù)，并輸出哈夫曼編碼實(shí)驗(yàn)五 圖（一）目的要求：1.熟悉圖的鄰接矩陣和鄰接表表