理论教学部分

第一讲 绪论（支撑课程目标1）

1. 内容：本章主要介绍数据结构的基本概念；抽象数据类型；描述算法所用的类C 语言中的一些语法问题和程序设计基本技巧；算法时间复杂度和空间复杂度的分析初步等。

2. 要求：了解数据结构的基本概念，抽象数据类型的概念、记法和用法，以及该记法和面向对象程序设计的关系；了解高级语言的基本构造和控制结构，数据存储的特点，指针、链表概念和相关操作对本课程的影响；了解算法时间复杂度和空间复杂度的概念和基本分析方法。理解数据结构的重要性和相关课程的关系。掌握程序设计基本技巧，多个分析的范例和相应的结论。

3. 重点：基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等；抽象数据类型。

4. 难点：算法时间复杂度和空间复杂度的分析初步。

5. 知识目标：理解常见的几种数据结构类型；理解抽象数据类型描述算法的基本方法；掌握分析算法性能的基本方法和算法时间复杂度的计算方法。

6. 能力目标：具备区分不同的数据结构类型，具备区分数据的逻辑结构和存储结构，并能够计算和分析算法的时间复杂度的能力。

第二讲 算法设计与分析（支撑课程目标1-3）

1. 内容：本章主要介绍分治法、回溯法、贪心法、动态规划法和分支限界法等几种常见的算法设计方法的概念、实现及相关应用等。

2. 要求：掌握分治法、回溯法、贪心法、动态规划法和分支限界法的基本思想及策略、实现的基本步骤，复杂性分析、以及依据算法设计方法设计程序时的思维过程等；了解各种算法设计方法的适用的情况，并了解使用每种算法设计方法求解的有哪些经典问题；掌握每一种方法的设计技巧，多分析每种方法实现的范例。

3. 重点：基本概念：分治法、回溯法、贪心法、动态规划法和分支限界法。

4. 难点：分治法、回溯法、贪心法、动态规划法和分支限界法的实现和复杂性分析。

5. 知识目标：掌握几种常见的算法设计方法和基本思想；理解它们实现的基本步骤，复杂性分析等。

6. 能力目标：具备运用各种算法设计方法来解决相应的工程问题，对于不同的问题能够正确选择合适的方法来进行算法设计，并且能够分析算法的效率。

第三讲 线性表（支撑课程目标1-3）

1. 内容：本章主要介绍线性表的基本概念和类型定义；线性表的顺序存储结构；线性表的连接存储结构等。

2. 要求：了解线性表结构的用途和性质，循环链表和双向链表的原理和相关的算法设计；掌握线性表的基本概念和类型定义，线性表的顺序存储结构和相应的算法设计以及该结构下相应操作示意图的画法，掌握线性表的链接存储结构和相应的算法设计，特别是单链表的查找、插入和删除等基本操作的算法，掌握循环链表和双向链表的原理和相关的算法设计结构下相应操作示意图的画法。

3. 重点：线性表的顺序存储结构；线性表的链接存储结构。

4. 难点：单链表的插入和删除操作算法，以及双向链表的插入和删除算法。

5. 知识目标：掌握线性表的基本概念和类型定义；掌握线性表的顺序存储结构和相应的算法设计；掌握线性表的链接存储结构和相应的算法设计，特别是单链表的查找、插入和删除等基本操作的算法；掌握循环链表和双向链表的实现原理和相关的算法设计。

6. 能力目标：具备运用顺序存储结构和链接存储结构来解决相应的工程问题，对于不同的问题能够正确选择合适的存储结构来进行算法设计，并且能够分析算法的效率。

第四讲 栈和队列（支撑课程目标1-3）

1. 内容：本章主要介绍栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法和栈的应用举例；队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

2. 要求：了解栈结构的用途和性质，栈的应用范例，队列结构的用途和性质；理解和掌握栈的基本概念和类型定义，栈的链接存储结构和相应的操作示意图的画法，掌握栈的链接存储结构下相应的算法设计；掌握队列的基本概念和类型定义，队列的顺序存储(循环队)和链接存储结构下相应的算法设计以及该结构下相应操作示意图的画法。

3. 重点：栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法；队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

4. 难点：栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法；队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。

