数据结构与算法142 48283数据结构与算法教学大纲 邓庆山

1、数据结构与算法（软件）课程教学大纲、课程总述本课程大纲以2014年软件工程本科专业人才培养方案为依据编制课程名称数据结构与算法（软件）课程代码48283课程性质专业必修先修课程C语言 （或者C+ ）程序设计，离散数学总学时数48周学时数6开课院系软件与通信工程学院任课教师邓庆山严军勇编写人邓庆山编写时间2015.1课程负责人邓庆山大纲主审人尹爱华使用教材教材：数据结构（C语言版）严蔚敏编，人民邮电出版社，2012教学参考资 料数据结构（C语言版）严蔚敏编，清华大学出版社1997数据结构习题集（C语言版），严蔚敏，清华大学出版社 数据结构，许卓群等，北京：高等教育出版社 数据结构（使用 C语言）

2、，蔡明志著，北京：科学出版社课程教学目 的数据结构是计算机科学的核心基础课程之一。数据是计算机处理的对 象，本门课程研究的数据是非数值性、结构性的数据。学习本门课程要求掌握 各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法实际， 对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握。通 过本门课程的学习，使学生透彻地理解各种数据对象的特点，学会数据的组织 方法和实现方法，并进一步培养基本的良好的程序设计能力。课程教学要 求对“数据结构”这门课程，要求学生掌握以下几个方面的问题：（1）线性表、树、图的基本结构。（2）线性表、树、图的基本算法。（3）对算法时间复杂度、空间

3、复杂度的计算。（4）查找、排序的主要算法及比较。（5）线性表、树、图的应用算法。（6）了解若干算法在计算机领域中的应用实例。其中（1）-（4）为基本要求，必须牢固掌握。（5）为较高层次要求，能加深学生对数据结构基本概念、基本算法的理解。（6）为知识性要求，为开拓学生思路，加强与其他课程间的联系而设。本课程的重 点和难点重点：（1） 顺序表和单链表的描述和插入、删除运算以及算法的效率分析，栈和队列的运算及循环队列；（2） 二叉树的性质及遍历算法，线索二叉树的运算，树、 森林与二叉树之 间的转换，Huffman树的构造算法及 Huffman编码、译码；（3） 图的邻接矩阵和邻接表存储结构，图的深度

4、优先和广度优先遍历，最小生成树、拓扑排序、关键路径和最短路径的求解；（4 ）顺序查找、折半查找算法及平均查找长度；（5）插入、交换、选择等基本排序方法和改进的排序方法，归并排序算法 及基数排序算法；难点：（1） 单链表的插入、删除运算和链表的应用，栈与递归的关系，栈与队列 的应用，串的改进模式匹配算法，稀疏矩阵的压缩存储及运算；（2）二叉树的遍历算法，尤其是非递归遍历算法，线索二叉树的运算；（3） 折半查找算法及平均查找长度、二叉查找树的构造、哈希表的冲突处 理；（4）快速排序算法、堆排序算法和归并排序算法；（5）求取小生成树、拓扑排序、关键路径和取短路径算法。课程考试书面考试与上机考试结合（

5、1） 平时成绩：20%。其中：考勤10%+课堂表现10% （课堂表现是指 学生回答问题、参与讨论交流、提问情况等等）。（2）项目完成：30%。项目报告+答辩，以学生互评形式。（3）期中测试：20%。笔试开卷。（4）期末考试：30%。笔试开卷。、教学时数分配早目教学内容教学时数分配课堂讲授实验（上机）11.绪论342.线性表633.栈和队列644.串055.数组和广义表066.树977.图98&查找399.排序610期中测试311项目答辩3合计48三、单元教学目的、教学重难点和内容设置第一章 绪论【教学目的】 通过这一章的学习，便学生全面了解数据结构的定义和研究的方向以及这门课程的知识体系，从而

