《数据结构》课程教学大纲 Data Structure

- 1 - 数据结构课程教学大纲 课程名称：数据结构/Data Structure 课程代码：02130108 课程类型：基础/必修 总学时数：64（理论学时：48 实验学时：16 ） 学 分：4（3/1） 先修课程：程序设计基础、离散数学 开课单位：信息与电子工程学院 适用专业：计算机科学与技术 一、课程的性质、目的和任务 《数据结构》是计算机科学与技术专业学生必修的专业基础课程之一。通过本课程学习，使学 生系统地掌握最常用的几种数据结构，包括：线性表、堆栈和队列、串、数组和广义表、树、图。 掌握它们的逻辑结构和存储结构，以及在不同存储结构下的一系列算法（操作），并对算法的效率进 行简要的分析。 二、教学内容、教学基本要求及教学重点与难点 1．绪论 掌握数据结构的基本概念和术语；了解数据结构发展概况及其与其它课程的关系；掌握算 法的特性，算法的描述和算法的分析。 教学重点：算法分析 教学难点：算法分析 2．线性表 掌握线性表的逻辑结构，掌握线性表的顺序存贮结构和链式存贮结构，掌握线性表的基本 操作，学会线性表的应用。 教学重点：线性表的顺序存储和链式存储下的算法 教学难点：链表的操作 3．栈和队列 掌握栈的定义及其操作，掌握栈的存贮结构，理解顺序栈和链栈，掌握用栈实现表达式的 求值，递归过程及其实现；掌握队列的定义及其基本操作；掌握队列的链式存贮结构和顺序存 贮结构。使学生掌握堆栈和队列在函数调用、递归和求解迷宫最近路径等的实际用途。 教学重点：堆栈、队列的应用 教学难点：堆栈在递归中的应用 4．串

- 2 - 掌握串的逻辑定义及其基本操作，掌握串的存贮结构及其基本操作的实现；掌握串的模式 匹配；了解串的应用示例。 教学重点：串的顺序存储、串的模式匹配 教学难点：串的模式匹配 5．数组和广义表 掌握数组的定义和运算，掌握数组的顺序存贮结构，理解稀疏矩阵的三元组表和十字链表 表示，理解矩阵的压缩存贮；理解广义表的定义和存贮结构。 教学重点：数组的顺序存储 教学难点：稀疏矩阵的十字链表 6．树和二叉树 理解树的定义、结构和基本操作，掌握二叉树的定义及其基本操作，掌握二叉树的性质和 存贮结构；掌握二叉树的遍历和线索二叉树；掌握树的存贮结构，理解森林与二叉树的相互转 换；理解树的遍历；掌握哈夫曼树及其应用。 教学重点：二叉树的性质、遍历，哈夫曼树及应用 教学难点：线索二叉树，哈夫曼树及应用 7．图 掌握图的定义和一些重要术语；理解图的存贮结构；掌握图的遍历；理解生成树；掌握无 向网的最小生成树及其应用；掌握有向网的最短路径及其求法，理解有向图的拓扑排序和关键 路径及其应用。 教学重点：图的遍历，最小生成树，最短路径，关键路径。 教学难点：最小生成树，最短路径，关键路径。 8．查找 掌握静态查找表的顺序查找和有序表二分查找及它们的平均查找长度；掌握二叉排序树和 平衡二叉树，理解 B-树，B+树，掌握哈希表的查找和平均查找长度的计算。 教学重点：二分查找，二叉排序树的查找，哈希表的查找，平均查找长度的计算。 教学难点：二叉排序树、哈希表的查找，平均查找长度的计算 9．内部排序 了解排序的分类，排序的稳定性概念；掌握插入排序、快速排序、选择排序、堆排序、归 并排序；理解基数排序；了解各种内部排序方法的使用场合和特性。 教学重点：希尔排序、快速排序、堆排序。 教学难点：希尔排序、堆排序。 10．文件 掌握文件的基本概念；了解顺序文件、索引文件、直接存取文件、多关键字文件。 教学重点：文件的存取

- 3 - 三、课内实验教学安排及要求 序 号 教学内容 教学基本要求 实验 类别 课内 学时 课外 学时 备注 1 线性表的基本操作（一 元多项式的加减法） 掌握线性表的链式存储，掌握对链表的一 些基本操作和具体的函数定义 设计性 3 6 必做 2 哈夫曼编码与解码算法 设计 掌握二叉树的顺序存储结构和具体实现， 掌握哈夫曼编码和译码算法，及其在顺序 存储结构下的实现 设计性 3 6 必做 3 最小生成树算法设计 掌握图的邻接矩阵、邻接表的存储方式， 掌握图的建立算法，掌握图的最小生成树 Prim 算法 设计性 4 8 必做 4 最短路径算法设计 掌握图的邻接矩阵、邻接表的存储方式， 掌握图的建立算法，掌握图的最短路径 Dijkstra 算法 设计性 4 8 必做 5 快速排序算法设计 掌握快速排序的思想，及在顺序存储结构 下的实现 设计性 2 4 必做 小计 16 32 四、学时分配表 序号 课程内容 课内学时 课 外 学 时 讲课 学时 课内 研讨 学时 实验 学时 实践 学时 上机 小 计 1 绪论 1 1 2 6 2 线性表 6 2 3 11 24 3 栈和队列 1 2 3 6 4 串 3 3 6 5 数组和广义表 3 1 4 6 6 树和二叉树 6 2 3 11 22 7 图 6 2 8 16 34 8 查找 2 2 4 10 9 内部排序 3 1 2 6 12 10 文件 4 4 4 合计 35 13 16 64 130 五、课外学习要求

- 4 - 本课程要求有较好的 C 语言基础，要求学生课前预习，课后复习，要求课后把课程中的一些算 法在计算机上实践一下，加深对算法的理解。 作业在每次课后布置，每次约 3-4 题，有些做在作业本上，有些要求课后上机实践。 本课程有网络课程，课外可以看看课程相关内容，课件，测试，作业，还有一些题目也可做做。 实验前要有足够时间的准备，课内实验 16 学时，课外准备至少需要 32 学时。 六、教学方法 主要研讨教学主题 ： 1、哈弗曼算法在压缩技术中的应用。 2、最小生成树算法求解一个最小成本的连通网络 3、最短路径算法求解网路和交通中的最短路径 七、课程考核要求及方法 1．考核方式：考试（√）；考查（） 2．成绩评定： 计分制：百分制（√）；五级分制（）；两级分制（） 总评成绩构成：平时考核（40）％；期末考核（60）％ 平时考核包括： 考勤考纪、作业、课堂讨论、研讨报告等 20%； 实验 20% 八、建议教材及参考资料 建议教材： 严蔚敏，吴伟民主编，《数据结构》（C 语言版），清华大学出版社，2014 年版 参考资料： 1．严蔚敏 数据结构（C 语言版）清华大学出版社，2014 年版 2．秦玉平，马靖善主编，《数据结构》(C 语言版)， 清华大学出版社，2005 年版 3．Mark Allen Weiss 主编，《数据结构与算法分析》(C 语言描述)， 机械工业出版社 2004 年版 4．Robert L.Kruse, Clovis L.Tondo 主编，《Data Structures & Program Design In C》, Second Edition, 清华大学出版社，2001 年版 执笔人：金国英 审核人： 审批人：