計(jì)科數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)理論教案大綱 課程編號(hào)：404511043 課程中文名稱：數(shù)據(jù)結(jié)構(gòu) 課程英文名稱：Data Structures 課程類別：專業(yè)基礎(chǔ)必修課 總 學(xué)時(shí)：84學(xué)時(shí) 本課程先修課程（高級(jí)語(yǔ)言程序設(shè)計(jì) （2 本課程的后續(xù)課程（操作系統(tǒng)、數(shù)據(jù)庫(kù)原理 四、教案內(nèi)容、基本要求及學(xué)時(shí)安排 第一章概論 1. 教案目的及要求 領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系； 清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算 及其實(shí)現(xiàn)； 理解抽象數(shù)據(jù)類型的概念； 2.教案重點(diǎn) 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)； 邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別； 運(yùn)算的概念； 存儲(chǔ)結(jié)構(gòu)及其三個(gè)組成部分

2、； 抽象數(shù)據(jù)類型和數(shù)據(jù)抽象； 評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法。 3. 教案難點(diǎn) 區(qū)別算法與程序； 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別； 抽象數(shù)據(jù)類型與數(shù)據(jù)抽象； 算法的時(shí)間復(fù)雜度分析。 4. 教案內(nèi)容及進(jìn)度安排 ( 4 學(xué)時(shí) 1.1 數(shù)據(jù)結(jié)構(gòu)的概念 1.2 抽象數(shù)據(jù)類型 1.3 算法和算法分析 第二章 線性表 1. 教案目的及要求 理解線性表的定義及其運(yùn)算； 理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說(shuō)明； 掌握在這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法； 了解循環(huán)鏈表、雙 ( 循環(huán) 鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。 2. 教案重點(diǎn) 線性表的定義及邏輯上的特點(diǎn)； 順序表上插入、刪除

3、和定位運(yùn)算的實(shí)現(xiàn)； 單鏈表的結(jié)構(gòu)特點(diǎn)及類型說(shuō)明； 頭指針和頭結(jié)點(diǎn)的作用及區(qū)別； 指針操作； 定位、刪除、插入運(yùn)算在單鏈表上的實(shí)現(xiàn)； 循環(huán)鏈表、雙鏈表的結(jié)構(gòu)特點(diǎn)； 循環(huán)鏈表、雙鏈表上刪除與插入運(yùn)算的實(shí)現(xiàn)。 3. 教案難點(diǎn) 線性表與線性結(jié)構(gòu)的聯(lián)系與區(qū)別； 頭結(jié)點(diǎn)在鏈表中的作用；指針操作； 刪除、插入運(yùn)算中的指針操作順序； 雙鏈表上指針的操作順序 4. 教案內(nèi)容及進(jìn)度安排 8 學(xué)時(shí) ) 2.1 線性表邏輯結(jié)構(gòu) 2.2 線性表的順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn) 2.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 第三章 棧和隊(duì)列 1. 教案目的及要求 理解棧的定義、特征及在其上所定義的基本運(yùn)算； 掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)

4、算的實(shí)現(xiàn)； 理解隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算； 掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。 2. 教案重點(diǎn) 棧的定義及邏輯特點(diǎn)； 棧上的基本運(yùn)算； 棧的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)； 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)； 入棧、出棧等運(yùn)算在鏈棧上的實(shí)現(xiàn)； 隊(duì)列的定義及邏輯特點(diǎn)； 隊(duì)列上的基本運(yùn)算； 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其上的運(yùn)算實(shí)現(xiàn)； 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)； 入隊(duì)、出隊(duì)等運(yùn)算在鏈隊(duì)列上的實(shí)現(xiàn)。 3. 教案難點(diǎn) 順序棧的溢出判斷條件； 循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿判斷條件； 循環(huán)隊(duì)列上的插入、刪除操作。 4. 教案內(nèi)容及進(jìn)度安排 4 學(xué)時(shí) ) 3.1 棧 3.2 棧應(yīng)用舉例 3.3 隊(duì)列 3.4 隊(duì)列應(yīng)用舉例

5、 第四章 串 1. 教案目的及要求 了解串的定義； 理解和領(lǐng)會(huì)串的存儲(chǔ)方式； 掌握常用的串運(yùn)算。 2. 教案重點(diǎn) 串的基本概念、基本運(yùn)算； 串的兩種存儲(chǔ)方式。 串的模式匹配算法。 3. 教案難點(diǎn) 串的模式匹配算法； 串的基本運(yùn)算的綜合應(yīng)用 4. 教案內(nèi)容及進(jìn)度安排 2 學(xué)時(shí) ) 4.1 串及其基本運(yùn)算 4.2 串的定長(zhǎng)順序存儲(chǔ)及基本運(yùn)算 4.3 串的堆存儲(chǔ)結(jié)構(gòu) 第五章 數(shù)組和廣義表 1. 教案目的及要求 理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式； 理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算； 領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡(jiǎn)單運(yùn)算； 了解廣義表的定義和基本運(yùn)算。 2. 教案重點(diǎn) 多維

