《数据结构》
实验报告
实 验 课 程： 数据结构
专
业： 信息与计算科学
年级（班级）： 10 级 1 班
姓
名：
学
号：
山东工商学院数学与信息科学学院
实验名称
实验报告
栈和队列的应用——停车场问题
实验时间 第十周 实验地点 三教 106 指导教师
一、实验目的：
1． 熟练掌握栈和队列的结构，以及这两种数据结构的特点；
temp++;
}
}
if(Check_Queue(p,a)){ if(p->front->car_num==a.car_num) DeQueue(p);
else { QueuePtr m,n; m=p->front->next; while(n->car_num!=a.car_num){ n=m; n=m->next; } m->next=n->next; free(n);
} printf("\n 请输入 A/D/E，车牌号，时刻:"); scanf("%c%d%d",&sign,&a.car_num,&a.time); sum--; }
四、实验结果及分析：
输入：5 10 A 10111120 0 D 10111120 1
得到如下输出结果：
五、感想与体会：
1、在做程序之前，一定要仔细分析此程序所运用的各种结构。比如在本程序中，设计 了栈队列的运用。大体轮廓如图所示：
s->base=(car_info *)malloc(STACK_INIT_SIZE*sizeof(car_info)); if(!s->base) exit(OVERFLOW); s->top=s->base; s->stacksize=0; } void push(sqstack *s,car_info e)//插入元素 e 为新的栈顶元素 { *s->top++=e; s->stacksize++; } car_info pop(sqstack *s)//若栈不空，则删除 s 的栈顶元素 { car_info e; if(s->top==s->base) exit(0) ; e=*--s->top; s->stacksize--; return e; } typedef struct Qnode { int car_num; int time; struct Qnode *next; }QNode,*QueuePtr;//便道的结点 typedef struct { QueuePtr front; QueuePtr rear; int lenth; }LinkQueue; //链队列 status InitQueue(LinkQueue *Q) //构造一个空队列 { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front)exit(OVERFLOW); Q->front->next=NULL; Q->lenth=0; return OK; }
int car_num; int time; }car_info; typedef struct//车辆的信息 { car_info *base; car_info *top;
status stacksize; }sqstack; void Initstack(sqstack *s)//构造一个空栈 {
备用栈
若停 车场 不满
停车场栈
若停车场不满 若停车场满
外来车辆
链队列
2、整体框架出来之后就是对问题的细节进行分析，比如对队列和栈的结构进行分析， 并用结构体来描述满足上述问题的节点空间。
3、然后就是利用自己所学的 c 语言的知识来进行编写程序。
4、再编完一段程序后就运行此段程序并分析程序报错原因反复进行调试，直到得到满 意的结果。
}
void arrive(sqstack *s,LinkQueue *p,car_info a,int n)//车辆进入停车场或便道 {
if(a.time>(s->top-1)->time) { if(!Check_Stack(s,a)&&!Check_Queue(p,a)){
if(s->stacksize<n) {
2． 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及 描述方法；
3． 熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条 件和描述方法；
二、实验内容：
设有一个可以停放 n 辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆 到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在 停车场最里面）。如果停车场已放满 n 辆车，则后来的车辆只能停在停车场大门外的便 道上等待，一旦停车场里有车开走，则排在便道上的第一辆车就进入停车场。若停车场 内有某辆车要开走，在它之后进入停车场的车都必须先退出停车场，为它让路，待其开 出停车场后，这些车再依原来的次序进场。每辆车离开停车场时，都应根据其在停车场 的逗留时间交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车 费，并且仍然保持在便道上等待的车辆顺序。编制一程序模拟停车场的管理。
} QueuePtr DeQueue(LinkQueue *Q) {
QueuePtr p,e; if(Q->front==Q->rear) { printf("便道上没有车辆!\n"); } p=Q->front->next; e=p; Q->front->next=p->next; Q->lenth--; if(Q->rear==p)Q->front=Q->rear; return e;
push(s,a); printf("\n 车牌号为%d 的车辆进入停车场%d 号车道\n",a.car_num,s->stacksize); }
else { EnQueue(p,&a); printf("\n 停车场已满,车牌号为%d 的车辆停在便道的%d 号位置\n",a.car_num,p->lenth); } }else printf("已有此车辆"); }else printf("输入时间不对"); }
//删除队尾结点
} int Check_Stack(sqstack *s,car_info a){//检查栈里是否有相同结点
car_info *temp=s->base; while(temp!=s->top&&temp->car_num!=a.car_num) temp++; if(temp==s->top)return ERROR; else return OK;
} } }
void main() {
sqstack tcc,dcc; LinkQueue p;
|%-6.2f
car_info a; int sum=1000,n; float pay; char sign; printf("\n|************************停车场管理**************************|\n"); printf("|******A/a:车辆到达*******D/d:车辆离开******E/e:推出系统*****|\n\n");
void EnQueue(LinkQueue *Q,car_info *a )//插入队尾元素 {
QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->car_num=a->car_num; p->time=a->time; p->next=NULL; Q->rear->next=p; Q->rear=p; Q->lenth++;
{
x=pop(dcc);
push(tcc,x);
}
if(tcc->stacksize<n&&p->lenth!=0)
{
b=DeQueue(p);
x.car_num=b->car_num; x.time=a.time;
push(tcc,x);

printf("车牌号为%d 的车辆由便道进入停车场%d 号车道\n",x.car_num,tcc->stacksize);
ss=pop(tcc);
push(dcc,ss);
if(ss.car_num==a.car_num)//计算费用
{
find=0;
cost=(a.time-ss.time)*pay;
arrivetime=ss.time;
}
}
pop(dcc);
//把临时堆栈的要离开的车去掉；
while(dcc->stacksize)
printf("**********************************************\n");
car_info *temp=tcc->base;
while(temp!=tcc->top)
{
printf("还剩以下车牌号的汽车");
printf("%d\n",temp->car_num);
三、实验程序：