数据结构实验大纲16

《数据结构》实验教学大纲一、课程说明（一）适用专业：计算机科学与技术（本科）（二）课程类别：专业课（三）课程性质与任务：《数据结构》是计算机应用专业的一门专业课，主要任务是讨论各种数据结构的逻辑结构，存储结构及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。（四）实验教学目标与基本要求：每个学生必须完成一定数量的上机作业，通过实验使学生更进一步了解数据结构的算法设计思想及实现方法,从而达到锻炼学生理论与实践相结合的能力。同时，在程序设计方法、程序设计风格及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练。提高分析问题和用计算机解决实际问题的能力。为后续课程的学习以及为应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。（六）学时、学分数：1.课程总学时与学分：72学时4.5学分2.实验学时与学分：16学时（七）实验类别：专业实验（八）考核方式与要求：学生要根据实验要求,完成相应的任务,需按时提交程序源代码及程序设计说明报告（实验报告），作为主要评分依据二实验内容及要求实验项目一：线性表基本操作的实现1实验目的：掌握线性表（顺序表和链表）的基本操作算法，如插入、删除等。实验内容：1定义顺序表的数据结构；编写构造一个顺序表的函数；编写实现插入及删除操作的函数；编写主函数，定义一个顺序表L，输入顺序表L的数据。键盘输入一个数据元素x，调用函数将x插入到L中。要求插入前和插入后显示运行结果，再删除x,显示运行结果。（按同样要求设计链表）2约瑟夫环问题(Josephus)：用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（使用循环链表或数组存储）教学方式：学生实际操作为主,教师辅助指导预习要求：预习课本2.2线性表的顺序表示和实现预习课本2.3线性表的链式表示和实现实验项目二：栈、循环队列的简单应用实验目的：利用栈的结构和特点实现数制转换，掌握循环队列的特点并灵活应用实验内容：1假设以顺序存储结构实现一个栈，编写程序完成十进制整数转换R进制整数2实现舞会上男女舞伴的自动匹配。舞会上先后到达男士和女士若干人，第一轮按照到来的先后顺序，男女搭配一组，如果有剩下的，等下一轮首先匹配。打印出匹配情况。教学方式：学生实际操作为主,教师辅助指导预习要求：预习栈的表示和实现及应用、循环队列的表示和实现实验项目三：数组与串的操作应用实验目的：掌握数组与广义表的基本操作掌握稀疏矩阵的特点(三元组存储方法)。掌握串的运算（赋值，比较，联结，插入子串，模式匹配……等）。实验内容：实现串的基本操作（输入字符串，利用数组进行不同字符个数的分类统计）*求两个具有相同行列数的稀疏矩阵的相加矩阵。教学方式：学生实际操作为主,教师辅助指导预习要求：预习数组和串的存储与表示实验项目四：二叉树的基本操作实现实验目的：实现二叉树的遍历及基本应用实验内容：实现二叉树的二叉链表存储结构；实现先序、中序和后序遍历二叉树；遍历二叉树的应用:计算叶子结点，二叉树深度等教学方式：学生实际操作为主,教师辅助指导预习要求：预习二叉树的存储和遍历实验项目五：哈夫曼编码/译码器实验目的：实现最优二叉树（哈夫曼树）的构造算法实验内容：设计一个利用哈夫曼算法的编码和译码系统，根据键盘输入的字符及其频度，进行编码和译码，并显示哈夫曼编码。教学方式：学生实际操作为主,教师辅助指导预习要求：预习哈夫曼算法实验项目六：图的基本操作实现实验目的：实现图的存储及遍历、最短路径的求解实验内容：实现图的存储结构；实现图的深度优先和广度优先遍历实现计算最短路径问题的Dijkstra算法和Floyd算法。教学方式：学生实际操作为主,教师辅助指导预习要求：预习图的存储和遍历、最短路径算法实验项目七：查找算法实现与分析实验目的：实现顺序查找、二叉排序树中的查找算法并分析其ASL实验内容：1设顺序表按关键字自大到小有序存放，编写程序实现有序表的顺序查找操作，要求将监视哨设在高下标端。2从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。教学方式：学生实际操作为主,教师辅助指导预习要求：预习顺序查找、二叉排序树实验项目八：内部排序算法实现与比较实验目的：实现常见内部排序算法，比较它们的算法时间性能实验内容：通过随机的数据比较各内部排序算法的关键字比较次数和关键字移动次数，以取得直观感受。教学方式：学生实际操作为主,教师辅助指导预习要求：预习各种常见内部排序算法：直接插入算法、折半插入算法、冒泡法、简单选择法、快速排序法、堆排序法等。三、实验设备及器材配置硬件：计算机软件环境：VisualC++或BorlandC四、参考教材及资料序号名称类别作者出版社或刊物名称出版或刊发时间页码1数据结构（C语言版）教材严蔚敏吴伟民清华大学出版社19971-3342数据结构（C语言描述）教材徐孝凯贺桂英清华大学出版社20041-2753数据结构题集(C语言版)教材严蔚敏吴伟民米宁清华大学出版社19994数据结构课程设计教材苏仕华机械工业出版社20051-1685数据结构实验与实训教程教材邓文华戴大蒙清华大学出版社20041-866数据结构教程上机实验指导教材李春葆清华大学出版社20051-135……