《数据结构实验》教学大纲.doc

数据结构实验教学大纲课程名称：数据结构实验课程编码：084300507 总 学 时：36学时适用对象：电子信息科学与技术一、教学目的与任务数据结构是计算机几相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。二、教学基本要求数据结构在计算机科学中是一门综合性的专业基础课，是计算机专业的核心课程。它不仅是一般程序设计的基础，而且也是设计和实现编译程序、操作系统及其他系统程序和大型应用程序的重要基础。随着计算机在非数值计算领域的应用的不断壮大，数据结构的研究与实际应用也显得越来越重要。由于数据结构中有大量的复杂算法，因此数据结构实验课在数据结构教学中占有重要的地位。通过实验要求学生更好的巩固和掌握所学的内容。三、教学内容及要求实验一 抽象数据的学习实验目的： 掌握抽象数据的表示和实现方法。 熟悉高级语言的实现方法。 掌握抽象数据常见算法。实验仪器：计算机，打印机实验内容： 编写复数四则运算程序。 编写有理数四则运算程序。 编写简单的作图程序。实验二 线性表的顺序存储结构实验目的： 掌握顺序存储结构的特点。 掌握顺序存储结构的常见算法实验仪器：计算机，打印机实验内容： 输入一组整型元素序列，建立顺序表。 实现该顺序表的遍历。 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 判断该顺序表中元素是否对称,对称返回1,否则返回0。 实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 输入整型元素序列利用有序表插入算法建立一个有序表。 利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 编写一个主函数,调试上述算法。* 综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。实验三 单向链表的有关操作实验目的： 掌握单向链表的存储特点及其实现。 掌握单向链表的插入、删除算法及其应用算法的程序实现。实验仪器：计算机，打印机实验内容： 随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。 遍历单向链表。 把单向链表中元素逆置（不允许申请新的结点空间）。 在单向链表中删除所有的偶数元素结点。 编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。 利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。 利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。 利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。* 采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。 在主函数中设计一个简单的菜单，分别调试上述算法。* 综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）实验四 栈和队列及其应用实验目的： 掌握栈、队列的思想及其存储实现。 掌握栈、队列的常见算法的程序实现。实验仪器：计算机，打印机实验内容： 采用链式存储实现栈的初始化、入栈、出栈操作。 采用顺序存储实现栈的初始化、入栈、出栈操作。 采用链式存储实现队列的初始化、入队、出队操作。 采用顺序存储实现循环队列的初始化、入队、出队操作。 在主函数中设计一个简单的菜单，分别测试上述算法。* 综合训练:1)利用栈实现表达式求值算法。2)利用栈实现迷宫求解。实验五 串及其应用实验目的： 熟悉串类型的实现方法。 熟悉文本模式匹配方法。 掌握一般文字处理软件的设计方法。实验仪器：计算机，打印机实验内容： 设计简单的文本处理软件。 设计文本格式化程序。 设计简单的行编辑程序。 串基本操作的演示。实验六 二叉树的常见操作实验目的： 掌握二叉树的存储实现。 掌握二叉树的遍历思想。 掌握二叉树的常见算法的程序实现。实验仪器：计算机，打印机实验内容： 输入字符序列，建立二叉链表。 中序遍历二叉树:递归算法。 中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法） 求二叉树的高度 。 求二叉树的叶子个数。* 将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。* 建立中序线索二叉树，并实现中序遍历。 借助队列实现二叉树的层次遍历。 在主函数中设计一个简单的菜单，分别调试上述算法。* 综合训练：为N个权值设计哈夫曼编码。实验七 图的有关操作实验目的： 掌握图的存储思想及其存储实现。 掌握图的深度、广度优先遍历算法思想及其程序实现。 掌握图的常见应用算法的思想及其程序实现。实验仪器：计算机，打印机实验内容： 键盘输入数据，建立一个有向图的邻接表。 输出该邻接表。* 建立一个无向图的十字链表。 在有向图的邻接表的基础上计算各顶点的度，并输出。 以有向图的邻接表为基础实现输出它的拓扑排序序列。* 采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。 采用邻接表存储实现无向图的深度优先非递归遍历。 采用邻接表存储实现无向图的广度优先遍历。* 采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。* 判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。 在主函数中设计一个简单的菜单，分别调试上述算法。* 综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。实验八 查找的有关操作实验目的： 掌握折半查找算法的思想及程序实现。 掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。 掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。实验仪器：计算机，打印机实验内容： 利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。 随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。* 建立树并实现删除某一指定关键字元素。 已知散列函数为H(key)=key%p（p为自定的常数），冲突处理方法分别为线性探测法、外拉链法实现散列表的建立（利用插入算法实现）。实验九 排序实验目的： 掌握常见的排序算法的思想及其适用条件。 掌握常见的排序算法的程序实现。实验仪器：计算机，打印机实验内容：输入一组关键字序列分别实现下列排序: 实现简单选择排序、直接插入排序和冒泡排序。 实现希尔排序算法。 实现快速排序算法。 实现堆排序算法。* 快速排序的非递归算法。* 实现折半插入排序。* 采用链式存储实现简单选择排序、直接插入排序和冒泡排序。 在主函数中设计一个简单的菜单，分别测试上述算法。* 综合训练：采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。实验十 文件操作实验目的： 熟悉各类文件的特点、构造方法。 掌握文件实现检索、插入和删除等操作。实验仪器：计算机，打印机实验内容： 建立一个文件,完成插入一个记录、删除一个记录和更新一个记录。 将两个顺序非空文件合并成新文件。 建立一个索引顺序文件来查找关键字。四、学时、类别和教学方式序号实验项目名称学时实验类别实验要求01抽象数据的学习3验证性必做02线性表的顺序存储结构3设计性必做03单向链表的有关操作6设计性选做04栈和队列及其应用3设计性必做05串及其应用3设计性选做06二叉树的常见操作3设计性必做07图的有关操作6设计性选做08查找的有关操作3综合性必做09排序3综合性必做10文件操作3验证性选做教学方式：以学生独立操作为主，教师指导为辅。五、考核方式1、实验报告：本门课程对实验报告的要求（应包括对报告内容的要求）；本课程实验要求书写实验报告，报告内容包括： 学生姓名、学号、实验组号及组内编号； 实验题目； 目的要求； 仪器用具: 仪器名称及主要规格、用具名称。 实验编程原理：简单但要抓住要点，画出程序原理框图。 实验内容：给出实验例程（对一些实验，根据教员要求要有实验步骤）。 数据处理及结果（结论）：按实验要求处理数据。 讨论：对实验中存在的问题、进一步的想法等进行讨论。2 实验课的考核方式和成绩评定办法。 预习情况：是否按要求写好预习报告；从提问讨论中，看学生对实验原理的理解及对实验内容的掌握。 实验操作：实验程序调试是否正确；仪器使用是否规范；能否按要求独立操作；遇到问题能否判断处理；数据是否正确；能否在规定时间完成实验内容；实验结束时是否能按要求将仪器复位；课上是否能主动探索和研究问题。 实验报告:是否符合实验报告要求的格式，叙述是否清楚；数据处理中的有效数字、单位、作图、思考题回答是否正确。 实验讨论：学生可对实验原理、测量方法、误差来源、实验结果的分析等诸方面及自己感兴趣的问题进入深入讨论。教员对学生实验能力，学习态度是否认真给予综合评定