6、數(shù)組的邏輯結(jié)構(gòu)； 多維組的兩種順序存儲(chǔ)方式； 計(jì)算給定元素在存儲(chǔ)區(qū)中的地址； 對(duì)稱矩陣、三角矩陣的壓縮存儲(chǔ)方式； 計(jì)算給定元素在存儲(chǔ)區(qū)中的地址； 稀疏矩陣的三元組表表示方法。 3. 教案難點(diǎn) 稀疏矩陣的壓縮存儲(chǔ)表示下的運(yùn)算的實(shí)現(xiàn) 4. 教案內(nèi)容及進(jìn)度安排 森林與二叉樹的轉(zhuǎn)換。 3. 教案難點(diǎn) 二叉樹的遞歸定義； 二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式； 三種遍歷的主要區(qū)別； 二叉樹上的復(fù)雜運(yùn)算； 哈夫曼算法及其應(yīng)用。 森林與二叉樹的轉(zhuǎn)換； 判定樹； 等價(jià)關(guān)系與等價(jià)類問(wèn)題。 4. 教案內(nèi)容及進(jìn)度安排 6 學(xué)時(shí) ） 6.1 二叉樹定義與性質(zhì) 6.2 存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn) 6.3 二叉樹的遍歷 6.4 線索

7、二叉樹 6.5 二叉樹的應(yīng)用 6.6 樹的概念、基本操作與存儲(chǔ) 6.7 樹、森林與二叉樹的轉(zhuǎn)換 6.8 樹或森林的遍歷 6.9 樹的應(yīng)用 第七章 圖 1. 教案目的及要求 理解圖的基本概念及術(shù)語(yǔ)； 掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu) （ 鄰接矩陣和鄰接表 的表示方法； 的算法思想、步 熟練掌握?qǐng)D的兩種遍歷 （ 深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷 驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列； 理解最小生成樹的概念，能按 Prim 算法構(gòu)造最小生成樹； 領(lǐng)會(huì)并掌握拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑的算法思想。 2. 教案重點(diǎn) 理解圖的定義、術(shù)語(yǔ)及其含義； 掌握各種圖的鄰接矩陣表示法及其類型說(shuō)明； 理解并

8、掌握?qǐng)D的按深度優(yōu)先搜索遍歷方法和按廣度優(yōu)先搜索遍歷方法； 領(lǐng)會(huì)生成樹和最小生成樹的概念； 掌握由 Prim 算法思想構(gòu)造最小生成樹按 Prim 算法思想； 領(lǐng)會(huì)拓?fù)湫蛄泻屯負(fù)渑判虻母拍睿?理解并掌握拓?fù)渑判虻乃惴ㄋ枷耄?理解并掌握關(guān)鍵路徑的算法思想； 理解并掌握最短路徑的算法思想。 3. 教案難點(diǎn) 正確理解與區(qū)別圖的常用術(shù)語(yǔ)； 區(qū)別圖的兩種存儲(chǔ)結(jié)構(gòu)的不同點(diǎn)及其應(yīng)用場(chǎng)合； 關(guān)鍵路徑的算法思想； 最短路徑的算法思想。 4. 教案內(nèi)容及進(jìn)度安排 8 學(xué)時(shí) ） 7.1 圖的基本概念 7.2 圖的存儲(chǔ)表示 7.3 圖的遍歷 7.4 圖的連通性 7.5 最小生成樹 7.6 最短路徑 7.7 有向無(wú)環(huán)圖及其

9、應(yīng)用 第八章 查找 1. 教案目的及要求 了解查找的基本思想及查找成功和不成功的概念； 掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的 平均查找長(zhǎng)度； 理解并掌握二叉排序樹、平衡二叉樹B- 樹的各種算法。 2. 教案重點(diǎn) 查找表的基本概念及查找原理； 查找表的順序存儲(chǔ)結(jié)構(gòu)、順序表及其類型說(shuō)明； 查找運(yùn)算在查找表和有序表上的實(shí)現(xiàn)； 二叉排序樹的定義、性質(zhì)及各結(jié)點(diǎn)間的鍵值關(guān)系； 二叉排序樹的查找算法和基本思想； 平衡二叉排序樹的概念； (7) B-樹和B+樹的概念； 散列表及散列存儲(chǔ)和散列查找的基本思想； 各種散列表的組織、解決沖突的方法； 在散列表上實(shí)現(xiàn)查找、插入和刪除

