《数据结构(Java版)》教学大纲 孙爱香

《数据结构(Java版)》教学大纲课程性质与任务本课程是计算机科学中一门综合性的基础课程，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础，它在计算机科学中具有承上启下的核心地位，是计算机及相关专业学生必修的专业基础课程。通过本课程的学习，学生能根据实际应用研究的要求，对大量的表面上杂乱无章的数据进行有效地组织、存储和处理，编制出相应的高效算法。学生必须熟练掌握计算机程序设计中常见的各种数据的逻辑结构、存储结构及相应的运算，掌握算法的时间分析和空间分析的技术，并能根据计算机加工的数据特性运用数据结构的知识和技巧设计出更好的算法和程序，培养良好的程序设计能力。学习数据结构应先修《计算机文化基础》、《高等数学》、《离散数学》、《JAVA程序设计》、《概率论与数理统计》，后续课程主要有《管理信息系统》《数据库原理及应用》《数据挖掘》，《网络程序设计》等。与先修课程的关系：数据逻辑结构的学习应在《离散数学》课程中完成，这样才会有充足的时间讲解物理存储结构，并分析每一种不同存储结构的优缺点。在分析插入和删除等操作的效率时，因为不同位置的数据操作概率不同，不结合概率论与数理统计的知识便无法分析。数据的存储结构是数据在计算机中的存储，没有人机交流语言无法描述存储结构，所以必须先修高级语言《JAVA程序设计》，分析算法的时间复杂度和空间复杂度时需要用到《高等数学》与《概率论与数理统计》的知识。与后续课程的关系：数据结构和算法分析可以为后续课程提供程序设计和系统开发方法论方面的指导与帮助。二、课程目标1．知识目标（1）知道《数据结构与算法分析》这门学科的性质、在计算机科学中的地位和独立价值。知道这门学科的研究范围、应用领域、研究方法。（2）掌握与数据结构有关的基本概念、明确数据的逻辑结构和物理结构的差别。（3）掌握各种主要数据结构线性表、栈、队列、串、树和图的特点、计算机内的表示方法，以及处理数据的算法实现。（4）会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并了解对算法的时间分析和空间分析技术。2．能力目标（1）培养学生数据抽象能力，能为应用涉及的数据选择合适的逻辑结构。（2）培养学生理解计算机思维方式能力，能为各种逻辑结构设计合适的存储结构。（3）培养学生进一步提高程序设计质量的能力。（4）培养学生理论联系实际能力及自学能力。3．素质目标（1）具备运用数据结构的理论方法进行高质量程序设计的素质。（2）具有良好的团队合作精神。

