数据结构与算法设计实验指导书.doc

数据结构与算法设计实验指导书实验1线性表的操作一、实验目的 通过对线性表的一些基本的操作和具体的函数实现，深入理解线性表的逻辑结构特性；了解并掌握单链表的存储结构的描述方法与线性链表的基本操作（建立、插入、删除）的实现算法及各函数间的调用关系；熟练掌握对大程序的输入、编辑、调试和运行过程。二、实验内容程序编程类题目：单链表的基本操作 ：实现单链表的建立；插入、删除等。三、实验步骤1问题理解和分析 充分地分析和理解问题本身，弄清要求做什么。2上机前程序静态检查 静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解程序而深入全面地理解程序逻辑。3程序调试和运行 用多组不同的数据进行测试，记录测试数据和运行输出及结果4完成实验报告 按实验大纲的要求完成书写工作。实验2二叉树操作一、实验目的 通过实现二叉树结点结构和对二叉树的基本操作，掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法二、实验内容程序编写类题目问题描述建立二叉树并实现对二叉树的先序、中序和后序遍历。基本要求（1） 编写函数实现按先序序列建立二叉树（2） 分别编写函数实现对二叉树的先序、中序和后序遍历（其中应有一个非递归调用的函数）（3） 对给定的任意先序序列均能建立对应的二叉树测试数据 见109页图5.12实现提示分别编写函数实现按先序序列建立二叉树、二叉树的先序、中序和后序遍历，最后编写主函数并在主函数中建立菜单，通过菜单项选择调用相应的函数。三、实验步骤1问题理解和分析 充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计） 主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码 确定算法的主要流程，再进行编程。4上机前程序静态检查 静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。5程序调试和运行6完成实验报告 按实验大纲纲的要求完成书写工作。实验3 图的运算一、实验目的 掌握图的邻接矩阵存储结构的实现算法；完成单源点最短路径。二、实验内容程序编写类题目问题描述对带权的有向图，求从某个源点到其他各顶点的最短路径。 基本要求（1） 编写函数实现构造图的邻接矩阵的算法（2） 利用Dijkstra算法实现从源点v1到其他各顶点的最短路径（3） 对给定的任意的有向图均能完成从某个源点到其他各顶点的最短路径测试数据 见171页习题6.15实现提示 通过键盘输入确定对应图的顶点数和各条边及对应权值，并根据输入数据构造图的邻接矩阵，然后调用函数实现从源点v1到其他各顶点的最短路径。三、实验步骤1问题理解和分析 充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计） 主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码 确定算法的主要流程，再进行编程。4上机前程序静态检查 静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。5程序调试和运行6完成实验报告 按实验大纲纲的要求完成书写工作。实验4 查找操作一、实验目的 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。二、实验内容程序编写类题目问题描述使用哈希函数除留余数法及线性探测法处理冲突的方法，实现对哈希表的查找。 基本要求（1） 通过键盘输入关键字序列，建立相应的哈希表（2） 输入的每个关键字后，显示哈希表当前状态（3） 对表中已存在的关键字，显示在表中的位置，并给出提示信息。测试数据 见202页上机练习5实现提示 建立结构体类型（至少两个字段，其中一个为关键字字段）的一维数组，编写一个输出哈希表的函数。初始化和插入关键字后调用该函数。三、实验步骤1问题理解和分析 充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计） 主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码 确定算法的主要流程，再进行编程。4上机前程序静态检查 静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。5程序调试和运行6完成实验报告 按实验大纲纲的要求完成书写工作。附录： 实验报告要求一、 需求分析1 程序的功能；2 输入输出的要求；3 测试数据。二、 详细设计1 采用c语言定义相关的数据类型；2 写出各模块的伪码算法或画出流程图；