数据结构与算法（共8篇）
数据结构与算法 篇1
《数据结构与算法》课程学习总结报告
070401301507计本（3）班张浩
本学期开设的《数据结构与算法》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。
一、《数据结构与算法》知识点
在课本的第一章便交代了该学科的相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。紧接着介绍了一些常用的数据运算。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。
第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的概念，重点在于串的模式匹配。
链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。
堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。
第六章介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题。
第七章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。
树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有：散列结构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。
最后一章介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。
二、对各知识点的掌握情况
总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象。现将各个章节出现的知识点理解情况列举如下。
第一章中我对数据和数据结构的概念理解较为透彻，熟悉数据结构的逻辑结构和存储结构。而对算法的时间、空间性能分析较为模糊，尤其是空间性能分析需要加强。
第二章，顺序表的概念、生成算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找较为含糊；排序问题中，由于冒泡排序在大一C语言课上已经学习过，再来学习感觉很轻松。对插入排序和选择排序理解良好，但是，在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力，现在对这种排序方法仍然非常模糊，所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。
链表这一章中，除对双向循环链表这一知识点理解困难之外，其他的知识点像单链表的建立和基本算法等都较为熟悉。
接下来的有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。不足之处仍然表现在算法的性能分析上。
在学习第六章时感觉较为吃力的部分在于矩阵的应用上，尤其对矩阵转置算法的C语言描述不太理解。稀疏矩阵相加算法中，用三元组表实现比较容易理解，对十字链表进行矩阵相加的方法较为陌生。
第七章是全书的重点，却也有一些内容没有完全理解。在第一节基本概念中，二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用，而对于二叉树应用中的哈弗曼树却比较陌生。
第八章内容较少，牵涉到所学的队列的有关内容，总体来说理解上没有什么困难，问题依旧出现在算法的性能分析上。
散列结构这一章理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实，对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好，问题在于用C语言描述上。
最后一章，图及其应用中，图的定义、基本运算如图的生成等起初理解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好，而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历（包括深度和广度优先遍历），最小生成树问题也是比较陌生的知识点。最短路径和AOV网学习起来感觉比较轻松，而对于C语言描述却又不大明白。
三、学习体会
接触这门课程以前，我对该课程所学的内容有许多疑点，例如：这门课是否是在介绍一种新的计算机语言？如果不是，那么学习这门课程的用途是什么？为什么市面上各种介绍数据结构的资料采用了不同的计算机语言，如C、C++还有Java？我的C语言学得不好，对学习这门课是否有影响„„
在学习伊始，老师就明确提出它不是一种计算机语言，不会介绍新的关键词，而是通过学习可以设计出良好的算法，高效地组织数据。一个程序无论采用何种语言，其基本算法思想不会改变。联系到在大一和大二上学期学习的C和C++语言，我深刻认识到了这一点。“软件开发好比写作文，计算机语言提供了许多华丽的辞藻，而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中，要熟悉对算法思想的一些描述手段，包括文字描述、图形描述和计算机语言描述等。因此，计算机语言基础是必须的，因为它提供了一种重要的算法思想描述手段——机器可识别的描述。
这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到
自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。
四、对《数据结构与算法》课程教学的建议
1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。
2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。
以上便是我对《数据结构与算法》这门课的学习总结，我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习，克服学习中遇到的难关，在打牢基础的前提下向更深入的层面迈进！
数据结构与算法 篇2
关键词：算法与数据结构,教学研究,教学改革
近年来, 信息技术已经改变人类社会生活的模式, 计算机技术的教育与应用得到了极大发展。数据结构作为计算机专业的七大核心课程之一, 被列为计算机科学与技术、软件工程、网络工程等信息类专业的全国统考研究生考试课程之一, 也是编译原理、操作系统、数据库原理、计算机网络等专业课程的先导课程, 在计算机专业课程体系中发挥着承上启下的核心作用。
一、数据结构与算法教学现状的分析
(一) 学生的课程学习现状
在传授学生学习算法和数据结构时, 学生的计算机编程的理论基础和应用经验往往是不同的, 因此很容易引起学生理解和掌握能力的偏差。
在实际授课中, 教学时间是有限的, 而且有的学生经常在听课的过程中聊天或玩游戏, 不按照训练复习。还有一些学生是为了应付期末考试和学习, 学习的方法和策略都没有用, 而且很难获得对知识的全面理解, 学习质量不高。
(二) 教学环节缺乏创新
以往的教学模式单一, 都是以教师为中心进行教学, 注重教学过程, 忽视学生的学习过程。学生只是被动接受学习, 根本无法提高学生的学习兴趣。
教师对计算机知识型内容的教学方法是比较熟悉的, 能够强调重点知识、讲解难点知识, 使学生能够有重点、有目标地进行学习, 但针对操作型内容教学则显得经验不足, 教学方法不当。
(三) 考核环节的缺陷
传统的考核模式是“以教师评价为主”, 强调最终评价结果, 当面临应用性评测时, 则暴露了它的缺点。学生本来就很难对一些知识进行运用, 而为了通过测试, 就抄袭、拷贝其他同学的程序, 所以经常出现全班的程序都是一个模版的情况。这样的考试不能考核出学生的真实水平。
二、教学研究中需要探索的内容
(一) 教学大纲的更新
教学大纲在教学中起着指导性的作用, 因此教学研究中务必跟踪新技术发展与数据结构的新算法, 不断更新教学内容, 完善教学大纲的编制。以算法与程序设计能力培养为主线, 提升学生应用基本结构分析问题、算法设计与编程的能力。结合《数据结构课程设计》等实践环节, 夯实学生的应用技能。
在教材方面, 可以选用张乃孝等人编著的高等教育出版社出版的最新版《算法与数据结构———C语言描述》作为主教材, 同时选用唐策善等人编著的高等教育出版社出版的《数据结构———用C语言描述》作为参考教材, 实现教材内容的高低配合, 理论算法与算法的相互补充。
(二) 教学模式的变革
在数据结构的教学改革中, 应摒弃传统的陈旧的教学模式。由浅入深、由线性到非线性、横向与纵向比对教学模式, 找出每种数据结构教学的优缺点。
(三) 强化实验和考核
数据结构实践教学要突出“理论与实践”的原则, 通过对问题的抽象, 选择合适的数据结构来解决实际问题, 提高应用能力。
考核评价设计紧密结合数据结构与算法课程, 注重过程考核、算法设计评价考核、实际解决问题能力的考核。加大实践环节考核的比例, 以阶段性课外作业的形式加强阶段性考核, 体现考核形式的多样化、考核标准的合理化以及考核的不间断性。
三、基于CDIO的多元教育模式教学改革
通过对当前数据结构教学的研究和分析, 笔者尝试将一种全能的工程理念———CDIO工程教育模式应用在指导数据结构教学的过程中。CDIO, 即构思 (conceive) 、设计 (design) 、实现 (implement) 和运作 (operate) , 它以产品研发到产品运行的生命周期为载体, 让学生以主动、实践、课程之间有机联系的方式学习工程。CDIO模式作为先进的多元教育模式可以很好地培养新型的优秀的工程人才。
(一) 教学指导思想的定位
CDIO模式突出了工程基础知识、个人能力、人际团队协调能力和工程系统能力。在完善数据结构课程教学指导思想时应当充分考虑以下几个方面。
1. 制定一体化教学计划。
新计划要大幅减少基础理论的权重, 可将涉及工程的一系列课程进行整合, 增加知识的综合运用能力。比如, 数据结构课程可以和C语言进行整合安排。
2. 以CDIO模式为基本环境。
应当以“基于项目的教育学习”为宗旨, 着力培养四种能力, 并围绕上述目标进行详细规划, 制定目标和标准。
3. 职业训练计划。
纳入CDIO模式后, 必须将学科学习与职业训练相结合, 要在大学期间融入优秀工程师的职业训练, 实际上也是四种能力培养的又一次强化。
(二) 精选实际问题用于设计性实验, 提高学生实际算法设计能力
由于数据结构课程与实际工程问题的融合, 在设计实验时, 要摒弃传统验证性的实验, 通过设计性实验来引导学生运用数据结构基础知识, 指导学生如何分析选择合适的数据结构, 传授正确的算法设计理念。通过设计一些实际的小型应用课题, 让学生自主探索实际运用算法的能力, 使学生有更多的创造空间。
(三) 以工程任务为牵引, 提高学生的算法设计创新能力
探索以实际的工程任务为牵引, 引导学生主动学习的新教学模式。改变传统教学中的先给学生布置作业, 然后再进行课堂教学的缺乏主动创新动力的模式。选取的工程任务力求既结合实际, 又能涵盖课程教学的要求。教师重点关注学生自学、开发和研究的进度。以工程任务为牵引的教学模式, 打破了算法设计类课程一贯采用的“填鸭式”教学模式, 变“要我学”为“我要学”。以任务为主线展开, 重在分析实际任务所涉及的数据结构、算法思路, 培养学生算法设计的创新能力。
(四) 考核评定的新标准
制定考核评定的标准应基于两个方面的考虑:一方面, 通过考核使教师和学生自觉以CDIO模式为前提开展数据结构课程的教与学, 避免推行CDIO模式流于形式化。另一方面, 考核标准要纳入CDIO模式原则和相关标准, 要实现从基础理论考核为主转变为“实践中学习”, 自主学习的实际动手能力考核。新标准要确立两个主体、三个客体:两个主体就是学生和教师。不仅考核学生的基础知识、自主学习能力、团队合作能力和工程软件项目能力, 而且要考核教师的CDIO模式运用能力、教师专业素质能力和调动学生兴趣的能力。三个客体是指考核的测评方:一是学校教学部门。主要考核教师的CDIO教学能力和学生最终的学习实践能力, 通过考核促进CDIO模式的推广和学生全方位适应用人单位的要求。二是合作项目单位。合作项目单位通过项目完成情况, 对学校、教师、学生的实际能力给予评价。三是授课教师。授课教师通过全过程的授课情况、学生完成项目情况、在项目合作中的表现和全课程中的自我学习情况, 结合基础知识考核给出学生综合分。
四、结语
CDIO模式是解决当前软件人才培养中学用脱节、不适应职业特征要素的有效举措。本文结合数据结构课程的教学改革与实践经验, 重点培养学生对基本数据结构的理解能力和应用能力, 提高算法设计和解决实际问题的综合能力, 为后续课程的学习与学生综合素质的提高打下坚实基础。
参考文献
[1]胡文龙.基于CDIO的工科探究式教学改革研究[J].高等工程教育研究, 2014 (1) .
[2]张伟, 王丽云.CDIO教学改革中的教学质量评估系统[J].辽宁大学学报, 2013 (3) .
[3]张国斌, 张树军, 刘春城, 等.基于CDIO模式的学生实践能力的培养[J].实验室科学, 2014 (1) .
[4]范会联, 仲元昌.基于CDIO理念的软件人才培养模式探索[J].实验室研究与探索, 2012 (1) .
[5]张婧, 韩雁, 梁志星.基于CDIO项目式教学的教师能力培养[J].重庆理工大学学报, 2013 (11) .
数据结构与算法 篇3
【摘 要】针对在数据结构与算法实验教学中如何提高学生的编程和算法设计能力，分析并指出了在实验教学中普遍存在的问题，结合实验课的教学改革，开发实验平台，以期有效激发学生的学习兴趣和积极性，培养动手和创新能力。
【关键词】数据结构与算法 实验改革 平台建设
【中图分类号】 G 【文献标识码】A
【文章编号】0450-9889（2014）07C-0132-03
数据结构与算法实验是计算机专业学生必修基础课数据结构与算法的配套实验课程，是培养学生程序设计技能必不可少的重要环节。其目标之一是培养学生能运用理论知识与算法技术分析解决实际问题，能运用高级程序设计语言编程实现算法。从近年实验情况来看，在上机编写程序实现具体算法时遇到的种种问题，效果不容乐观，学生很难按时完成实验所要求的内容。
一、实验教学存在的问题与分析
数据结构与算法实验是一门实践性很强的技术基础课，经过多年实验教学分析，发现普遍存在如下主要问题：
（一）课程抽象，实验难度大
数据结构具有一定的抽象性，学生面对抽象概念在学习过程中常会遇到困难，基本每本理论教材在呈现概念时都会受到多方面限制，比如篇幅的限制，省略了算法细节部分或只给出伪代码，由学生自己补充，学生需要将算法用程序设计方法实现，完成有一定难度和技巧的程序设计并上机调试运行。对编程基础稍微薄弱的学生来说，就会出现不小的困难。
（二）实验相关资料偏少
由于学生基础薄弱，实验前又没有更多的相关实验资料进行预习，仅靠看课本理论和实验时的几个学时难以完成实验所要求的任务，也就谈不上创新人才的培养。
（三）学生程序设计语言课程基础薄弱
数据结构与算法课程是第四学期开设，对于很多先修课程要求高，高级程序设计语言是大学生进校第一、二学期学习，第一学期学习过程序设计思想，第二学期学习面向对象程序设计思想，由于大部分同学高中没接触过计算机语言学习，对过程程序设计思想还没掌握透，第二学期的面向对象程序设计学习又开始，学习非常吃力；导致常用的一些语法结构，如指针和结构体等内容难于理解。而这些语法恰恰是程序设计语言教学时的难点，也正好是学生完成数据结构实验必须掌握的内容，这给部分学生学习带来了一定困难。
（四）编程语言难
数据结构与算法编程语言描述主要用到C++语言，并大量用到了指针、链表和结构体等运算，这部分内容正好是大多数学生掌握知识点薄弱的环节，导致学生很难用高级语言将教材中的算法描述出来，由于问题的堆积、实验的欠账，容易使学生丧失学习兴趣和信心，导致学生间抄袭程序或实验报告的现象。
（五）编程技巧差
普通学生在低年级只编写过功能单一、结构简单的程序；而从功能单一的简单程序向涉及算法和稍复杂程序的数据结构编写过渡学习时，需循序渐进的方式和细致的引导，紧密结合理论教学。学生一下从简单编程直接到复杂的程序设计，不仅不适应，且设计技巧性较差。
二、实验教学改革目标的提出
根据以上学生实验时出现的诸多问题，特提出该课程的实验改革目标：
一是紧密配合理论教学，通过相关实验，帮助学生加深对数据的逻辑结构、存储结构、算法思想和具体实现等各个环节的整体理解，强化学生“结构——算法——编程”三者密切相关的意识，让学生思考和发现利用数据结构解决实际应用问题的有效方法，从而使学生分析和解决问题的能力得到锻炼和提高。
二是因材施教，让原本不同水平和能力起点的学生通过数据结构实验，能力和水平都有所提高，并且有兴趣有信心学好数据结构课程。
三是培养学生多方面能力，比如团队精神，口头表达能力，对学生全方面发展起到较好的推动作用。
三、调整实验项目内容，使其更加符合学生的认知规律
数据结构与算法实验内容主要是编程实验，提高学生的实践编程能力，巩固和强化理论课的教学效果。为了保证和提高实验教学质量，加深对课堂知识的理解，培养学生动手能力和思维能力，尝试对数据结构与算法实验项目进行重新设计，主要内容有：
针对编程基础较薄弱的学生，我们开发了数据结构与算法实验教学平台，学生在该平台上可获知实验相关的更多内容，通过平台引导学生重点回顾程序设计语言的基础知识，特别是数组和指针等有关操作。通过这些辅助手段，使学生对将要编写程序的一些语法和程序规则有所复习和掌握。还可通过平台对实验原理的动画演示，得到帮助和启发，从而更好更快地完成实验内容。
每个实验内容以章节为单位安排，依据实验教学目的，针对计算机相关专业所要达到的不同实验教学目标，以及考虑学生个体差异，每个实验项目都设置基础必做题和附加选做题两部分内容。这两类实验都需要紧密结合理论教学。必做题相对简单，目的在于帮助学生掌握基础知识。对于该部分题目，学生容易完成，能提高学生学习积极性并增强学习信心；选做题针对学有余力的学生，各个实验项目中的必做题均设计详细的实验准备内容，用于引导学生更好地进行实验前预习准备工作；主要在于培养和鼓励学生的学习兴趣和扩大知识面，进一步培养学生应用能力和创新意识，保证基础弱的同学学习兴趣，也提高了编程能力强的同学动手能力。例如，与线性表一章理论教学相配合的实验项目是多项式加减法，这个实验是对线性链表的建立、插入、删除、遍历等进行综合运算，对数据结构与算法第一实验内容来说稍有难度，可作为选作题或增加实验学时。在与栈一章理论教学相配合的实验项目是迷宫，这部分实验内容要求掌握回溯法和栈的基本运算等知识，有一定难度；用括号匹配作为必做题，能培养学生独立钻研，有助于学生解决问题能力的训练。
四、实验教学方法探究
实验前学生必须先预习和熟悉实验教学平台，了解实验内容的目的和要求，理解算法，描述语言的语法，查看相关资料，写预习报告。
通过多年实验教学中实验完成情况分析，软件工程专业的学生语言掌握较好，大部分学生能按时完成实验项目，其它专业的学生实验完成情况较差；由此，实验编程语言可以因学生而异，除软件工程专业的学生采用面向对象程序设计C++外，其它专业主要采用C语言描述，并且可增加前期语言学习时间。只有编程语言掌握扎实，数据结构与算法实验才能很好地完成。
开发数据结构与算法实验网络教学平台系统，该平台主要包含有课程介绍、在线课程、互动学习、下载资料等模块。有针对性地对每一个实验项目进行详细讲解和实验原理分析的动画演示，将抽象的数据结构问题制作为教学动画，借助形象的案例理解抽象的概念。教学内容利用Web页面为基本元素出现在站点中，学生通过访问站点来进行交互式学习。以辅助学生自主学习为主要目的，解决学生实验时无从下手的局面，启发学生思维，促进学生程序设计能力的提高。平台系统流程图如图1所示。
在线课程是教学平台核心部分，也是学生对数据结构与算法实验加深理解的重要环节，该平台从实验预习，到实验原理算法的演示，再通过在线课堂的视频教学、在线测试题训练及各种原理进行拓展教学。为了方便学生学习较抽象的数据结构与算法，能顺利进行程序编写，该教学平台还包含有18个flash动画用于原理算法演示，主要包括栈和队列、线性表、递归、查找与排序、树、图等内容，每个flash动画都有实验原理及主要代码实现过程，能更加形象展示数据结构的原理。例如：栈是一种先进后出的数据结构，在对栈原理进行动画设计时，根据用数组实现栈的特点，采取对栈先进行初始化的代码模块来对栈进行初始化，之后运行相应代码模块观察压栈出栈过程，同时还能观察到栈中数据的变化。在大部分flash动画演示过程中，flash页面左侧是代码部分，能体现当前执行的代码，并与右侧的动画演示及讲解分析一一对应。演示过程中如用户需要重新开始，还可点击“重新开始”按钮。这些flash动画演示将代码与动画有机的结合在一起，将抽象的代码转换为有形的动画，大大方便学生学习和对实验内容的理解。
如对栈原理进行动画演示的flash点击界面中压栈代码动画效果，该动画效果包括等待入栈的数字入栈的动画效果和位于等待区域的数字前移的动画效果。等待入栈的数字、入栈的动画效果和位于等待区域的数字前移的动画效果如图3所示。
图3 压栈的动画效果图
该平台互动学习是一个教师和学生互动的场所，实现动态交互的功能，教师能添加、更改、删除各种资源，学生、教师可以查看各种资源库里的资源。同时，学生可从平台上下载练习题和测试练习题资料，练习题有主要算法描述，可帮助学生进一步理解每个章节的算法原理，测试练习题有自动报错功能。
五、改革数据结构实验考核方式
让学生对以前所做实验作一个分析和总结。具体操作方案如下：首先将学生自由分组，小组成员共同从以前做过的实验项目选做题中选择一个进行程序的分析设计和编码实现，要求考虑程序的编写规范，程序的执行效率等方面。考核时，由实验教师从该小组随机抽取学生到讲台进行讲解和演示，根据程序完成情况和学生演示情况，决定该小组成员的平均得分，而每位学生的具体得分由小组成员内部根据该学生在该程序实现中的工作情况决定。通过这种方式，能培养学生的团队意识，达到互学互助的效果，同时也锻炼了学生的表达能力。
数据结构与算法实验环节教学改革的创新之处在于依托一门编程语言以及所开发的实验教学平台，因材施教，根据不同专业实际情况，综合考虑进行实验项目、实验内容和实验准备的合理设置，帮助学生在实验课上找到自己的最好学习方式，提高实验教学质量。
【参考文献】
[1]吴兵.高校计算机文化基础课程网络学习题库的研发[J].实验技术与管理，2011（2）
[2]朱洪浩.数据结构课程“工程化”实践教学模式研究[J].赤峰学院学报（自然科学），2013（15）
[3]马晓波，王翠茹.《数据结构》实践教学改革探讨[J].内蒙古农业大学学报（社会科学版），2010（02）
[4]赵耀红，孙宇.数据结构实验教学的实践与探索[J].长春大学学报，2012（04）
《算法与数据结构》教学大纲 篇4
一、使用说明
（一）课程性质
《数据结构》是一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的先修课程为C程序设计或C++程序设计。
（二）教学目的
学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，要求学生会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。
（三）教学时数
课堂讲授每周4学时，18周，共72学时。
（四）教学方法
本课程将采用课堂讲授及课堂讨论相结合的交互式教学法，同时辅以必要的上机操作实践。
（五）面向专业
计算机科学与技术专业。
二、教学内容
第一章 绪论
（一）教学目的要求
介绍数据结构的一些基本概念，算法的时间复杂度和空间复杂度的分析方法，抽象数据类型的定义和使用以及算法的描述方法。掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。
（二）教学内容
主要内容：数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。抽象数据类型。算法时间复杂度和空间复杂度的分析。
教学重点：有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。
教学难点：算法时间复杂度和空间复杂度的分析。
第一节
一、非数值计算
二、数据结构课程内容的历史演变
三、数据结构研究范围
第二节
一、数据
二、数据结构
三、数据类型
四、抽象数据类型
五、多型数据类型
第三节
一、固有数据类型
抽象数据类型的表示与实现
基本概念和术语 什么是数据结构
二、数据抽象
三、抽象数据类型的描述语言
第四节
一、算法
二、算法设计的要求
三、算法效率的度量
四、算法的存储空间需求
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
4学时。
第二章 线性表
（一）教学目的与要求
介绍线性表的基本概念和类型定义，对顺序表和单链表的常用操作方法及其程序实现，循环链表和双向链表的定义和它的插入、删除等操作方法。掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。
（二）教学内容
主要内容：线性表的基本概念和类型定义，线性表的顺序存储结构，线性表的链接存储结构：（1）单链表的查找、插入和删除；（2）循环链表；（3）双向链表。
教学重点：在顺序表和链表上各种基本算法的实现及相关的时间性能分析。
教学难点：用所学的基本知识设计有效算法解决与线性表相关的应用问题。链表要分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针以及循环链表、双向链表的特点等。
第一节
一、线性表的定义
二、线性表的基本操作
第二节
一、顺序表
二、顺序表上基本运算的实现
三、顺序表应用举例
第三节
一、线性链表
二、循环链表
三、双向链表
四、静态链表
第四节 一、一元多项式的数学表示 二、一元多项式的计算机表示
三、抽象数据类型：一元多项式的定义
四、抽象数据类型：一元多项式的存储结构
五、抽象数据类型：一元多项式的基本操作算法实现
（三）教学方法与形式
一元多项式的表示及相加 线性表的链式存储表示和实现 线性表的顺序存储表示和实现
线性表的类型定义 算法和算法分析 课堂讲授、多媒体课件。
（四）教学时数
8学时。
第三章 栈和队列
（一）教学目的与要求
介绍栈和队列的定义，顺序和链接存储的栈和队列的各种运算的方法及其程序实现。掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现。
（二）教学内容
主要内容：栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法，栈的应用举例，队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。
教学重点：栈和队列在两种存储结构上实现的基本运算。教学难点：递归的实现、循环队列中对边界条件的处理。
第一节
一、抽象数据类型栈的定义
二、栈的表示和实现
第二节
一、数制转换
二、括号匹配的检验
三、表达式求值
第三节
一、函数调用与栈
二、递归调用栈的变化
第四节
一、抽象数据类型队列的定义
二、链队列--队列的链式表示和实现
三、循环队列--队列的顺序表示和实现
第五节
一、优先级队列的概念
二、优先级队列的存储表示和实现
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
4学时。
第四章 串
（一）教学目的与要求
介绍串的基本概念和操作，串的存储结构以及基本操作的算法实现。掌握串的基本概念和操作，掌握串的存储结构以及基本操作的算法实现。
（二）教学内容
主要内容：串的类型定义，串的表示和实现，正文模式匹配，正文编辑——串操作应用举例串的类型定义。
教学重点：串类型定义中各基本操作的定义以及串的实现方法。教学难点：利用串的基本操作来实现串的其它操作。
优先级队列 队列 栈与递归的实现 栈的应用举例
栈
第一节
一、串的定义
二、串的基本操作
第二节
一、定长顺序存储表示
二、堆分配存储表示
三、串的块链存储表示
四、字符串操作的实现
第三节
二、模式匹配的一种改进算法
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
4学时。
串的类型定义
串的表示和实现
字符串的模式匹配
一、求子串位置的定位函数Index（S，T，pos）
第五章 数组和广义表
（一）教学目的
介绍数组的基本概念和基本操作的算法实现；稀疏矩阵的定义和各种存储结构，稀疏矩阵的转置和相加的方法并了解其算法；广义表的定义、存储结构和求广义表的长度及深度的算法，建立广义表和输出广义表的方法并了解其算法。掌握数组的基本概念和基本操作的算法实现；掌握稀疏矩阵的定义和各种存储结构，掌握稀疏矩阵的转置和相加的方法并了解其算法；掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握建立广义表和输出广义表的方法并了解其算法。
（二）教学内容
主要内容：稀疏矩阵的定义、存储和运算，广义表的定义、存储和运算串的类型定义。教学重点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。教学难点：特殊矩阵的压缩存储，以及稀疏矩阵的三元组顺序表示。
第一节 第二节
一、数组的存储方式
二、数组元素存储位置的计算
三、基本操作的实现
第三节
一、特殊矩阵
二、稀疏矩阵
第四节
一、广义表的基本概念
二、广义表的三个重要结论
第五节
一、头尾链表存储表示
二、扩展线性链表存储表示
第六节
广义表的递归算法 广义表的存储表示 广义表的定义 矩阵的压缩存储 数组类型 数组的顺序表示和实现
一、求广义表的深度
二、复制广义表
三、建立广义表的存储结构
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
6学时。
第六章 树和二叉树
（一）教学目的与要求
介绍树的定义、性质、存储结构及遍历算法，握二叉树的各种遍历方法及其实现，二叉树的其他操作方法及实现，树、森林和二叉树的转换方法，哈夫曼树的定义和构造哈夫曼树的方法，哈夫曼树编码的方法。掌握树的定义、性质、存储结构及遍历算法，熟练掌握二叉树的各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，掌握树、森林和二叉树的转换方法，掌握哈夫曼树的定义和构造哈夫曼树的方法，了解哈夫曼树编码的方法。
（二）教学内容
主要内容：树的定义、性质和表示方法，二叉树的定义、性质和存储结构，二叉树的各种遍历方法及实现，建立二叉树、输出二叉树、求二叉树深度等的操作方法及实现，树的存储结构，进行先根遍历、后根遍历和按层遍历的方法及实现，进行树与二叉树的转换方法，哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的方法。
教学重点：二叉树和树的遍历及其应用。
教学难点：实现二叉树和树的各种操作的递归算法。
第一节
一、树的定义
二、森林的定义
三、树的抽象数据类型定义
第二节 一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构
第三节
一、遍历二叉树
二、线索二叉树
第四节
一、树的存储结构
二、森林与二叉树的转换
三、树和森林的遍历
第五节
一、最优二叉树（赫夫曼树）
二、赫夫曼编码
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
10学时。
最优树和赫夫曼编码
树和森林
遍历二叉树和线索二叉树
二叉树
树的定义和基本术语
第七章 图
（一）教学目的与要求
介绍图的定义和术语；图的存储结构及深度和广度优先搜索方法及其实现；图的生成树的概念，求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；拓扑排序的方法并了解其实现算法；计算关键路径的方法及其实现算法。掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索方法及其实现；掌握图的生成树的概念，掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法；掌握拓扑排序的方法并了解其实现算法；了解计算关键路径的方法并了解其实现算法。
（二）教学内容
主要内容：图的定义和术语，图的邻接矩阵、邻接表和边集数组表示，图的深度和广度优先搜索遍历，图的生成树和最小生成树，拓扑排序。
教学重点：图在邻接矩阵与邻接表上实现的遍历算法(DFS和BFS)。教学难点：基于遍历算法的应用。
第一节
一、图的定义
二、无向图
三、有向图
四、连通图
五、生成树
第二节
一、数组表示法
二、邻接表 三、十字链表
四、邻接多重表
第三节
一、深度优先搜索
二、广度优先搜索
三、连通分量
第四节
一、Kruskal算法
二、Prim算法
第五节
一、拓扑排序
二、关键路径
第六节
一、从某个源点到其余各项点的最短路径
二、每一对顶点之间的最短路径
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
12学时。
最短路径 有向无环图及其应用
最小生成树 图的遍历 图的存储表示 图的定义和术语
第八章 查找表
（一）教学目的与要求
介绍顺序表查找和有序表查找的方法及实现；二叉排序树和平衡二叉树的定义、对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；B树的定义，查找、插入和删除元素的方法。熟练掌握顺序表查找和有序表查找的方法及实现；掌握二叉排序树和平衡二叉树的定义、熟练掌握对二叉排序树和平衡二叉树进行插入、删除和查找的方法和实现。掌握哈希表的定义，构造哈希函数的多种方法，以及处理冲突的方法；了解B树的定义，查找、插入和删除元素的方法。
（二）教学内容
主要内容：顺序查找和二分查找，索引查找和分块查找，散列查找，动态查找树表。教学重点：顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。
教学难点：二叉排序树的删除算法。
第一节
一、顺序表的查找
二、有序表的查找
三、静态树表的查找
四、索引顺序表的查找
第二节 一、二叉排序树
二、平衡二叉树
三、动态的m路搜索树
四、B树和B+树基本概念
第三节
一、什么是哈希表
二、哈希函数的构造方法
三、处理冲突的方法
四、哈希表的查找及其分析
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
10学时。
第九章 内部排序
（一）教学目的与要求
介绍插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，快速排序、堆排序、二路归并排序的方法及其实现，各种排序方法的稳定性、时间复杂度和空间复杂度。掌握插入排序、交换排序、选择排序、快速排序、归并排序、基数排序的方法及其实现，熟练掌握快速排序、堆排序、二路归并排序的方法及其实现，掌握各种排序方法的稳定性、时间复杂度和空间复杂度。
（二）教学内容
主要内容：排序的概念，直接插入排序，冒泡排序和快排序，直接选择排序和堆排序，归并排序。
哈希表 动态查找表 静态查找表 教学重点：插入排序(直接插入、折半插入)、交换排序（冒泡、快速排序）、选择排序（直接选择、堆）、2-路归并排序。
教学难点：快速排序partition算法的应用和堆的调整。
第一节
一、稳定的排序方法
二、内部/外部排序
三、内部排序种类
四、排序中的基本操作
五、排序数据的存储方式
第二节
一、直接插入排序
二、其他插入排序
三、希尔排序
第三节
一、起泡排序算法
二、快速排序算法
第四节
一、简单选择排序
二、树形选择排序
三、堆排序
第五节 第六节
一、多关键字的排序
二、链式基数排序
第七节
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
10学时。
第十章 文件
（一）教学目的与要求
介绍文件和记录的基本概念以及基本操作。掌握文件和记录的基本概念以及基本操作。
（二）教学内容
主要内容：基本概念，顺序文件，索引文件，索引顺序文件，散列文件，多关键码文件。教学重点：各种文件的结构特点及其适用场合。教学难点：各种文件的结构特点及其适用场合。
第一节
一、文件及其类别
二、记录的逻辑结构和物理结构
三、文件的操作
四、文件的物理结构
第二节
一、顺序文件的定义
顺序文件 基本概念
各种排序方法的综合比较
归并排序法 基数排序 选择排序法 交换排序法 插入排序 排序的定义和方法
二、顺序文件的优缺点
第三节
一、索引文件的定义
二、索引文件的特点
第四节
一、ISAM文件
二、VSAM文件
第五节
一、散列文件的定义
二、散列文件的特点
第六节
一、多重表文件
二、倒排文件
（三）教学方法与形式
课堂讲授、多媒体课件。
（四）教学时数
4学时。
三、考核方式
本课程的考核采用闭卷考试的方式，课程的总评成绩由平时成绩、实验成绩和期末考试成绩三部分组成，其中平时成绩占总评成绩的10%，实验成绩占总评成绩的30%，期末考试成绩占总评成绩的60%。
四、教材选用
1、殷人昆，陶永雷，谢若阳等：《数据结构（用面向对象方法与C++语言描述）》，清华大学出版社，2007.6年第二版。
2、严蔚敏，吴伟民：《数据结构（C语言版）》 及《数据结构题集（C语言版）》，清华大学出版社，2003年第一版。
多关键码文件 散列文件 ISAM文件和VSAM文件
数据结构与算法课程学习总结报告 篇5
数据结构与算法是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。通过学习，先报告如下：
一、数据结构与算法知识点
本学期学的《数据结构与算法》这本书共有十一个章节：
第一章的内容主要包括有关数据、数据类型、数据结构、算法、算法实现、C语言使用中相关问题和算法分析等基本概念和相关知识。其中重点式数据、数据类型、数据结构、算法等概念；C语言中则介绍了指针、结构变量、函数、递归、动态存储分配、文件操作、程序测试与调试问题等内容。
第二章主要介绍的是线性逻辑结构的数据在顺序存储方法下的数据结构顺序表（包括顺序串）的概念、数据类型、数据结构、基本运算及其相关应用。其中重点一是顺序表的定义、数据类型、数据结构、基本运算和性能分析等概念和相关知识。二是顺序表的应用、包括查找问题（简单顺序查找、二分查找、分块查找）、排序问题（直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、归并排序）、字符处理问题（模式匹配）等内容。本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。
第三章主要介绍的是线性逻辑结构的数据在链接存储方法下数据结构链表的相关知识。主要是单链表、循环链表的数据类型结构、数据结构、基本运算及其实现以及链表的相关应用问题，在此基础上介绍了链串的相关知识。在应用方面有多项式的相加问题、归并问题、箱子排序问题和链表在字符处理方面的应用问题等。本章未完全掌握的是循环链表的算法问题和C的描述。
第四章介绍在两种不同的存储结构下设计的堆栈，即顺序栈和链栈的相关知识，了解堆栈的相关应用，掌握应用堆栈来解决实际问题的思想及方法。本章主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。本章堆栈算法思想较为简单，所以能较好掌握。
第五章主要介绍顺序存储和链接存储方法下的两种队列、顺序（循环）队列和链队列的数据结构、基本运算及其性能分析以及应用。顺序队列(重点是循环队列）和链队列的概念、数据类型描述、数据结构和基本运算算法及其性能分析等。本章同堆栈有点类似，算法思想较为简单，所以能较好掌握；但难点重在循环队列队空、队满的判断条件问题。第六章“特殊矩阵、广义表及其应用”将学习数组、稀疏矩阵和广义表的基本概念，几种特殊矩阵的存储结构及其基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。本章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。
第七章“二叉树及其应用”的知识结构主要是：非线性结构数据二叉树的定义、性质、逻辑结构、存储结构及其各种基本运算算法，包括二叉树的建立、遍历、线索化等算法。在此基础上，介绍二叉树的一些应用问题，包括哈夫曼编码问题、（平衡）二叉排序树问题和堆排序问题等。
第八章“树和森林及其应用”介绍树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树之间的转换算法等，在此基础上介绍树的应用---B-树，应用B-树来实现数据元素的动态查找。本章基本掌握树和森林的概念和性质、数据结构、树的基本算法及性能分析，树和二叉树间的转换及其算法，并用应用B-树来实现数据元素的动态查找未能掌握好。
第九章“散列结构及其应用”是逻辑结构“集合型”的数据元素在散列存储方法下的数据结构及其应用知识内容。主要介绍散列函数的概念、散列结构的概念、散列存储结构的概念---散列表、散列函数和散列表中解决冲突的处理方法---开放定址法、链地址法以及散列表的基本算法及其性能分析。本章概念较为多，所以掌握不太好。
第十章“图及其应用”是逻辑结构为“图形”的数据结构及其应用知识内容，主要介绍图的定义和基础知识，图的2种存储结构。图的基本算法以及图的典型应用问题（最小生成树、最短路径、拓扑排序和关键路径等）。
二、对各知识点的掌握情况
我对各知识点的掌握情况总结如下：
第一章不太难，能基本掌握。但关系全书的时间性能分析有些未能全部掌握。第二章本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。本章未掌握的为希尔排序、快速排序、归并排序的时间复杂度分析。第三章，对链表掌握还好，对其数据结构进行了分析，有循环链表，掌握的不是很好，对其中一些用法不熟练。第四章堆栈，本章堆栈算法思想较为简单，所以能较好掌握，但表达式计算问题未掌握好的。第五章的循环队列队空、队满的判断条件问题掌握的不是很好。第六章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构。第七章对二叉树掌握较好，其概念，存储，遍历有很好的掌握。就是对二叉排序树有点生疏，它的生成算法不是很会。第八章树树与二叉树之间的转换，森林与二叉树的转换算法思想基本掌握。第九章散列的一些知识，没有深入学习，大概了解了散列存储结构散列表，散列函数，冲突的处理方法。第十章了解了图的逆邻接表的存储结构，关键路径求解算法未能掌握好，不能灵活运用图的不同数据结构和遍历算法解决复杂的应用问题。
三、学习体会
通过学习数据结构与算法，让我对程序有了新的认识，也有了更深的理解。同时，也让我认识到，不管学习什么，概念是基础，所有的知识框架都是建立在基础概念之上的，所以，第一遍看课本要将概念熟记于心，然后构建知识框架。并且，对算法的学习是学习数据结构的关键。在第二遍看课本的过程中，要注重对算法的掌握。对于一个算法，读一遍可能能读懂，但不可能完全领会其中的思想。掌握一个算法，并不是说将算法背过，而是掌握算法的思想。我们需要的是耐心。每看一遍就会有这一遍的收获。读懂算法之后，自己再默写算法，写到不会的地方，看看课本想想自己为什么没有想到。对算法的应用上，学习算法的目的是利用算法解决实际问题。会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。
四、对课程教学的建议
1、感觉上课时的气氛不是很好，虽然大部分人都在听，可是效果不是很好。所以希望老师能在授课中间能穿插一些活跃课堂氛围的话题，可以是大家都非常关心的一些内容，这样既让大家能在思考之余有一个放松，也能够提高学生的学习积极性和学习效率。
2、学习的积极性很重要，有时候我们花了很长时间去写实验报告，也很认真的去理解去掌握，可是最后实验报告可能就只得了一个C，抄的人反而得A，这样的话很容易打击学生的积极性，在后面的实验报告中没动力再去认真写。所以希望老师能在这方面有所调整。
数据结构与算法 篇6
实训报告
题 目：凸多边形直径计算研究与实现 完 成 人： 专业班级： 学 号： 指导教师：
****年**月**日
广西科技大学计算机学院
计算机学院 班 数据结构与算法实训报告 题目：凸多边形直径计算研究与实现
说明：1.请按实训要求完成实训任务，鼓励提出自己的算法，或是在已有算法基础上进行改进，以提高计算速度；2.程序代码不能低于500行；3.每位同学须完成实训报告，并打印上交；4.每位同学须参加实训答辩。5.答辩成绩占40％，平时成绩占30％，文档书写占30％。1.生成一个凸多边形
1.1生成来自同一个圆上的点集
阶段一（一次）
对于同一个圆上的点集，按顺时针（逆时针）顺序依次连接这些顶点，即可得到一个凸多形。
思考：是否可以通过随机生成圆上的点，来得到凸多边形的顶点集？ 参考代码：
void generate_circle_points(int n,int seed){ double theta;double temp_x,temp_y;int i;srand(seed);for(i = 1;i <= n;i++){ theta =(2*PI / double(n))* i;//将圆等分的生成圆上点
temp_x = cos(theta);temp_y = sin(theta);Point[i][0]=temp_x*350+500;Point[i][1]=temp_y*250+300;} Point[0][0]=Point[n][0];Point[0][1]=Point[n][1];} 完成后的截图示例：
图1 生成圆上的点
1.2编程实现已有的凸壳（凸包）算法
阶段二（两次）
利用中国知网下载凸壳（凸包）计算的相关文献，任选择一篇文献编程实现；也可从图书馆查阅相关书籍，寻找简单的凸壳（凸包）计算的方法，编程实现。
完成后的截图示例：
图2 凸壳计算
2.实现文献中的凸多边形直径计算 阶段三（三次）
要求编程实现指定文献[1]中的凸多边形直径计算算法。完成后的截图示例：
图3 待计算的点集
图4 凸多边形直径值
3.利用数据结构中的算法对文献中的方法进行改进
阶段四（两次）：上交改进算法的思想。阶段五（两次）：实现改进算法。实验对比
为验证本文算法有效性，进行了大量实验，算法均能正确地计算出凸多边形直径，并分别与文献[1]、[2]、[3]、[4]进行对比实验，实验表 明，算法稳定性好，运行效率高。同时为验证本文对找首个对跖点对算法改进的有效性，与文献[1]、[4]算法进行了实验对比，结果表明，算法非常有效，运行效率非常高。限于篇幅，这里仅举出其中一例。该例实验的方法是通过随机函数自动生成以半径为250个象素宽的圆周上的点，点坐标值采用浮点型，则以这些点所构成的多边形必定是凸多边形，测得对比实验运行时间如表1所示，单位为1/10000秒。4.撰写实训报告
阶段六（一次）：撰写并上交实训报告。
一、本文涉及的知识点有：
宏定义、全局变量、二维数组、一维数组、for循环、自定义头文件、指针
二、功能要求：
1、生成来自同一个圆上的点集
对于同一个圆上的点集，按顺时针（逆时针）顺序依次连接这些顶点，即可得到一个凸多形。
2、实现文献中的凸多边形直径计算，还要包括计算其运行时间。
3、算法设计
void sift(double A[],int s, int m){ //输出以A[m]为根节点的子树为堆
double t;int j;t=A[s];j=2*s;while(j<=m){ if(j A[s]=A[j]; s=j; j=2*j;} else j=m+1;} A[s]=t;} void heapsort(double A[],int n){ /*A是待排序数组（从下标1开始存储，最大元素下标为n），n为数组的元素的个数*/ int i,k;double temp;k=n/2;for(i=k;i>0;i--)//无序序列建堆 sift(A,i,n);for(i=n;i>1;i--){ //堆顶元素换到最后 temp=A[1]; A[1]=A[i]; A[i]=temp; sift(A,1,i-1);//调整 建堆 } } void generate_circle_points(int n,int seed){ //随机生成圆上的点 double angle[MaxLen+1];double temp_x,temp_y; int i,k;CString str; srand(seed); for(i = 1;i <= n;i++){ angle[i] =((double)rand()/ RAND_MAX)* 2 * PI;/*将圆随机的生成圆上点*/ for(k = 1;k < i;k++) { if(angle[k]==angle[i] || angle[k]==angle[i]+ 2*PI || angle[k]+ 2*PI==angle[i])//将重复的点去掉 { i--; break; } } } heapsort(angle,n); for(i = 1;i <= n;i++){ temp_x = cos(angle[i]); temp_y = sin(angle[i]); Point[i][0]=temp_x*200+400; Point[i][1]=temp_y*200+400;} Point[0][0]=Point[n][0];Point[0][1]=Point[n][1];Point[n+1][0]=Point[1][0];Point[n+1][1]=Point[1][1];} double Calculate_Maxdist(int n){ //计算凸多边形上最远的两点的距离 int i=0,j=1,k,antips[MaxLen][2],ant=0,l,pi,pj;double pd,d,dc;while((Point[i+1][0]-Point[i][0])*(Point[j+1][1]-Point[j][1])-(Point[i+1][1]-Point[i][1])*(Point[j+1][0]-Point[j][0])>0)//当其面积之差大于0时 j++;k=j;while(!(i==k && j==n)){ dc=(Point[i+1][0]-Point[i][0])*(Point[j+1][1]-Point[j][1])-(Point[i+1][1]-Point[i][1])*(Point[j+1][0]-Point[j][0]);/*计算其两三角形的面积之差*/ if(dc<0) { i++; antips[ant][0]=i; antips[ant++][1]=j; } else if(dc>0) { j++; antips[ant][0]=i; antips[ant++][1]=j; } else i++;} pd=-1;for(l=0;l pi=antips[l][0]; pj=antips[l][1]; d=(Point[pi][0]-Point[pj][0])*(Point[pi][0]-Point[pj][0])+(Point[pi][1]-Point[pj][1])*(Point[pi][1]-Point[pj][1]); if(d>pd) pd=d;} return sqrt(pd);//返回计算结果 } void CConvexDiameterView::OnDraw(CDC* pDC){ /*画出生成来自同一个圆上的点集 按顺时针（逆时针）顺序依次连接这些顶点，即可得到一个凸多形。*/ CConvexDiameterDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);CClientDC pa(this);//自定义一个(this)指针 OnPrepareDC(& pa);// TODO: add draw code for native data here if(liulang==1){ int i; for(i=0;i pDC->Ellipse(Point[i][0]+4,Point[i][1]+4,Point[i][0]-4,Point[i][1]-4); CString pajiho; pajiho.Format(_T(“%d”),i+1);//输出点的序号 pa.TextOut(Point[i][0],Point[i][1],pajiho); for(int j=0;j { if(i>0) { //顺序两点相连 pa.MoveTo(Point[i-1][0],Point[i-1][1]); pa.LineTo(Point[i][0],Point[i][1]); //任意两点相连 // pa.LineTo(Point[j][0],Point[j][1]); } } } liulang=0;} //起点和末点链接 pa.MoveTo(Point[MaxLen-1][0],Point[MaxLen-1][1]);pa.LineTo(Point[0][0],Point[0][1]);} void CConvexDiameterView::OnAngleSign(){ // TODO: Add your command handler code here double Maxdis;generate_circle_points(MaxLen,100);/* 生成圆形上数据,第二参数为随机函数的种子*/ clock_t start_time, finish_time;//用于测试时间 double during_time=0.0;start_time = clock(); for(int i=0;i Maxdis=Calculate_Maxdist(MaxLen); finish_time= clock();during_time=((double)(finish_time-start_time)/ CLOCKS_PER_SEC)/xunhuancishu*10000;CString str;str.Format(“所花费的时间是%lf(万分之一秒)”,during_time);AfxMessageBox(str); str.Format(“最大距离为：%lf”,Maxdis);AfxMessageBox(str); liulang=1;Invalidate();UpdateWindow(); } 运行结果： 三、实训总结： 关键词：数据结构与算法,教学改革,课程建设 1. 引言 《数据结构与算法》课程是计算机类专业课程体系中一门重要的核心专业课程, 是各高校为相关专业学生开设的一门计算机专业必修课, 《数据结构与算法》教学的主要内容是研究数据的逻辑结构与存储结构, 继而研究数据之间的关系与各种运算的算法设计和实现, 是用来进行程序设计的计算机重要理论技术基础, 是一门集理论性、技术性和实践性于一体的课程。通过本课程的学习, 为学生学习后续程序设计语言和其它相关课程如操作系统、软件工程和数据库系统等课程打下基础, 同时也通过对学生程序设计与开发、分析和解决问题的能力的锻炼, 来培养学生的抽象思维和创造能力。我院自《数据结构与算法》精品课程申请以来, 注重理论与实践相结合, 多年来终坚持以教学为中心、以素质拓展为核心, 积极创新教育加强教学管理, 实行“厚基础”、“宽专业”的培养模式, 结合学生的实际情况, 不断开展教学改革, 不断引入新的教学内容, 加强教学模式的改进, 从算法设计入手对教学方法等教学因素进行积极深入研究, 搭建网络辅助教学平台, 为本课程的教学质量提高打下坚实基础, 取得了良好的教学效果。 2.《数据结构与算法》教学现状 随着计算机软硬件技术的发展和应用领域的扩大, 计算机所需要处理的对象和数据也越来越复杂, 同时也对其处理的效率也提出了更高的需求。《数据结构与算法》就是随着处理对象的复杂性而不断发展完善起来的一门课程, 作为计算机学科的一门综合性的专业基础课, 《数据结构与算法》在专业人才培养体系中占有非常重要的地位, 是一门承上启下的核心枢纽课程, 同时也是一门实践性很强的专业技术基础课。但是往往我们的教师在教学过程中局限于书本, 只会照本宣科, 眼界不够开阔。《数据结构与算法》课程核心主要就是学习算法思想的, 特别是算法的改进与创新, 理解算法的意义主要就是用来解决实际问题。一些教师的教学方法过于单调, 多只是对知识进行灌输, 在教学中只注重概念, 忽视算法的讲解, 同时所选的实例和在实验课上布置的内容只是简单的验证题, 对解决实际问题的一些经典算法讲解太少, 使得部分学生在学习过程中, 只知道照搬而不能融会变通, 无法真正形成自己的思维。由于本课程内容比较抽象, 有时教师即使花了很多的时间准备, 也会出现学生看似明白算法思想, 可是却无法真正去通过编程去实现算法, 从而使学生缺乏一定的感性认识, 学习兴趣缺失。 同时作为实践性很强的计算机类专业基础课, 《数据结构与算法》教学中必然离不开实践。而大部分高校的上机实验课程一般多采用验证性实验, 作为课程理论知识的补充, 所布置的多都是与课堂教学内容相关的一些小型练习题, 让学生去完成程序的相关设计与调试。但由于教材中多半都是已有现成的算法和代码实现, 学生也一般只是照搬, 从而学生本身的思维能力并没有得到很有效的培养与锻炼。同时这些小型的练习题一般都可以由学生独自完成, 缺乏了对学生团队协作能力的培养。 3. 积极教学改革、加强精品课程建设 3.1 注重前导与后继课程、完善课程体系 构建“厚基础”、“宽纵深”的专业核心课程体系。计算机类专业知识核心基础课程主要由离散数学、编译原理、C语言程序设计、计算机组成原理、数据结构与算法、操作系统、数据库原理、面向对象程序设计这8门课程组成, 由此支撑起各个计算机类相关专业的核心基础课。我院以此8门课程来建立计算机类相关专业的核心基础课程群, 如图1所示。 多年来, 我院一直积极加强课程群的建设, 以培养学生综合运用计算机相关知识的能力出发, 积极打破课程之间的壁垒, 积极强化课程之间的联系, 积极以数据结构与算法为核心, 将一些相关内容积极连通在各个课程的讲授中注重前后课程的继承与知识之间的联系, 同时算法的理念贯穿前后课程, 特别是程序设计中的运用, 以此来努力培养学生的思维与创新能力, 从而将课程群的教学内容整合成一个大的知识体系。同时在实践课程上, 我们也注重联系, 除了有关课程各自单独的实验课外, 在相关后继程序设计课程结束后, 我们还安排了一个综合的课程设计实践教学, 将课程群中与数据结构联系比较紧密的课程整合起来, 布置一个大作业, 要求学生分组团队协作完成各自的项目, 以此来培养锻炼学生的综合素质能力。 3.2 加强团队建设、注重师资培养 团队建设与师资培养也是课程建设的关键。目前我院计算机中心引进归国留学人才一名, 教学团队共有主讲教师8人, 其中博士3人, 副高以上职称人员6人, 均由3、40岁的中青年教师组成。大家精力充沛, 工作热情高昂, 在管理上制定了相关的规章制度和对应奖惩措施。坚持教学与科研相结合, 以各级教科研项目为依托, 不断提高科研水平和能力。以博士牵头积极带队进行教科研, 积极提高整个中心的教科研水平。同时以精品课程建设为契机严格管理, 加强教学研究, 积极集体备课, 定期相互观摩学习吸取好的教学方法与经验, 积极改善教学模式与利用先进教学手段。在教学中, 对青年教师积极进行集中备课, 统一课件, 相互督促, 同时开展相互之间的良性的讲课比赛。这些制度的实施保证了教学工作的正常开展和教学质量的不断提高。多年来我们教学团队的教学效果优异, 学生学评教满意度超过90%, 多次在学校的教学质量评价中获得优异成绩, 在全校的“园丁杯”教学竞赛中二次获得全校二等奖等。 3.3 积极改革教学、加强教材建设 根据《数据结构与算法》课程教学大纲的要求, 从学生的特点出发, 我们积极改革教学内容, 从课程的知识体系入手, 依据数据结构的逻辑结构、存储结构去组织适当的教学内容。在各种抽象数据类型的基础上, 加强各种运算的讲解, 依据对应的算法, 结合一定实例加强算法的教授以此加深学生对相关算法的理解, 同时鼓励学生举一反三, 自行去改进与创新, 多多对现有算法进行积极思考。“兴趣”是最好的老师, 我们积极构建以学生为主体, 教师为主导的教学模式, 实现教与学的双边互动。现在随着教育的发展, 强调的是素质教育, 只有充分发挥学生的主观能动性, 才能有效培养学生依据算法去学好各种思维, 以此不断提高分析解决实际问题的能力。我们在教学中积极采用任务驱动的教学模式, 通过先期一些实际任务来引入对应相关理论知识的讲解, 在获取一定知识储备后再去解决问题来激发提高学生的学习兴趣, 并布置一些新的任务提出一些新的问题来激发学生的继续求知欲望从而使学生积极主动、能动地去喜欢学习。通过对新结构、新算法、新思想的不断学习, 逐步加深学生的知识储备, 慢慢拓宽学生的眼界。 精品课程建设的重要组成部分之一就是教材建设。由于计算机科学是一门快速发展的新兴科学, 数据结构与算法相关的理论、概念和常用算法也在不断的更新与发展。我们始终紧跟计算机科学技术发展的步伐, 在教材的选择上始终保持不断的更新。现在教材选用的版本为Java版本的, 方便学生适应后继课程与运用。同时我们积极建立动态教材和各种电子教材, 并列入教学计划和授课计划执行。我们编写了对应的课程讲义和各种PPT都面向学生公开, 同时新版的上机实验指导也已修订与编写完成。 3.4 改革实践教学与考核模式 《数据结构与算法》是一门要求具有相当实践能力的专业基础课, 我们制定的对应教学目标之一就是通过实践来巩固相关理论知识, 培养学生的程序设计能力养成良好编程风格。具体在多年的实践中, 我们在教学计划里不断增加实践考核的内容, 现在学生的程序设计能力有了显著的提高。我们实践教学体系由基础验证型实验、综合设计型实验、综合性课程设计 (大作业) 来构成。其中基础验证型实验与理论课程讲授同步, 用于基本知识点的理解与验证;综合设计型实验是在一章结束或者是一个相对比较完整的知识体系结束时来对所学的内容进行一个完整性的综合训练;综合性课程设计一般是在《数据结构与算法》课程结束后, 给学生分组布置的以项目组来合作完成的大型程序, 用以培养学生的综合运用和团队协作的能力。在实践教学中, 我们积极以算法为核心对学生进行讲解, 转变学生的思想, 积极要求学生尝试对算法进行改进与研究, 努力使学生从一个程序设计的初学者慢慢转变成为具备一定能力的入门者, 进而精通。现我院成立的自主学习中心拥有6个标准教学实验室和4个学生自主上机实验室共600余台电脑, 最大程度地保障了实践教学的顺利实施。 在课程的考核方面, 根据不同的教学环节, 我们采用不同的考核方式和成绩评定模式, 将平时学生的验证型实验报告与综合型实验报告相结合做为平时成绩的一部分来成为考核依据。同时我们采用了一套新型的考试系统来在每学期末进行上机考核作为总成绩的一部分。这样整个课程成绩=期末上机考试成绩×60%+验证型实验报告×20%+综合型实验报告×20%。最后的综合性课程设计单独作为选修课计算学分 (以激励学生认真完成) 。通过这样一系列手段来促进学生重视实践教学, 激励学生积极主动去学习, 从而真正提高学生的编程能力与综合素质。 4. 结语 《数据结构与算法》课程具有理论基础较强、实践应用性突出等特点, 是计算机类专业的一门核心基础课, 是学习后续课程的基础。我院自开设该课程以来, 积极以培养“创新型应用人才”为目标对其课程从课堂教学与实践教学两方面不断进行建设与晚上, 从课程的内容体系、教学模式、教学方法等方面进行创新与实施。精品课程建设是一项长期而艰巨的任务, 需要适应当前时代的变化不断改革和完善课程的各个方面, 进一步提高教学质量和水平, 强化教学的各个环节, 为学生提供更多更好的优质资源, 培养出更多更好符合国家需要的应用型技术人才。 参考文献 [1]刘晓静, 黄维通, 王晓英.西部地区CDIO理念下的数据结构与算法课程建设[J].计算机教育, 2013, 17:107-111. [2]钱红兵, 唐发根.“算法与数据结构”课程教学体系的建设[J].计算机教育, 2009 (17) :65-66. 关键词:数据结构与算法;综合性实验;设计性实验 一、引言 在计算机科学与技术、软件工程等专业中,《数据结构与算法》课程具有较强的实践性,因此实验教学是该课程教学过程中的一个非常重要的环节。在以往的实验教学中,学生都是按照已经设计好的实验要求和步骤进行着验证性的实验,学生一般是被动地接受或机械式地编程,以完成实验讲义中的验证或孤立的单元实验。这种实验教学模式使得学生缺乏主动性和独立思考问题的能力,不利于他们综合素质的提高和自主创新能力的培养。为了克服这些不足,使学生真正能把理论知识灵活运用到实践当中,我们开设了《数据结构与算法》课程综合性、设计性实验项目并立项进行实践研究,通过两三年的实践,取得了一些经验和成果,学生的实践能力也有了较大提高。 二、综合性、设计性实验项目的实践环节 1.实验项目的选择。 通过《数据结构与算法》课程的学习和前期验证性实践环节,学生已初步具备了进行综合性、设计性实验的能力。为进一步提高学生的设计能力和编程能力,我们设计了4个综合性、设计性实验项目供学生选择: ①校园导游系统的设计(设计性); ②书管理系统的设计(综合性); ③哈夫曼编码/译码器(综合性); ④散列表的设计与实现(设计性)。 2.实验项目的内容。 校园导游系统的设计 问题描述: 设计一个校园导游程序,为来访的客人提供信息查询服务。 基本要求: ①设计你所在的学校的校园平面图,所含景点不少于15个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息,以边表示路径,存放路径长度等相关信息; ②为来访客人提供图中任意景点相关信息查询; ③为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短路径(静态或动态表示出来)。 图书管理系统的设计 问题描述: 设计一个图书管理系统完成图书管理基本业务。 基本要求: ①每种书的登记内容包括书号、书名、著作者和库存量; ②对书号建立索引表(线性表或树表)以提高查找效率; ③系统主要功能如下: 采编入库:新购一种书,确定书号后,登记到图书账目表中,如果表中已有,则只将库存量增加; 借阅:如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量; 归还:注销对借阅者的登记,改变该书的现存量。 用户管理。 数据存储(要求用文件实现数据存储)。 哈夫曼编码/译码器 问题描述: 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。 基本要求: ①随机抽取20个文本文件作为统计样本,统计这些文本文件中各字符的平均出现次数,作为权值,建立哈夫曼树及各个字符的哈夫曼编码; ②将用户输入或选择的待压缩文本文件利用①建立的编码表进行编码,生成压缩文件(后缀名.cod); ③输入一个待解压的压缩文件名称,并利用相应的编码表进行译码; ④显示指定的压缩文件和文本文件; ⑤(选作) 把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算实现真正的数据压缩,并求压缩比。 散列表的设计与实现 问题描述: 设计散列表实现电话号码查找系统。 基本要求: ①随机生成1万个记录,每个记录有下列数据项:电话号码、用户名、地址,每个数据项的内容都是随机生成的; ②分别以电话号码和用户名为关键字建立散列表(自行选择或构造合适的散列函数); ③采用双散列法解决冲突; ④查找并显示给定电话号码的记录; ⑤查找并显示给定用户名的记录。 3.预期目标。 进一步巩固和加深对《数据结构与算法》课程中基本知识的理解,熟悉各种逻辑结构及存储结构; 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; 培养学生从事软件开发的编程及创新能力; 提高学生综合运用所学的理论知识解决问题的能力; 训练用系统的观点和软件进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。 4.实验项目的组织与实施。 针对综合性设计性实验项目,安排学生自选项目并进行项目设计和开发,每个项目20学时,按照下面的项目开发设计步骤,最后完成课题的总体设计与实现。 项目分析 根据实验项目内容的要求,充分地分析和理解问题,明确问题要求做什么、解决什么问题、实现什么功能。 概要设计 对项目内容描述中涉及的操作对象,设计相应的数据结构,并按照以数据结构为中心的原则对模块进行划分,定义主程序模块和逻辑结构。逻辑设计的结果是每种数据结构的定义(包括数据结构的描述和每个基本操作的功能说明)。 详细设计 为各个数据结构设计相应的存储结构并写出各模块的算法。设计是编程中重要的一环,在“详细设计”过程中,引导学生结合总体设计制订合理的程序结构和算法,理顺各个模块之间的相互关系,将详细设计的结果用结构图及流程图清晰地描述出来,在本过程中,教师要尽可能帮助学生养成自己解决问题的习惯。 编程 将详细设计的结果进一步求精为程序设计语言程序。在该环节中,教师应指导学生按照规范的程序编写方法去编程,并指导学生按照大型软件中常用的调试方法对程序进行跟踪及改进。 结果分析 在编程过程中及结束后,形成学生、课题小组组长、指导教师三位一体的项目质量监控体系,做到对各个阶段的结果都能进行实时的检测,如有不足之处,小组内成员和学生自行研讨出合理的整改方案并对课题实施进行改进,直至达到功能要求。 5.项目总结。 主要包括学生实验项目总结心得、实验报告撰写,学生成绩的评定。 实验项目总结心得 在实验临将近结束时让学生共同讨论实验结果的正确性,讨论实验设计步骤的合理性,总结经验,进一步改善项目实施的方案及步骤。笔者认为,实验后的总结非常重要,是从理论到实践,再由实践到理论认识的进一步升华,也是使学生提高实验兴趣、锻炼并增解决实际问题的重要过程和手段。 实验报告撰写 学生实验报告一般应包含的内容是:实验题目、实验环境、实验目的、实验任务、数据结构描述、算法流程图表示、实验总结。 学生成绩的评定 教师根据学生的实验设计报告、学生的实际操作能力(程序检查)及学生的创新能力等几个方面综合评定,给出综合成绩。 三、实践的成果 1.对学生的影响。 经过近两年的实验教学实践,有超过70%的学生认为此次实验收获很大,大约80%的学生对这类实验取得的成果表示满意。从总体效果来看,学生通过综合性、设计性实验,提高了设计及编程能力。大部分学生认为《数据结构与算法》综合性、设计性实验项目的开展改变了以往传统的实践教学模式,内容新颖,提高了他们的编程兴趣和热情,对他们帮助很大。 2.对教师的促进。 《数据结构与算法》综合性、设计性实验的指导教师由计算机科学技术学院《数据结构与算法》课程的主讲教师和专业实验室的教师共同承担,我们认为,开展综合性设计性实验项目整合了多个知识环节,既能够帮助学生掌握知识的系统性和衔接性,理清程序设计的思路,促进知识的融会贯通;同时也给主讲教师带来新的挑战,能使教师总结在理论教学中的不足,进一步加强教学方法和内容的改革。 参考文献: [1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006. [2]唐册善.数据结构—C语言描述[M].北京:高等教育出版社,2003.数据结构与算法 篇7
数据结构与算法 篇8