华北水利水电学院数据结构实验报告2011～2012学年第二学期2011级计算机专业班级：**** 学号：***** 姓名：**** -实验二栈和队列及其应用一、实验目的：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’表示输入结束。

三、实验要求：1．C/ C++完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．写出算法设计小结和心得。

四、程序源代码：1.#include<iostream.h>#include<stdlib.h>typedef struct stnode{int data;stnode *next;}LinkStack;//创建一个栈头结点，无头结void InitStack(LinkStack *&ls){ls=NULL;}//进栈，相当于头插法void Push(LinkStack *&ls,int x){LinkStack *p;p=(LinkStack *)malloc(sizeof(LinkStack));p->data=x;p->next=NULL;p->next=ls;ls=p;}//出栈void Pop(LinkStack *&ls){if(ls==NULL)return;LinkStack *p;int x;p=ls;while(p){x=p->data;ls=p->next;cout<<x<<" ";free(p);p=ls;}cout<<"出栈成功!!"<<endl;}//创建栈void CreatStack(LinkStack *&ls){InitStack(ls);int i=1,num;cout<<"以000表示输入结束!!"<<endl;while(1){cout<<"请输入第"<<i<<"个元素:";cin>>num;if(num==000)break;Push(ls,num);i++;}cout<<"进栈成功！！"<<endl;}void main(){LinkStack *ls,*p;CreatStack(ls);Pop(ls);}2.#include<iostream.h>#define QueueSize 100typedef struct sqqueue{int data[QueueSize];int front,rear;}SqQueue;//初始化队列void InitQueue(SqQueue &qu){qu.rear=qu.front=0;}//进队int EnQueue(SqQueue &sq,int x){if((sq.rear+1)%QueueSize==sq.front) return 0;sq.rear=(sq.rear+1)%QueueSize;sq.data[sq.rear]=x;return 1;}//出队void DeQueue(SqQueue &sq){int x;if(sq.front==sq.rear)return;while(sq.front!=sq.rear){sq.front=(sq.front+1)%QueueSize;x=sq.data[sq.front];cout<<x<<" ";}cout<<"出队成功!!"<<endl;}//创建队void CreatQueue(SqQueue &sq){InitQueue(sq);int num,i=1;cout<<"以000表示输入结束！！"<<endl;while(1){cout<<"请输入第"<<i<<"个元素:";cin>>num;if(num==000)break;EnQueue(sq,num);i++;}cout<<"进队成功！！"<<endl;}void main(){SqQueue sq;CreatQueue(sq);DeQueue(sq);}3.#include<iostream.h>#include<stdlib.h>#include<stdio.h>#define MAX 2#define price 0.05typedef struct node{int hour;int min;}Time;//时间结点typedef struct Node{char num[10];//车牌号Time reach;//时间Time leave;}CarNode;//车辆信息结点typedef struct NODE{CarNode *stack[MAX];int top;}CarStack;//顺序栈模拟车站typedef struct QNode//队列{CarNode *data;QNode *next;}QueueNode;//链队结点类型typedef struct pqrt{QueueNode *front,*rear;//设置头指针尾指针}LinkQueueCar;//模拟通道//初始化栈void InitStack(CarStack *cs);//初始化队列(便道)int InitQueue(LinkQueueCar *qc);//车辆到达int Arrival(CarStack *Enter,LinkQueueCar *qc);//车辆离开void Leave(CarStack *Enter,CarStack *Temp,LinkQueueCar *qc); //显示车库信息void List(CarStack s,LinkQueueCar w);void main(){CarStack Enter,Temp;LinkQueueCar Wait;int ch;InitStack(&Enter);InitStack(&Temp);InitQueue(&Wait);while(1){cout<<"欢迎光临"<<endl;cout<<"-----------------------"<<endl;cout<<"1.车辆到达"<<endl;cout<<"2.车辆离开"<<endl;cout<<"3.车场显示"<<endl;cout<<"4.退出程序"<<endl;cout<<"-----------------------"<<endl;cout<<"请选择所需的服务!"<<endl;while(1){cin>>ch;if(ch>=1&&ch<=4)break;}switch(ch){case 1:Arrival(&Enter,&Wait);break;case 2:Leave(&Enter,&Temp,&Wait);break;case 3:List(Enter,Wait);break;case 4:exit(0);break;default:break;}}}void InitStack(CarStack *cs){cs->top=-1;//初始化栈for(int i=0;i<MAX;i++)cs->stack[cs->top]=NULL;}int InitQueue(LinkQueueCar *qc)//初始化队列{//qc=(LinkQueueCar *)malloc(sizeof(LinkQueueCar));这句话不能要?????qc->front=(QueueNode *)malloc(sizeof(QueueNode));if(qc->front!=NULL){qc->front->next=NULL;//带头结点的qc->rear=qc->front;//一定要注意赋值顺序不能反了!!!!!!!!!!return 1;}elsereturn -1;}//打印车站车离开的信息void Print(CarNode *p,int room){int A1,A2,B1,B2;//车辆收费cout<<"请输入离开时间:/**:**/"<<endl;cout<<"请输入离开时间的时(0-23):";cin>>p->leave.hour;while(p->leave.hour<p->reach.hour||p->leave.hour>23){cout<<"error!!"<<endl;cin>>p->leave.hour;}B1=p->leave.hour;cout<<"请输入离开时间的分钟(0-59):";cin>>p->leave.min;while(p->leave.min<0||p->leave.min>59){cout<<"error!!"<<endl;cin>>p->leave.min;}B2=p->leave.min;cout<<endl<<"离开汽车的车牌号为："<<endl;puts(p->num);cout<<"其到达时间为:"<<p->reach.hour<<":"<<p->reach.min<<endl;cout<<"其离开时间为:"<<p->leave.hour<<":"<<p->leave.min<<endl;A1=p->reach.hour;A2=p->reach.min;cout<<"应交费用为:"<<((B1-A1)*60+(B2-A2))*price<<"元"<<endl;free(p);}int Arrival(CarStack *Enter,LinkQueueCar *qc){CarNode *p;QueueNode *t;p=(CarNode *)malloc(sizeof(CarNode));cout<<"请输入车牌号(例A8888):"<<endl;gets(p->num);if((Enter->top+1)<MAX){Enter->top++;cout<<"车辆在车场第"<<Enter->top<<"位置"<<endl;cout<<"请输入到达时间:/**:**/"<<endl;cout<<"请输入到达时间的时(0-23):";cin>>p->reach.hour;while(p->reach.hour<0||p->reach.hour>23){cout<<"error!!"<<endl;cin>>p->reach.hour;}cout<<"请输入到达时间的分(0-59):";cin>>p->reach.min;Enter->stack[Enter->top]=p;//注意数组下标是从0开始，在显示时下标也要与之对应cout<<"车近停车场成功!!"<<endl;return 1;}else{cout<<"该车需在便道上等待!"<<endl;t=(QueueNode *)malloc(sizeof(QueueNode));//进队列t->data=p;t->next=NULL;qc->rear->next=t;qc->rear=t;cout<<"车进便道成功!!"<<endl;return 1;}}void Leave(CarStack *Enter,CarStack *Temp,LinkQueueCar *qc){CarNode *p,*t;QueueNode *q;int room;if(Enter->top>-1)//判断车场是否为空{while(1){cout<<"请输入车在车场中的位置:";cin>>room;if(room>=0&&room<=Enter->top)break;}//要离开的车后面还有车，则后面的车需进入临时栈给前面的车让路while(Enter->top>room)//用Enter->top和room相比看你的车在第几个位置，前面的几辆车需全部让路{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;}//让路完以后车再离开p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;//车离开后，如果临时栈里有车，重新进车站while(Temp->top>=0){Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;cout<<"临时车场里的车重新进站成功!!"<<endl;}Print(p,room);//调用计费函数//车离开后如果便道上有车，也进车站if(qc->front!=qc->rear&&Enter->top<MAX)//判断便道上是否有车以及车站是否已满{q=qc->front->next;t=q->data;Enter->top++;cout<<"便道上的"<<t->num<<"号车进入车场第"<<Enter->top<<"位置"<<endl;cout<<"请输入现在的时间:/**:**/"<<endl;cout<<"请输入到达时间的时(0-23):";cin>>t->reach.hour;while(t->reach.hour<0||t->reach.hour>23){cout<<"error!!"<<endl;cin>>t->reach.hour;}cout<<"请输入到达时间的分(0-59):";cin>>t->reach.min;qc->front->next=q->next;//出便道if(q==qc->rear) qc->front=qc->rear;Enter->stack[Enter->top]=t;//进车站free(q);cout<<"便道的车进入停车场成功!!"<<endl;}elsecout<<"便道里没有车!!"<<endl;}elsecout<<"车场里没有车!!"<<endl;}void List1(CarStack *s)//显示车场信息{int i;if(s->top>-1){cout<<"车场"<<endl;cout<<"位置时间车牌号"<<endl;for(i=0;i<(s->top+1);i++){cout<<" "<<i<<" "<<s->stack[i]->reach.hour<<":"<<s->stack[i]->reach.min<<" "<<s->stack[i]->num<<endl;}}elsecout<<"车场里没有车!!"<<endl;}void List2(LinkQueueCar *w)//显示便道信息{QueueNode *p;p=w->front->next;//p先指向第一辆车，if(w->front!=w->rear)//判断便道是否为空{cout<<"等待车辆的号码为:"<<endl;while(p)//用指针p遍历输出数据{puts(p->data->num);p=p->next;}}elsecout<<"便道里没有车!"<<endl;}void List(CarStack s,LinkQueueCar w)//显示整个停车场的信息{int flag,tag;flag=1;while(flag){cout<<"请选择1|2|3:"<<endl;cout<<"1.车场"<<" "<<"2.便道"<<" "<<"3.返回"<<endl;while(1){cin>>tag;if(tag>=1||tag<=3)break;elsecout<<"请选择1|2|3:"<<endl;}switch(tag){case 1:List1(&s);break;case 2:List2(&w);break;case 3:flag=0;break;default:break;}}}五、程序运行情况（写出输入数据及运行结果）六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）本次实验前两题是栈和队列的基本算法，是基础练习，关键是第三题，具体谈谈我理解的停车场。