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

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)課程編號(hào)：408009420009436009適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)網(wǎng)絡(luò)工程軟件工程課程類別：專業(yè)必修課專業(yè)必修課專業(yè)必修課課程學(xué)分：4總 學(xué) 時(shí)：72其中：理論學(xué)時(shí)42實(shí)驗(yàn)學(xué)時(shí)30先修課程：數(shù)據(jù)結(jié)構(gòu)、匯編程序設(shè)計(jì)、微機(jī)原理、操作系統(tǒng)原理、高等代數(shù)一、課程的性質(zhì)、目的與任務(wù)數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門必修的專業(yè)基礎(chǔ)課。這門課程的主要特點(diǎn)是實(shí)踐性很強(qiáng),不僅要學(xué)習(xí)基本理論知識(shí),更要注重上機(jī)實(shí)踐,通過上機(jī)實(shí)踐驗(yàn)證算法的正確性,掌握和鞏固所學(xué)理論知識(shí)。設(shè)立本門課程的目的是通過學(xué)習(xí)，使學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適

2、當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步了解對(duì)算法的時(shí)間分析和空間分析技術(shù)。另一方面，通過對(duì)本課程算法設(shè)計(jì)和上機(jī)實(shí)踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能力，為后續(xù)課程，特別是軟件課程打下堅(jiān)實(shí)的知識(shí)基礎(chǔ)。要求學(xué)生掌握各種常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及有關(guān)操作的算法。二、課程教學(xué)基本內(nèi)容與要求第一章、緒論（一）基本教學(xué)內(nèi)容：1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念與術(shù)語1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4 算法與算法分析（二）基本要求教學(xué)目的：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，了解抽象數(shù)據(jù)類型，了解算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析，了解算法的描述方法。重點(diǎn)：據(jù)結(jié)構(gòu)的基本概念、算法描述、算法

3、分析難點(diǎn)：算法描述、算法分析第二章、線性表（一）基本教學(xué)內(nèi)容：2.1 線性表的類型定義2.2 線性表的順序表示與實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)（二）基本要求教學(xué)目的：理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明；掌握在順序表和鏈表上實(shí)現(xiàn)的插入、刪除和按值查找的算法；了解循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。重點(diǎn)：線性表的定義及其運(yùn)算、組織形式、結(jié)構(gòu)特征和類型說明、順序表和鏈表上實(shí)現(xiàn)的插入、刪除和按值查找的算法、循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作難點(diǎn)：線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)相關(guān)算法、循環(huán)鏈表、雙(循環(huán)

4、)鏈表的插入、刪除等操作第三章、棧和隊(duì)列（一）基本教學(xué)內(nèi)容：3.1 棧3.2 棧的應(yīng)用舉例3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列（二）基本要求教學(xué)目的：理解棧的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)算的實(shí)現(xiàn)；理解隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。重點(diǎn)：棧的存儲(chǔ)結(jié)構(gòu)、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、棧與隊(duì)列的應(yīng)用難點(diǎn)：隊(duì)列的存儲(chǔ)結(jié)構(gòu)、棧與隊(duì)列的應(yīng)用第四章、串（一）基本教學(xué)內(nèi)容：4.1 串類型的定義4.2 串的表示與實(shí)現(xiàn)4.3 串的模式匹配算法4.4 串的操作應(yīng)用舉例（二）基本要求教學(xué)目的：了解串的邏輯定義；掌握用順序存儲(chǔ)串

5、及堆存儲(chǔ)串時(shí)的特點(diǎn)及在這兩種存儲(chǔ)方式下基本操作的實(shí)現(xiàn)；了解改進(jìn)的模式匹配算法；重點(diǎn)：串的存儲(chǔ)結(jié)構(gòu)、串的模式匹配難點(diǎn)：串的存儲(chǔ)結(jié)構(gòu)、串的模式匹配第五章、數(shù)組和廣義表（一）基本教學(xué)內(nèi)容：5.1 數(shù)組的定義5.2 數(shù)組的順序表示與實(shí)現(xiàn)5.3 矩陣的壓縮存儲(chǔ)5.4 廣義表的定義（二）基本要求教學(xué)目的：掌握數(shù)組的順序存儲(chǔ)結(jié)構(gòu)及特殊矩陣的存儲(chǔ)方式；了解稀疏矩陣的壓縮存儲(chǔ)方式三元組表。重點(diǎn)：數(shù)組的順序存儲(chǔ)結(jié)構(gòu)、.特殊矩陣的壓縮存儲(chǔ)方法難點(diǎn)：.特殊矩陣的壓縮存儲(chǔ)方法第六章、樹和二叉樹（一）基本教學(xué)內(nèi)容：6.1 樹的定義和基本術(shù)語6.2 二叉樹6.3 遍歷二叉樹和線索二叉樹6.4 樹和森林6.6赫夫曼樹及應(yīng)用（