5. 知识目标：掌握栈的基本概念和类型定义，了解该结构的用途和性质，掌握栈的链接存储结构和相应的操作示意图的画法，掌握栈的链接存储结构下相应的算法设计，了解栈的应用范例，能够举一反三的进行案例讨论；掌握队列的基本概念和类型定义，了解该结构的用途和性质，掌握队列的顺序存储(循环队)和链接存储结构下相应的算法设计，掌握该结构下相应操作示意图的画法。

6. 能力目标：具备运用栈设计解决实际应用问题的能力；具备运用队列设计解决实际应用问题的能力。

第五讲 串（支撑课程目标1-3）

1. 内容：本章主要介绍串类型的定义；串的表示和实现；串的模式匹配；串操作应用举例等。

2. 要求：理解串的基本概念；掌握串的基本操作的算法，以及串的存储结构；了解串操作应用举例。

3. 重点：串的基本操作的算法；串的存储结构；串的模式匹配算法。

4. 难点：串的模式匹配算法。

5. 知识目标：掌握串的存储方法；理解串的模式匹配算法，尤其是KMP 算法。

6. 能力目标：具备运用串的基本操作函数解决实际问题的能力；具备在实际文档处理问题中能够运用串的模式匹配算法的能力。

第六讲 数组和广义表（支撑课程目标1-3）

1. 内容：本章主要介绍数组的定义；数组的顺序表示和实现；矩阵的压缩存储；广义表的定义及存储结构等。

2. 要求：明确数组和广义表这两种数据结构的特点；掌握数组存储时地址计算方法；掌握几种特殊矩阵的压缩存储方法；了解广义表的定义及存储结构等。

3. 要点：多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算。

4. 难点：难点是稀疏矩阵的压缩存储表示下实现的算法。

5. 知识目标：掌握数组的顺序存储；掌握稀疏矩阵的压缩存储，掌握广义表的定义及存储结构。

6. 能力目标：具备在解决实际问题中使用稀疏矩阵压缩存储和特殊矩阵压缩存储的能力；具备灵活运用广义表解决实际问题的能力。

第七讲 树和二叉树（支撑课程目标1-3）

1. 内容：本章主要介绍树的定义、性质和表示方法；二叉树的定义、性质和存储结构；二叉树的各种遍历方法及实现；建立二叉树、输出二叉树、求二叉树深度等操作方法及实现；树的存储结构，进行各种遍历的讨论；树与二叉树、森林与二叉树之间的相互转换方法；哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生等内容。

2. 要求：了解树的定义、性质和表示方法，树的各种遍历方法及实现，了解相应的算法设计；了解树与二叉树、森林与二叉树之间的相互转换方法；理解非线性结构的特点和存储实现的困难；掌握二叉树的定义、性质和存储结构，能够正确画出相应结构的示意图；掌握二叉树的先根遍历、中根遍历、后根遍历和按层次遍历的原理及实现，掌握相应的算法设计；掌握二叉树的各种遍历方法及实现，掌握相应的算法设计；掌握哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生，掌握相应的算法设计。

3. 要点：二叉树的定义、性质和存储结构；二叉树的各种遍历方法及实现；建立二叉树、输出二叉树、求二叉树深度等操作方法及实现；哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生。

4. 难点：二叉树的定义、性质和存储结构；二叉树的各种遍历方法及实现；建立二叉树、输出二叉树、求二叉树深度等操作方法及实现；哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的产生。

5. 知识目标：理解树结构的定义和基本操作；理解二叉树的基本概念、基本性质，以及树和二叉树的关系；理解遍历二叉树的几种算法和线索二叉树的方法；理解二叉树和树、森林之间的相互转换；理解哈夫曼树的创建及其应用。

6. 能力目标：具备用树来描述现实世界、应用二叉树解决实际问题的能力；具有恰当的选择二叉树作为数据的逻辑结构和存储结构的能力。

第八讲 图（支撑课程目标1-3）

1. 内容：本章主要介绍图的定义和术语；图的邻接矩阵、邻接表表示；图的深度和广度优先搜索遍历；图的生成树和最小生成树；拓扑排序；图的关键路径和最短路径等内容。

2. 要求：掌握图的定义及术语，图的存储结构，图的深度和广度搜索遍历，图的连通性问题；了解有向无环图及其应用；掌握最短路径和关键路径的求解过程和算法。

3. 要点：图的邻接矩阵、邻接表表示；图的深度和广度优先搜索遍历；图的生成树和最小生成树；图的最短路径。

