第1章 绪论 (2学时)

教学目标：理解数据结构, 掌握算法分析。

重点、难点：重点是数据结构（逻辑结构、存储结构）；难点是抽象数据类型。

1.1什么是数据结构

1.2抽象数据类型的表示与实现

1.3算法描述和算法分析

第2章 线性表 (8学时)

教学目标：理解循环链表、双向链表, 掌握单链表。

重点、难点：重点是单链表；难点是循环链表、双向链表。

2.1线性表的抽象数据类型定义(1学时)

2.2

线性表的顺序表示和实现 (1学时

)

2.3线性表的链式表示和实现(4学时)

2.3.1单链表

2.3.2循环链表

2.3.3双向链表

2.3.4静态链表

2.4一元多项式的表示及相加运算(2学时)

第3章 栈和队列 (6学时)

教学目标：理解栈和队列, 掌握栈和队列的应用。

重点、难点：重点是栈、队列的基本操作算法；难点是栈、队列在程序设计中的实际应用。

3.1栈 (3学时)

3.1.1栈的抽象数据类型定义

3.1.2栈的表示和实现

3.1.3栈的应用举例

3.1.4栈与递归的实现

3.2队列(3学时)

3.2.1队列的抽象数据类型定义

3.2.2队列的表示和实现

3.2.3队列的应用举例

第4章 串 (3学时)

教学目标：理解串的抽象数据类型定义, 掌握字符串的模式匹配。

重点、难点：重点是字符串的抽象数据类型定义和操作实现；难点是字符串的模式匹配。

4.1串的抽象数据类型定义(1学时)

4.2串的表示和实现(2学时)

4.2.1定长顺序串

4.2.2堆串

第5章 数组和广义表 (4学时)

教学目标：理解广义表的定义, 掌握稀疏矩阵。

重点、难点：重点是特殊矩阵的压缩存储，稀疏矩阵；难点是稀疏矩阵的乘法运算。

5.1数组的抽象数据类型定义(0.5学时)

5.2数组的顺序表示和实现(0.5学时)

5.3矩阵的压缩存储(2学时)

5.3.1特殊矩阵

5.3.2稀疏矩阵

5.4广义表(1学时)

第6章 树和二叉树 (10学时)

教学目标：理解二叉树的遍历, 掌握哈夫曼树。

重点、难点：重点是二叉树的遍历，哈夫曼树及其应用；难点是线索二叉树。

6.1树的抽象数据类型定义(1学时)

6.2二叉树（2学时)

6.2.1二叉树的抽象数据类型定义

6.2.2二叉树的性质

6.2.3二叉树的存储结构

6.3二叉树的遍历与线索化(3学时)

6.3.1二叉树的遍历

6.3.2基于栈的递归消除

6.3.3遍历算法应用

6.3.4线索二叉树

6.4树和森林(2学时)

6.4.1树的存储结构

6.4.2树、森林与二叉树的相互转换

6.4.3树和森林的遍历

6.5哈夫曼树及其应用(2学时)

6.5.1哈夫曼树

6.5.2哈夫曼编码

6.5.3哈夫曼编码算法的实现

第7章 图 (10学时)

教学目标：理解图的存储结构， 掌握求最小生成树、拓扑排序和最短路径。

重点、难点：重点是用普里姆算法求最小生成树、拓扑排序、关键路径、用迪杰斯特拉算法求最短路径的程序实现；难点是邻接多重表、用克鲁斯卡尔算法求最小生成树。

7.1图的抽象数据类型定义和术语(1学时)

7.2图的存储结构(1学时)

7.2.1邻接矩阵

7.2.2邻接表

7.2.3十字链表

7.2.4邻接多重表

7.3图的遍历(2学时)

7.3.1深度优先搜索

7.3.2广度优先搜索

7.4图的连通性问题(2学时)

7.4.1无向图的连通分量

7.4.2最小生成树

7.5有向无环图及其应用(2学时)

7.5.1拓扑排序

7.5.2关键路径

7.6最短路径(2学时)

7.6.1从某个源点到其余各顶点的最短路径

7.6.2每一对顶点之间的最短路径

第8章 查找 (8学时)

教学目标：理解查找的基本方法, 掌握二叉排序树、哈希表。

重点、难点：重点是顺序查找、折半查找、分块查找、二叉排序树、哈希表；难点是平衡二叉排序树、B-树和B+树。

8.1基于线性表的查找方法(2学时)

8.1.1顺序查找法

8.1.2折半查找法

8.1.3分块查找法

8.2基于树的查找方法(4学时)

8.2.1二叉排序树

8.2.2平衡二叉排序树

8.2.3 B树

8.3计算式查找方法——哈希表(2学时)

8.3.1哈希函数的构造方法

8.3.2处理冲突的方法

8.3.3哈希表的查找过程

8.3.4哈希表的性能分析

第9章 内部排序 (5学时)

教学目标：理解内部排序的基本方法， 掌握直接插入排序、快速排序、堆排序、归并排序。

重点、难点：重点是直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序；难点是堆排序，基数排序。

9.1概述

9.2插入类排序(1学时)

9.2.1直接插入排序

9.2.2其它插入排序

9.2.3希尔排序

9.3交换类排序(1学时)

9.3.1冒泡排序

9.3.2快速排序

9.4选择类排序(2学时)

9.4.1简单选择排序

9.4.2树形选择排序

9.4.3堆排序

9.5归并排序(0.5学时)

9.6分配类排序(0.5学时)

9.6.1多关键字排序

9.6.2链式基数排序

9.6.2基数排序的顺序表结构

9.7各种排序方法的综合比较