数据结构实验二

PAGE第1页共9页华北水利水电学院数据结构实验报告2011～2012学年第二学期2011级计算机专业班级：2011179学号：201117914姓名：刘珍实验二栈和队列及其应用实验目的：1．掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2．掌握队列的特点(先进先出FIFO)及基本操作，如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活运用。实验内容：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’表示输入结束。实验要求：C/C++完成算法设计和程序设计并上机调试通过。撰写实验报告，提供实验结果和数据。写出算法设计小结和心得。程序源代码：1，2放在一快写：#include<stdio.h>#include<malloc.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintelemtype;typedefintstatus;typedefstructQNode{elemtypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;typedefstructlnode{elemtypedata;structlnode*next;}stacknode,*linkstack;statusinitstack(linkstacktop){top->next=NULL;}statusisempty(linkstacktop){if(top->next==NULL)returnOK;returnERROR;}statuspush(linkstacktop,elemtypee){stacknode*p;p=(stacknode*)malloc(sizeof(stacknode));if(p==NULL)returnERROR;p->data=e;p->next=top->next;top->next=p;returnOK;}statuspop(linkstacktop,elemtype*e){if(isempty(top))returnERROR;stacknode*p=top->next;*e=p->data;top->next=p->next;free(p);returnOK;}statusshstack(linkstacktop){ stacknode*p; p=(stacknode*)malloc(sizeof(stacknode)); p->next=top->next; while(p->next!=NULL){ printf("%d",p->next->data); p->next=p->next->next; } returnOK;}statusinitqueue(LinkQueue*q){ (*q).front=(*q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*q).front)exit(OVERFLOW); (*q).front->next=NULL; returnOK;}statusenqueue(LinkQueue*q,elemtypee){ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e; p->next=NULL; (*q).rear->next=p; (*q).rear=p; returnOK;}statusdequeue(LinkQueue*q,elemtype*e){ if((*q).front==(*q).rear)returnERROR; QueuePtrp; p=(*q).front->next; *e=p->data;//注意 (*q).front->next=p->next; if((*q).rear==p)(*q).rear==(*q).front; free(p); returnOK;}voidmain(){ linkstacks; s=(linkstack)malloc(sizeof(stacknode)); initstack(s); printf("进入栈的4个元素依次为：\n"); for(inti=0;i<4;i++) { elemtypea; scanf("%d",&a); push(s,a); } printf("\n栈顶到栈底的元素依次为；\n"); shstack(s); elemtypeb,c,d; pop(s,&b); pop(s,&c); pop(s,&d); push(s,b); printf("\n\n出栈的元素为:"); printf("%d",c); printf("%d\n",d); printf("\n现在栈中的元素为："); shstack(s); LinkQueueq; initqueue(&q); elemtypea; printf("\n\n\n请输入5个进队的元素:\n"); for(inti=0;i<5;i++) {scanf("%d",&a);enqueue(&q,a); } printf("\n元素的出列为:\n"); for(inti=0;i<5;i++) { elemtypee; dequeue(&q,&e); printf("%d",e); }}3中代码：#include"iostream.h"intN;constintM=5;//M为单元时间的收费值structcinfo//定义栈中元素的类型{intcnum;intatime;};structstack//定义栈{cinfocstack[3000];//这里随便定义一个数字表示数组的长度,因为后inttop;//面会根据用户输入的N值作为停车场能够停车的intsize;//数量.};structnode//定义队列节点的类型{node*next;intnnum;};structqueue//定义队列{node*front,*rear;};voidinitstack(stack*s)//初始化栈{s->top=-1;}intinstack(stack*s,cinfox)//元素进栈{//int元素进栈n;if(s->top==N-1){cout<<"Stackisfull!"<<endl;return0;}else{s->cstack[++s->top]=x;return1;}}cinfooutstack(stack*s)//元素出栈{cinfoy;if(s->top<0){um=NULL;y.atime=NULL;returny;}else{s->top--;returns->cstack[s->top+1];}}voidinitqueue(queue*q)//初始化队列{q->front=newnode;q->rear=q->front;q->front->next=NULL;q->front->nnum=0;}voidinqueue(queue*q,intnum1)//元素进队列{node*p;p=newnode;p->nnum=num1;p->next=NULL;q->rear->next=p;q->rear=p;q->front->nnum++;}intoutqueue(queue*q)//元素出队列{node*p;intn;if(q->front==q->rear)return0;else{p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;n=p->nnum;deletep;q->front->nnum--;returnn;}}voidcarrival(stack*s,queue*q,cinfox)//处理车辆到达的情况{intf;f=instack(s,x);if(f==0){inqueue(q,um);cout<<"TheNumber"<<um<<""<<"carparkintothepos"<<q->front->nnum<<""<<"oftheroad."<<endl;}else{cout<<"TheNumber"<<um<<""<<"carparkintothepos"<<s->top+1<<""<<"oftheroom."<<endl;}}voidcarleave(stack*s1,stack*s2,queue*q,cinfox)//处理车辆离开{node*p;cinfoy;inta,n=0;while((s1->top>-1)&&(n==0)){y=outstack(s1);if(um!=um){a=instack(s2,y);}elsen=1;}if(um==um){cout<<"Thenumber"<<um<<""<<"carwanttoleave,thechargeis"<<""<<(x.atime-y.atime)*M<<""<<"yuan!"<<endl;while(s2->top>-1){y=outstack(s2);n=instack(s1,y);}a=outqueue(q);if(a!=0){um=a;y.atime=x.atime;n=instack(s1,y);cout<<"TheNumber"<<um<<""<<"carparkintothepos"<<s1->top+1<<""<<"oftheroom."<<endl;}}else{while(s2->top>-1){y=outstack(s2);n=instack(s1,y);}p=q->front;n=0;while(p->next!=NULL&&n==0){if(p->next->nnum!=um)p=p->next;else{p->next=p->next->next;q->front->nnum--;if(p->next=NULL)q->rear=q->front;cout<<"Thenumber"<<um<<""<<"wanttoleavefromtheroad."<<endl;n=1;}}if(n==0){cout<<"Youhaveenteredawrongnumber!"<<endl;}}}voidmain()//主程序{//intmaxsize;cout<<"Start，WrittenbyZIGZ"<<endl<<endl<<endl;cout<<"PleaseenteranumberasthemaxsizeoftheroomStack:"<<endl;cin>>N;//这里N将作为栈能存放元素的数量while(N<=0){cout<<"Oh!Youhaveenterawrongnumber,'N'shouldabove0.Pleaseenteranothernumberagain:"<<endl;cin>>N;}//stack*max;//max->size=maxsize;charch1;stack*s1,*s2;queue*q;cinfox;intflag;s1=new