6、二）基本要求教學(xué)目的：深刻理解二叉樹的定義、性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題。重點(diǎn)：二叉樹的定義，性質(zhì)，基本運(yùn)算和存儲(chǔ)結(jié)構(gòu)、二叉樹的遍歷和線索二叉樹、Huffman樹及應(yīng)用難點(diǎn)：二叉樹的遍歷和線索二叉樹、Huffman樹及應(yīng)用第七章、圖（一）基本教學(xué)內(nèi)容：7.1 圖的定義和術(shù)語7.2 圖的存儲(chǔ)結(jié)構(gòu)7.3 圖的遍歷7.4 圖的連通性7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑（二）基本要求教學(xué)目的：理解圖的基本概念及術(shù)語；掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)方法

7、；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；領(lǐng)會(huì)拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)、圖的遍歷、圖的連通性問題難點(diǎn)：有向無環(huán)圖及其應(yīng)用第九章、查找（一）基本教學(xué)內(nèi)容：9.1 靜態(tài)查找表9.2 動(dòng)態(tài)查表9.3 哈希表（二）基本要求教學(xué)目的：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度；理解并掌握二叉排序樹的各種算法；重點(diǎn)：.動(dòng)態(tài)查找表、哈希表難點(diǎn)：動(dòng)態(tài)

8、查找表、哈希表十、內(nèi)部排序（一）基本教學(xué)內(nèi)容：10.1 概述10.2 插入排序10.3 快速排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序10.7 各種內(nèi)部排序方法的比較討論（二）基本要求教學(xué)目的：領(lǐng)會(huì)排序的基本思想和基本概念；理解并掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟和時(shí)空效率分析；三、課程各章節(jié)學(xué)時(shí)分配序號(hào)內(nèi)容理論學(xué)時(shí)實(shí)驗(yàn)學(xué)時(shí)計(jì)科網(wǎng)工軟工計(jì)科網(wǎng)工軟工1緒論2220002線性表8884443棧與隊(duì)列6664444串2222225數(shù)組與廣義表4442226樹與二叉樹8886667圖6666669查找33333310內(nèi)排序3333

9、33合計(jì)424242303030四、本課程課外學(xué)習(xí)與修學(xué)指導(dǎo)本課程強(qiáng)調(diào)理論和實(shí)踐的結(jié)合，突出對(duì)學(xué)生的動(dòng)手能力的培養(yǎng)。在對(duì)學(xué)生進(jìn)行基本數(shù)據(jù)結(jié)構(gòu)的技術(shù)、理論、設(shè)計(jì)等各種技能培養(yǎng)的同時(shí)，培養(yǎng)學(xué)生將實(shí)際問題轉(zhuǎn)化為基本數(shù)據(jù)結(jié)構(gòu)的問題的分析能力，鼓勵(lì)學(xué)生學(xué)以致用，將學(xué)到的知識(shí)用以解決實(shí)際問題，從而提高學(xué)生算法設(shè)計(jì)能力和軟件開發(fā)能力。由于該課程涉及數(shù)據(jù)的各種組織方法，內(nèi)容復(fù)雜，難度較大，且具有很強(qiáng)的實(shí)踐性，所以要學(xué)好本課程，必須做到理論與實(shí)踐緊密結(jié)合，才能達(dá)到較好的學(xué)習(xí)效果。要求學(xué)生多參閱相關(guān)書籍，多做練習(xí)，多上機(jī)實(shí)驗(yàn)，掌握算法的基本原理及其實(shí)現(xiàn)過程。五、本課程考核方式及成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)考核方式：閉卷考試成績(jī)?cè)u(píng)

10、定方法：本課程的考核是平時(shí)成績(jī)、上機(jī)考試和期終考試成績(jī)相結(jié)合。具體比例為：平時(shí)（出勤、作業(yè)）20%，上機(jī)考試占20%，期末考試成績(jī)占60%。其中期未考試總分100分，基礎(chǔ)題占50%，中等難度題占40%，較難題占10%。考試題型主要有：選擇題、填空題、簡(jiǎn)單算法應(yīng)用題、算法填空題、算法設(shè)計(jì)等。六、教學(xué)參考書1嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社.2006,42Sartaj Sahni. Data Structure, Algorithms, and Application in C+. The McGraw-Hill Company Inc.2006(數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語言描述.北京:機(jī)械工業(yè)出版社.2006)3Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996(數(shù)