课程教学大纲

一、          课程说明

用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构与算法》要研究的内容。它不仅是计算机学科的核心课程，而且也是通信类专业的重要选修课程。随着软件在通信行业的作用不断提高，《数据结构与算法》在通信工程专业的教学中，也越来越占有重要的地位。本课程主要说明如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为后期其它计算机课程奠定基础。

二、          课程目标

本课程是计算机软件编程的基础课程，课程从基本的数据组织与管理角度介绍算法设计思路以及如何设计和评价性能更优的算法。本课程的目标：

目标1：了解数据结构及其分类、数据结构与算法的密切关系。（支撑毕业要求1.2）

目标2：熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 （支撑毕业要求2.1）

目标3：掌握设计算法的步骤和算法分析方法。（支撑毕业要求2.1）

目标4：掌握数据结构在排序和查找等常用算法中的应用。（支撑毕业要求1.2）

目标5：初步掌握文件组织方法和索引技术。（支撑毕业要求1.2）

三、          课程目标与毕业要求的对应关系

四、          教学内容与学时安排

第1章 数据结构概论（2课时，课程目标1）

1.1 数据结构的概念

1.2 数据结构的抽象形式

1.3 作为ADT的C++类

1.4 算法定义

1.5 算法性能分析与度量

教学要求：

1.   通过对数据结构举例，说明数据结构的分类说明数据结构的概念，并向学生说明数据结构课程的内容。

2.   说明数据抽象与抽象的数据类型

3.   说明面向对象的概念，说明C＋＋中的类、对象、输入输出、函数、继承等概念，说明动态存储分配和多态性的概念

4.   说明算法定义以及性能分析与度量的各种概念

第2章 线性表（2课时，课程目标2，课程目标3）

2.1 线性表

2.2 顺序表

2.3 单链表

2.4 线性链表的其他变形

2.5 单链表的应用

2.6 静态链表

教学要求：

1.   说明线性表的概念和定义。

2.   说明数序表、单链表以及其他变形表的概念、定义和操作方法，通过代码说明定义和操作的实现方法。

3.   说明单链表的各种应用

第3章 栈和队列（4课时，课程目标2，课程目标3）

3.1  栈

3.2  栈与递归

3.3  队列

3.4  优先级队列

3.5  双端队列

教学要求：

1.   说明顺序栈和链式栈的定义，说明二者的区别。

2.   说明递归的概念以及递归与栈的关系

3.   说明循环队列和链式队列的概念，通过举例队列的应用方法。

4.   说明优先级队列的概念以及表示和实现方法。

5.   说明双端队列的概念以及表示和实现方法。

第4章 数组、串与广义表（4课时，课程目标2，课程目标3）

4.1  多维数组的概念与存储

4.2  特殊矩阵

4.3  稀疏矩阵

4.4  字符串

4.5  广义表

教学要求：

1.   说明多维数组的概念和存储表示方法

2.   说明对称矩阵、三对角线/多对角线矩阵的压缩存储

3.   说明稀疏矩阵机器三元组数组表示方法、转置、相加和相乘算法，说明矩阵的正交链表表示

4.   说明字符串的概念、实现、自定义类、操作的实现、模式匹配和存储方法

5.   说明广义表的定义与性质、表示方法、存储结构的实现、递归算法。

第5章 树（4课时，课程目标2，课程目标3）

5.1  树的基本概念

5.2  二叉树

5.3  二叉树的存储表示

5.4  二叉树遍历及其应用

5.5  线索二叉树

5.6  树与森林

5.7  树与森林的变量及其应用

5.8  堆

5.9  Hufffman树及其应用

教学要求：

1.   说明树的基本概念：定义和术语、抽象数据类型

2.   说明二叉树的定义、性质和抽象数据类型

3.   说明二叉树的数组和链表的存储表示

4.   说明二叉树遍历的递归和非递归算法、应用以及计数方法

5.   说明线索的概念、终须线索二叉树的建立和遍历、插入和删除

6.   说明树的存储表示、森林与二叉树的转换、树与二叉树的转换

7.   说明树与森林的深度、广度有限遍历算法

8.   说明最小堆和最大堆的概念、堆的建立方法、堆的插入与删除算法

9.   说明路径长度的概念、Huffman树的概念

第6章 集合与字典（2课时，课程目标2，课程目标3）

6.1  集合及其表示

6.2  并查集与等价类

6.3  字典

6.4  跳表

6.5  散列

教学要求：

1.   说明集合的基本概念以及用位向量和有序链表实现集合抽象数据类型的方法

2.   说明并查集的定义机器实现，说明并查集的应用。

3.   说明字典的概念和字典的新兴表描述算法。

4.   说明跳表的概念，介绍跳表的类定义以及操作算法

5.   说明散列表和三列方法的概念，说明散列函数，说明处理冲突的闭散列方法以及开散列方法

6.   说明散列表的分析方法

第7章 搜索结果（4课时，课程目标4）

7.1  静态搜索结构

7.2  二叉搜索树

7.3  AVL树

7.4  伸展树

7.5  红黑树

