-
第一章绪论
数据结构的课程简介、基本概念及术语、抽象数据类型的介绍，以及算法的定义、时间复杂度、空间复杂度的描述
-
●1.1什么是数据结构
数据结构等基本概念的定义，以及数据结构的各种逻辑结构和存储结构的描述
-
●1.2基本概念和术语
描述数据结构等基本概念的定义
-
●1.3抽象数据类型的表示与实现
描述抽象数据类型的定义及表示方法
-
●1.4算法和算法分析
算法的定义、设计要求、及评价算法的时间复杂度和空间复杂度的度量方法进行描述
-
第二章线性表
线性表的定义，线性表的顺序表示及实现，线性表的链式表示和实现，以及用单链表完成一元多项式的表示及相加
-
●2.1线性表的类型定义
线性表是由n≥0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结点。
-
●2.2线性表的顺序表示和实现
顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和
逻辑结构中各结点相邻关系是一致的。地址计算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址为1）
在顺序表中实现的基本运算：
•插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。
•删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。 -
●2.3线性表的链式表示和实现
采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O（1），不用
遍历整个链表。
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方
向的链。由头指针head惟一确定。
双链表也可以头尾相链接构成双（向）循环链表。
双链表上的插入和删除时间复杂度均为O （1）。
顺序表和链表的比较： •基于空间：
•顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小时采用。
•线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构。
一个单链表由头指针的名字来命名。 -
●2.4一元多项式I的表示及相加
如何用链表表示一元多项式，及在此存储结构上如何完成一元多项式的相加。
-
第三章栈和队列
栈（Stack）是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表（Last In First Out）。通常栈有
顺序栈和链栈两种存储结构。
队列（Queue）是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称
为队头（front），允许插入的一端称为队尾（rear） ，队列的操作原则是先进先出的，又称作FIFO表（First In
First Out） .队列也有顺序存储和链式存储两种存储结构。 -
●3.1栈
栈和队列的抽象类型定义及其顺序存储结构和链式存储的表示及实现，栈的应用举例。
-
●3.2栈的应用举例
利用栈解决各种经典的应用问题的举例
-
●3.3队列
队列抽象类型定义，及链队列、循环队列的表示方法
-
第四章串
串是零个或多个字符组成的有限序列。
•空串：是指长度为零的串，也就是串中不包含任何字符（结点）。
•空白串：指串中包含一个或多个空格字符的串。
•在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。
•子串在主串中的序号就是指子串在主串中首次出现的位置。
•空串是任意串的子串，任意串是自身的子串。
串分为两种： •串常量在程序中只能引用不能改变；
•串变量的值可以改变。
串的基本运算有： •求串长strlen（char*s）
•串复制strcpy（char*to，char*from）
•串联接strcat（char*to，char*from）
•串比较charcmp（char*s1，char*s2）
•字符定位strchr（char*s，charc） -
●4.1串类型的定义
串(字符串)是由零个或多个字符组成的有限序列。由一对单引号相括，如: ‘a string’
-
●4.2串的表示和实现
串的定长存储表示方法，及在此结构上串的典型算法的实现方法
-
●4.3串的模式匹配算法
介绍一般的串的模式匹配算法，在此基础上重点介绍了KMP算法。
-
第五章数组和广义表
数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一种数据结构。
-
●5.1数组的定义
数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：
(1) 取值操作：给定一组下标，读其对应的数据元素。
(2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 -
●5.2数组的顺序表示和实现
对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。
-
●5.3矩阵的压缩存储
首先介绍了几种特殊矩阵的定义及存储方法，然后描述了稀疏矩阵的定义及三元组的存储方法，及在此存储结构上完成矩阵的转置的算法，最后介绍了稀疏矩阵的其他链式的存储方法。
-
●5.4广义表的定义
广义表的定义及其抽象数据类型的定义。
-
●5.5广义表的存储结构
介绍存储广义表的表头、表尾表示法
-
●5.6广义表操作的递归函数
利用递归函数完成求广义表的深度问题，复制广义表的问题，建立广义表的存储结构的问题。
-
第六章树和二叉树
树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。
-
●6.1树的定义和基本术语
树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称 根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结 点）；除根外的分支结点称内部结点； 有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合；
-
●6.2二叉树
二叉树及其基本术语的定义，二叉树的基本性质及证明过程，二叉树的顺序存储及二叉链表、三叉链表的存储方法。
-
●6.3遍历二叉树和线索二叉树
遍历二叉树的三种方法的定义及其实现的递归算法，以及中序遍历的非递归算法，线索二叉树的定义、存储结构、中序线索树的遍历算法、建立中序线索树的算法。
-
●6.4树和森林
树的双亲表示法、孩子链表表示法、儿子-兄弟链表存储表示方法，森林与二叉树的转换方法，以及树和森林的遍历算法的描述。
-
●6.5赫夫曼树及其应用
最优二叉树的定义，赫夫曼树的定义、构造方法、赫夫曼编码方法、及其算法描述。
-
●6.6树的计数
树的计数的定义，二叉树的计数问题，树的计数问题。
-
第七章图
图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。
-
●7.1图的定义和术语
图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重 的简单路径； 网络：是带权的图。
-
●7.2图的存储结构
介绍图的4种存储结构,包括数组表示法、邻接表、十字链表、邻接多重表。
-
●7.3图的遍历
介绍图的两种遍历算法：深度优先搜索和广度优先搜索，并结合上节的存储结构给出算法描述。
-
●7.4图的连通性问题
首先介绍无向图的连通分量的定义，然后描述最小生成树的定义及其应用，最后重点介绍了生成最小生成树的普里姆算法及克鲁斯卡尔算法。
-
●7.5有向无环图及其应用
首先描述了有向无环图的定义，然后定义了图的拓扑排序及如何进行拓扑排序的算法，最后定义了AOE网及求取关键路径的算法。
-
●7.6最短路径
首先讲解了最短路径的概念及其应用，然后讲解了求解单源最短路径的Dijsktra算法，最后讲解了Floyd算法求解每一对定点之间的最短路径。
-
第八章查找
查找的定义及分类，静态查找表的存储方式及其查找算法，动态查找表定义和存储方式及其查找、插入、删除的算法，哈希表的定义，构造哈希表的方法，处理冲突的算法。
-
●8.1查找概述
查找的定义，查找的分类。
-
●8.2静态查找表
静态查找表的定义及其查找算法，包括顺序表、有序表和索引顺序表的查找算法。
-
●8.3动态查找表
动态查找表的定义，二叉排序树、平衡二叉树、B-树和B+树的定义、存储结构、查找、插入、删除的算法。
-
●8.4哈希表
介绍了哈希表的定义、特点、查找效率等，构造哈希函数的方法，处理冲突的方法。
-
第九章内部排序
内部排序、外部排序的定义，各种内部排序算法的描述，包括插入排序、选择排序、归并排序、基数排序、及各种内部排序方法的比较讨论等。
-
●9.1概述
排序、内部排序、外部排序的定义，内部排序的分类。
-
●9.2插入排序
插入排序的定义，直接插入排序、折半插入排序、希尔排序的算法描述及示例。
-
●9.3快速排序与选择排序
选择排序的定义，简单选择排序算法、堆排序的算法描述，堆排序包括建堆及筛选的过程
-
●9.4归并排序
归并排序的定义及算法描述。
-
●9.5基数排序
基数排序的定义，多关键字的排序方法及算法描述，链式基数排序的方法及算法描述。
-
●9.6各种内部排序方法的比较讨论
对各种排序算法的稳定性、适合情况、优缺点进行总结和比较。