数据结构教学大纲

中文课程名称：数据结构

英文课程名称：Data Structures

适用专业：信息管理与信息系统

                           制定单位：商学院

                             执笔人：

                             审核人：

                         单位负责人：

                           制定时间：2017-2-10

XX师范学院教务处

二〇一七年一月

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

一、课程基本信息

（一）课程代码及课程名称

1.课程代码：06151090

2.课程名称（中/英文）：数据结构/Data Structures 

（二）课程类别及课程性质

专业教育必修课程

（三）学时及学分： 

总学时数：；总学分数：3。

其中，讲授学时：32 ，实践（实验）学时：32。

（四）适用专业及开设学期

适用专业：信息管理与信息系统（本科）

开设学期：第二学期

（五）先修课程与后续课程

先修课程：大学计算机基础、高等数学、C语言程序设计

后续课程：数据库原理与应用、管理信息系统分析与设计、管理信息系统、Java程序设计(高级)

二、课程简介

“数据结构”是信息管理与信息系统专业一门重点专业基础课程，也是学科专业核心专业基础课程之一，属于专业学位必修课程。本课程的教学任务是针对大量的信息处理对象，介绍对象信息与数据表示的各种抽象的、基本的逻辑结构及其上的基本运算操作。通过研究各种基本数据结构内在的逻辑关系和它们在计算机中的存储表示方式，初步建立数据结构上基本运算操作的正确性概念，同时，结合各种典型问题讨论其上的各种基本运算操作及其基本算法，讲授各种数据结构的特点、适用范围，以及对一些基本算法效率的定性和定量分析方法，为后续课程提供必要的数据结构基础。此外，配合实验课程的教学中，学生应理论联系实际，理论指导实践，通过规范地完成一系列数据结构实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。

三、教学目的与基本要求

（一）该课程教学目的与专业培养要求对应关系矩阵

  培养要求

（二）教学目的

《数据结构A》在计算机科学中是一门综合性的专业基础课，不仅是一般程序设计的基础，而且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基础。本课程讨论各种数据组织中的数据的逻辑结构、存储结构以及有关操作的算法。目的是使学生学会分析研究计算机所要加工处理的数据的特征，掌握组织数据、存储数据和处理数据的基本方法，并加强在实际应用中选择合适的数据结构和设计相应算法的训练，课程的具体教学目的如下：

数据结构与算法是计算机科学教育中的一门核心课程。数据结构与算法主要讨论在应用计算机解决问题时，如何有效地组织数据、表示数据和处理数据， 以及如何设计正确的算法和评价算法的效率。课程介绍常见的数据结构及其应用，常用的数据处理技术和算法，以及算法效率估算的基本技术。通过本课程的学习， 学生应该掌握常用的数据结构，掌握合理地组织数据结构和表示数据的方法，掌握有效地处理数据的方法，掌握评价算法性能的基本方法。通过本课程的训练，进一步提高学生的数据抽象能力；提高学生设计高质量程序的能力。本课程也为学生学习操作系统、编译原理和数据库等后续课程奠定基础。

1. 知识方面

 1.1理解数据结构的一些基本概念、理解并掌握算法的描述方法，理解并掌握算法的时间复杂度和空间复杂度的概念以及分析方法。

1.2理解各种数据结构的基本概念，深刻理解各种数据结构的逻辑特性，理解并熟练掌握各种数据结构的存储表示方法，理解并掌握在各种数据结构基础上的算法设计与描述，并理解和掌握对算法性能进行分析的方法以及分析结果。

1.3理解查找、排序的基本概念，掌握各种查找、排序方法及其算法描述和性能分析方法和分析结果。

2. 能力与素质方面

2.1 具备依据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力。

2.2 具备为解决工程实际问题进行算法设计与分析的能力。

2.3 具备将算法通过具体的编程语言加以实现的能力。

（三）教学要求：

通过本课程的学习，在基础方面，要求学生能够掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。

1.掌握数据结构的概念及术语。

2.掌握线性表（栈、队列）的存储结构（顺序和链式存储）、算法描述及应用。

3.掌握数组的顺序存储和特殊矩阵的压缩存储。

4.掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。

5.掌握图的基本概念和术语、存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。   

6.掌握查找的基本概念、基于线性表的查找方法（顺序、折半）。

7.掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。

四、教学内容

（一） 绪论（共4学时）