6、为后面章节的学习打下基础。另外，对一个算法好坏的度量，时间 复杂度是一个重要的指标，通过这一章的学习，以便学生对算法的时间复杂度和空间 复杂度有所了解。【重点难点】 数据结构的定义以及时间复杂度的分析【教学内容】1.1 什么是数据结构1.2 基本概念、术语1.3 抽象数据类型的表示与实现1.4 算法和算法分析1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间的需求【课时要求】3节第二章 线性表【教学目的】 通过本章的学习，应使学生掌握对线性数据结构的存储和处理以及应用。【重点难点】线性表的存储结构 - 顺序表和链表以及在存储结构下的线性数据处理。 【

7、教学内容】2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线形链表2.3.2循环链表2.3.3双向链表课时要求】6节第三章 栈和队列【教学目的】 通过本章的学习，应使学生掌握对栈和队列这两种特殊的线性表的存储和处理以及应用。【重点难点】本章重点和难点： 栈和队列线性表的存储结构- 顺序表和链表以及他们和线形表相比的特殊性。【教学内容】3.1 栈3.1.1 抽象数据类型栈的定义3.1.2 栈的表示和实现3.2 栈的应用举例3.2.1 数字转换3.2.2 括号匹配的检验3.2.3 行编辑程序3.3 栈与递归的实现3.4 队列3.4.1 抽象数据类型队列的定义

8、3.4.2 链队列 队列的链式表示和实现3.4.3 循环队列 队列的顺序表示和实现【课时要求】 6节第四章 串【教学目的】 本章以学生自学为主， 串这一数据结构的特殊存储和处理方法， 以及串的模式匹配 算法。【重点难点】 重点是重载方法和参数的传递；难点是递归的实现。【教学内容】4.1 串类型的定义4.2 串的表示和实现4.2.1 定长顺序存储表示4.2.2 堆分配存储表示4.2.3 串的块链存储表示4.3 串的模式匹配算法4.3.1 串的模式匹配的一般算法4.3.2 串的模式匹配的一种改进算法【课时要求】 0节第五章 数组和广义表【教学目的】 本章以学生自学为主， 通过本章的学习， 应使学生

9、掌握对数组和广义表的存储和处理。【重点难点】 数组和广义表的存储结构及其实现。【教学内容】5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构【课时要求】0节第六章 树和二叉树【教学目的】通过本章的学习， 应使学生掌握对树这一特殊数据结构的存储和处理， 特别是二叉树的 各方面的知识，能理解二叉树、树和森林之间的转换关系，以及树的各种应用。【重点难点】 树这一数据结构的特殊存储和处理方法，特别是二叉树的特征、遍历和线索，以 及树与森林的关系。【教学内容】6.1树的定义和基本术语6.2二叉树6.2.1二叉数的定义6.2.2二叉数的性质6.

10、2.3二叉数的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉数6.4树和森林6.4.1树的存储结构6.4.2森林和二叉数的转换6.4.3树和森林的遍历6.6哈夫曼树及其应用6.6.1最优二叉树（哈夫曼树）6.6.2哈夫曼编码课时要求】9节第七章 图 【教学目的】 考虑到信息专业和计算机专业的不同， 本章以学生自学为主， 通过本章的学习， 应使学 生简单了解图的一些基本概念和简单运用。【重点难点】 图这一数据结构的特殊存储和处理方法及其应用。【教学内容】7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径课时要求】9节第八章 查找【教学目的】 通过本章的学习， 应使学生对各种查找方法有较为清楚的理解， 能够对各种查找算法效率进行分析。【重点难点】 查找表这一数据结构上的各种查找方法的含义、特点以及它们的的算法效率的分析。【教学内容】8.1静态查找表8.1.1顺序表的查找8.1.2有序表的查找8.1.3静态树表的查找8.1.4索引顺序表的查找8.3哈希表8.3.1什么是哈希表8.3.2哈希函数的构造方法8.3.3处理冲突的方法课时要求】3节第九章 内部排序【教学目的】 通过本章的学习， 应使学生对各种排序方法有较为清楚的理解， 能够对各种排序算法效 率进行分析，培养学生较高的编程能力。【重点