-
第一章绪论
本章为绪论部分，全面介绍本门课程结构。
-
●1.1导读
本节为第一章导读。
-
●1.2数据结构及其讨论范畴
本节首先介绍了计算机求解现实问题的一般步骤，介绍了“算法+数据结构=程序设计”这一著名公式；
之后介绍了什么是数值数据和非数值数据，以及相应的数值计算问题和非数值计算问题；
在此基础上，本节介绍了数据结构及其讨论的范畴，指出数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的课程。 -
●1.3基本概念和术语
本节首先介绍数据结构相关的一些基本概念和术语，包括数据、数据元素和数据项等；之后本节重点介绍了数据结构的定义及数据结构的类型；最后，本节还介绍了什么是数据的逻辑结构和存储结构？以及逻辑结构的类型和存储结构的几种典型表示方法。
-
●1.4抽象数据类型的表示和实现
本节重点讨论了抽象数据类型的概念以及抽象数据类型的表示和实现方法。结合一个抽象数据类型的实例——复数抽象数据类型，详细阐述了抽象数据类型的表示和实现方法。
-
●1.5算法及其设计要求
本节首先介绍了算法的概念及常见的描述方法；之后介绍了算法必须满足的五个重要特性：有穷性、确定性、可行性和输入、输出；最后还介绍了算法设计的基本原则和要求。
-
●1.6算法效率的度量
本节重点讨论了算法效率的衡量方法；分析了和算法执行时间相关的因素，介绍了时间复杂度和空间复杂度的概念；结合具体实例讨论了时间复杂度的计算方法。
-
第二章线性表
线性结构是最简单且最常用的数据结构。而线性表是一种典型的线性结构，
在程序设计设计中广泛使用。
本章将从线性表的逻辑结构、存储结构及运算三个方面来学习线性表。主要内容如下：
（1）线性表的逻辑结构，即数据元素之间存在着线性关系；
（2）线性表的存储结构：顺序存储结构和链式存储结构；
（3）线性表的两种存储结构的基本算法:建立、查找、插入、删除等。 -
●2.1导读
本节为线性表的导读
-
●2.2线性表的概述
了解线性表的有关概念及研究内容，即线性表的逻辑结构、存储结构及运算。
-
●2.3顺序表的定义
学习顺序表的定义，顺序表的存储结构如何反映数据元素之间的逻辑关系，数据元素地址的计算等。
-
●2.4顺序表的插入和删除
本节介绍顺序表的插入和删除算法及算法时间复杂度分析。
-
●2.5单链表的定义
单链表是一种相对简单的线性表的链式存储结构，本节主要介绍单链表的定义及其存储结构。
-
●2.6单链表中获取某个元素
本节介绍如何在单链表中获取某个元素的算法及时间复杂度分析。
-
●2.7单链表的插入和删除
本节介绍单链表的插入和删除算法及算法时间复杂度分析。
-
●2.8单链表的建立
本节介绍单链表建立的两种方法：头插入法建立带头结点的单链表、尾插入法建立带头结点的单链表。
-
●2.9两个单链表的合并
本节介绍如何将两个“数据元素按值递增有序排列”的线性表归并为新的链表具有同样的性质的算法。
-
●2.10循环链表
本节介绍如何在单链表的基础上构造循环链表,指向尾结点指针的循环链表的特点。
-
●2.11双向链表
本节介绍为什么要构造双向链表，栓想链表的特点及插入、删除的实现等。
-
●2.12一元多项式的表示和相加
介绍一元多项式的顺序存储及链式存储，一元多项式加法的实现算法。
-
●2.13线性表总结
总结线性表讲述的内容，主要从线性表的逻辑结构、存储结构及运算进行总结，比较顺序表和链表的优缺点及选择。
-
第三章栈与队列
本章主要介绍栈与队列的相关内容
-
●3.1导读
介绍了栈和队列的知识内容、重难点、教学规划及学习方法
-
●3.2栈的定义与实现
介绍栈的定义、存储、运算规则以及相关操作。
-
●3.3栈的引用举例—数值转换
介绍栈在实现计算过程的重要应用-------数值转换
-
●3.4栈的引用举例—表达式求值
介绍栈在语言编译系统中的重要应用---------表达式求值
-
●3.5队列的定义
介绍队列的定义、运算规则以及相关操作
-
●3.6链队列的表示与实现
介绍链队列的概念、链队列的表示以及基本的出队、入队算法
-
●3.7循环队列的表示与实现
介绍循环队列定义、队满与队空的判别以及基本操作算法
-
第四章串
在非数值处理、事务处理等问题常涉及到一系列的字符操作。计算机的硬件结构主要是反映数值计算的要求，因此，字符串的处理比具体数值处理复杂。本章中我们将来讨论串的定义、存储结构及其模式匹配算法。
-
●4.1导读
本节为串的导读
-
●4.2串的定义
我们目前只知道字符与串有关，它们之间具体的联系我们通过对本节当中所将要讲解的串的基本概念及抽象数据类型定义来理解。
-
●4.3串的定长顺序存储表示
串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串的存储方式取决于将要对串所进行的操作，首先我们在这节当中来讨论串的定长顺序存储表示的C语言实现方式和在这种存储表示方式下的连接算法及子串删除算法。
-
●4.4堆分配和块链存储表示
本节当中我们来学习串的对分配存储表示和块链存储表示。首先分别介绍这两种存储表示方式的基本概念和C语言实现，着重讨论堆分配存储表示的连接算法和求子串算法。
-
●4.5模式匹配简单算法
模式匹配是一个较为复杂的串操作过程，迄今为止，人们对串的模式匹配提出了许多思想和效率各不相同的计算机算法。本节课我们先来讨论模式匹配简单算法的C语言实现，并通过算法分析来理解其模式匹配过程，最终通过例题讲解来巩固对模式匹配简单算法的理解。
-
●4.6模式匹配KMP算法
本节要学习一种高效率的模式匹配算法，KMP算法。首先我们来讨论他与模式匹配简单算法在匹配过程当中的区别，再接着来看KMP算法当中关键的next[j]函数的定义，以便推导出来模式串指针的指向。
-
第五章数组与广义表
本章主要介绍数组和广义表相关内容
-
●5.1导读
本章主要内容主要包括三个部分，一是理解数组的定义，数组的顺序表示和实现；二是理解和掌握特殊矩阵和稀疏矩阵，尤其稀疏矩阵的三元组表压缩存储方法和其上的矩阵转置运算的算法；三是熟悉广义表的定义、存储结构和深度。
-
●5.2数组的定义
本节学习的内容主要分为三个部分，第一个部分，理解数组与线性表关系。第二个部分，掌握二维数组的抽象类型定义。第三个部分，理解n维数组的抽象类型定义。
-
●5.3数组顺序表示和实现
本节学习的内容主要分为三个部分，第一个部分，理解数组的顺序表示。第二个部分，掌握数组元素存储地址的计算。第三个部分，掌握数组的实现。
-
●5.4矩阵的压缩存储
本节学习的内容主要分为三个部分，第一个部分，理解矩阵压缩存储的概念。第二个部分，掌握对称矩阵与三角矩阵。第三个部分，理解对角矩阵。
-
●5.5稀疏矩阵的定义与三元顺序表
本节学习的内容主要分为三个部分，第一个部分，理解稀疏矩阵的定义。第二个部分，掌握三元组顺序表。第三个部分，应用三元组表表示的稀疏矩阵转置。
-
●5.6行逻辑链接的顺序表
本节主要讲述了三元组顺序表的特点：非零元在表中按行序有序存储，便于进行依行顺序处理的矩阵运算，若需要按行号存取某一行的非零元，则需从头开始查找。为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置，这种“带行链接信息”的三元组表为行逻辑链接的顺序表。即行逻辑链接的顺序表是三元组顺序表的改进，在三元组顺序表的存储结构中加入“行链接”信息。
-
●5.7十字链表
本节学习的内容主要是：由于稀疏矩阵的非零元的个数和位置在某些矩阵运算的过程中会发生很大的变化，如矩阵的加法、减法等运算，为了避免非零元的插入和删除过程中的元素移动，采用链式存储结构表示三元组的线性表更适当。
-
●5.8广义表的定义及存储结构
本节学习的内容主要是：广义表，又称其为列表(Lists)，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。它被广泛的应用于人工智能等领域的表处理语言LISP语言。在LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。
-
●5.9广义表的递归算法
这一节将介绍以下三部分内容，一递归函数，二分治法及其设计思想，三求广义表深度的递归算法。要求理解递归函数的定义，掌握基于分治法的递归算法设计思想，在上述两个知识点学习的基础上，进一步学习求广义表深度的递归算法。
-
第六章树
本章为关于树的相关内容的介绍
-
●6.1导读
介绍了树的知识内容、重难点、教学规划及学习方法。
-
●6.2树的定义与表示
本节介绍树的定义和表示
-
●6.3树的基本术语
本节介绍树的一些基本术语
-
●6.4二叉树的概念与性质
本节介绍二叉树的概念与性质
-
●6.5二叉树的存储结构
本节介绍二叉树的存储结构
-
●6.6二叉树的遍历
本节介绍二叉树的遍历
-
●6.7二叉树的遍历方法
本节介绍二叉树的遍历方法
-
●6.8二叉树遍历的基本应用
本节介绍二叉树遍历的基本应用
-
●6.9二叉树中序非递归的遍历算法
本节介绍二叉树中序非递归的遍历算法
-
●6.10线索化二叉树的表示
本节介绍线索化二叉树的表示
-
●6.11中序线索链表的中序遍历
本节介绍中序线索链表的中序遍历
-
●6.12中序线索化二叉树
本节介绍中序线索化二叉树
-
●6.13树的存储结构
本节介绍树的存储结构
-
●6.14树、森林与二叉树的转换
本节介绍树、森林与二叉树的转换
-
●6.15树和森林的遍历
本节介绍树和森林的遍历
-
●6.16赫夫曼树
本节介绍赫夫曼树
-
●6.17赫夫曼编码
本节介绍赫夫曼编码
-
第七章图
本章为关于图的内容介绍
-
●7.1导读
介绍了图的知识内容、重难点、教学规划及学习方法。
-
●7.2图的定义
介绍图的定义、类型、运算规则以及相关操作。
-
●7.3图基本术语
介绍图的基本术语。
-
●7.4图的邻接矩阵表示法
介绍图的存储、邻接矩阵存储法。
-
●7.5邻接矩阵构建图
介绍图的邻接矩阵数据类型定义、图的创建算法及实现。
-
●7.6图的邻接表存储
介绍图的邻接表存储法、有向图、无向图和网的存储结构及其特点。
-
●7.7邻接表构建图
介绍图的邻接矩表数据类型定义、图的创建算法及实现。
-
●7.8图的深度优先遍历
介绍图的遍历概念，深度优先遍历算法思想、步骤演示、算法设计与实现。
-
●7.9图的广度优先遍历
介绍图的广度优先遍历算法思想、算法示例演示、算法设计与实现。
-
●7.10非联通图遍历
介绍非连通图的遍历算法思想、算法示例演示、算法设计与实现。
-
●7.11生成树与最小生成树
介绍图的生成树的概念、生成树产生的算法、最小生成树概念及实现算法。
-
●7.12Prim思想与分析
介绍Prim算法的思想、步骤、算法示例演示。
-
●7.13Prim设计与实现
介绍Prim算法设计、实现、复杂度分析。
-
●7.14Kruskal算法思想与分析
介绍Kruskal算法的思想、步骤、算法示例演示。
-
●7.15Kruskal算法设计与实现
介绍Kruskal算法设计、实现、复杂度分析。
-
●7.16最短路径和Dijkstra算法
介绍最短路径的概念、单源最短路径的概念、Dijkstr算法思想、步骤和示例演示。
-
●7.17Dijkstra算法设计与实现
介绍Dijkstra算法设计、实现、复杂度分析。
-
●7.18Floyd算法思想与步骤
介绍Floyd算法思想、步骤和示例演示。
-
●7.19Floyd算法设计与实现
介绍Floyd算法设计、实现、复杂度分析。
-
●7.20拓扑排序
介绍拓扑排序的概念、AOV网的概念、拓扑排序步骤、示例演示、算法设计和算法实现。
-
第八章查找
本章主要介绍数据结构中的数据运算：查找运算。本章将分为四大块进行讲解，首先是查找运算中涉及到的基本概念，其次讲解静态查找表，然后讲解动态查找表，最后讲解哈希表。
静态查找表中涉及顺序查找表、折半查找表、索引顺序表。动态查找表中主要涉及二叉排序树和平衡二叉树。哈希表中主要讲解哈希表的定义，哈希函数的构造方法，处理冲突的方法和哈希表的查找。 -
●8.1导读
本节为查找的导读
-
●8.2查找的基本概念
本节介绍查找表、静态查找表、动态查找表、主关键字、次关键字、查找、查找成功、查找不成功、平均查找长度、静态查找表的抽象数据类型、动态查找表的抽象数据类型、哈希表的定义。其中平均查找长度、静态查找表、动态查找表、哈希表的定义是重点内容。
-
●8.3顺序表
本节主要围绕顺序查找进行讲解，主要介绍顺序查找的存储结构、查找思想、算法以及实现、最后进行顺序查找的性能分析。理解顺序查找的思想，掌握其算法，并能用C语言实现。
-
●8.4有序表-折半查找
本节主要围绕有序表的折半查找进行讲解，主要介绍折半查找的前提要求、查找思想、算法以及实现、最后进行折半查找的性能分析。理解折半查找的思想，掌握其算法，并能用C语言实现。
-
●8.5索引顺序表
本节主要围绕索引顺序表的查找进行讲解，主要介绍构建索引顺序表的前提要求、索引顺序表的查找思想以及查找算法的性能分析。
-
●8.6二叉排序树（上）
本节主要介绍二叉排序树的定义、存储结构、查找思想、查找算法以及算法分析、插入算法以及算法分析、删除算法以及算法分析。重点理解二叉排序树的定义，查找、插入、删除都是围绕二叉排序树的定义展开的。
-
●8.7二叉排序树（下）
本节主要介绍二叉排序树的定义、存储结构、查找思想、查找算法以及算法分析、插入算法以及算法分析、删除算法以及算法分析。重点理解二叉排序树的定义，查找、插入、删除都是围绕二叉排序树的定义展开的。
-
●8.8平衡二叉树
本节主要介绍平衡二叉树的定义以及平衡旋转的四种方法。
-
●8.9哈希表（一）
本节主要介绍哈希表的定义，哈希函数的构造方法，处理冲突的方法，哈希表的查找及其分析。其中处理冲突的开发地址法和链地址法、哈希表的查找以及性能分析是本节的重点内容。
-
●8.10哈希表（二）
本节主要介绍哈希表的定义，哈希函数的构造方法，处理冲突的方法，哈希表的查找及其分析。其中处理冲突的开发地址法和链地址法、哈希表的查找以及性能分析是本节的重点内容。
-
●8.11哈希表（三）
本节主要介绍哈希表的定义，哈希函数的构造方法，处理冲突的方法，哈希表的查找及其分析。其中处理冲突的开发地址法和链地址法、哈希表的查找以及性能分析是本节的重点内容。
-
●8.12哈希表（四）
本节主要介绍哈希表的定义，哈希函数的构造方法，处理冲突的方法，哈希表的查找及其分析。其中处理冲突的开发地址法和链地址法、哈希表的查找以及性能分析是本节的重点内容。
-
第九章排序
本章主要围绕数据结构中的数据运算：排序运算展开讲解。本章涉及的内容包括排序的相关概念；插入类排序；快速排序；选择类排序；归并排序；基数排序。插入类排序里面包含直接插入排序；折半插入排序；表插入排序；希尔排序。快速排序包含起泡排序；快速排序；选择排序包含简单选择排序；树形选择排序和堆排序。基数排序包含多关键字排序和链式基数排序。
-
●9.1导读
本节为排序的导读
-
●9.2排序的相关概念
本节主要介绍一下概念：排序、内部排序、外部排序、内部排序的分类、排序方法的稳定性、排序方法的不稳定性、排序的存储结构、排序算法的效率分析。
-
●9.3直接插入排序
本节介绍直接插入排序的算法思想、算法实现以及分析算法的性能。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.4折半插入排序
本节介绍折半插入排序的算法思想、算法实现以及分析算法的性能。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.5表插入排序
本节介绍表插入排序的算法思想、算法的存储结构。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.6希尔排序
本节介绍希尔排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.7起泡排序
本节介绍起泡排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.8快速排序
本节介绍快速排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.9简单选择排序
本节介绍简单选择排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.10树形选择排序
本节介绍树形选择排序的算法思想。在讲解过程中，给出算法演示进一步理解算法思想。
-
●9.11堆排序
本节介绍堆的定义、堆排序的基本思想、如何将无序序列建成堆、堆的重新调整，已经堆排序算法的性能分析。
-
●9.12归并排序
本节主要介绍归并排序的算法思想已经算法性能分析，结合实例进行算法演示，进一步理解算法思想。
-
●9.13基数排序
本节主要介绍基数排序算法思想，两种基数排序算法：多关键字排序和链式基数排序，以及基数排序的算法性能分析。
-
●9.14内部排序方法的比较排序
本节从各类排序算法的时间复杂度、空间复杂度、算法的稳定性方面进行比较。
