华北电力大学数据结构实验报告剖析.doc

华北电力大学 实 验 报 告 | | 实验名称 算法与数据结构综合实验 课程名称 算法与数据结构 | | 专业班级： 学生姓名： 学 号： 成 绩： 指导教师： 实验日期： （实验报告如打印，纸张用A4，左装订；页边距：上下2.5cm,左2.9cm, 右2.1cm；字体：宋体小四号，1.25倍行距。） （实验一 停车场管理） （实验二 约瑟夫环） （实验三 二叉树的存储及遍历） （实验四 图的存储及遍历） （实验五 哈希表的设计） 一、实验目的及要求 二、所用仪器、设备 三、实验原理 四、实验方法与步骤 五、实验结果与数据处理 六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在的问题等进行分析和讨论，对实验的进一步想法或改进意见） 七、所附实验输出的结果或数据 实验一 停车场管理 实验内容 设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。 2、车站已满进入便道： 车辆离开： 总结与体会 1、虽然实验中遇到了一些问题，但最后在老师的帮助下问题很快就解决了，主要是由于刚开始接触算法不是很熟悉。 2、通过《停车场管理》的实验学习使我基本上理解并学会了用栈的先进后出和队列的先进先出的原理去解决实际问题的思想和方法。但是在编程方面还是很欠缺，还要加强学习。 实验二 约瑟夫环 一、实验内容 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 分析约瑟夫问题：n个人围成圈，密码，从第一个人开始，数到第m个人，删除，从下一个人开始进行第二轮操作，直到所有人都出列。n个人围圈，形成线性关系；处理为逐个删除，故用链式结构合适；又人员围成圆圈，所以此链式结构采用循环方式较好；排号按照一个方向进行，故数据结构采用带头结点的单向循环链表。假设人员以首次的编号命名，对每个人员采用编号加以描述。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 2、输入密码m，进行约瑟夫环游戏 总结与体会 1、刚开始对头结点的运用不是很熟悉，通过本次实验加深了我对头结点、链表和顺序表的认识。 2、这次实验相对来说比较简单，但中间也出现了一些错误，在老师的帮助下问题很快就解决了。 3、认识到自己的编程技术还是比较次的，以后一定多多练习。 实验三 二叉树的存储及遍历 一、实验内容 1、按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树。 2、然后按先序、中序、后序顺序分别遍历这棵二叉树。 二、实验目的 1、 树是一种重要的非线性数据结构，要求掌握二叉树的两种基本的存储结构，及各种操作的算法实现（建立、遍历）以及应用。 2、 本实验训练的要点是：递归算法的设计方法以及二叉树的应用。 三、所用仪器、设备 计算机，VC++2010。 四、实验方法与步骤 1、编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建立。 2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，采用递归实现，遍历算法有先序、中序和后序遍历算法 详细步骤： 1、定义树： typedef struct btnode { char data; struct btnode *Lchild,*Rchild; }*Tree; 2、建立二差树：void CreateTree(Tree *t) v