【文章內容簡介】 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. 三、課程性質與教學目的 課程性質 是 一門研究非數值計算的程序設計問題中計算機的操作對象及其之間關系與操作的學科，是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程，屬于計算機學科中的一門綜合性專業(yè)基礎課程，是一般程序設計的基礎，也是設計和實現編譯程序、操作系統(tǒng)、數據庫系統(tǒng)及其他系統(tǒng)程序和大型應用程序的重要基礎。 教學 目的 一方面 學會分析研究計算機加工的數據結構的特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及其相應的算法，并初步掌握 算法的時間分析和空間分析的技術。另一方面，本課程的學習過程也是復雜程序設計的訓練過程，要求學生編寫的程序結構清楚和正確易讀，符合軟件工程的規(guī)范。如果說高級語言程序設計課程對學生進行了結構化程序設計的初步訓練的話，那么數據結構課程就要培養(yǎng)他們的數據抽象能力。 四、教學內容及要求 第一章 緒論 (一 ) 目的與要求 1. 通過本章的學習，使學生領會數據、數據元素和數據項的概念及其相互間的關系 ； 2. 掌握數據結構的邏輯結構、存儲結構的聯系與區(qū)別 ； 3. 了解算法時間復雜度和空間復雜度的分析。 (二 ) 教學內容 第一節(jié) 什么是數據結構 1. 主要內容 由數學方程無法描述的非數值計算問題引出數據結構表、圖、樹的 3 種實例，數據結構的概念，數據結構的內涵和特點，數據結構所處的學科地位，數據結構的學科背景、起源、發(fā)展和現狀。 2. 基本概念 和 知識點 數據結構的概念 ； 數據結構的內涵和特點 ； 數據結構所處的學科地位 ； 數據結構的學科背景、起源、發(fā)展和現狀 。 3. 問題與應用（能力要求） 要求學生掌握數據結構的概念，能辨別數學模型中數學方程和表、圖、樹等數據結構的區(qū)別。 第二節(jié) 基本概念和術語 1． 主要內容 本課使用的一些基本概念，包括數據、數據元素、數據項、 數據對象、數據結構、集合、結構、線性結構、樹形結構、圖狀結構、網狀結構、邏輯結構、物理結構、存儲結構、位、元素、結點、數據域、順序映像、非順序映像、順序存儲結構、鏈式存儲結構、指針、虛擬存儲結構、數據類型、原子類型、結構類型、抽象數據類型、固定聚合類型、可變聚合類型、多形數據類型 。 2． 基本 概念和 知識點 數據、數據元素、數據項、數據對象、數據結構、集合、結構、線性結構、樹形結構、圖狀結構、網狀結構等在內的所有基本概念 。 3． 問題與應用（能力要求） 掌握包括數據、數據元素、數據項、數據對象、數據結構、集合、結構、線性 結構、樹形結構、圖狀結構、網狀結構等基本概念。 第 三 節(jié) 抽象數據類型的表示與實現 1． 主要內容 抽象數據類型的常用表示方法 。 2． 基本 概念和 知識點 抽象數據類型的常用表示方法，包括預定義常量和類型、數據結構的表示用類型定義（ typedef）描述、函數表示法、各種賦值語句、選擇語句、結束語句、輸入和輸出語句、基本函數、邏輯運算約定 。 3． 問題與應用（能力要求） 掌握抽象數據類型的類 C 語言 11 種表示方法。 第四 節(jié) 算法與算法分析 1． 主要內容 算法的定義，算法的 5 個重要特征。好算法設計的 4 個要求。算法效率的 2 種度量方法 ，時 間復雜度的概念，頻度的概念 。空間復雜度的概念，空間復雜度的表示法，算法原地工作的概念 。 2． 基本 概念和 知識點 算法的定義，算法的 5 個重要特征。好算法設計的 4 個要求。 時間復雜度， 空間復雜度的概念，空間復雜度 。 3． 問題與應用（能力要求） 掌握算法的定義 ； 理解算法的 5 個重要特征 ； 理解好算法設計的4 個要求 ；掌握空間復雜度的概念。 (三 ) 課后練習 配套習題集 P7 ， P8 （ 1）、（ 6）， P10 。 (四 ) 教學方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結合的方式 。 第二章 線性表 （一） 目的與要求 1． 了 解線性表的基本概念和類型定義 ； 2． 熟練掌握順序存儲的線性表和單鏈表的算法設計及其程序實現 ； 3． 掌握循環(huán)鏈表和雙向鏈表的操作。 （二） 教學內容 第一節(jié) 線性表的類型定義 1． 主要內容 線性結構的特點，線性表的抽象數據類型定義，數據項、記錄、文件的定義，實例說明線性表的插入、刪除、歸并等操作方式，并對算法做相應的分析 。 2． 基本概念 和 知識點 線性結構的特點 , 線性表的插入、刪除、歸并等操作 。 3． 問題與應用（能力要求） 要求學生掌握線性表的概念和抽象數據類型定義。 第二節(jié) 線性表的順序表示和實現 1． 主要內容 線性 表的順序表示的概念，順序映像的方式，順序映像的隨機存取特性，實 例描述線性表在順序存儲表示時進行插入、刪除、合并操作的幾種算法。 2． 基本 概念和 知識點 線性表的順序表示的概念 , 插入、刪除、合并操作的幾種算法 。 3． 問題與應用（能力要求） 掌握線性表的順序表示的概念和順序映像的方式 ； 理解線性表在順序存儲結構時的插入、刪除、合并等操作方法。 第 三 節(jié) 線性表的鏈式表示和實現 1． 主要內容 線性鏈表的概念 ， 單鏈表的插入、刪除、合并操作處理算法，靜態(tài)鏈表的算法；循環(huán)鏈表的概念，循環(huán)鏈表的操作特點；雙向鏈表的概念和特點，雙向鏈表 的抽象數據類型定義，雙向 鏈表的幾種操作算法。 2． 基本 概念和 知識點 幾種 鏈表的概念 ,操作特點及 處理算法 。 3． 問題與應用（能力要求） 掌握線性有序鏈表的概念 ； 理解單鏈表的插入、刪除、合并操作算法 ； 掌握循環(huán)鏈表的概念 ； 掌握雙向鏈表的概念 ；了 解雙向鏈表的抽象數據類型定義 ；了解 雙向鏈表的操作算法。 *第 四 節(jié) 一元多項式的表示及相加 （選學） 1． 主要內容 利用線性鏈表的基本操作來實現一元多項式的定義、相加和相乘運算。 2． 基本 概念和 知識點 一元多項式的定義、相加和相乘運算 。 3． 問題與應用（能力要求） 掌握利用線性鏈表的基本操作來實 現一元多項式的定義、相加和相乘運算。 （三） 實踐環(huán)節(jié) 建立線性表類 ， 實現相關操作 ， 應用于多項式 相加 、相乘問題。 （四） 教學方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結合的方式 。 第三章 棧和隊列 （一） 目的與要求 1． 掌握棧和隊列的定義 ； 2． 熟練掌握順序和鏈接存儲的棧和隊列的算法設計及其程序實現 ； 3． 了解棧和隊的各種應用。 （二） 教學內容 第一節(jié) 棧 1． 主要內容 棧、棧頂、棧底、后進先出等概念，棧的抽象數據定義；棧的 2種存儲表示法：順序棧和鏈棧的定義，順序棧的模塊說明。 2． 基本概念 和 知識點 棧及棧的相關概 念，棧的抽象數據定義 ； 順序棧的定義 。 3． 問題與應用（能力要求） 掌握棧及棧的相關概念 ； 理解棧的抽象數據定義 ； 掌握順序棧的定義 。 第二節(jié) 棧的應用舉例 1． 主要內容 應用棧結構的后進先出特性，進行十進制 N 和其它 d 進制數的轉換算法 ； 進行圓括號和方括號書寫格式是否正確的檢查算法。 2． 基本 概念和 知識點 十進制 N 和其它 d 進制數的轉換算法 ； 圓括號和方括號書寫格式是否正確的檢查算法 。 3． 問題與應用（能力要求） 理解應用棧結構的數制轉換算法 ； 理解應用棧結構的括號匹配檢驗算法。 第 三 節(jié) 棧與遞歸的實現 1． 主要內容 遞歸的 概念、遞歸問題的特性，棧在 n 階 Hanoi 塔問題等典型遞歸問題中的應用。 2． 基本 概念和 知識點 遞歸的概念、遞歸問題的特性， n 階 Hanoi 塔問題 。 3． 問題與應用（能力要求） 理解棧在 n 階 Hanoi 塔遞歸算法中的應用。 第 四 節(jié) 隊列 1． 主要內容 隊列、 FIFO 的概念，隊列的特性，隊列的抽象數據定義 。 隊列鏈式表示的基本操作函數。 循環(huán)隊列的概念。 2． 基本 概念和 知識點 隊列、 FIFO 的概念，隊列的特性，隊列的抽象數據定義 。 隊列鏈式表示的基本操作函數。 循環(huán)隊列的概念。 3． 問題與應用（能力要求） 掌握隊列的概念 ； 理解隊列的特性， 隊列的抽象數據定義 ； 理解隊列鏈式表示的基本操作函數 。 （三） 實踐環(huán)節(jié) 建立順序存儲的棧類 ， 應用于十進制向 d 進制數字轉換問題 。 （四） 教學方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結合的方式 。 第四章 串 （一） 目的與要求 1. 掌握串的基本存儲結構及基本操作 ； 2. 了解改進的模式匹配算法 。 （二） 教學內容 第一節(jié) 串類型的定義 1． 主要內容 串產生的背景，串的概念，串長度、空串、子串、主串 、位置、空格串等概念，串的抽象數據類型定義，串的基本操作集概念。 2． 基本概念 和 知識點 串的概念，串的抽象數據類型定義，串 的基本操作集概念 。 3． 問題與應用（能力要求） 掌握串及相關的概念，理解串的抽象數據類型定義。 第二節(jié) 串的表示和實現 1． 主要內容 串在機內的定長順序表示，串的連接操作和子串操作 ，串的堆分配存儲表示，在這種存儲結構表示時如何實現串的插入操作。 2． 基本 概念和 知識點 串在機內的定長順序表示 及相關操作算法； 串的堆分配存儲表示及相關操作算法。 3． 問題與應用（能力要求） 掌握串的定長順序存儲表示 ； 理解在定長順序存儲結構表示時實現串的連接操作和子串操作的方法 ； 掌握串的堆分配存儲表示 ；了 解在堆分配存儲結構表示時實現串 的插入操作串的塊鏈存儲表示； 了解 串的塊鏈存儲表示 。 *第 三 節(jié) 串的模式匹配算法 （選學） 1． 主要內容 串的 定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函數； KMP 模式匹配算法。 2． 基本 概念和 知識點 串的 定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函數； KMP 模式匹配算法 。 3． 問題與應用（能力要求） 掌握模式匹配的概念，熟悉求子串位置的定位函數 ， 熟悉 KMP 模式匹配算法 。 第 四 節(jié) 串操作應用舉例 1． 主要內容 在文本編輯中使用串操作；使用串建立詞索引表的方法，詞索引表插入的實現算法。 2． 基本 概念和 知識點 在文本編輯中使用串操作；使用串建立詞索引表的方法 。 3． 問題與應用（能力要求） 理解文本編輯中串的用法 ，了 解建立詞索引表中串的用法 。 （三） 實踐環(huán)節(jié) 1. 熟悉串類型的實現方法，了解簡單文字處理的設計方法。 2. 熟悉 C 語言的字符和把字符串處理的原理和方法。 （四） 教學方法與手段 采用黑板 板書 和 PowerPoint 電子教案相結合的方式 。 第五章 數組和廣義表 （一） 目的與要求 1． 掌握數組的順序存儲結構及特殊矩陣的存儲方式； 2． 掌握數組的順序存儲結構及特殊矩陣的存儲方式 ； 3． 了解稀疏矩陣的壓縮存儲方式 — 三元組表 ； 4． 理解 廣義表的定義、術語、存儲結構、運算 。 （二） 教學內容 第一節(jié) 數組的定義 1． 主要內容 抽象數據類型數組的定義。 2． 基本概念 和 知識點 抽象數據類型數組 。 3． 問題與應用（能力要求） 掌握抽象數據類型數組的定義 。 第二節(jié) 數組的順序表示和實現 1． 主要內容 數組的順序存儲結構，以列序為主序的二維數組存儲方式，以行序為主序的二維數組存儲方式， n 維數組的數據元素存儲位置的計算 。 2． 基本 概念和 知識點 數組的順序存儲結構 ， n 維數組的數據元素存儲位置的計算 。 3． 問題與應用（能力要求） 掌握數組的順序表示法。 第 三 節(jié) 矩陣的壓縮存儲 1． 主要內容 矩陣、壓縮存儲、特殊矩陣的概念，特殊矩陣的壓縮存儲算法；稀疏矩陣的概念，稀疏矩陣的壓縮存儲算法，兩個稀疏矩陣相乘的算法