教学要求：

1.   说明静态搜索表的概念，说明顺序搜索和基于有序顺序表的顺序搜索和折半搜索的的概念和算法

2.   说明二叉搜索树的概念，说明二叉搜索树的搜索、插入、删除以及性能分析方法，介绍最优二叉树搜索

3.   说明AVL树的概念，说明平衡话旋转的概念，说明AVL树的插入、删除和性能分析方法。

4.   说明伸展树的概念

5.   说明红黑树的概念和性质、说明红黑树的搜索的算法，介绍红黑树的插入、删除算法

第8章 图（8课时，课程目标2，课程目标3）

8.1图的基本概念

8.2图的存储结构

8.3图的遍历

8.4最小生成树

8.5最短路径

8.6用顶点表示活动的网络（AOV网络）

8.7用边表示活动网络（AOE网络）

教学要求：

1.   说明与图有关的若干概念，说明图的抽象数据类型

2.   说明图的邻接矩阵、邻接表、邻接多重表的表示方法

3.   说明深度有限、广度有限的搜索算法、说明连通分量的概念，介绍重连通分量

4.   说明Kruskal算法和Prim算法

5.   说明非负权值的单源最短路径，介绍任意权值的单源最短路径以及所有定点之间的最短路径。

6.   说明用顶点表示活动的网络（AOV网络）的概念

7.   说明用边表示活动的网络（AOE网络）的概念

第9章 排序（4课时，课程目标4）

9.1排序的概念及其算法性能分析

9.2 插入排序

9.3快速排序

9.4选择排序

9.5 归并排序

9.6基于链表的排序算法

9.7分配排序

9.8内部排序算法的分析

教学要求：

1.   说明排序的概念和排序算法的性能评估、说明排序表的类定义

2.   说明直接插入、折半插入和希尔排序算法

3.   说明快速排序的过程、性能分析。介绍改进算法和三路划分的快速排序算法。

4.   说明直接选择排序和堆排序，介绍锦标赛排序

5.   说明归并的概念以及其排序算法

6.   介绍基于链表的插入排序、归并排序以及排序结果的重排

7.   介绍桶式排序、基数排序和LSD基数排序算法，介绍MSD基数排序

8.   说明排序方法的下界问题，对各种内部排序方法进行比较

第10章 文件、外部排序与搜索（2课时，课程目标5）

10.1 主存储器和外存储器

10.2 文件组织

10.3外排序

10.4多级索引结构

教学要求：

1.   说明磁带、磁盘存储器、缓冲区与缓冲池的基本概念和原理

2.   说明文件的概念和存储结构

3.   说明外排序的基本过程、说明k路平衡归并与败者树，介绍初始归并段的生成、并行操作的缓冲区处理以及最佳归并树。

4.   说明静态ISAM方法、动态的m路搜索树、B树以及B树的插入、删除算法。介绍B＋树和VSAM的概念

实验课程：（36课时）

实验一 数据类型的定义（2课时）

实验二 用双向链表实现约瑟夫问题（4课时）

实验三 堆栈实验（6课时）

实验四 队列实验（6课时）

实验五 树的应用（6课时）

实验六 图的应用（6课时

实验七 排序算法（6课时）

第1章 数据结构概论（2课时）

第2章 线性表（2课时）

第3章 栈和队列（4课时）

第4章 数组、串与广义表（4课时）

第5章 树（4课时）

第6章 集合与字典（2课时）

第7章 搜索结果（4课时）

第8章 图（8课时3）

第9章 排序（4课时）

第10章 文件、外部排序与搜索（2课时）

实验一 数据类型的定义（2课时）

实验二 用双向链表实现约瑟夫问题（4课时）

实验三 堆栈实验（6课时）

实验四 队列实验（6课时）

实验五 树的应用（6课时）

实验六 图的应用（6课时

实验七 排序算法（6课时）

五、          教学方法：

1.   部分章节利用课堂讲授、课堂讨论方式教学；

2.   部分章节利用课题设计为导向，引导学生自主学习+讲授+程序设计方式教学；

3.   部分重点章节利用教学、实验混合方式教学，使得理论与实践紧密结合；

4.   重点知识点以在作品设计中予以实现方式教学，强调综合设计能力和动手实践能力；

六、          考核方式

1. 课程考核方式

2. 课程目标与考核方式对应关系

七、          推荐教材和教学参考书目与文献

教材：

1.   教材：殷人昆主编：《数据结构(用面向对象方法与c++语言描述)第二版》，清华大学出版社，2012年2版 ISBN：9787302148111 普通高等教育“十一五”国家级规划教材

。

参考书目：

1、科尔曼著，殷建平译：《算法导论》，机械工业出版社，2013年版

2、巴尔加瓦著：《算法图解》，人民邮电出版社，2017年版

3、乔兹德克(Drozdek, A.)主编：《C++数据结构与算法》，清华大学出版社，2014年版

4、熊岳山主编：《数据结构与算法》，清华大学出版社，2013年版

八、          评分标准【请按照本门课程采用的课程考核方式选择下表之一填写】

表1：