教育材料《数据结构》-整体设计

《数据结构》课程整体设计课程代码KJAVA12课程性质专业基础课总学时72适用专业软件技术及相关专业教学方式“教、学、做”一体化制定单位学校武汉软件工程职业技术学院制定日期2012.8.8审核部门软件技术专业资源库建设项目组企业武汉光谷信息技术有限公司一、课程设计思路本课程依据课程标准，以软件技术专业学生的就业岗位群能力目标为导向，以数据结构与算法为主线，把整个课程分成知识技能篇和技术应用篇，培养学生具有数据抽象能力和复杂程序设计能力，为今后软件开发设计打下坚实基础。二、课程目标设计课程定位在培养学生的数据抽象能力和复杂程序设计的能力为总目标。通过对本课程的学习，使学生掌握各种常用数据的逻辑结构、存储表示、基本操作及算法设计，学会分析计算机加工的数据对象的特性，以便选择合适的数据逻辑结构、存贮结构及相应的基本处理算法；初步掌握算法的时间和空间复杂度分析技术,培养学生数据抽象能力和复杂程序设计能力，为今后软件开发设计打下坚实基础。知识目标1．了解数据结构的逻辑结构和物理结构之间的关系，数据结构和数据类型的关系，数据结构和算法的关系；2．熟悉和掌握各种基本数据结构的概念、特点、存储结构，各种基本数据结构的运算及其算法设计；3．熟悉和掌握算法的基本分析方法；4．熟悉和掌握排序和查找的基本算法，根据实际文体提出的要求，学会如何选择合理的排序和查找算法。职业能力目标1．掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法实现。2．使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。3．通过对本课程算法设计和上机实践的训练，培养学生的数据抽象能力和复杂程序设计的能力。4．有初步的算法分析和设计能力。5．能够有效地获取、利用、传递信息。6．通过独立学习，不断获取新的知识和技能，能够在工作中寻求发现问题、解决问题的途径。职业素质养成目标1．培养学生良好的协调和沟通能力；2．培养学生勇于创新和严谨细致的工作作风；3．培养学生良好的职业道德和团队合作精神；4．培养学生善于收集信息和良好的自学能力；5．培养学生理论联系实际，善于发现问题并积极寻求解决问题方法的能力。（四）其他目标通过本课程的学习，可以参加以下职业资格证书的考试。1．全国计算机等级二级考试；2．程序员。三、课程内容设计根据课程标准，将教学内容分为知识篇和应用篇。知识篇分为绪论、线性表、栈和队列、串、数组和广义表、树、图、查找、排序和文件十个单元。通过本篇的学习，使学生循序渐进的掌握各类数据结构，掌握数据结构应用思想，达到具有分析问题、利用数据结构解决实际问题的能力。实训篇完成七个模块单元：求出约瑟夫环的出列、模拟手机短信功能、学生成绩管理系统、学生信息管理系统、求二叉树上结点的路径的应用和交通查询系统设计。通过对本篇的学习，使学生循序渐进地掌握结构化程序设计的思想，掌握各类数据结构的使用，达到具有分析问题、编程解决实际问题的能力。具体内容设计如下：课程内容总体设计篇名单元单元名称学时安排知识篇单元一绪论2单元二线性表4单元三栈和队列2单元四串2单元五数组和广义表4单元六树6单元七图6单元八查找6单元九排序6单元十文件2合计40应用篇模块模块名称学时安排模块一了解JAVA开发环境4模块二求出约瑟夫环的出列——链表应用4模块三模拟手机短信功能——队列应用4模块四文本编辑——字符串处理4模块五学生成绩信息管理系统——结构体与程序逻辑4模块六求二叉树上结点的路径的应用——二叉树应用6模块七交通查询系统设计——图与最短路径6合计32总计72课程内容详细设计1．知识篇详细设计篇名单元名称单元内容知识目标学时安排知识篇单元一：绪论数据结构基本概念理解数据结构的基本概念；掌握逻辑结构、物理结构的概念及相互关系；掌握本书介绍的四种基本结构的特点；理解算法及其特性；了解算法分析的一般概念。1算法概念及特性1小计2单元二：线性表线性表概念理解线性表的定义及两种存储结构；理解线性表顺序存储的特点、实现方法和应用；掌握顺序表的基本操作；掌握链表的基本操作（包括建立链表、遍历链表、删除、插入、查找）和应用；了解双向链表、循环链表的原理和相关操作。1顺序表基本及操作2链表基本及操作1小计4单元三：栈和队列栈、队伍概念掌握栈和队列的操作特点；理解顺序栈、顺序队列的基本操作；了解在实际编程中栈和队列的不同应用；理解循环队列的概念、实现方法。掌握循环队列判空、判满的条件；能利用递归程序设计技术实现相关算法。1顺序栈、顺序队列、链栈、链队列的基本操作1小计2单元四：串串的基本概念理解串的定义和存储方法；了解串的基本操作和相关算法；掌握用JAVA语言处理字符串的语法规则。1串的存储、基本操作1小计2单元五：数组和广义表数组概念、存储结构了解数组的存储结构；掌握特殊矩阵进行压缩存储的下标转换公式；理解稀疏矩阵的压缩存储原理；掌握利用三元组表示稀疏矩阵的方法；了解广义表的概念和存储结构。1特殊矩阵1广义表概念、存储结构2小计4单元六：树树和二叉树的定义了解树和二叉树的定义；掌握二叉树的基本性质，能利用相关性质解决简单计算问题；了解二叉树的顺序存储结构；掌握二叉树的链式存储结构、相关操作；掌握二叉树的有关算法并能编程实现；掌握利用遍历构造二叉树的规则和具体步骤；掌握哈夫曼树的定义、性质和构造方法；了解哈夫曼树的应用。1二叉树的基本性质1二叉树的存储结构1二叉树的算法及实现1哈夫曼树概念及应用2小计6单元七：图图的基本概念了解图的基本概念；掌握图的存储方法（邻接矩阵、邻接表）；掌握图的深度优先和广度优先遍历的规则1和步骤；理解在连通图中求最小生成树的方法；了解求图的最短路径等相关算法及其应用。1图的存储结构1图的遍历1最小生成树1最短路径2小计6单元八：查找查找的相关概念了解查找的相关概念；掌握顺序表的查找方法、步骤、程序实现、时间复杂度和平均查找长度；掌握在有序的顺序表上进行折半查找的方法、步骤、程序实现；掌握折半查找的判定树的构造方法；掌握二叉排序树的确切定义；掌握建立二叉排序树的步骤和方法；理解在二叉排序树中进行输入、删除操作的规则；了解哈希表的相关概念和原理；了解常用哈希函数的构造和处理冲突的方法；掌握哈希函数和哈希表的关系及在查找中的应用。1顺序查找1折半查找1索引查找1哈希查找2小计6单元九：排序插入排序掌握教材中介绍的各种排序算法的基本原理、步骤；掌握相关排序算法的规则人工完成排序；3．能通过分析排序的中间结果判断所用的排序算法；能正确理解相关排序算法的程序实例，并重点掌握算法中的关键步骤和关键语句；掌握堆和特殊的完全二叉树的对应关系；掌握建堆、“筛选”完全二叉树相关操作的方法。1交换排序1选择排序1归并排序1各种排序方法比较2小计6单元十：文件文件的概念与分类掌握文件概念；掌握顺序文件操作方法；掌握索引文件操作方法；掌握各类文件的数据读写方法；了解多关键字文件。1各类文件的操作1小计2合计402．实训篇详细设计篇名模块名称子模块名称知识目标学时安排实训篇模块一：了解JAVA开发环境使用JAVA开发简单JAVA程序掌握JAVA语言程序开发过程；掌握JDK6.0和MyElicpe的编程环境；了解算法的评价标准。2使用JAVA开发控制台类型的简单JAVA程序2小计4模块二：求约瑟夫环的出列——链表应用链表建立、初始化熟练定义并实现链表；熟练使用链表常用操作。2根据用户输入的值得出符合条件的序列2小计4模块三：模拟手机短信功能——队列应用设计链式存储结构的队列掌握队列的定义；熟练掌握队列的实现；熟练掌握的队列常用操作。2队列的操作2小计4模块四：文本编辑——字符串处理文本的输入、查找掌握控制台应用程序菜单的实现；掌握使用串的常用操作；熟练掌握串的查询。1文本的修改、删除1文本的输出2小计4模块五：学生成绩信息管理系统——结构体与程序逻辑设计学生成绩信息管理系统的图形界面掌握控制台应用程序多级菜单的实现；掌握结构体变量的定义和使用方法；掌握串的链式存储结构；掌握文件的读写操作；掌握结构化程序设计方法。1学生基本信息的输入、修改、删除、查询1学生成绩的输入、修改、删除、查询2小计4模块六：求二叉树上结点的路径的应用——二叉树的应用二叉树建立熟练掌握二叉树定义及存储实现；熟练掌握二叉树的遍历算法设计。2二叉树初始化2二叉树遍历2小计6模块七：交通查询系统设计——图与最短路径建立交通网络图的存储结构熟练掌握图的存储结构；熟练掌握两种求最短路径的算法设计；熟练掌握两点之间最短路径算法设计。2单源最短路径2实现两个城市顶点之间的最短路径2小计6合计32四、能力训练设计1．知识篇能力训练设计序号单元/模块名称能力目标能力描述训练方式结果（可展示）1单元一：绪论具备计算算法能力。能够编写简单的JAVA程序；能够进行简单的算法评价。讲练结合程序代码2单元二：线性表具备构建顺序表、链表，并对顺序表、链表进行添加与删除等简单应用的能力。能够定义并实现顺序表；能够实现顺序表常用操作；能够定义并实现链表；能够实现链表常用操作。讲练结合程序代码3单元三：栈与队列具备构建栈、队列，并利用顺序和链表对栈、队列进行添加与删除等简单应用的能力。能够定义并实现栈；能够实现栈常用操作；能够定义并实现队列；能够实现队列常用操作。讲练结合程序代码4单元四：串具有解决串操作应用问题程序设计能力。能够定义并实现串；能够使用串的各种函数。讲练结合程序代码5单元五：数组与广义表具备运用数组处理数据，并对数据进行增、删、改、查的操作的能力。能够定义多维数组；能够利用特殊矩阵进行压缩存储的下标转换公式；能够用三元组实现稀疏矩阵；能够用广义表实现各种操作。讲练结合程序代码6单元六：树具有运用树、二叉树操作解决应用问题的能力。能够定义并实现二叉树的存储实现；能够进行二叉树的遍历算法设计；实现二叉树的有关算法并能编程实现；实现哈夫曼树的应用。讲练结合程序代码7单元七：图具有运用图操作解决应用问题的能力。能够定义并实现图的存储结构；能够实现图的深度优先和广度优先遍历；能够实现图中求最小生成树；能够进行两点之间最短路径算法设计。讲练结合程序代码8单元八查找具有运用四种查找方法操作解决应用问题的能力。能够定义并实现顺序查找；能够定义并实现二分查找；能够定义并实现索引查找；能够定义并实现哈希查找。讲练结合程序代码9单元九：排序具有运用四大类、七种排序方法操作解决应用问题的能力。能够定义并实现插入排序；能够定义并实现交换排序；能够定义并实现选择排序；能够定义并实现归并排序；讲练结合程序代码10单元十：文件具有综合运用所学文件知识进行应用程序的能力。能够定义文件类型；能够实现各类文件的操作。讲练结合程序代码2．应用篇能力训练设计序号单元/模块名称能力目标能力描述训练方式结果（可展示）1模块一：了解JAVA开发环境具备配置JAVA语言开发环境，编写简单JAVA程序的能力。能够使用JDK6.0及MyElicpe开发环境；能够编写简单的JAVA程序；能够进行简单的算法评价。实践操作程序代码2模块二：求出约瑟夫环的出列——链表应用具备构建链表，并对链表进行添加与删除等简单应用的能力。能够定义并实现链表；能够实现链表常用操作。实践操作程序代码3模块三：模拟手机短信功能——队列应用具备构建链式队列，并利用链表对队列进行添加与删除等简单应用的能力。能够定义并实现队列；能够实现队列常用操作。实践操作程序代码4模块四：文本编辑——字符串处理具有解决串操作应用问题程序设计能力。能够定义并实现串；能够使用串的各种函数。实践操作程序代码5模块五：学生成绩信息管理系统——结构体与程序逻辑具备运用结构体处理数据，并对数据进行增、删、改、查的操作的能力。能够实现控制台应用程序多级菜单；能够使用结构体处理数据；能够灵活运用串的链式存储结构进行数据操作；能够进行文件的读写操作。实践操作分组讨论程序代码6模块六求二叉树上结点的路径的应用——二叉树的应用具有运用树操作解决应用问题的能力。能够定义并实现二叉树的存储实现；能够进行二叉树的遍历算法设计。实践操作分组讨论程序代码7模块七交通查询系统设计——图与最短路径具有综合运用所学知识进行应用程序的算法设计。能够定义并实现图的存储结构；能够进行两点之间最短路径算法设计。实践操作分组讨论程序代码五、考核评价设计本课程考核采用形成性考核方式，总评成绩由形成性考核的各项成绩组成，全面考核学生的动手能力、基础理论和平时学习状况，考核标准以奖励为主，惩罚为辅，具体分值比例如下：综合素质评价（平时表现+通用能力考核）20%过程性考核（课堂实践考核+课后实践考核+项目开发实践）50%终结性考核（期终考核）30%综合素质评价考核内容评价标准考核分值出勤情况迟到、早退1次扣0.5分，旷课1次扣2分，扣完5分为止，旷课3次及以上不得参加终结性考核。5%学习态度不认真听课、不按时完成课堂或课外实践1次扣0.5分，扣完5分为止。5%学习表现主动提出问题、回答问题1次加0.5分；课堂或课外实践完成质量高（正确率80%以上）1次加0.5分，加满5分为止。5%通用能力提出问题、回答问题时语言表达准确、逻辑性强1次加0.5分，加满5分为止。5%过程考核考核内容评价标准考核分值课堂实践课堂实践完成质量高（正确率80%以上）1次加0.5分，加满10分为止。10%课外实践课外实践完成质量高（