数据结构与算法
一、课程说明
课程编号： 090314Z10
课程名称：数据结构与算法/ Data Structures and Algorithm
课程类别：专业教育课程
学时/学分：48/3（含实践学时：8 ）
先修课程：计算机与程序设计语言基础
适用专业： 电子信息工程专业
教材、教学参考书：
1.数据结构(C语言版).严蔚敏，吴伟民 北京：清华大学出版社，2011
2.数据结构(Java语言描述). 刘小晶,杜选，北京：清华大学出版社，2011
3.Data Structures and Algorithms. Adam Drozdek, 2004
4.Data Structures & Algorithm Analysis in C++.  Mark A. Weiss, 2013
5.Data Structures and Algorithm Analysis in C++ 3rd Edition, Clifford A.Shaffer,2013
二、课程设置的目的意义
数据结构，是电子信息工程专业一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在信息学科中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。
学习本门课程要求掌握各种主要数据结构的特点，在计算机内的存储表示方法，处理数据的算法设计，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握，以及数据结构在计算机科学中的应用。通过本门课程的学习，要求学生能够组织，处理数据的理
论和方法，培养训练学生选用合适的数据结构，能编写质量高，风格好的应用程序及初步评价算法程序的能力，使学生的逻辑分析、抽象思维和程序设计的能力得到提高。
学生学习时应注意本门课的特点：首先搞清楚各种数据结构的定义（逻辑结构），然后研究其可能的存储结构（物理结构），最后是一定存储结构上算法的实现。另外，配合适量的习题，辅以一定学时数的上机实践也是非常必要的，使学生对系统软件、应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。
三、课程的基本要求
通过本课程的学习，要求学生能够掌握数据的逻辑结构、存储结构以及其他结构定义的各种运算及应用。对同一种逻辑结构的数据，讨论其不同的物理结构和相应的有关算法；要求学生学会分析、研究计算机加工的数据对象特性，以便选择适当的数据结构以及相应的算法，并初步掌握算法的时间分析和空间分析方法。此外，学习本课程的过程也是进行程序设计的训练过程，所以要求学生书写的算法结构清楚，正确易读。具体要求如下：
（一）知识学习要求
1. 理解掌握数据结构的基本概念和术语，算法的描述和算法分析基本方法；
2. 熟练掌握线性表的逻辑结构，线性表的顺序存储结构，线性表的链式存储结构，一元多项式的表示及相加；
3. 熟练掌握栈和队列的基本概念、存储方式，运用栈结构实现表达式求值，熟悉栈与递归过程的关系，以及队列与离散事件模拟；
4. 熟练掌握树和二叉树：树的结构定义和基本操作，二叉树，遍历二叉树和线索二叉树，树和森林，哈夫曼树及其应用；
5. 掌握图的定义及术语，图的存储结构，图的遍历操作；理解图的连通性问题，有向无环图及其应用，最短路径等相关应用；
6. 掌握查与排序的基本概念、基本方法，熟悉理解经典的查算法、内排序算法，理解不同排序算法的优缺点，以及选择应用的标准。
（二）能力培养要求
1. 掌握程序设计的基本方法、算法设计与分析的基本方法，算法时间、空间复杂度的分析能力；
2. 应用线性表解决复杂软件工程问题，设计使用堆栈和队列相关算法的设计的能力，掌握程序设计的基本方法、软件建模方法；
3. 具备基于树结构设计算法的能力，应用树结构解决复杂工程问题的能力；
4. 具备基于图结构设计算法的能力，应用图结构解决复杂工程问题的能力。
5. 具备排序相关算法的设计能力，掌握各排序算法的特点，能在不同场合选择最合适的排序算法解决问题的能力；
6. 具备查算法的设计能力，掌握各查算法的特点，根据工程问题的性质选择最佳查算法并解决问题的能力。
（三）素质培养要求
1. 能够针对具体的数据要求，使用批判性思维方法，不断完善和丰富数据结构；
2. 能够从描述现实数据的多个角度思考开发的软件程序，培养基本的职业素质、敬业精神和职业道德。
四、教学内容、重点难点及教学设计
章节
教学内容
总学时
学时分配
教学重点
教学难点
教学方案设计（含教学方法、教学手段）
讲课
(含研讨)
实践
第1章
1.数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构、算法等。
2.抽象数据
类型。
3.描述算法的程序语言。
4.算法时间复杂度和空间复杂度的分析。
2
数据类型、抽象数据类型、数据抽象和信息隐蔽  原则
算法的定义、算法的特性、算法的时间代价、算法的空间代价
　讲授
课堂讨论
第2章
1.线性表的基本概念和类型
定义
2.线性表的顺序存储结构
3.线性表的链接存储结构
(1) 单链表的查、插入和删除
(2) 循环链表
(3) 双向链表
10
8
2
线性表的逻辑结构特性，以及线性表的两种存储实现  方式
　顺序表的定义与实现；单链表的定义、单链表的基本算法
  讲授