10、運(yùn)算的算法。 3. 教案難點(diǎn) 理解查找表的邏輯結(jié)構(gòu)是集合，它的運(yùn)算以查找為核心； 二叉排序樹上的插入算法； 平衡二叉樹的旋轉(zhuǎn)平衡算法； 散列表上的有關(guān)算法 4. 教案內(nèi)容及進(jìn)度安排 6 學(xué)時(shí) ) 8.1 基本概念與術(shù)語(yǔ) 8.2 靜態(tài)查找表 8.3 動(dòng)態(tài)查找表 8.4 哈希表查找 ( 雜湊法 第九章 排序 1. 教案目的及要求 領(lǐng)會(huì)排序的基本思想和基本概念； 理解并掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和 基數(shù)排序的基本思想、步驟、算法及時(shí)空效率分析； 了解外排序的定義和基本方法。 2. 教案重點(diǎn) 排序基本概念及內(nèi)排序和外排序、穩(wěn)定排序和非穩(wěn)定排序的區(qū)別； 插入排序的基

11、本思想、基本步驟和算法； 冒泡排序的基本思想、基本步驟、算法和算法分析； 快速排序的基本思想、基本步驟和算法； 直接選擇排序的基本思想、基本步驟、算法和算法分析； 堆排序的基本思想、基本步驟和算法； 歸并排序的思想； 兩個(gè)有序文件合并的方法和算法； 二路歸并排序的算法和時(shí)空性能 3. 教案難點(diǎn) 快速排序算法； 堆排序方法 4. 教案內(nèi)容及進(jìn)度安排 6 學(xué)時(shí) ) 9.1 基本概念 9.2 插入排序 9.3 交換排序 9.4 選擇排序 9.5 二路歸并排序 9.6 基數(shù)排序 9.7 外排序 五、實(shí)踐性教案環(huán)節(jié) 數(shù)據(jù)結(jié)構(gòu)是信息與計(jì)算科學(xué)專業(yè)中一門重要的專業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來(lái)解決實(shí)際 問(wèn)題時(shí)，就要

12、涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程 的主要研究對(duì)象，通過(guò)這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了 厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用專業(yè) 中具有舉足輕重的作用。 本課程的任務(wù)是：通過(guò)實(shí)踐，學(xué)生對(duì)常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法的 理論得到進(jìn)一步的掌握，并對(duì)在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算方式和技巧有所體會(huì)。 六、教案方法與手段 課堂講授為主，結(jié)合輔導(dǎo)、答疑，進(jìn)行必要的上機(jī)實(shí)驗(yàn)。課外20 學(xué)時(shí)主要由學(xué)生自行 安排，可以到實(shí)驗(yàn)室上機(jī)，為實(shí)驗(yàn)課作準(zhǔn)備。 七、考核與成績(jī)?cè)u(píng)定 1、考核目的：本課程是以實(shí)用為最

13、終目的，因此，考核的重點(diǎn)是考察學(xué)生對(duì)各種數(shù)據(jù) 結(jié)構(gòu)的理解程度和基于這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)的能力。不要求學(xué)生死記具體的定義， 但需要學(xué)生在實(shí)踐過(guò)程中逐步熟練運(yùn)用。 2、考核形式：采用實(shí)驗(yàn)考核、期末考核與平時(shí)成績(jī)相結(jié)合的方式。其中 , 平時(shí)考核： 平時(shí)作業(yè)占考核總成績(jī)的5%，平時(shí)考勤占考核總成績(jī)的5%，實(shí)驗(yàn)成績(jī)占考核總成績(jī)的50%, 期末考核：采用筆試，它占總成績(jī)的40%，考試方式為閉卷，答題時(shí)限100 分鐘。以上三 個(gè)成績(jī)累計(jì) 60 分以上 包括 60 分）算考核通過(guò)。 3、主要考核內(nèi)容： 數(shù)據(jù)結(jié)構(gòu)的概念，線性表，棧，隊(duì)列，遞歸概念，廣義表，樹和二叉樹，圖，查找， 排序。 4、考核題型：有單選

14、題、填空題、應(yīng)用題、程序填空題和綜合編程題等五種題型。 5、成績(jī)?cè)u(píng)定：實(shí)驗(yàn)考核50%，平時(shí) 10%，期未 40% 八、教材及參考書 教材： 1 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版）M.（第一版 北京：清華大學(xué)出版社.1997 參考書： 2 Sartaj Sahni. Data Structure, Algorithms, and Application in C+. The McGraw-Hill Company Inc.1998M（第一版 （數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語(yǔ)言描述. 北京 :機(jī)械工業(yè)出版社 .1999 3 Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Com