文档介绍：华北电力大学
实验报告
|
|
实验名称算法与数据结构综合实验
课程名称算法与数据结构综合实验
|
|
实验一约瑟夫环
实验目的及要求
问题描述
约瑟夫(Joseph)问题是:编号为1、2、……、n的n个人按顺时针方向围坐一圈,每个人有一个正整数编号。从某个位置上的人开始报数,数到m的人便出列;下一个人(第m+1个)又从1数起,数到m的人便是第二个出列的人;依次重复下去,直到最后一个人出列,于是得到一个新的次序,试设计程序求出出列顺序。
实验要求
利用单向循环链表存储结构模拟此过程;
利用顺序结构模拟此过程;
输入测试数据m=4,n=8,输出次序为48521376。
所采用存储结构
本次实验采用两种存储结构即单项循环链表和顺序结构分别模拟此过程。
单向循环链表
定义单链表类型:
typedef struct Node
{
int data;
struct Node *next;
}*Pointer;
顺序存储
创建一个数组a用于存放约瑟夫环中的编号,当其出圈时,将出圈数据存放入另一数组b以便输出,之后移动数组a 中元素删除出圈数据,并更改数组长度。
int List::get(int i) //出圈
{
int x=data[i-1];
for(int j=i;j<number;j++)
{
data[j-1]=data[j];
}
number--;
return x;
}
实验设计
单向循环链表
建立链结点用于存储参与游戏人员的编号,主函数中设置两个变量n和m分别代表游戏人数和出圈报数数字,利用Joseph(int n,int m,Pointer&Head)函数来初始化循环单链表并构建约瑟夫环;利用Print(int n,int m,Pointer&Head)函数来输出出圈人员编码,在该函数中,设置三个Node类型的指针*pr,*pn,*a,移动*pn来寻找出圈人员,*pr为*pn的前驱,始终尾随*pn移动,*a用于临时存放出圈人员的数据,在主函数中调用两个函数完成模拟。
顺序存储
建立一个类List来存放游戏人员编号并实现出圈方法,在主函数中判断出圈条件,将出圈人员编号依次存入数组并输出。
四、实验结果
1)单项循环链表
2)顺序存储
五、心得体会
通过本次实验巩固了我对顺序存储和链式存储知识点的理解,就本次实验而言,顺序结构的存储方式结构胶简单,但在处理出圈过程中的判断条件较为复杂,删除数据元素也不方便,而链式存储中只需要移动、修改指针就可完成出圈,删除的操作,理解起来较为容易。顺序结构的模拟程序最初代码较为冗杂,经过多次调试修改,我合并了一些语句操作,让程序变得更加精简清晰。在今后的实验中,应该多思考,多尝试,不断完善自己的程序。
实验二停车场管理
实验目的及要求
问题描述
设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供进出。汽车在停车场按车辆到达时的先后顺序,依次由南到北排列(大门在最南端,最先到达的第一辆车停放在车厂的最北端),若停车场内已停满n辆车,则后来的汽车只能在门外的便道上等候,一旦停车场内有车开走,则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时,由于停车场是狭长通道,在它之后开入车场必须先退出车场为它让路,待车辆开出大门外后,为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。每辆停放在车场的车在它离开车场时,必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。要求:根据各结点信息,调用相应的函数或者语句,将结点入栈或入队,出栈或出队。
实验要求
接受命令和车号,当输入数据包括数据项为汽车的“到达”(‘A’表示)信息、汽车标识(牌照号)及到达时刻时,先判断停车是否满,若不满,则汽车入停车场;否则汽车入便道队等候,并输出汽车在停车场内或便道上的停车位置。
接受命令和车号,当输入数据包括数据项汽车的“离去”(‘D’表示)
信息、汽车标识(牌照号)及离去时刻,将停车场栈上若干辆汽车入临时栈,为该汽车让路,这辆车出停车场栈,临时栈中汽车出栈,入到停车场栈,再看便道队列是否为空,若不空则说明有汽车等候,从队头取出汽车信息,让该车进停车场栈,并输出汽车在停车场停留的时间和应缴纳的费用(便道上停留的时间不收费)。
接受命令和车号,当输入数据项为(‘P’,0,0)时,应输出停车场的车数;当输入数据项为(‘W’,0,0)时,应输出候车场车数;当输入数据项(‘E’,0,0)时,退出程序;若输入数据项不是以上所述,就输出“ERROR!”。
所采用存储结构
本实验将停车场模拟为一个栈,便道设计为一个队列。栈采用顺序存储结构