4. 难点：图的邻接矩阵、邻接表表示；图的深度和广度优先搜索遍历；图的生成树和最小生成树；图的关键路径；图的最短路径。

5. 知识目标：理解图的深度和广度优先搜索遍历相应的原理算法；理解图的生成树和最小生成树的原理和算法；理解拓扑排序的原理和算法；理解图的关键路径和图的最短路径相应的原理和算法。

6. 能力目标：具有恰当的选择图作为数据的逻辑结构的能力；具有应用图解决实际问题的能力。

第九讲 查找（支撑课程目标1-3）

1. 内容：本章主要介绍顺序查找和二分查找；索引查找和分块查找；哈希查找等内容。

2. 要求：了解索引查找和分块查找以及哈希查找相应的算法设计；理解和掌握顺序查找和二分查找的原理和相应的算法设计；理解和掌握索引查找和分块查找以及哈希查找的原理。

3. 要点：顺序查找和二分查找；哈希查找，以及哈希冲突的解决方法。

4. 难点：索引查找和分块查找，以及哈希查找。

5. 知识目标：理解顺序查找和二分查找的原理，掌握相应的算法设计；理解索引查找和分块查找的原理，了解相应的算法设计；理解掌握哈希查找的原理，了解相应的算法设计。

6. 能力目标：具有应用适当的查找方法解决实际问题的能力；具备平均查找长度的求解和分析能力。

第十讲 排序（支撑课程目标1-3）

1. 内容：本章主要介绍排序的基础概念；插入排序；交换排序；选择排序；归并排序基数排序；各种内部排序方法的讨论等内容。

2. 要求：了解排序的基础概念和相应算法的分析方法；了解归并排序的原理和相应的算法设计；了解基数排序的原理和相应的算法设计；理解和掌握直接插入排序的原理和相应的算法设计；理解和掌握冒泡排序和快速排序的原理和相应的算法设计；理解和掌握直接选择排序和堆排序的原理和相应的算法设计。

3. 要点：快速排序、堆排序、归并排序和基数排序的基本思想及排序过程。

4. 难点：快速排序、堆排序、归并排序和基数排序等算法的实现。

5. 知识目标：了解排序的基础概念和相应算法的分析方法；理解直接插入排序的原理和相应的算法设计；理解冒泡排序和快速排序的原理和相应的算法设计；理解直接选择排序和堆排序的原理和相应的算法设计；理解归并排序的原理和相应的算法设计；了解基数排序的原理和相应的算法设计。

6. 能力目标：具有应用适当的排序方法解决实际问题的能力；具备对各种排序算法效率及性能的分析能力。

实验教学部分

第一次实验 线性表（支撑课程目标1-3）

1. 实验目标：通过线性表的实验使学生掌握顺序表及其基本操作的实现，以及链表及其基本操作的实现；具备能够采用顺序存储和链接存储等数据的基本存储方式来处理数据在计算机中的存储能力。

2. 实验内容：

（1）实验要求：掌握顺序表的创建以及相关的基本操作；单链表(带头结点、不带头结点) 、双向链表的创建及其相关的基本操作。

（2）实验过程：

1）编程实现一个对顺序表进行基本操作的系统，主要包括表的创建、输入、查询、取值、插入、删除和输出等操作。

2）编程实现一个对单链表进行基本操作的系统，主要包括表的创建、输入、查询、取值、插入、删除和输出等操作。（要求：可以采用带头结点和不带头结点的单链表）

3）利用线性表的基本操作实现对一个班级学生信息（包括：学号、姓名、学院、专业、班级、性别、年龄等）管理的系统（主要功能包括：数据录入、插入、删除、输出、查找等）。

第二次实验 栈和队列（支撑课程目标1-3）

1. 实验目标：通过栈和队列的实验使学生能够掌握栈和队列的特点，并能在相应的应用问题中正确选用相应的数据结构算法。熟练掌握顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件。熟练掌握循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。理解递归算法执行过程中栈的状态变化过程。

2. 实验内容：

（1）实验要求：掌握栈和队列的特点，并能在相应的应用问题中正确选用相应的数据结构算法。

（2）实验过程： 

1）编程实现栈的基本操作，主要包括栈的创建、压栈栈和弹栈等基本操作。

