tcc.rar_Parking Lot_TCC_停车场 数据结构

1.实验目的: (1)掌握栈和队列的顺序存储和链式存储结构. (2)掌握栈和队列的特点. (3)掌握栈和队列的基本运算. 2.实验内容: 设有一个可以停放N辆汽车的狭长停车场,它只有一个大门可以供车辆进出.车辆按到达停车场时间的早晚,依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面).如果停车场已放满N辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场.停车场内如有某辆车要开走,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆再依原来的次序进场.每辆车在离开停车场时,都应根据它在停车场内停留的时间长短交费.如果停留在便道上的车末进停车场就要离去,允许其离,不收停车费,并且仍然保持在便道上等待的车辆的次序.编制一程序模拟该停车场的管理. 3.实验提示: 可以将停车场内的车辆管理,看作是堆栈,采用先进后出的运算规则;而在停车场外排队的车辆管理,可以看作是队列,采用先进先出的运算规则. 4.基本思想: 根据题目要求,停车场只有一个大门因些可用一个栈来模拟.而当栈满后,继续来到的车辆只能停在便道上,根据便道停车的特点,可知这可以用一个队列来模拟,先排队的车辆先离开便道,进入车场.由于排在集车场中间的车辆可以提出离开停车场,并且要求在离开车辆到停车场大门之间的车辆都必须先离开停车场,让些车辆离去,然后再让这些车辆依原来的次序进入停车场,因些在一个栈和一个队列的基础上,还需要有一个地方保存为了让路离开停车场的车辆,很显然这也应该用一个栈来模拟.因些,本题中用到两个栈和一个队列. #include <stdio.h> #define maxnum 5 #define maxnum1 3 /*存储结构*/ struct seqstack {int s[maxnum]; int t; }; typedef struct seqstack *pseqstack; pseqstack pastack,pastack1; struct seqqueue {int q[maxnum]; int f,r; }; typedef struct seqqueue *pseqqueue; pseqqueue queue; pseqstack createemptystack_seq(void) {pseqstack pastack; pastack=(pseqstack)malloc(sizeof(struct seqstack)); if(pastack==NULL) printf("空间溢出!\n"); else pastack->t=-1; return(pastack); } push_seq(pseqstack pastack, int x) {if(pastack->t>maxnum-1) {printf("车子过多!\n");return(NULL);} else {pastack->t=pastack->t+1; pastack->s[pastack->t]=x; } return(NULL); } void pop_seq(pseqstack pastack) {if(pastack->t==-1) printf("没有车了。\n"); else pastack->t=pastack->t-1; } pseqqueue createemptyqueue_seq(void) {pseqqueue paqu; paqu=(pseqqueue)malloc(sizeof(struct seqqueue)); if(paqu==NULL) printf("空间溢出!\n"); else {paqu->f=0; paqu->r=0; } return(paqu); } void enqueue_seq(pseqqueue paqu,int x) {if ((paqu->r+1)%maxnum1==paqu->f) printf("便道已经停满。\n"); else {paqu->q[paqu->r]=x; paqu->r=(paqu->r+1)%maxnum1; } } void dequeue_seq(pseqqueue paqu) {if (paqu->f==paqu->r) printf("便道已没有车。\n"); else paqu->f=(paqu->f+1)%maxnum; } main() { int i,carnum; printf("停车位的总数：%d\n",maxnum); printf("现在开始进入停车位：\n"); pastack=createemptystack_seq(); pastack1=createemptystack_seq(); for(i=0;i<maxnum;i++) { push_seq(pastack,i); printf(" %d ",i); } printf("\n"); printf("继续有车辆进入，此时停放在便道上。\n"); queue=createemptyqueue_seq(); for(i=0;i<maxnum1-1;i++) {enqueue_seq(queue,i+maxnum); printf(" %d ",i+maxnum); } printf("\n"); printf("请输入要从车库中开出的车号："); scanf("%d",&carnum); while (pastack->s[pastack->t]!=carnum) {push_seq(pastack1,pastack->s[pastack->t]); printf(" 第%d号车开出车库",pastack->s[pastack->t]); pop_seq(pastack); }printf("\n"); if(pastack->s[pastack->t]==carnum) {pop_seq(pastack); push_seq(pastack,pastack1->s[pastack1->t]); /*while(push_seq(pastack,pastack1->s[pastack1->t]))*/ push_seq(pastack,pastack1->s[pastack1->t]); printf(" af%d ",pastack->t); push_seq(pastack,queue->q[queue->f]); dequeue_seq(queue); } for (i=0;i<maxnum;i++) {printf(" %d ", pastack->t); pastack->t=pastack->t-1;} } 程序2 #include<stdlib.h> #include<stdio.h> #include<iostream.h> #include<string.h> #include<math.h> #define size 1 //停车场位置数 //模拟停车场的堆栈的性质； typedef struct zanlind{ int number; //汽车车号 int ar_time; //汽车到达时间 }zanInode; typedef struct{ zanInode *base; //停车场的堆栈底 zanInode *top; //停车场的堆栈顶 int stacksize_curren; }stackhead; //堆栈的基本操作； void initstack(stackhead &L) //构造一个空栈 { L.base=(zanInode*)malloc(size*sizeof(zanlind)); if(!L.base) exit(0); L.top=L.base; L.stacksize_curren=0; } void push(stackhead &L,zanInode e) //把元素e压入s栈 { *L.top++=e; L.stacksize_curren++; } void pop(stackhead &L,zanInode &e) //把元素e弹出s栈 { if(L.top==L.base) { cout<<"停车场为空 !!"; return; } e=*--L.top; L.stacksize_curren--; } //模拟便道的队列的性质； typedef struct duilie{ int number; //汽车车号 int ar_time; //汽车到达时间 struct duilie *next; }*queueptr; typedef struct{ queueptr front; //便道的队列的对头 queueptr rear; //便道的队列的队尾 int length; }linkqueue; //队列的基本操作； void initqueue(linkqueue &q) //构造一个空队列 { q.front=q.rear=(queueptr)malloc(sizeof(duilie)); if(!q.front||!q.rear) exit(0); q.front->next=NULL; q.length=0; } void enqueue(linkqueue &q,int number,int ar_time) //把元素的插入队列（属性为number，ar_time） { queueptr p; p=(queueptr)malloc(sizeof(duilie)); if(!p) exit(0); p->number=number; p->ar_time=ar_time; p->next=NULL; q.rear->next=p; q.rear=p; q.length++; } void popqueue(linkqueue &q,queueptr &w) //把元素的插入队列（属性为number，ar_time） { queueptr p; if(q.front==q.rear) { cout<<"停车场的通道为空 ! !"<<endl; return; } p=q.front->next; w=p; q.front->next=p->next; q.length--; if(q.rear==p) q.front=q.rear; } void jinru(stackhead &st,linkqueue &q) //对进入停车场的汽车的处理； { int number,time_a; cout<<"车牌为："; cin>>number; cout<<"进场的时刻:"; cin>>time_a; if(st.stacksize_curren<2) { zanInode e; e.number=number; e.ar_time=time_a; push(st,e); cout<< " 该车已进入停车场在: "<<st.stacksize_curren<<" 号车道"<<endl<<endl; } else { enqueue(q,number,time_a); cout<<"停车场已满，该车先停在便道的第"<<q.length<<"个位置上"<<endl; } } void likai(stackhead &st,stackhead &sl,linkqueue &q) //对离开的汽车的处理； { //st堆栈为停车场，sl堆栈为倒车场 int number,time_d,flag=1,money,arrivaltime; //q为便道队列 cout<<"车牌为："; cin>>number; cout<<"出场的时刻："; cin>>time_d; zanInode e,q_to_s; queueptr w; while(flag) //找到要开出的车，并弹出停车场栈 { pop(st,e); push(sl,e); if(e.number==number) { flag=0; money=(time_d-e.ar_time)*2; arrivaltime=e.a