课堂讨论
课程实验
第3章
1.栈的类型定义
2.栈的顺序存储和链接存储的表示和实现
3.栈的应用举例（难点）
(1)迷宫求解
(2)表达式求值
4.队列的类型
定义
5.队列的顺序存储(循环队)和链接存储的表示和实现
3
栈的顺序存储和链接存储的表示和  实现
队列的顺序存储(循环队)和链接存储的表示和实现
讲授
课堂讨论
第4章
1.串的类型定义
2.串的顺序存储和链接存储的表示和实现
3.串的模式匹配算法
1
串的顺序存储和链接存储的表示和  实现
串的模式匹配算法
讲授
课堂讨论
第5章
1.递归的基本原理与求解过程
2.递归的种类
3.递归与非递归的转换
1
递归的基本原理与求解过程
递归与非递归的转换
讲授
课堂讨论
第6章
1. 数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式
2. 稀疏矩阵的压缩存储及
二叉树的遍历及应用实验报告
运算
2
数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式
稀疏矩阵的压缩存储及运算
讲授
课堂讨论
第7章
1. 树的定义、性质、存储结构
2. 二叉树
3. 二叉树的遍历和线索二
叉树
4. 树与二叉树的转换
5. 二叉树的
应用
9
7
2
二叉树
二叉树的遍历和线索二叉树
讲授
课堂讨论
          课程实验
第8章
1. 图的定义和术语
2. 图的存储
结构
3. 图的深度和广度搜索遍历
4. 拓扑排序
5. 最短路径
6. 最小生成树
9
7
2
图的存储结构、图的深度和广度搜索遍历、拓扑排序、最短路径 、最小生成树
图的深度和广度搜索遍历、拓扑排序、最短路径 、最小生成树
讲授
课堂讨论
          课程实验
第9章
1.静态查表
(1) 顺序查和二分查
(2) 分块查和索引查
2.动态查
(1) 二叉排序树
(2) AVL树
(3) B树和B+树
3.哈希表
3
顺序查和二分查、二叉排序树
顺序查和二分查、二叉排序树
讲授
课堂讨论
第10章
1.排序的概念
2.插入排序
3.交换排序
4.选择排序和堆排序
5．归并排序
6．基数排序
8
6
2
插入排序 、交换排序、选择排序和堆排序、基数排序
插入排序 、交换排序、选择排序和堆排序、基数排序
讲授
课堂讨论
          课程实验
合计
48
40
8
注：实践包括实验、上机等
五、实践教学内容和基本要求
实验方式采取单人分组独立实验，教师临场指导。教师事先布置任务，学生预习算法的基本流程撰写预习报告后进行实验。要求学生运用自己熟练的编程语言将算法实现，并用给定的测试数据进行验证。
实验基本要求如下：
(1)    熟练掌握C/C++语言的编辑、编译、调试程序。
(2)    会书写类C/C++语言的算法，并将算法转变为程序实现。
(3)    正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。
(4)    针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。
(5)    学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；
(6)    本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力；
(7)    通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。
六、考核方式及成绩评定
考核方式
考核内容
成绩比例（%）
备注
课堂提问和测验
数据结构基本概念
10
实验报告
数据结构设计的基本技能
20
软件项目作品展示
课堂讨论
数据结构综合实践与创新
10
期末考试
数据结构理论知识运用
60
七、大纲主撰人：                大纲审核人： ，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。