2）编程实现队列的基本操作，主要包括队列的创建、入队和出队等基本操作。

3）用本章所学数据结构实现十进制数转换成二、八、十六进制数。

4）通过修改完善教材中的算法3.22，利用栈来实现算术表达式求值的算法。

第三次实验 串的模式匹配（支撑课程目标1-3）

1. 实验目标：通过串的模式匹配实验使学生掌握串的定义及实现；掌握串的两种模式匹配算法，BF算法和KMP算法；利用串的模式匹配算法进行一些实际应用的程序设计。

2. 实验内容：

（1）实验要求：掌握串的定义及实现；掌握串的两种模式匹配算法，BF算法和KMP算法；利用串的模式匹配算法进行一些实际应用的程序设计，存储结构可以根据实际情况选择顺序存储或链接存储。

（2）实验过程：

1）请编程实现串的模式匹配的BF算法。

2）请编程实现串的模式匹配的KMP算法。

3）请采用KMP算法编程实现病毒感染检测算法。 

第四次实验 二叉树（支撑课程目标1-3）

1. 实验目标：通过二叉树的实验使学生掌握二叉树的链式存储结构及其相关操作的实现；掌握二叉树的先序、中序、后序的递归遍历算法；理解二叉树的各种非递归遍历算法的实现。具备对二叉树的工程应用能力。

2. 实验内容：

（1）实验要求：掌握二叉树的基本概念，以及二叉树的基本操作；重点掌握二叉树的前、中和后序遍历，以及二叉树的线索化等算法；掌握赫夫曼树的含义及其应用。

（2）实验过程：

1）编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法。

2）编程实现哈夫曼树的构造，以及对该赫夫曼树的编码。

3）编程实现利用二叉树求解表达式的值。（算法参考教材算法5.12-5.13）

第五次实验 图（支撑课程目标1-3）

1. 实验目标：通过对图的一些基本操作的实验使学生掌握图的深度优先遍历和广度优先遍历算法；掌握图的的拓扑排序、关键路径和最短路径等算法的实现过程。具备运用图的基本算法解决实际工程问题的能力。

2. 实验内容：

（1）实验要求：图的深度优先遍历和广度优先遍历算法的实现；图的最小生成树和最短路径算法的实现。

（2）实验过程：

1）编程实现全国交通咨询模拟系统。出于不同目的的旅客对交通工具有不同的要求。

实现功能：

① 对城市信息进行编辑的功能；

② 城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑的功能；

③ 两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具；

④ 途中耗费的总时间应该包括中转站的等候时间；

⑤ 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

第六次实验 查找（支撑课程目标1-3）

1. 实验目标：通过对不同查找方法的实验使学生掌握顺序查找与折半（二分法）查找算法；掌握二叉排序树的创建及查找算法的实现；掌握哈希表的造表及在哈希表中查找算法的实现。具备依据不同问题选择不同查找方法处理实际问题的能力。

2. 实验内容：

（1）实验要求：顺序查找与折半（二分法）查找算法；二叉排序树的创建及查找算法的实现；哈希表的造表及在哈希表中查找算法的实现。

（2）实验过程：

1）用递归调用形式编写折半查找算法程序。

2）编写读入一串整数构成一棵二叉排序树的算法，并且对其做一些相关的查找。

3）编写实现哈希表的造表及在哈希表中查找的算法。

第七次实验 排序（支撑课程目标1-3）

1. 实验目标：通过对不同排序算法的实验使学生掌握交换排序（冒泡排序、快速排序）算法的实现方法；掌握选择排序（堆排序）算法的实现方法。具备依据不同问题选择较为合适的排序方法来解决实际问题的能力。

2. 实验内容：

（1）实验目标：冒泡排序、快速排序和堆排序算法的实现。

（2）实验过程：编写程序实现冒泡排序、快速排序和堆排序等算法。

第八次实验 常见算法设计方法的实现（支撑课程目标1-3）

1. 实验目标：通过对不同算法设计方法的实验使学生掌握各种常见算法设计方法的基本思想和实现方法；了解各种算法设计方法的适用的情况，并了解使用每种算法设计方法求解的有哪些经典问题。 

2. 实验内容：

（1）实验目标：贪心法、动态规划法和分支限界法等的实现，及经典应用问题。

（2）实验过程：编写程序实现贪心法、动态规划法和分支限界法等。