《数据结构》教学大纲

1、数据结构课程教学大纲课程代码： 课程中文名称: 数据结构课程英文名称：Data Structures 课程类别：必修课程学分数：4课程学时数：54+18授课对象：计算机科学与技术、信息安全及相关专业本科本课程的前导课程：高级语言程序设计、离散数学本课程的后续课程：编译原理、操作系统一、教学介绍本课程是计算机科学与技术专业和信息安全专业的必修课。讲授数据结构基本原理， 软件设计中常用的各种数据结构如线性表、栈、队列、串、数组和稀疏矩阵、树和二叉树以及图的实现，查找和排序算法设计技术，解决基本的数据组织和数据处理问题，提高软件开发与高效算法设计能力，为后续专业课程学习和复杂算法设计分析打下基础。二

2、、教学目的掌握数据结构的基本原理，深刻理解数据逻辑结构、存储结构和运算算法设计之间的关系，能够从求解问题中提炼出数据模型并准确地采用抽象数据类型进行描述。掌握常用数据结构的实现过程，针对逻辑结构特点设计相应的存储结构，继而高效地设计数据结构基本运算算法，能够对算法进行时间和空间复杂度分析。掌握常用数据结构的特点及其应用，能够在综合性求解问题中选择合适数据结构并设计出高效算法，具备基本的数据组织和数据处理能力。程问题的能力。2三、课程内容与学时分配主要内容：绪论：数据结构相关概念、算法及算法分析。教学重点：数据结构的 3 个方面（逻辑结构，存储结构和运算）。算法的特性和算法时间与空间复杂度分析，

3、数据结构的目标。ADT 最坏和平均时间复杂度分析方法。STL vector list 容器的应用。教学重点：顺序表存储结构，线性表基本运算算法设计和顺序表应用算法设计。链式存储结构，线性表基本运算算法设计和链表应用算法设计。线性表两类存储结构的比较。教学难点：基于整体建表和二路归并的高效算法设计方法。STL queuedeque priority_queue 容器的应用。教学重点：栈和队列的存储结构及其基本运算算法设计，利用栈求简单表达式值和求解迷宫问题，利用队列求解迷宫问题的算法设计，用栈和队列求解迷宫问题的差别。教学难点：栈和队列的综合应用。STL 中的 string 的应用。BF KMP

4、 算法。教学难点：KMP 算法。矩阵的三元组表示、稀疏矩阵的十字链表表示。教学重点：特殊矩阵的压缩存储和稀疏矩阵的压缩存储。教学难点：稀疏矩阵的压缩存储。法到非递归算法的转换。教学重点：递归调用的实现原理，递归模型，基于递归数据结构的递归算法设计方法和基于归纳的递归算法设计方法。教学难点：递归算法设计方法。运算及其实现、二叉树的遍历、二叉树的构造、线索二叉树、哈夫曼树和并查集。教学重点：树和二叉树的性质，二叉树存储结构，二叉树遍历算法设计及其应用。教学难点：二叉树的递归算法设计方法。AOE 网与关键路径。Prim Kruskal 算法，3求最短路径的 Dijkstra 和 Floyd 算法。教

5、学难点：图遍历应用算法设计，求最小生成树的 Prim 和 Kruskal 算法，求最短路径的 Dijkstra 和 Floyd 算法。STL 中的 map和 unordered_map 等容器的应用。教学难点：折半查找算法设计及其分析，二叉排序树的插入、生成、查找和删除算法设计。哈希表查找的性能分析。各种内排序方法比较和外排序过程。教学重点：各种内排序算法设计，各种内排序方法的比较和选择。教学难点：希尔排序、快速排序、堆排序、二路归并排序和基数排序算法设计。课程内容与学时分配表：内容绪论课堂学时4实验学时线性表84栈与队列82串4数组和稀疏矩阵2递归4树和二叉树64图64查找62排序62小计5418