实验二 栈和队列的基本操作.doc
文本预览下载声明
实验二 栈和队列的基本操作
一、实验目的与基本要求
1.掌握栈和队列的顺序存储和链式存储结构。
掌握栈和队列的特点。
掌握栈和队列的基本运算。
二、实验条件
硬件:一台微机
软件:操作系统和C语言系统
三、实验方法
确定存储结构后,上机调试实现栈和队列的基本运算。
四、实验内容
写出栈的入栈和出栈算法。
写出队列的入队和出队算法。
一个双向栈S是在同一顺序存储空间内实现的两个栈,它们的栈底分别设在顺序存储空间的两端。试为此双向栈S设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)的算法,其中i为0或1,用以指示栈号。
设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚,依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已停放n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆再依原来的次序进场。每辆车在离开停车场时,都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场要离去,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆次序。编制一个程序模拟该停车场的管理。
五、实验提示
参考算法:
入栈算法如下:
void push(stack s)
{ if (top m)
{ top=top+1;
s[top]=x;
}
else error(“OVERFLOW”);
}
出栈算法如下:
void pop(stack s)
{ if(top0)
{ s[top]=x;
top=top-1;
}
else error(“OVERFLOW”);
}
2、 参考算法:
入队:假设队列采用顺序存储结构,f,r分别表示队首和队尾指针。
入队算法如下:
void insertq(queue s)
{ if(r != m) ( r+1 !=f)
{ r=r+1;
s[r]=x;
}
else
if (r=m) (f != 1)
{ r=1;
s[r]=x;
}
else error(“队列已满”);
}
出队: 同入队,只是将指针r换做指针f,稍作修改即可。
3、参考算法:
初始化算法如下:
void Initstack(s)
{ scanf(”%d”, i);
if(i= =0)
s1-top=0;
if(i= =1)
s2-top=m+1;
}
入栈算法如下:
void Push(s,i,x)
{ scanf(“%d”,i);
if(i= =0)
{ s1-top=s1-top+1;
s1-data[top]=x;
}
if(i= =1)
{ s2-top=s2-top-1;
s2-data[top]=x;
}
}
出栈算法如下:
void Pop(s)
{ scanf(“%d”,i);
if(i= =0)
s1-top=s1-top-1;
if(i= =1)
s2-top=s2-top+1;
}
4、提示:可以停车场内的车辆管理,看做是堆栈,采用先进后出的运算规则;而在停车场外排队的车辆管理,可以看做是队列,采用先进先出的运算规则。
基本思想:根据题目要求,停车场只有一个大门,因此可用一个栈来模拟。而当栈满后,继续来到的车辆只能停在便道上,根据便道停车的特点,可知这可以用一个队列来模拟,先排队的车辆先离开便道,进入停车场。由于排在停车场中间的车辆可以提出离开停车场,并且要求在离开车辆到停车场大门之间的车辆都必须离开停车场,让此车辆离去,然后再让这些车辆依原来的次序进入停车场,因此在一个栈和一个队列的基础上,还需要有一个地方保存为了让路离开停车场的车辆,很显然这也应该用一个栈来模拟,因此,本题中要用到两个栈和一个队列。
参考程序如下:
#define N 2 /* 定义停车场栈长度 */
#define M 5 /* M为单元时间的收费值 */
#define True 1
#define False 0
#inc
显示全部