2022年数据结构与算法设计实验指导书 .pdf

《2022年数据结构与算法设计实验指导书 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构与算法设计实验指导书 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法设计实验指导书实验 1 顺序表的操作一、实验目的通过对线性表的一些基本的操作和具体的函数实现，深入理解线性表的逻辑结构特性；了解并掌握线性表的顺序存储结构的描述方法与顺序表的基本操作（建立、 插入） 的实现算法及各函数间的调用关系；熟练掌握对程序的输入、编辑、调试和运行过程。二、实验内容程序编程类题目：顺序表的操作：实现顺序表的建立、插入等。题目：设线性表中的数据元素是按值非递减有序排列的，试以顺序存储结构，编写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性。解：本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将 x 插入，并返回向量的新长度三、实

2、验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解程序而深入全面地理解程序逻辑。3程序调试和运行用多组不同的数据进行测试，记录测试数据和运行输出及结果4完成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 实验 2 单链表的操作一、实验目的通过对单链表的一些基本的操作和具体的函数实现，深入

3、理解线性表的逻辑结构特性；了解并掌握单链表的存储结构的描述方法与单链表的基本操作（建立、 插入） 的实现算法及各函数间的调用关系。二、实验内容程序编程类题目：单链表的操作：实现单链表的建立；插入等。题目：设线性表中的数据元素是按值非递减有序排列的，试以链式存储结构，编写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性。解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；

4、通过阅读或给别人讲解程序而深入全面地理解程序逻辑。3程序调试和运行用多组不同的数据进行测试，记录测试数据和运行输出及结果4完成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 实验 3 栈的操作一、实验目的通过对栈的一些基本的操作和具体的函数实现，深入理解栈类型的特点；熟练掌握栈类型的实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。二、实验内容程序编程类题目：栈的操作：实现栈的定义、入

5、栈、出栈等操作。题目：设单链表中存放n 个字符 ,设计一个算法 ,使用栈判断该字符串是否中心对称,如 abccba即为中心对称字符串. 提示：先用 create()函数从用户输入的字符串创建相应的单链表，然后调用 bj()函数判断是否为中心对称字符串。在bj（）函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解程序而深入全面地理解程序逻辑。3程序调试和运行用多组不同的数据进行测试，记录测试数据和运行输出及结果4完成实验

6、报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 实验 4 队列的操作一、实验目的通过对队列的一些基本的操作和具体的函数实现，深入理解队列类型的特点；熟练掌握队列类型的实现方法，特别应注意队列满和队列空的条件以及它们的描述方法。二、实验内容程序编程类题目：队列的操作：实现队列的定义、入队列、出队列等操作。题目：舞伴问题提示： 先入队的男士或女士亦先出队配成舞伴。可用队列作为算法的数据结构。在算法中

7、，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素， 并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她） 将是下一轮舞曲开始时第一个可获得舞伴的人三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解程序而深入全面地理解程序逻辑。3程序调试和运行用多组不同的数据进行测试，记录测试数据和运行输出及结果4完

8、成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 实验 5 二叉树操作一、实验目的通过实现二叉树结点结构和对二叉树的基本操作，掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法二、实验内容程序编写类题目 问题描述 建立二叉树并实现对二叉树的先序、中序和后序遍历。 基本要求 （1）编写函数实现按先序序列建立二叉树（2）分别编写函数实现对二叉树的先

9、序、中序和后序遍历 （其中应有一个非递归调用的函数）（3）对给定的任意先序序列均能建立对应的二叉树 测试数据 见 109 页图 5.12 实现提示 分别编写函数实现按先序序列建立二叉树、二叉树的先序、中序和后序遍历，最后编写主函数并在主函数中建立菜单，通过菜单项选择调用相应的函数。三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计）主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码确定算法的主要流程，再进行编程。4上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自

10、己的程序而深入全面地理解程序逻辑。5程序调试和运行6完成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 实验 6 图的运算一、实验目的掌握图的邻接矩阵存储结构的实现算法；完成单源点最短路径。二、实验内容程序编写类题目 问题描述 对带权的有向图，求从某个源点到其他各顶点的最短路径。 基本要求 （1） 编写函数实现构造图的邻接矩阵的算法（2） 利用 Dijkstra算法实现从源点v1 到其他各顶

11、点的最短路径（3） 对给定的任意的有向图均能完成从某个源点到其他各顶点的最短路径 测试数据 见 171 页习题 6.15 实现提示 通过键盘输入确定对应图的顶点数和各条边及对应权值，并根据输入数据构造图的邻接矩阵，然后调用函数实现从源点v1 到其他各顶点的最短路径。三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计）主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码确定算法的主要流程，再进行编程。4上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全

12、面地理解程序逻辑。5程序调试和运行6完成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 实验 7 查找操作一、实验目的熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。二、实验内容程序编写类题目 问题描述 使用哈希函数除留余数法及线性探测法处理冲突的方法，实现对哈希表的查找。 基本要求 （1） 通过键盘输入关键字序列，建立相应的哈希表（2） 输入的每个关键字后，显示哈希表

13、当前状态（3） 对表中已存在的关键字，显示在表中的位置，并给出提示信息。 测试数据 见 202 页上机练习5 实现提示 建立结构体类型（至少两个字段，其中一个为关键字字段）的一维数组，编写一个输出哈希表的函数。初始化和插入关键字后调用该函数。三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计）主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码确定算法的主要流程，再进行编程。4上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。5程序

14、调试和运行6完成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 实验 8 排序一、实验目的了解排序的定义和各种排序方法的特点。熟悉交换排序方法的排序过程及其依据的原则。二、实验内容程序编写类题目 问题描述 交换排序快速排序通过一趟排序， 将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序 基本要求 （1） 通过

15、键盘输入关键字序列，建立无序的顺序表（2） 输出建立无序的顺序表（3） 对建立的顺序表采用快速排序方法进行排序后输出顺序表。 测试数据 见 225 页上机练习1 实现提示 建立一维数组， 编写一个输出函数和快速排序的函数。用 225 页上机练习1 的数据初始化数组后调用相应的函数。三、实验步骤1问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2确定解决问题的方法（设计）主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3详细设计和编码确定算法的主要流程，再进行编程。4上机前程序静态检查静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。5程序调试和运行6完成实验报告按实验报告的要求完成书写工作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -