数据结构教学大纲

《数据结构与算法》教学大纲

课程编号：030816 适用专业：教育技术学 总学时数：64

学 分：4

编制单位：茂名学院理学院教育与信息技术系 编制时间：2008年6月20日

一、课程地位、性质和任务

《数据结构与算法》课程是计算机相关学科专业的基础课程中的一门重要的核心课

程。通过本课程的教学，使学生知道求解非数值类问题的基本模型（表、树、图），模型的特点和适用场合，能够根据问题设计和选择好的算法，为学习后续的操作系统、编译原理和软件工程等专业课程，设计应用程序打下基础。

本课程以提高学生的计算机应用能力和综合素质为目标，通过课程教学，为学生构建数据结构与算法方面的知识体系，使学生一方面能够根据问题选择合适的数据结构，设计高效的算法，提高程序设计能力，另一方面，在工程应用中，具有甄别好算法的能力，也就是要从建模、解模和综合等三个方面，提高学生的程序设计能力。

二、与其他课程的关系

先修课：程序设计基础、离散数学、计算机组成原理、计算机文化基础

三、教学内容、课时安排和基本要求 （一）教学部分 第1章 绪论（2学时） 1.1什么是数据结构 1.2 基本概念和术语

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

1.4 算法和算法分析（算法及其设计的要求， 算法效率的度量，算法的存储空间需求） 1.5 问题求解

基本要求：

了解：抽象数据类型，算法设计方法与算法分析。

掌握：数据与数据结构、算法的基本概念；问题求解的方法与步骤 重点：数据结构和算法的概念，算法的描述形式和评价方法，问题求解的一般步骤

1

难点：评价算法的标准和评价方法，最坏情况和平均情况的区分。

第2章 线性表（8学时） 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现（线性链表，循环链表，双向链表） 2.4 一元多项式的表示及相加

基本要求：

了解：两种存储结构（顺序存储结构和链式存储结构）及一元多项式的表示

及相加。

掌握：要求熟练掌握处理线性表的各种算法。为后继章节的学习打基础。 重点：各种算法。 难点：链表的理解。

第3章 栈与队列（4学时）

3.1 栈（定义，栈的表示和实现）

3.2 栈的应用举例（数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值）

3.3 栈与递归的实现

3.4 队列及其实现（定义，链队列，循环队列） 3.5 *离散事件模拟

教学要求：熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。栈和队列是表最基本和重要的数据结构，是数据结构课程的基础。

基本要求：

了解： 栈和队列的定义及其实现。

掌握： 熟练掌握栈和队列的特性和在不同存储结构前提下的算法实现。 重点： 栈和队列的算法实现。 难点： 栈和队列的算法实现。

第4章 串（2学时） 4.1 串类型的定义

4.2 串的表示和实现（定长顺序存储，堆分配存储，串的块链存储） 4.3 串的模式匹配算法（求子串位置的定位函数，模式匹配的一种改进算法） 4.4 串操作应用举例（文本编辑，建立词索引表）

2

基本要求：

了解：串的基本概念及主要操作和运算。 掌握：掌握串的基本概念和运算。 重点：主要操作和运算。 难点：模式匹配及串的应用。

第5章 数组（2学时） 5.1 数组的定义

5.2 数组的顺序表示和实现

5.3 矩阵的压缩存储（特殊矩阵，稀疏矩阵） 5.4 广义表的定义 5.5 广义表的存储结构 5.6 m元多项式的表示

5.7 广义表的递归算法（求广义表的深度，复制广义表，建立广义表的存储结构）

基本要求：

了解：了解作为抽象数据类型的数组和C语言的数组。认识到数组可以作为

顺序存储结构用于顺序表、字符串和稀疏矩阵的实现。也可以采用链式存储结构。

掌握：掌握基本概念和算法。 重点：算法。

难点：广义表的递归算法。

第6章 树与二叉树（15学时） 6.1 树的定义和基本术语

6.2 二叉树（二叉树的定义，二叉树的性质，二叉树的存储结构） 6.3 遍历二叉树和线索二叉树（遍历二叉树，线索二叉树）

6.4 树和森林（树的存储结构，森林与二叉树的转换，树和森林的遍历） 6.5 树与等价问题

6.6 赫夫曼树及其应用（最优二叉树（赫夫曼树），赫夫曼编码） 6.7 回溯法与树的遍历 6.8 树的计数

基本要求：

3

了解：理解树与森林的定义与术语。

掌握：熟练掌握二叉树性质和遍历算法，掌握树与森林的孩子兄弟存储表示

和遍历。掌握哈夫曼树构造的方法和算法。 重点： 树的存储结构和遍历算法。 难点：哈夫曼树构造的方法和算法

第7章 图（11学时） 7.1 图的定义和术语

7.2 图的存储结构（数组表示法，邻接表，十字链表，邻接多重表） 7.3 图的遍历（深度优先搜索，广度优先搜索）

7.4 图的连通性问题（无向图的连通分量和生成树，有向图的强连通分量，最小生成树，关节点和重连通分量）

7.5 有向无环图及其应用（拓扑排序，关键路径）

7.6 最短路径（从某个源点到其余各项点的最短路径，每一对顶点之间的最短路径） 基本要求：

了解：图的基本概念和相关术语。

掌握：图的两种主要存储结构及遍历算法。掌握最小生成树、最短路径和活

动网算法的思想。

重点：图的两种主要存储结构及遍历算法。 难点：图的遍历算法，最短路径算法。

第8章 查找（8学时）

9.1 静态查找表（顺序表，有序表，静态树表，索引顺序表） 9.2 动态查找表（二叉排序树和平衡二叉树，B_树和B+树，键树） 9.3 哈希表（定义，构造方法，处理冲突的方法，查找及其分析）

基本要求：

了解： 各种查找法的基本概念及实现的基本思想。

掌握：熟练掌握搜索结构的折半查找、二叉搜索树、平衡二叉树主要搜索算

法。掌握哈希表查找算法。 重点：各种算法的基本思想及实现。 难点：哈希表查找算法。

4

第9章 内部排序（8学时） 10.1 概述

10.2 插入排序（直接插入，其他插入，希尔） 10.3 交换排序（冒泡排序、快速排序） 10.4 选择排序（简单，树形，堆） 10.5 归并排序

10.6 基数排序（多关键字，链式） 10.7 排序算法分析

基本要求：

了解：基数排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交换排序，选择排序，归并排序重点：内部排序算法

难点：基数排序（多关键字，链式）

第10章 *外部排序（2学时） 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树

基本要求：

了解：外部排序的基本概念和相关术语。

掌握：基本掌握外排算法的基本思想，不同排序方法的比较。 重点：外部排序算法 难点：多路平衡归并的实现 第11章 算法设计的一般方法（2学时）

1．重点

（1）有效算法的概念，问题固有难度的概念；

（2）递归法；分治法；平衡原则；贪心法；动态规划的基本原理； （3）搜索-回溯法的基本原理和本质. 2．难点

（1）问题固有难度的概念；

（2）递归分治法的效率分析（写出时间耗费的递推式，并求解）； （3）动态规划法中的状态转移方程的确定。

5

（二）实验、实习部分

课程安排五个类别的实验，实验时数为12课时，其中： 实验一、线性链表及运算 2课时 实验二、栈和队列 2课时 实验三、树和二叉树 4课时 实验四、图及其应用 2课时 实验五、查找与排序 2课时

四、课程考核方式

闭卷考试70%、平时作业与实验30%

五、建议教材和教学参考书 参考教材：

1、《数据结构》（C语言描述）高等教育出版社 耿国华主编

2、《数据结构》（C语言版） 清华大学出版社 严蔚敏，吴伟民编者 3、《数据结构题集》（C语言版）清华大学出版社 严蔚敏，吴伟民编者 4、《数据结构》算法实现及解析（第二版） 西安电子科技大学出版社 高一凡 六、说明

1、因课时安排少，教学内容多。建议采用多媒体教学。

2、由于本课程内容较多，在实际教学中可根据大纲内容，进行适当调整。

6

本文来源：https://www.bwwdw.com/article/2o1t.html