（一）教学目的和要求

介绍数据结构课程的研究对象，基本术语，掌握算法的要领，描述算法的类语言。了解数据结构的发展概况及其在计算机中的地位。

（二）教学重点与难点

教学重点：

1、熟悉各名词、术语的含义，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质；

2、了解抽象数据类型的定义、表示和实现方法；

3、理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）；

4、掌握计算语句频度和估算算法时间复杂度的方法。

教学难点：

1、掌握数据结构的意义及数据结构的基本内容；

2、掌握数据结构及数据、数据元素等相关概念；

3、掌握算法描述的方法；

4、算法时间复杂度的计算。

（三）教学内容

1、什么是数据结构 

2、基本概念和术语 

3、抽象数据类型的表示与实现 

4、算法和算法分析

（二） 线性表（共8学时）

（一）教学目的和要求

掌握线性表的逻辑结构、顺序存储结构和链式存储结构。掌握在线性表上实现基本运算的算法。

（二）教学重点与难点

教学重点：

1、线性表的定义及逻辑上的特点；

2、顺序表上插入、删除和定位运算的实现；

3、单链表的结构特点及类型说明；

4、头指针和头结点的作用及区别；指针操作；

5、定位、删除、插入运算在单链表上的实现；

6、循环链表、双链表的结构特点；及其删除与插入运算的实现。

教学难点：

1、线性表与线性结构的联系与区别；

2、线性表的顺序存储结构及其运算； 

3、头结点在链表中的作用和指针的操作；

4、单链表存储结构定义，删除、插入运算中的指针操作顺序；

5、单链表的基本运算的实现；

6、循环链表、双链表上指针的操作顺序及其相关运算。

（三）教学内容

1、线性表的类型定义 

2、线性表的顺序表示和实现 

3、线性表的链式表示和实现 

4、一元多项式的表示及相加  

（三） 栈和队列（共8学时）

（一）教学目的和要求

掌握栈和队列的逻辑结构定义，掌握在两种存储结构上如何实现栈和队列的基本运算，掌握栈在程序设计中的应用。

（二）教学重点与难点

教学重点：

1、栈的定义及逻辑特点；栈上的基本运算；

2、栈的顺序存储结构及运算实现；链式存储结构；

3、入栈、出栈等运算在链栈上的实现；

4、队列的定义及逻辑特点；队列上的基本运算；

5、队列的顺序存储结构及其上的运算实现；

6、队列的链式存储结构；

7、入队、出队等运算在链队列上的实现。

教学难点：

1、顺序栈基本运算的实现；

2、顺序栈的溢出判断条件； 

3、栈的应用；

4、循环队列的队空、队满判断条件；循环队列上的插入、删除操作。

（三）教学内容

1、栈的类型定义

2、栈的应用举例

3、栈与递归的实现

4、队列的类型定义 

（四） 串和数组（共8学时）

（一）教学目的和要求

掌握字符串的存储结构，以及字符串的操作算法，掌握数组的顺序存储和特殊矩阵的压缩存储。

（二）教学重点与难点

教学重点：

1、熟悉串的定义及串的基本操作；

2、串的两种存储方式；

3、字符串的运算；

4、串的模式匹配算法。

5、组的逻辑结构，两种顺序存储方式；

6、计算给定元素在存储区中的地址；

7、对称矩阵、三角矩阵的压缩存储方式；

8、计算给定元素在存储区中的地址；

9、稀疏矩阵的三元组表表示方法；

教学难点：

1、串的基本运算的综合应用；

2、串的模式匹配算法。

3、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；

4、稀疏矩阵的压缩存储表示下的运算的实现；

5、了解稀疏矩阵的三类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；

（三）教学内容

1、栈的类型定义

2、栈的应用举例

3、栈与递归的实现

4、队列的类型定义

5、数组的定义

6、数组的顺序表示和实现

7、矩阵的压缩存储

（五） 树和二叉树（共12学时）

（一）教学目的和要求

    掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。

（二）教学重点与难点

教学重点：

1、二叉树的定义、性质、逻辑特点及五种基本形态、基本运算； 

2、二叉树的链式存储结构、顺序存储结构及其类型说明； 

3、二叉树链式存储结构的组织方式； 

4、二叉树的三种遍历方法及其算法，以遍历为基础在二叉树上实现的几种运算； 

