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

數(shù)據(jù)結(jié)構(gòu)PAGE1《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱目錄一、教學(xué)目的和要求 1二、本課程與其它課程的聯(lián)系和分工 1三、教學(xué)中應(yīng)注意的問題 1四、教學(xué)內(nèi)容 2五、教學(xué)課時(shí)分配 7六、參考書目 7課程名稱：數(shù)據(jù)結(jié)構(gòu) 學(xué)時(shí)：64學(xué)時(shí)課程類型：必修 課程性質(zhì)：學(xué)科基礎(chǔ)課開課學(xué)期：第3學(xué)期先修課程：程序設(shè)計(jì)基礎(chǔ)、程序設(shè)計(jì)基礎(chǔ)II適用專業(yè)：網(wǎng)絡(luò)工程專業(yè)一、教學(xué)目的和要求《數(shù)據(jù)結(jié)構(gòu)》是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的科學(xué)。學(xué)會(huì)分析研究計(jì)算機(jī)加工數(shù)據(jù)對(duì)象的特性，以便為應(yīng)用所設(shè)計(jì)的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及恰當(dāng)?shù)乃惴?，并初步掌握算法的?fù)雜度分析技術(shù)，這是一個(gè)從事計(jì)算機(jī)科學(xué)與技術(shù)研究和應(yīng)用的科學(xué)工作者的基本要求，也是進(jìn)一步學(xué)習(xí)計(jì)算機(jī)的重要基礎(chǔ)，不論是對(duì)程序設(shè)計(jì)，還是對(duì)實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)等均具有十分重要的意義。學(xué)習(xí)掌握數(shù)據(jù)結(jié)構(gòu)，并應(yīng)用它來處理其它問題，也是進(jìn)行復(fù)雜程序設(shè)計(jì)的一種基本訓(xùn)練，對(duì)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力意義重大。二、本課程與其它課程的聯(lián)系和分工先修課程：程序設(shè)計(jì)基礎(chǔ)、程序設(shè)計(jì)基礎(chǔ)II。后續(xù)課程：算法設(shè)計(jì)與分析、操作系統(tǒng)、軟件工程。本課程是一個(gè)學(xué)科基礎(chǔ)課程，使學(xué)生具備較好的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和實(shí)現(xiàn)能力。三、教學(xué)中應(yīng)注意的問題1、突出重點(diǎn)：緊緊圍繞數(shù)據(jù)結(jié)構(gòu)的中心內(nèi)容（數(shù)據(jù)之間的邏輯結(jié)構(gòu)表示、重點(diǎn)是物理結(jié)構(gòu)的表示以及相應(yīng)的算法）進(jìn)行講解。2、重視難點(diǎn)：結(jié)合典型問題或者實(shí)際事例進(jìn)行數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)以及有關(guān)算法的實(shí)現(xiàn)進(jìn)行講解。3、本課程的前導(dǎo)課,至少學(xué)過一門通用的高級(jí)語言的程序設(shè)計(jì)。離散數(shù)學(xué)（圖論部分）等課程。四、教學(xué)內(nèi)容說明:計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)授課學(xué)時(shí)為64,目錄所列內(nèi)容全部講授,其他專業(yè)為48學(xué)時(shí),建議標(biāo)注(**)的內(nèi)容不講。第一章緒論（4）本章內(nèi)容：1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析1.4.1算法1.4.2算法設(shè)計(jì)的要求1.4.3算法效率的度量1.4.4算法的存儲(chǔ)空間教學(xué)重點(diǎn)：１、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語的確定含義；抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法；描述算法的類C語言；算法設(shè)計(jì)的基本要求以及從時(shí)間和空間角度分析算法的方法。2、熟悉各個(gè)名詞、術(shù)語的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間的關(guān)系；了解邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的性質(zhì)；了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。3、理解算法五個(gè)特征的含義：有窮性、確定性、有效性、有輸出、有輸入。4、掌握計(jì)算語句頻度和算法時(shí)間復(fù)雜度的方法。教學(xué)難點(diǎn)：1、抽象數(shù)據(jù)類型的定義。2、算法時(shí)間復(fù)雜度的計(jì)算。第二章線性表（8）本章內(nèi)容：2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加教學(xué)重點(diǎn)：1、線性表的類型定義2、線性表的兩種存儲(chǔ)方式及相關(guān)運(yùn)算的實(shí)現(xiàn)。教學(xué)難點(diǎn)：線性表的具體應(yīng)用及相關(guān)算法的實(shí)現(xiàn)。第三章棧與隊(duì)列（6）本章內(nèi)容:3.1棧3.1.1抽象數(shù)據(jù)類型棧的定義3.1.2棧的表示和實(shí)現(xiàn)3.2棧的應(yīng)用舉例3.2.1數(shù)制轉(zhuǎn)換3.2.2括號(hào)匹配的檢驗(yàn)3.2.3行編輯程序3.2.4迷宮求解3.2.5表達(dá)式求值3.3棧與遞歸的實(shí)現(xiàn)（**）3.4隊(duì)列3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義3.4.2鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)3.4.3循環(huán)隊(duì)列—隊(duì)列的順序表示和實(shí)現(xiàn)3.5離散事件模擬（**）教學(xué)重點(diǎn):1、棧的特點(diǎn)及應(yīng)用2、棧的存儲(chǔ)結(jié)構(gòu)及相關(guān)算法的實(shí)現(xiàn)3、隊(duì)列的特點(diǎn)及應(yīng)用4、隊(duì)列的存儲(chǔ)結(jié)構(gòu)及相關(guān)算法的實(shí)現(xiàn)教學(xué)難點(diǎn)：存儲(chǔ)結(jié)構(gòu)的選擇及相關(guān)算法的實(shí)現(xiàn)第四章串（5）教學(xué)內(nèi)容：4.1串類型的定義4.2串的表示和實(shí)現(xiàn)4.2.1定長(zhǎng)順序存儲(chǔ)表示4.2.2堆分配存儲(chǔ)表示4.2.3串的塊鏈存儲(chǔ)表示4.3串的模式匹配算法（**）4.3.1求子串位置的定位函數(shù)INDEX（S，T，POS）4.3.2模式匹配的一種改進(jìn)算法4.4串操作應(yīng)用舉例4.4.1文本編輯4.4.2建立詞索引表教學(xué)重點(diǎn):1、串的數(shù)據(jù)類型定義2、串的三種存儲(chǔ)表示（定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)、塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)）3、串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用4、串的模式匹配算法。教學(xué)難點(diǎn)：串的各種運(yùn)算的實(shí)現(xiàn)算法；串的的模式匹配及改進(jìn)算法。第五章數(shù)組與廣義表（6）本章內(nèi)容:5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.3.1特殊矩陣5.3.2稀疏矩陣5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)5.6m5.7廣義表的遞歸算法（**）教學(xué)重點(diǎn):1、數(shù)組的類型定義和表示方式2、特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法和運(yùn)算實(shí)現(xiàn)3、廣義表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)教學(xué)難點(diǎn)：矩陣壓縮存儲(chǔ)算法第六章樹和二叉樹（10）本章內(nèi)容：6.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.4.1樹的存儲(chǔ)結(jié)構(gòu)6.4.2森林與二叉樹的轉(zhuǎn)換6.4.3樹和森林的遍歷6.5樹與等價(jià)問題（**）6.6哈夫曼樹及其應(yīng)用6.6.1最優(yōu)二叉樹6.6.2哈夫曼編碼教學(xué)重點(diǎn):二叉樹的定義、性質(zhì)、存儲(chǔ)結(jié)構(gòu)二叉樹的遍歷和線索化以及遍歷算法的各種描述形式樹和森林的定義、存儲(chǔ)結(jié)構(gòu)與二叉樹的轉(zhuǎn)換4、哈夫曼樹的建立及哈夫曼編碼教學(xué)難點(diǎn)：樹的各種運(yùn)算實(shí)現(xiàn)的遞歸算法第七章圖（8）本章內(nèi)容：7.1圖的定義和術(shù)語7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.1數(shù)組表示法7.2.2鄰接表7.2.3十字鏈表7.2.4鄰接多重表7.3圖的遍歷7.3.1深度優(yōu)先搜索7.3.2廣度優(yōu)先搜索7.4圖的連通性問題7.4.1無向圖的連通分量和生成樹7.4.2有向圖的強(qiáng)連通分量（**）7.4.3最小生成樹7.4.4關(guān)節(jié)點(diǎn)和重連通分量7.5有向無環(huán)圖及其應(yīng)用7.5.1拓?fù)渑判?.5.2關(guān)鍵路徑7.6最短路徑7.6.1從某個(gè)源點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑7.6.2每對(duì)頂點(diǎn)間的最短路徑教學(xué)重點(diǎn):圖的定義和術(shù)語圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法、鄰接表、十字鏈表、鄰接多重表圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索圖的連通性：連通分量和最小生成樹；拓?fù)渑判蚝完P(guān)鍵路徑6、兩類求最短路徑問題的解法。教學(xué)難點(diǎn)：各種算法的實(shí)現(xiàn)；關(guān)鍵路徑；最短路徑第八章查找（7）本章內(nèi)容：8.1靜態(tài)查找表8.1.1順序表的查找8.1.2有序表的查找8.1.3靜態(tài)樹表的查找(**)8.1.4索引順序表查找8.2態(tài)查找表—二叉排序樹和平衡二叉樹、B-樹和B+樹、鍵樹8.3哈希表8.3.1什么是哈希表8.3.2函數(shù)函數(shù)的構(gòu)造方法8.3.3處理沖突的方法8.3.4哈希表的查找查找及其分析教學(xué)重點(diǎn):1、討論查找表（包括靜態(tài)查找表和動(dòng)態(tài)查找表）的各種實(shí)現(xiàn)方法：順序表、有序表、樹表和哈希表2、關(guān)于衡量查找表的主要操作—查找的查找效率的平均查找長(zhǎng)度的討論。教學(xué)難點(diǎn)：各種查找算法的實(shí)現(xiàn)第九章排序（6）本章內(nèi)容9.1概述9.2插入排序9.2.1直接插入排序9.2.2其它插入排序9.2.3希爾排序9.3快速排序9.4選擇排序9.4.1簡(jiǎn)單選擇排序9.4.2樹形選擇排序9.4.3堆排序9.5歸并排序9.6基數(shù)排序9.6.1多關(guān)鍵字的排序9.6.2鏈?zhǔn)交鶖?shù)排序9.7各種排序的比較教學(xué)重點(diǎn):討論比較各種內(nèi)部排序的方法插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點(diǎn)、排序過程以及他們的時(shí)間復(fù)雜度分析3、在每類排序方法中，從簡(jiǎn)單方法入手，重點(diǎn)討論性能先進(jìn)的高效方法（如：插入排序類中的希爾排序、交換排序中的快速排序、選擇排序中的堆排序）教學(xué)難點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效排序方法的實(shí)現(xiàn)算法及效率分析五、教學(xué)課時(shí)分配學(xué)時(shí)分配表章