三、教学内容及教学要求参考理论学时48参考实验学时16课程内容及要求序号教学项目教学内容和教学要求教学设计建议参考学时1绪论1.数据结构的概念和术语；2.算法的描述与算法分析；3.数据结构的地位。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。61.掌握数据结构的概念和术语；2.理解算法的描述与算法分析；3.理解数据结构的地位。2线性表1.线性表的类型定义；2.线性表的顺序存储与实现；3.性表的链式存储结构与实现；4.线性表的应用。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。61.掌握线性表的类型定义；2.掌握线性表的顺序存储与实现；3.掌握线性表的链式存储结构与实现；4.了解线性表的应用。实验1线性表的应用1.利用线性表开发一元多项式运算系统。43栈和队列1.栈和队列的定义；2.栈和队列的顺序存储和链式存储；3.栈和队列的应用。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。61.掌握栈的定义、栈的存储及其实现；2.掌握队列的定义、存储及其实现；3.了解栈和队列的应用。实验2栈和队列的应用1.编写程序，从键盘输入一个十进制数，输出与其等值的八进制数。2.编写程序，利用栈和队列实现判断一个字符串是否是回文。24串1串类型的定义，串的存储；2.串的运算实现。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。41.掌握串类型的定义，串的存储；2.理解串的运算实现。5数组与广义表1.掌握：数组的定义、数据的顺序存储和实现，特殊矩阵的压缩存储，稀疏矩阵的三元组表存储；2.理解：稀疏矩阵的十字链表；3.了解：广义表的定义和广义表的存储结构。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。61.掌握：数组的定义、数据的顺序存储和实现，特殊矩阵的压缩存储，稀疏矩阵的三元组表存储；2.理解：稀疏矩阵的十字链表；3.了解：广义表的定义和广义表的存储结构。实验3特殊矩阵的运算1.压缩存储下实现各种特殊矩阵的运算。26树与二叉树1.树的定义和基本术语、树的存储结构、二叉树的概念、存储及遍历二叉树、线索二叉树、哈夫曼树及其应用；2.森林的概念、森林与树的转换及树和森林的遍历；树的应用1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。61.掌握树的定义和基本术语、树的存储结构、二叉树的概念、存储及遍历二叉树、线索二叉树、哈夫曼树及其应用；2.理解森林的概念、森林与树的转换及树和森林的遍历，树的应用；实验4树的应用1.从键盘接受n个字符的权值，输出此n个字符的哈夫曼编码，请尝试基于二叉树不同的存储结构实现。2.从键盘接受某一集合s的r等价关系，即接受n个等价偶对，输出s基于r的等价类。27图1.图的定义和术语、图的存储结构及操作实现、图的遍历、最小生成树；2.图的连通性问题。3.有向无环图的拓扑排序，关键路径、最短路径。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。61.掌握：图的定义和术语、图的存储结构及操作实现、图的遍历、最小生成树；2.理解：图的连通性问题；3.理解：有向无环图的拓扑排序关键路径、最短路径。实验5图的应用1.从键盘接受图的顶点和及边的权值，输出图的最小生成树，尝试在不同的存储结构下实现。2.从键盘接受AOE图的顶点和及边的权值，输出从源点到汇点的关键路径，尝试在不同的存储结构下实现。3.从键盘接受图的顶点和及边的权值，输出图各对顶点之间的最短路径，尝试在不同的存储结构下实现。28查找1.顺序查找法，折半查找法，二叉排序树的查找，哈希表及其查找；2.分块查找法，二叉平衡树生成及其查找。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。41.掌握顺序查找法，折半查找法，二叉排序树的查找，哈希表及其查找；2.理解分块查找法，二叉平衡树生成及其查找。实验6查找1.从键盘接受一个整数序列，构造一棵二叉排序树并输出。29排序1.直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序、归并排序；2.希尔排序、堆排序；3.基数排序。1.多媒体教学，进行启发诱导，重点讲解；2.课堂练习；3.布置课后作业。41.掌握直接插入排序、折半插入排序、冒泡排序、快速排序、简单选择排序、归并排序；2.理解希尔排序、堆排序。3.了解基数排序。实验7排序1.从键盘接受一个整数数据序列，尝试用不同的排序方法，在屏幕输出它的非递减有序序列。2合计64

四、教学方法在教学过程中，应立足于加强学生实际编程能力的培养，采用项目教学，以工作任务引领提高学生学习兴趣，激发学生的成就动机。通过对项目的课外分析与编程和课堂总结，培养学生利用计算机编程解决实际问题的能力，综合分析能力，创新能力。增设数据结构与算法分析课程主页，实现网上交互式教学，在每一章的教学内容之后配备相关的编程题目，倡导“问题导向”，引导学生对相关题目进行编程，以掌握程序设计的基本原理：数据结构+算法=程序编程开发：编程开发是数据结构与算法分析教学联系实际的特色形式，应引起教师高度重视。本课程所选编程题目，应是较为典型的、学生有能力完成的。教师的指导重点要放在指导学生如何进行程序设计以及提高程序的质量上，而不是代替他们进行程序设计，鼓励学生课下自己根据编译器的错误提示信息，找出所编制程序的错误，逐步提高程序调试水平。作业评讲：制作学生作业错误汇总PPT，收集学生平时作业中的常见问题,以图片展示、关键点解释、计算技巧讲解的方式教会学生如何自己发现错误、如何自行纠正错误的方法与技巧。鼓励学生上网查阅中国学术期刊，万方数据库、中宏数据库等电子资源。向学生推荐数据结构与算法分析理论与应用成果较多的1.软件学报2.计算机学报3.计算机研究与发展4.系统仿真学报5.计算机辅助设计与图形学学报6.自动化学报7.控制与决策8.中国图象图形学报9.计算机集成制造系统10.中文信息学报11.控制理论与应用12.计算机应用13.计算机应用研究14计算机科学15.信息与控制16.模式识别与人工智能等国内高水平科技期刊。让学生主动查阅、了解数据结构与算法分析的发展现状和新理论、新方法、新概念、