5、哈夫曼树和哈夫曼算法；森林与二叉树的转换。

教学难点：

1、二叉树的递归定义；

2、二叉树链式存储结构的组织方式；

3、三种遍历的主要区别；二叉树上的复杂运算

4、森林与二叉树的转换；

5、哈夫曼算法及其应用。

（三）教学内容

1、树的定义和基本术语

2、二叉树

3、遍历二叉树和线索二叉树

4、树和森林

5、回溯法与树的遍历

6、赫夫曼树及其应用

（六） 图（共8学时）

（一）教学目的和要求

    掌握图的基本概念和术语、存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。理解拓扑排序及关键路径和最短路径的应用及意义。

（二）教学重点与难点

教学重点：

1、理解图的定义、术语及其含义，各种图的邻接矩阵表示法及其类型说明；

2、理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；

3、领会生成树和最小生成树的概念；

4、掌握由Prim算法思想构造最小生成树按Prim算法思想；

5、掌握拓扑序列和拓扑排序的概念，拓扑排序、关键路径、最短路径的算法思想。

教学难点：

1、正确理解与区别图的常用术语；

2、区别图的两种存储结构的不同点及其应用场合；

3、关键路径的算法思想；最短路径的算法思想。

（三）教学内容

1、图的定义和术语

2、图的存储结构

3、图的遍历

4、图的连通性问题

5、有向无环图及其应用

6、最短路径

（七） 查找（共8学时）

（一）教学目的和要求

   掌握查找的基本概念、基于线性表的查找方法（顺序、折半）。理解基于树的查找方法（二叉排序树、平衡二排序叉树）。

（二）教学重点与难点

教学重点：

1、查找表的基本概念及查找原理；顺序存储结构、顺序表及其类型说明；

2、查找运算在查找表和有序表上的实现；

3、二叉排序树的定义、性质及各结点间的键值关系，查找算法和基本思想；

4、平衡二叉排序树的概念；B-树和B+树的概念；

5、散列表及散列存储和散列查找的基本思想；各种散列表的组织、解决冲突的方法；

教学难点：

1、理解查找表的逻辑结构是集合，它的运算以查找为核心；

2、二叉排序树上的插入算法；平衡二叉树的旋转平衡算法；

3、散列表上的有关算法。

（三）教学内容

1、静态查找表

2、动态查找表

3、哈希表

（八） 排序（共8学时）

（一）教学目的和要求

    掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。理解选择类排序、归并类排序和基数类排序。

（二）教学重点与难点

教学重点：

1、排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别；

2、插入排序、冒泡排序、快速排序、直接选择排序、堆排序的基本思想、基本步骤和算法；

3、归并排序的思想；两个有序文件合并的方法和算法；

4、二路归并排序的算法和时空性能；

教学难点：

1、快速排序算法；

2、堆排序方法。

（三）教学内容

1、插入排序

2、快速排序

3、选择排序

4、归并排序

5、基数排序

6、各种内部排序方法的比较讨论

五、教学时数分配

《数据结构》课程教学时数分配表

总学时：      学分：3 

《数据结构》课程实验教学一览表 

八、主要的教学方法与教学手段

1.课程与教学方法、教学手段对应关系矩阵

2.主要采用的几种教学方法和手段

1、理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。

2、传统教学手段与多媒体等现化手段相结合。

3、重视实验教学，要求学生利用一切可利用的时间和机会去实验室，实现并验证书本上的各种算法，达到真正实现教学目的。

九、考核与成绩评定

1. 该课程与评价方法对应关系矩阵

2.具体考核与成绩评定办法

本课程为考试科目，课程结束后采用闭卷考试。考核总成绩中，平时成绩占30%（出勤占10%，实验完成情况占20%），期中考试占30%，期末考试占40%；考核范围为本大纲规定的基本要求教学内容。

十、推荐教材及参考书

（一）推荐教材

《数据结构》，邓文华主编，电子工业出版社，2015年6月第4版。

（二）参考书

1.《数据结构》，严蔚敏、李冬梅、吴伟民主编，人民邮电出版社，2011年2月第1版。

2.《数据结构课程设计》，苏仕华魏韦巍等主编，机械工业出版社，2010年3月第1版。

3.《数据结构与算法学习辅导及习题详解》，张乃孝主编，电子工业出版社，2014年10月第1版。

十一、其他需要说明的问题