station.cpp

关于数据结构的一个算法问题

#define OK 1
#define ERROR 0
#define null 0
#include <stdio.h>
int StackSize;							//定义车库大小
typedef struct CARLNode{				//定义栈中车节点的类型
	char ad;
	int paizhao;
	int time;
}CARLNode,*LinkList;
typedef struct CARQNode{				//定义队列中车节点的类型
	int paizhao;
	int time;
    struct CARQNode  *next;
  } CARQNode, *QueuePtr;
typedef struct {						//定义队列
    QueuePtr  front;  
    QueuePtr  rear;  
} LinkQueue;
typedef struct Stack{					//定义栈
	CARLNode *base;
	CARLNode *top;
	int stacksize;
}Stack;
void InitQueue (LinkQueue &Q){			//初始化队列
	Q.front=Q.rear=new(CARQNode);
	Q.front->next=null;
}
void EnQueue (LinkQueue &Q, CARLNode e){  //入队
	CARQNode *p;
    p=new(CARQNode);
	p->paizhao=e.paizhao;
	p->time=e.time;
	p->next=0;
	Q.rear->next=p;    
	Q.rear=p;
}
unsigned InitStack(Stack &s){			//初始化栈
	s.base=new(CARLNode);
	if(!s.base){
		printf("Init Stack Error!\n");
		return ERROR;
	}
	s.top=s.base;
	s.stacksize=StackSize;
	return OK;
}
unsigned Push(Stack &s,CARLNode e){   //压栈
	if(s.top-s.base>=s.stacksize)
	return ERROR;
	*s.top++=e;
	return OK;
}
unsigned Pop(Stack &s,CARLNode &e){		//出栈
	if(s.top==s.base)return ERROR;
	e=*--s.top;
	return OK;
}
void carrival(Stack &s,LinkQueue &Q,CARLNode e){  //车到达时的处理
	if(s.top-s.base==StackSize){
		EnQueue (Q,e);
		printf("\n此车停在便道上!!\n\n");
		return;
	}
	Push(s,e);
	printf("\n此车在停车场内%d号!\n\n",s.top-s.base);
}
void carleave(LinkQueue &Q,CARLNode e,Stack &s){	//车离开时的处理
	QueuePtr t,d;
	t=Q.front;
	d=Q.front;
	CARLNode p,data;
	LinkList t1;
	QueuePtr t2;
	Stack temp;
	if(s.top==s.base){								//判断停车场(栈)内是否有车
		printf("\n停车场内还没有车!!\n\n");
		return;
	}
	if(Q.front!=Q.rear){							//判断便道(队列)中是否有车
		t=Q.front->next;
		while(t->paizhao!=e.paizhao){				//要出的车是否在便道(队列)中
			t=t->next;
			d=d->next;
			if(t==null) goto loop;					//如果不在转到loop行
		}
		printf("\n此车将开出便道!!\n\n");			//如果在便道(队列)中则删除该节点
		d->next=t->next;
		t=d;
		if(Q.rear->paizhao==e.paizhao)Q.rear=t;
		return;
	}
	loop:if(t==null||Q.front==Q.rear){	
			t1=s.base;
			while(t1->paizhao!=e.paizhao){			//检查停车场(栈)中是有此车
				t1++;
				if(t1==s.top){
					printf("\n没有此车!!\n\n");
					return;
				}
			}
	}
	data=*t1;
	printf("\n此车需交%d元!\n\n",e.time-data.time);
	InitStack(temp);
	while(t1!=s.top){								//此车后面的车出停车场(t1上面的元素出栈)
		p=*--s.top;
		Push(temp,p);
	}
	temp.top--;
	while(temp.top!=temp.base){						
			Pop(temp,p);							//车进停车场(入栈)
			Push(s,p);								
	}
	if(Q.front!=Q.rear){							//从便道中进停车场一辆(p压入s栈)
		t2=Q.front->next;
		p.paizhao=e.paizhao;
		p.time=e.time;
		p.ad='A';
		Q.front=Q.front->next;
		Push(s,p);
	}
}
void information(Stack s,LinkQueue Q){							//停车信息
	int n=1;
	int m=1;
	for(LinkList i=s.base;i!=s.top;i++){
		printf("停车场%d号位置的车牌号为%d\n",n,i->paizhao);
		n++;
	}
	for(QueuePtr i2=Q.front;Q.rear!=i2;m++){
		i2=i2->next;
		printf("便道中%d号位置的车牌号为%d\n",m,i2->paizhao);
	}
}
void main(){
	Stack s;
	LinkQueue Q;
	printf("请输入车库大小:");
	scanf("%d",&StackSize);
	getchar();
	InitStack(s);
	InitQueue(Q);
	while(1){ 
		printf("请输入数据(用逗号隔开):");										//判断车的进出
		CARLNode e;  
		scanf("%c,%d,%d",&(e.ad),&(e.paizhao),&(e.time));
  		getchar();
		switch(e.ad){   
			case'A':   
			case'a':carrival(s,Q,e),information(s,Q);   
			break;   
			case'D':   
			case'd':carleave(Q,e,s),information(s,Q);  
			break;   
			case'E':   
			case'e':printf("此程序将结束!!");return;
			break;   
			default:printf("输入错误!!\n");   
		}   
	}   
}