【文章內(nèi)容簡介】 eration’s implementing. Recursion algorithm and all sorts of typical sort and search algorithms are also included. Through learning this course, students could lay a theory foundation for later courses, especially for software analysis and design relative courses. On the other hand, abundant training is practiced in the process. 三、課程性質(zhì)與教學(xué)目的 課程性質(zhì) 是 一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象及其之間關(guān)系與操作的學(xué)科，是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程，屬于計(jì)算機(jī)學(xué)科中的一門綜合性專業(yè)基礎(chǔ)課程，是一般程序設(shè)計(jì)的基礎(chǔ)，也是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。 教學(xué) 目的 一方面 學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握 算法的時(shí)間分析和空間分析的技術(shù)。另一方面，本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。如果說高級語言程序設(shè)計(jì)課程對學(xué)生進(jìn)行了結(jié)構(gòu)化程序設(shè)計(jì)的初步訓(xùn)練的話，那么數(shù)據(jù)結(jié)構(gòu)課程就要培養(yǎng)他們的數(shù)據(jù)抽象能力。 四、教學(xué)內(nèi)容及要求 第一章 緒論 (一 ) 目的與要求 1. 通過本章的學(xué)習(xí)，使學(xué)生領(lǐng)會數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系 ； 2. 掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別 ； 3. 了解算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。 (二 ) 教學(xué)內(nèi)容 第一節(jié) 什么是數(shù)據(jù)結(jié)構(gòu) 1. 主要內(nèi)容 由數(shù)學(xué)方程無法描述的非數(shù)值計(jì)算問題引出數(shù)據(jù)結(jié)構(gòu)表、圖、樹的 3 種實(shí)例，數(shù)據(jù)結(jié)構(gòu)的概念，數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵和特點(diǎn)，數(shù)據(jù)結(jié)構(gòu)所處的學(xué)科地位，數(shù)據(jù)結(jié)構(gòu)的學(xué)科背景、起源、發(fā)展和現(xiàn)狀。 2. 基本概念 和 知識點(diǎn) 數(shù)據(jù)結(jié)構(gòu)的概念 ； 數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵和特點(diǎn) ； 數(shù)據(jù)結(jié)構(gòu)所處的學(xué)科地位 ； 數(shù)據(jù)結(jié)構(gòu)的學(xué)科背景、起源、發(fā)展和現(xiàn)狀 。 3. 問題與應(yīng)用（能力要求） 要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的概念，能辨別數(shù)學(xué)模型中數(shù)學(xué)方程和表、圖、樹等數(shù)據(jù)結(jié)構(gòu)的區(qū)別。 第二節(jié) 基本概念和術(shù)語 1． 主要內(nèi)容 本課使用的一些基本概念，包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、 數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、集合、結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、存儲結(jié)構(gòu)、位、元素、結(jié)點(diǎn)、數(shù)據(jù)域、順序映像、非順序映像、順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、指針、虛擬存儲結(jié)構(gòu)、數(shù)據(jù)類型、原子類型、結(jié)構(gòu)類型、抽象數(shù)據(jù)類型、固定聚合類型、可變聚合類型、多形數(shù)據(jù)類型 。 2． 基本 概念和 知識點(diǎn) 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、集合、結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)等在內(nèi)的所有基本概念 。 3． 問題與應(yīng)用（能力要求） 掌握包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、集合、結(jié)構(gòu)、線性 結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)等基本概念。 第 三 節(jié) 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn) 1． 主要內(nèi)容 抽象數(shù)據(jù)類型的常用表示方法 。 2． 基本 概念和 知識點(diǎn) 抽象數(shù)據(jù)類型的常用表示方法，包括預(yù)定義常量和類型、數(shù)據(jù)結(jié)構(gòu)的表示用類型定義（ typedef）描述、函數(shù)表示法、各種賦值語句、選擇語句、結(jié)束語句、輸入和輸出語句、基本函數(shù)、邏輯運(yùn)算約定 。 3． 問題與應(yīng)用（能力要求） 掌握抽象數(shù)據(jù)類型的類 C 語言 11 種表示方法。 第四 節(jié) 算法與算法分析 1． 主要內(nèi)容 算法的定義，算法的 5 個(gè)重要特征。好算法設(shè)計(jì)的 4 個(gè)要求。算法效率的 2 種度量方法 ，時(shí) 間復(fù)雜度的概念，頻度的概念 。空間復(fù)雜度的概念，空間復(fù)雜度的表示法，算法原地工作的概念 。 2． 基本 概念和 知識點(diǎn) 算法的定義，算法的 5 個(gè)重要特征。好算法設(shè)計(jì)的 4 個(gè)要求。 時(shí)間復(fù)雜度， 空間復(fù)雜度的概念，空間復(fù)雜度 。 3． 問題與應(yīng)用（能力要求） 掌握算法的定義 ； 理解算法的 5 個(gè)重要特征 ； 理解好算法設(shè)計(jì)的4 個(gè)要求 ；掌握空間復(fù)雜度的概念。 (三 ) 課后練習(xí) 配套習(xí)題集 P7 ， P8 （ 1）、（ 6）， P10 。 (四 ) 教學(xué)方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結(jié)合的方式 。 第二章 線性表 （一） 目的與要求 1． 了 解線性表的基本概念和類型定義 ； 2． 熟練掌握順序存儲的線性表和單鏈表的算法設(shè)計(jì)及其程序?qū)崿F(xiàn) ； 3． 掌握循環(huán)鏈表和雙向鏈表的操作。 （二） 教學(xué)內(nèi)容 第一節(jié) 線性表的類型定義 1． 主要內(nèi)容 線性結(jié)構(gòu)的特點(diǎn)，線性表的抽象數(shù)據(jù)類型定義，數(shù)據(jù)項(xiàng)、記錄、文件的定義，實(shí)例說明線性表的插入、刪除、歸并等操作方式，并對算法做相應(yīng)的分析 。 2． 基本概念 和 知識點(diǎn) 線性結(jié)構(gòu)的特點(diǎn) , 線性表的插入、刪除、歸并等操作 。 3． 問題與應(yīng)用（能力要求） 要求學(xué)生掌握線性表的概念和抽象數(shù)據(jù)類型定義。 第二節(jié) 線性表的順序表示和實(shí)現(xiàn) 1． 主要內(nèi)容 線性 表的順序表示的概念，順序映像的方式，順序映像的隨機(jī)存取特性，實(shí) 例描述線性表在順序存儲表示時(shí)進(jìn)行插入、刪除、合并操作的幾種算法。 2． 基本 概念和 知識點(diǎn) 線性表的順序表示的概念 , 插入、刪除、合并操作的幾種算法 。 3． 問題與應(yīng)用（能力要求） 掌握線性表的順序表示的概念和順序映像的方式 ； 理解線性表在順序存儲結(jié)構(gòu)時(shí)的插入、刪除、合并等操作方法。 第 三 節(jié) 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 1． 主要內(nèi)容 線性鏈表的概念 ， 單鏈表的插入、刪除、合并操作處理算法，靜態(tài)鏈表的算法；循環(huán)鏈表的概念，循環(huán)鏈表的操作特點(diǎn)；雙向鏈表的概念和特點(diǎn)，雙向鏈表 的抽象數(shù)據(jù)類型定義，雙向 鏈表的幾種操作算法。 2． 基本 概念和 知識點(diǎn) 幾種 鏈表的概念 ,操作特點(diǎn)及 處理算法 。 3． 問題與應(yīng)用（能力要求） 掌握線性有序鏈表的概念 ； 理解單鏈表的插入、刪除、合并操作算法 ； 掌握循環(huán)鏈表的概念 ； 掌握雙向鏈表的概念 ；了 解雙向鏈表的抽象數(shù)據(jù)類型定義 ；了解 雙向鏈表的操作算法。 *第 四 節(jié) 一元多項(xiàng)式的表示及相加 （選學(xué)） 1． 主要內(nèi)容 利用線性鏈表的基本操作來實(shí)現(xiàn)一元多項(xiàng)式的定義、相加和相乘運(yùn)算。 2． 基本 概念和 知識點(diǎn) 一元多項(xiàng)式的定義、相加和相乘運(yùn)算 。 3． 問題與應(yīng)用（能力要求） 掌握利用線性鏈表的基本操作來實(shí) 現(xiàn)一元多項(xiàng)式的定義、相加和相乘運(yùn)算。 （三） 實(shí)踐環(huán)節(jié) 建立線性表類 ， 實(shí)現(xiàn)相關(guān)操作 ， 應(yīng)用于多項(xiàng)式 相加 、相乘問題。 （四） 教學(xué)方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結(jié)合的方式 。 第三章 棧和隊(duì)列 （一） 目的與要求 1． 掌握棧和隊(duì)列的定義 ； 2． 熟練掌握順序和鏈接存儲的棧和隊(duì)列的算法設(shè)計(jì)及其程序?qū)崿F(xiàn) ； 3． 了解棧和隊(duì)的各種應(yīng)用。 （二） 教學(xué)內(nèi)容 第一節(jié) 棧 1． 主要內(nèi)容 棧、棧頂、棧底、后進(jìn)先出等概念，棧的抽象數(shù)據(jù)定義；棧的 2種存儲表示法：順序棧和鏈棧的定義，順序棧的模塊說明。 2． 基本概念 和 知識點(diǎn) 棧及棧的相關(guān)概 念，棧的抽象數(shù)據(jù)定義 ； 順序棧的定義 。 3． 問題與應(yīng)用（能力要求） 掌握棧及棧的相關(guān)概念 ； 理解棧的抽象數(shù)據(jù)定義 ； 掌握順序棧的定義 。 第二節(jié) 棧的應(yīng)用舉例 1． 主要內(nèi)容 應(yīng)用棧結(jié)構(gòu)的后進(jìn)先出特性，進(jìn)行十進(jìn)制 N 和其它 d 進(jìn)制數(shù)的轉(zhuǎn)換算法 ； 進(jìn)行圓括號和方括號書寫格式是否正確的檢查算法。 2． 基本 概念和 知識點(diǎn) 十進(jìn)制 N 和其它 d 進(jìn)制數(shù)的轉(zhuǎn)換算法 ； 圓括號和方括號書寫格式是否正確的檢查算法 。 3． 問題與應(yīng)用（能力要求） 理解應(yīng)用棧結(jié)構(gòu)的數(shù)制轉(zhuǎn)換算法 ； 理解應(yīng)用棧結(jié)構(gòu)的括號匹配檢驗(yàn)算法。 第 三 節(jié) 棧與遞歸的實(shí)現(xiàn) 1． 主要內(nèi)容 遞歸的 概念、遞歸問題的特性，棧在 n 階 Hanoi 塔問題等典型遞歸問題中的應(yīng)用。 2． 基本 概念和 知識點(diǎn) 遞歸的概念、遞歸問題的特性， n 階 Hanoi 塔問題 。 3． 問題與應(yīng)用（能力要求） 理解棧在 n 階 Hanoi 塔遞歸算法中的應(yīng)用。 第 四 節(jié) 隊(duì)列 1． 主要內(nèi)容 隊(duì)列、 FIFO 的概念，隊(duì)列的特性，隊(duì)列的抽象數(shù)據(jù)定義 。 隊(duì)列鏈?zhǔn)奖硎镜幕静僮骱瘮?shù)。 循環(huán)隊(duì)列的概念。 2． 基本 概念和 知識點(diǎn) 隊(duì)列、 FIFO 的概念，隊(duì)列的特性，隊(duì)列的抽象數(shù)據(jù)定義 。 隊(duì)列鏈?zhǔn)奖硎镜幕静僮骱瘮?shù)。 循環(huán)隊(duì)列的概念。 3． 問題與應(yīng)用（能力要求） 掌握隊(duì)列的概念 ； 理解隊(duì)列的特性， 隊(duì)列的抽象數(shù)據(jù)定義 ； 理解隊(duì)列鏈?zhǔn)奖硎镜幕静僮骱瘮?shù) 。 （三） 實(shí)踐環(huán)節(jié) 建立順序存儲的棧類 ， 應(yīng)用于十進(jìn)制向 d 進(jìn)制數(shù)字轉(zhuǎn)換問題 。 （四） 教學(xué)方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結(jié)合的方式 。 第四章 串 （一） 目的與要求 1. 掌握串的基本存儲結(jié)構(gòu)及基本操作 ； 2. 了解改進(jìn)的模式匹配算法 。 （二） 教學(xué)內(nèi)容 第一節(jié) 串類型的定義 1． 主要內(nèi)容 串產(chǎn)生的背景，串的概念，串長度、空串、子串、主串 、位置、空格串等概念，串的抽象數(shù)據(jù)類型定義，串的基本操作集概念。 2． 基本概念 和 知識點(diǎn) 串的概念，串的抽象數(shù)據(jù)類型定義，串 的基本操作集概念 。 3． 問題與應(yīng)用（能力要求） 掌握串及相關(guān)的概念，理解串的抽象數(shù)據(jù)類型定義。 第二節(jié) 串的表示和實(shí)現(xiàn) 1． 主要內(nèi)容 串在機(jī)內(nèi)的定長順序表示，串的連接操作和子串操作 ，串的堆分配存儲表示，在這種存儲結(jié)構(gòu)表示時(shí)如何實(shí)現(xiàn)串的插入操作。 2． 基本 概念和 知識點(diǎn) 串在機(jī)內(nèi)的定長順序表示 及相關(guān)操作算法； 串的堆分配存儲表示及相關(guān)操作算法。 3． 問題與應(yīng)用（能力要求） 掌握串的定長順序存儲表示 ； 理解在定長順序存儲結(jié)構(gòu)表示時(shí)實(shí)現(xiàn)串的連接操作和子串操作的方法 ； 掌握串的堆分配存儲表示 ；了 解在堆分配存儲結(jié)構(gòu)表示時(shí)實(shí)現(xiàn)串 的插入操作串的塊鏈存儲表示； 了解 串的塊鏈存儲表示 。 *第 三 節(jié) 串的模式匹配算法 （選學(xué)） 1． 主要內(nèi)容 串的 定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函數(shù)； KMP 模式匹配算法。 2． 基本 概念和 知識點(diǎn) 串的 定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函數(shù)； KMP 模式匹配算法 。 3． 問題與應(yīng)用（能力要求） 掌握模式匹配的概念，熟悉求子串位置的定位函數(shù) ， 熟悉 KMP 模式匹配算法 。 第 四 節(jié) 串操作應(yīng)用舉例 1． 主要內(nèi)容 在文本編輯中使用串操作；使用串建立詞索引表的方法，詞索引表插入的實(shí)現(xiàn)算法。 2． 基本 概念和 知識點(diǎn) 在文本編輯中使用串操作；使用串建立詞索引表的方法 。 3． 問題與應(yīng)用（能力要求） 理解文本編輯中串的用法 ，了 解建立詞索引表中串的用法 。 （三） 實(shí)踐環(huán)節(jié) 1. 熟悉串類型的實(shí)現(xiàn)方法，了解簡單文字處理的設(shè)計(jì)方法。 2. 熟悉 C 語言的字符和把字符串處理的原理和方法。 （四） 教學(xué)方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結(jié)合的方式 。 第五章 數(shù)組和廣義表 （一） 目的與要求 1． 掌握數(shù)組的順序存儲結(jié)構(gòu)及特殊矩陣的存儲方式； 2． 掌握數(shù)組的順序存儲結(jié)構(gòu)及特殊矩陣的存儲方式 ； 3． 了解稀疏矩陣的壓縮存儲方式 — 三元組表 ； 4． 理解 廣義表的定義、術(shù)語、存儲結(jié)構(gòu)、運(yùn)算 。 （二） 教學(xué)內(nèi)容 第一節(jié) 數(shù)組的定義 1． 主要內(nèi)容 抽象數(shù)據(jù)類型數(shù)組的定義。 2． 基本概念 和 知識點(diǎn) 抽象數(shù)據(jù)類型數(shù)組 。 3． 問題與應(yīng)用（能力要求） 掌握抽象數(shù)據(jù)類型數(shù)組的定義 。 第二節(jié) 數(shù)組的順序表示和實(shí)現(xiàn) 1． 主要內(nèi)容 數(shù)組的順序存儲結(jié)構(gòu)，以列序?yàn)橹餍虻亩S數(shù)組存儲方式，以行序?yàn)橹餍虻亩S數(shù)組存儲方式， n 維數(shù)組的數(shù)據(jù)元素存儲位置的計(jì)算 。 2． 基本 概念和 知識點(diǎn) 數(shù)組的順序存儲結(jié)構(gòu) ， n 維數(shù)組的數(shù)據(jù)元素存儲位置的計(jì)算 。 3． 問題與應(yīng)用（能力要求） 掌握數(shù)組的順序表示法。 第 三 節(jié) 矩陣的壓縮存儲 1． 主要內(nèi)容 矩陣、壓縮存儲、特殊矩陣的概念，特殊矩陣的壓縮存儲算法；稀疏矩陣的概念，稀疏矩陣的壓縮存儲算法，兩個(gè)稀疏矩陣相乘的算法