《数据结构》教学大纲
课程名称：
| 数据结构
|
|
|
课程编号：
| 408009
| 420009
| 436009
|
适用专业：
| 计算机科学与技术
| 网络工程
| 软件工程
|
课程类别：
| 专业必修课
| 专业必修课
| 专业必修课
|
课程学分：
| 4
|
|
|
总 学 时：
| 72
|
|
|
其中：理论学时
| 42
|
|
|
实验学时
| 30
|
|
|
先修课程：
| 数据结构、汇编程序设计、微机原理、操作系统原理、高等代数
|
一、课程的性质、目的与任务
《数据结构》课程是计算机科学与技术专业的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。设立本门课程的目的是通过学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。
二、课程教学基本内容与要求
第一章、绪论
（一）基本教学内容：
1.1 什么是数据结构
1.2 基本概念与术语
1.3 抽象数据类型的表示与实现
1.4 算法与算法分析
（二）基本要求
教学目的：掌握数据结构的基本概念，了解抽象数据类型，了解算法时间复杂度和空间复杂度的分析，了解算法的描述方法。
重点：据结构的基本概念、算法描述、算法分析
难点：算法描述、算法分析
第二章、线性表
（一）基本教学内容：
2.1 线性表的类型定义
2.2 线性表的顺序表示与实现
2.3 线性表的链式表示与实现
（二）基本要求
教学目的：理解线性表的定义及其运算；理解顺序表和链表的定义、组织形式、结构特征和类型说明；掌握在顺序表和链表上实现的插入、删除和按值查找的算法；了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。
重点：线性表的定义及其运算、组织形式、结构特征和类型说明、顺序表和链表上实现的插入、删除和按值查找的算法、循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作
难点：线性表的链式表示与实现相关算法、循环链表、双(循环)链表的插入、删除等操作
第三章、栈和队列
（一）基本教学内容：
3.1 栈
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列
（二）基本要求
教学目的：理解栈的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现；理解队列的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。
重点：栈的存储结构、队列的存储结构、栈与队列的应用
难点：队列的存储结构、栈与队列的应用
第四章、串
（一）基本教学内容：
4.1 串类型的定义
4.2 串的表示与实现
4.3 串的模式匹配算法
4.4 串的操作应用举例
（二）基本要求
教学目的：了解串的逻辑定义；掌握用顺序存储串及堆存储串时的特点及在这两种存储方式下基本操作的实现；了解改进的模式匹配算法；
重点：串的存储结构、串的模式匹配
难点：串的存储结构、串的模式匹配
第五章、数组和广义表
（一）基本教学内容：
5.1 数组的定义
5.2 数组的顺序表示与实现
5.3 矩阵的压缩存储
5.4 广义表的定义
（二）基本要求
教学目的：掌握数组的顺序存储结构及特殊矩阵的存储方式；了解稀疏矩阵的压缩存储方式—三元组表。
重点：数组的顺序存储结构、.特殊矩阵的压缩存储方法
难点：.特殊矩阵的压缩存储方法
第六章、树和二叉树
（一）基本教学内容：
6.1 树的定义和基本术语
6.2 二叉树
6.3 遍历二叉树和线索二叉树
6.4 树和森林
6.6赫夫曼树及应用
（二）基本要求
教学目的：深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；理解并掌握二叉树的三种遍历算法；掌握二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题。
重点：二叉树的定义，性质，基本运算和存储结构、二叉树的遍历和线索二叉树、Huffman树及应用
难点：二叉树的遍历和线索二叉树、Huffman树及应用
第七章、图
（一）基本教学内容：
7.1 图的定义和术语
7.2 图的存储结构
7.3 图的遍历
7.4 图的连通性
7.5有向无环图及其应用
7.6最短路径
（二）基本要求
教学目的：理解图的基本概念及术语；掌握图的两种存储结构(邻接矩阵和邻接表)方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；领会拓扑排序、关键路径、最短路径的算法思想。
重点：图的存储结构、图的遍历、图的连通性问题
难点：有向无环图及其应用
第九章、查找
（一）基本教学内容：
9.1 静态查找表
9.2 动态查表
9.3 哈希表
（二）基本要求
教学目的：了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度；理解并掌握二叉排序树的各种算法；
重点：.动态查找表、哈希表
难点：动态查找表、哈希表
十、内部排序
（一）基本教学内容：
10.1 概述
10.2 插入排序
10.3 快速排序
10.4 选择排序
10.5 归并排序
10.6 基数排序
10.7 各种内部排序方法的比较讨论
（二）基本要求
教学目的：领会排序的基本思想和基本概念；理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤和时空效率分析；
三、课程各章节学时分配
序号
| 内容
| 理论学时
| 实验学时
|
计科
| 网工
| 软工
| 计科
| 网工
| 软工
|
1
| 绪论
| 2
| 2
| 2
| 0
| 0
| 0
|
2
| 线性表
| 8
| 8
| 8
| 4
| 4
| 4
|
3
| 栈与队列
| 6
| 6
| 6
| 4
| 4
| 4
|
4
| 串
| 2
| 2
| 2
| 2
| 2
| 2
|
5
| 数组与广义表
| 4
| 4
| 4
| 2
| 2
| 2
|
6
| 树与二叉树
| 8
| 8
| 8
| 6
| 6
| 6
|
7
| 图
| 6
| 6
| 6
| 6
| 6
| 6
|
9
| 查找
| 3
| 3
| 3
| 3
| 3
| 3
|
10
| 内排序
| 3
| 3
| 3
| 3
| 3
| 3
|
合计
| 42
| 42
| 42
| 30
| 30
| 30
|
四、本课程课外学习与修学指导
本课程强调理论和实践的结合，突出对学生的动手能力的培养。在对学生进行基本数据结构的技术、理论、设计等各种技能培养的同时，培养学生将实际问题转化为基本数据结构的问题的分析能力，鼓励学生学以致用，将学到的知识用以解决实际问题，从而提高学生算法设计能力和软件开发能力。
由于该课程涉及数据的各种组织方法，内容复杂，难度较大，且具有很强的实践性，所以要学好本课程，必须做到理论与实践紧密结合，才能达到较好的学习效果。要求学生多参阅相关书籍，多做练习，多上机实验，掌握算法的基本原理及其实现过程。
五、本课程考核方式及成绩评定标准
考核方式：闭卷考试
成绩评定方法：本课程的考核是平时成绩、上机考试和期终考试成绩相结合。具体比例为：平时（出勤、作业）20%，上机考试占20%，期末考试成绩占60%。
其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：选择题、填空题、简单算法应用题、算法填空题、算法设计等。
六、教学参考书
[1]严蔚敏,吴伟民.数据结构（C语言版）.北京：清华大学出版社.2006,4
[2]Sartaj Sahni. Data Structure, Algorithms, and Application in C++. The McGraw-Hill Company Inc.2006(数据结构、算法与应用——C++语言描述.北京:机械工业出版社.2006)
[3]Willan Ford,Willian Topp. Data Structures with C++. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996(数据结构——C++语言描述.北京:清华大学出版社，1997)
[4]徐孝凯.数据结构实用教程（C/C++描述）.北京:清华大学出版社.2010,12
[5]陈慧南.数据结构（使用C++语言描述）.南京:东南大学出版社.2010,1
[6]殷人昆,陶永雷,谢若阳等.数据结构（用面向对象方法与C++描述）.北京:清华大学出版社.2002,7
大纲撰写人：朱素英
大纲审阅人：罗如为
教学副主任：易叶青
编写日期：2012.6
