《数据结构》实训课程教学大纲
课程名称:数据结构
学时25
适用专业:计算机应用
课程的地位,目的和任务
《数据结构》是专业基础课,计算机科学各领域(包括计算机系统结构部分和计算机应用部分)都要涉及到各种数据结构.通过本课程的练习,使学生在数据的逻辑特征和物理特征、数据结构的选择和应用,以及算法设计实现等方面加深对数据结构基本内容的理解和灵活应用.同时,在程序设计方法以及上机操作基本技能和科学作风方面受到比较系统严格的训练,培养软件工作所需要的动手能力.
二,课程与相关课程的联系与分工
本课程的先修课有《计算机程序设计》,《面向对象程序设计》,其主要内容有:数据结构和算法设计与分析的基本知识,各种基本数据结构的定义,存储结构,相应的算法以及应用,了解基本的数据结构与算法的关系.培养相关专业的学生结合实际应用,设计有效的算法和数据结构的能力.
三,实训内容与要求
理解有关数据结构的基本概念,不同数据类型的存储和基本操作的算法实现,理解数据类型的逻辑结构及物理存储结构, 通过自己设计,编程,调试,测试,能够基本掌握在不同存储结构下的算法实现及算法优化.
具体功能包括:
第一部分 线性表的应用:设计一个链表
实训要求:了解线性表的存储结构,
第二部分:栈的应用 迷宫的实现
实训要求:设计迷宫的存储结构 ,算法设计,实现输入迷宫图,输入入口和出口,程序自动输出走出迷宫的路径;其中要建立栈的基本操作函数的头文件;第四部分:遍历二叉树
实训要求:建立二叉树的存储结构,对其进行遍历,遍历的方法要求可以选则层序遍历,先序遍历,后序遍历的方法分别进行;
第五部分:图的应用:
实训要求:
1,建立图的不同的存储结构,(邻接矩阵,邻接表),在不同的存储结构下分别实现,图的拓扑排序算法;
2,实现最短路径的算法:
第六部分:排序和查找
实训要求:掌握顺序存储结构和链式存储结构下的不同排序方法
1,实现插入法排序
2,实现冒泡法的改进算法的排序
3,实现顺序结构下的查找算法;(有序表的折半查找,顺序查找)
实训课程学时分配
实训内容 学时分配 实训条件
讲课 实训
1线性表的应用实现 7
2栈的应用 4
3二叉树的操作6
5图的应用5
6排序与查找 3
合计 25
五,参考教材,实训指导书
参考教材一:《数据结构及应用算法教程 》
作者:严蔚敏 陈文博
出版社: 清华大学出版社
六,教学方法与考核方式
考核方式: 书面报告(50%),程序实现(50%),平时(10%),: 实训要求每个学生在两周课程设计结束时,上交内容,开发计划,各个题目的需求分析,存储结构的设计,算法的描述,测试数据,测试结果,算法改进分析,课程设计总结;
七,实训环境:visual c++ ,turbo c++.