文档详情

实验二 栈和队列的基本操作.doc

发布:2017-12-17约2.97千字共5页下载文档
文本预览下载声明
实验二 栈和队列的基本操作 一、实验目的与基本要求 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
显示全部
相似文档