文档介绍：数
据
结
构
专
题
实
验
自动化05班
董家新
2010054113
专题实验一停车场问题
需求分析:
问题描述:有一狭长停车场可停放n辆车,只有一个门可供进出。车辆按照到达的早晚从最里面依次向外排列,若停车场中的车辆出来,则在它之后进入停车场的车都要让路,然后这些车辆再依次进场。
要求: 该程序以该问题为背景,实现:
1)基于链表和顺序表来实现栈的pop与push操作,队列的EnQueue和DeQueue操作,
2)实现车辆进出的调度。
(1)输入的形式以及输入值的范围:
用户需指定车辆总数n,以及第m辆车次
(2)输出的形式:
程序依次显示每辆车的调度结果.
(3)程序能达到的功能:
由用户指定n的大小及第m辆车出停车场;在文件或屏幕上显示以下两个时刻栈和队列中的车辆情况:
1)第m辆车可以开出停车场;
2)第m辆车开出后,其它车重新回到停车场。
(4)测试数据:
n=8;m=3
概要设计:
本程序主要选用线性栈和队列来解决
本程序包含两个模块:
1)主函数:
int main()//主函数
{
int in = 0, out, i, j, k,m, n, l, a;
char op;
Queue q;
SqStack s;
InitStack(s);
InitQueue(&q);
printf("请输入停车场车辆数目\n");
scanf("%d", &n);
for(k = 0; k < n; k++)
{
Push(s, ++in);
}
while(1)
{
printf("选择哪辆车离开?\n");
scanf("%d", &out);
l = StackLength(s);
printf("临时车场里的车辆:\n");
m = 0;
for(i = l; i > out; --i)
{
Pop(s, a);
printf("%d ", a);
EnQueue(&q, a);
m++;
}
Pop(s, a);
putchar('\n');
rintf("在停车场内依然有的车辆t\n");
Traverse(s);
while(j < m)
{
j = 0;
DeQueue(&q, &a);
Push(s, a);
j++;
}
printf("在第%dst 辆车离开后停车场的情况\n", out);
Traverse(s);
getchar();
printf("continue?(Y/N)\n");
op = getchar();
if(op=='N')
break;
else
continue;
return 0;
}
}
2)栈、队列的初始化及对栈、队列的基本操作:
typedef struct Queue//定义队列
{
QElemType element[QSize];
int front;
int rear;
}Queue;
typedef struct SqStack//定义线性栈
{
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
void InitQueue(Queue* q)//初始化队列
{
q->front = q->rear = 0;
}
Status EnQueue(Queue* q, int a) //入队
{
if ((q->rear + 1) % QSize == q->front) return ERROR;
q->element[q->rear] = a;
q->rear = (q->rear + 1) % QSize;
return OK;
}
Status DeQueue(Queue* q, int* a)//出队
{
if (q->front == q->rear) return ERROR;
*x = q->element[q->front];
q->front = (q->front + 1) % QSize;
return OK;
}
Status QueueEmpty(Queue* q)//判断队空
{
if (q->front == q->rear) return OK;
return ERROR;
}
Status GetQueueHead(Queue* q,int *e)//获得表头元素
{