数据结构-链队列和停车场

数据结构与算法课程实验报告实验二：栈和队列的应用姓名：沈靖雯班级：14信息与计算科学（2）班学号：2014326601094实验二栈和队列的应用【实验内容】一、实现链队列（带头结点）的各种基本运算二、停车场管理【实验目的】掌握栈和队列的定义和实现，学习利用栈和队列解决实际问题。【问题描述】一、问题描述：1）初始化并建立链队列2）入队列3）出队列二、问题描述：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。分析:以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。【问题实现】实现链队列基本运算（1）抽象数据类型ADTSqQueue{数据对象:数据关系：基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入e为Q新队尾元素。DeQueue(&Q,&e)初始条件：队列Q已存在且非空。操作结果：删除Q队头元素，用e返回其值。SqQueueprint(Q)初始条件：队列Q已存在。操作结果：输出队列。}ADTSqQueue（2）主要实现思路：首先定义队列的链式存储结构，然后初始化构建空队列；分别定义一个入队列和出队列函数；定义一个队列输出函数输出队列，检验操作结果；定义主函数，总体完成以上所有函数功能的实现。（3）主要程序代码：//初始化队列intInitQueue(SqQueue*Q){ Q->front=Q->rear=(Queue)malloc(sizeof(QNode)); if(!Q->front)exit(OVERFLOW); Q->front->next=NULL; return0;}//入队列intEnQueue(SqQueue*Q,inte){ //插入e为Q新队尾元素QueueP=(Queue)malloc(sizeof(QNode)); if(!P)exit(OVERFLOW); P->base=e;P->next=NULL; Q->rear->next=P; Q->rear=P; return0;}//出队列intDeQueue(SqQueue*Q,int*e){ if(Q->front==Q->rear)return-1;//队列空QNode*q=NULL; q=Q->front->next; e=q->base; Q->front->next=q->next; if(Q->rear==q)Q->rear=Q->front; free(q); return0;}//输出队列元素voidSqQueueprint(SqQueueQ){ QNode*q=Q.front->next;while(q!=Q.rear){printf("%d",q->base); q=q->next;} printf("%d",q->base);printf("\n"); }程序运行如图1：图SEQ图\*ARABIC1停车场管理数据类型定义//车辆信息结点typedefstruct{ charnum[10]; intrtime; intltime;}Car;typedefstruct{ Car*data; structQNode*next;}QNode;//栈（停车栈，临时停车栈）typedefstruct{ Car*stack[100]; inttop;}ParkStack;//队列（便道）typedefstruct{ QNode*head; QNode*rear;}LinkQueue;基本操作：voidInitStack(ParkStack*);//初始化栈intInitQueue(LinkQueue*);//初始化便道intarrive(ParkStack*,LinkQueue*);//车辆到达voidleave(ParkStack*,ParkStack*,LinkQueue*);//车辆离开主要实现思路和程序代码：1).首先定义抽象数据类型，构建程序框架；2).定义车辆到达函数；intarrive(ParkStack*park,LinkQueue*W)用户输入车牌号，判断停车场是否停满：如果未满，车停进停车场；满，车辆进入便道等待。（if-else） if(park->top<SIZE)//停车场未满，车进车场 { park->top++; printf("\n停车位置:%d号停车位。",park->top); printf("\n请输到达时间:"); scanf("%d",&(p->rtime)); park->stack[park->top]=p; getchar();return1; } else//停车场已满，车进便道 { printf("\n停车位已满，该车须在便道等待！\n"); t=(QNode*)malloc(sizeof(QNode)); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; getchar();return1; }3).定义车辆离开函数；voidleave(ParkStack*park,ParkStack*Tempark,LinkQueue*W)/首先判断车场内是否有车（if-else），如果无车，输出停车场无车：printf("\n停车场里没有车\n");如果有车，用户输入离开车辆所在停车场位置，该车后面进入停车场的车辆开进临时停车栈为其离开停车场让路，随后待用户车辆离开，车辆从临时停车栈回到停车场： while(park->top>place)//退出给要离去汽车让路的车辆进入临时停车栈 { Tempark->top++; Tempark->stack[Tempark->top]=park->stack[park->top]; park->stack[park->top]=NULL; park->top--; } //车辆离开 p=park->stack[park->top]; park->stack[park->top]=NULL; park->top--; while(Tempark->top>0)//让路车辆从临时停车栈回到停车栈 { park->top++; park->stack[park->top]=Tempark->stack[Tempark->top]; Tempark->stack[Tempark->top]=NULL; Tempark->top--; }输出离开车辆信息： printf("\n输入离开时间:"); scanf("%d",&(p->ltime)); printf("\n车牌号码:%s",p->num);printf("停车时间:%dh",(p->ltime)-(p->rtime)); printf("\n费用为:%d元",((p->ltime)-(p->rtime))*price); free(p);同时在车辆离开函数里添加if函数判断便道上是否存在等待车辆，如果有，位于便道上第一辆车进入停车位： //判断便道上是否有车及停车栈是否已满 if((W->head!=W->rear)&&park->top<SIZE)//便道的车辆进入停车栈 { q=W->head->next; t=q->data; park->top++; printf("\n便道上车牌%s车进入车场第%d号停车位。",t->num,park->top); printf("\n请输入现在的时间:"); scanf("%d",&(t->rtime)); W->head->next=q->next;//出队列 if(q==W->rear)W->rear=W->head; park->stack[park->top]=t; free(q); } 4).定义主函数（voidmain（）），完成停车场管理操作。主函数主要使用while函数实现用户选择操作（车辆到达、离开或退出系统）：while(1) { ch=getchar(); switch(ch) {case'A':arrive(&park,&Wait);break;//车辆到达 case'D':leave(&park,&Tempark,&Wait);break;//车辆离开 case'E':{printf("谢谢使用！");exit(0);}//退出 } }程序运行如图2：图SEQ图\*ARABIC2【总结】两个实验结果都基本实现问题的要求。基础实验链队列的操作使本人对队列有初步的了解，会对其进行初始化，入队列和出队列等操作，一开始错用了循环队列的顺序存储表示，后来重新做了实验正确实现了队列的链式存储运算，虽然耗费了很多时间，但通过这次审题失误使本人对链式存储和顺序存储的差别印象极为深刻。处理停车场管理问题过程中，本人对栈和队列的理解大大加深，明白栈LIFO和队列FIFO的差别，会用其解决实际问题。附件：代码一：实现链队列基本运算#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOVERFLOW-2typedefstructNode{ intbase; structNode*next;}QNode,*Queue;typedefstruct{ Queuefront;//头指针 Queuerear;//尾指针}SqQueue;//构造一个空队列intInitQueue(SqQueue*Q){ Q->front=Q->rear=(Queue)malloc(sizeof(QNode)); if(!Q->front)exit(OVERFLOW); Q->front->next=NULL; return0;}//入队列intEnQueue(SqQueue*Q,inte){ //插入e为Q新队尾元素QueueP=(Queue)malloc(sizeof(QNode)); if(!P)exit(OVERFLOW); P->base=e;P->next=NULL; Q->rear->next=P; Q->rear=P; return0;}//出队列intDeQueue(SqQueue*Q,int*e){ if(Q->front==Q->rear)return-1;//队列空QNode*q=NULL; q=Q->front->next; e=q->base; Q->front->next=q->next; if(Q->rear==q)Q->rear=Q->front; free(q); return0;}//输出队列元素voidSqQueueprint(SqQueueQ){ QNode*q=Q.front->next;while(q!=Q.rear){printf("%d",q->base); q=q->next;} printf("%d",q->base);printf("\n"); }intmain(){ SqQueueQ; int*e; InitQueue(&Q); //入队列操作EnQueue(&Q,1);EnQueue(&Q,2);EnQueue(&Q,3);printf("现有队列：");SqQueueprint(Q);printf("\n9入列，得对列：\n"); EnQueue(&Q,9); SqQueueprint(Q); printf("3入列，6入列：\n"); EnQueue(&Q,3); EnQueue(&Q,6);SqQueueprint(Q);//出队列操作DeQueue(&Q,&e); printf("\n出队列一位：\n");SqQueueprint(Q);printf("继续出队列两位：\n");DeQueue(&Q,&e);DeQueue(&Q,&e);SqQueueprint(Q);return0;}代码二：停车场管理#include<stdio.h>#include<stdlib.h>#defineSIZE2#defineprice10typedefstruct{ charnum[10]; intrtime; intltime;}Car;//车辆信息结点typedefstruct{ Car*data; structQNode*next;}QNode;typedefstruct{ Car*stack[100]; inttop;}ParkStack;//栈（停车栈，临时停车栈）typedefstruct{ QNode*head; QNode*rear;}LinkQueue;//便道voidInitStack(ParkStack*s)//初始化栈{inti=0; s->top=0; for(i=0;i<=SIZE;i++) s->stack[s->top]=NULL;}intInitQueue(LinkQueue*Q)//初始化便道{Q->head=Q->rear=(QNode*)malloc(sizeof(QNode)); if(!Q->head)exit(0); Q->head->next=NULL; return1; }intarrive(ParkStack*park,LinkQueue*W)//车辆到达{ Car*p; QNode*t; printf("\n停车场剩余停车位:%d",SIZE-park->top); printf("\n请输车牌号码:"); p=(Car*)malloc(sizeof(Car)); getchar(); gets(p->num); if(park->top<SIZE)//停车场未满，车进车场 { park->top++; printf("\n停车位置:%d号停车位。",park->top); printf("\n请输到达时间:"); scanf("%d",&(p->rtime)); park->stack[park->top]=p; getchar();return1; } else//停车场已满，车进便道 { printf("\n停车位已满，该车须在便道等待！\n"); t=(QNode*)malloc(sizeof(QNode)); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; getchar();return1; } }voidleave(ParkStack*park,ParkStack*Tempark,LinkQueue*W)//车辆离开{ intplace; Car*p,*t; QNode*q;//判断车场内是否有车 if(park->top>0)//有车 { printf("\n请输入车在停车场的位置(1-%d)：",park->top); scanf("%d",&place); while(park->top>place)//退出给要离去汽车让路的车辆进入临时停车栈 { Tempark->top++; Tempark->stack[Tempark->top]=park->stack[park->top]; park->stack[park->top]=NULL; park->top--; } //车辆离开 p=park->stack[park->top]; park->stack[park->top]=NULL; park->top--; while(Tempark->top>0)//让路车辆从临时停车栈回到停车栈 { park->top++; park->stack[park->top]=Tempark->stack[Tempark->top]; Tempark->stack[Tempark->top]=NULL; Tempark->top--; } printf("\n输入离开时间:"); scanf("%d",&(p->ltime)); printf("\n车牌号码:%s",p->num);printf("停车时间:%dh",(p->ltime)-(p->rtime)); printf("\n费用为:%d元",((p->ltime)-(p->rtime))*price); free(p); //判断便道上是否有车及停车栈是否已满 if((W->h