a1.cpp

清化大学的数据结构（C语言版本）上所有例子的代码实现

 #include<malloc.h> // malloc()等
 #include<stdio.h> // EOF(=^Z或F6),NULL
 #include<stdlib.h> // atoi()
 #include<iostream.h> // cout,cin
 // 函数结果状态代码
 #define NULL 0
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0

typedef struct {
				int num; //车牌号码
				char AorD; //车的进或出的情况
				int time; //车进或出的时间
}CAR;

//*****************************************************************************
typedef struct{
				CAR *base;
				int top;
				int size;
}sqstack;

typedef struct QNode{
			    CAR date;
				struct QNode *next;
}QNode,*qptr;


typedef struct{
				qptr front;
				qptr rear;
}LinkQueue;

//*****************************************************************************
//构造空栈
void Initstack(sqstack &s,int n){
				s.base=(CAR *)malloc(n*sizeof(CAR));
					//if(!s.base)   // return error;
						s.top=0;
						s.size=n;
					//	return OK;
}
//*****************************************************************************

//建立空链表
void Initqueue(LinkQueue &Q)
{
	  Q.front=(qptr)malloc(sizeof(QNode));
      Q.front->next=NULL;Q.rear=Q.front;
	 //  return OK;
}
//**************************************************************************************************************

//入队列情况（进入便道内）
void Enqueue(LinkQueue &Q,CAR e){
			qptr p;
                        p=(qptr)malloc(sizeof(QNode));
			//	if(!p)   return error;
						p->date.num=e.num;p->date.AorD=e.AorD;p->date.time=e.time;
						p->next=NULL;
						Q.rear->next=p;
						Q.rear=p;
			
				//	return OK;
}
//**************************************************************************************************************



//退出队列情况
void Dequeue(LinkQueue &Q,CAR e){
          
          qptr p,q,s;
          if( Q.front==Q.rear) cout<<"输入错误，不存在这样的车"<<endl;
          else{
               p=Q.front;
			   q=p->next;s=Q.rear;
               while(q!=s->next&&e.num!=q->date.num)
                  {
			       p->next=q->next;
			       Q.rear->next=q; 
                   Q.rear=q;
			       q=p->next;
		          }
        
	          if(q=s->next)  cout<<"输入错误，不存在这样的车"<<endl;
	          else
                {
                   int T=e.time-q->date.time;
			       cout<<"该车在便道上停留的时间是"<<T<<endl;
                   cout<<"免费"<<endl;	
                   p->next=q->next;
                   if(s!=q)
                     {  free(q);	
                        q=p->next;
                        while(q!=s->next)
                           {
			                   p->next=q->next;
			                   Q.rear->next=q; Q.rear=q;
                               q=p->next;
                           }
                      }
                  else free(q);
          
			     }   
		      Q.rear->next=NULL;
	        }
	        }
//*****************************************************************************


 //入栈情况（进入停车场内）
int push(sqstack &s,CAR e){
	     
		if(s.top>=s.size){//栈满
			return ERROR;
           }
		else{	s.base[s.top].num=e.num;	s.base[s.top].AorD=e.AorD;	
                 s.base[s.top].time=e.time;
			s.top++;
			cout<<"该车在停车场内的位置："<<s.top<<endl;
			return OK;
		}//else
}//push


//*****************************************************************************

void pop(sqstack &s,LinkQueue &Q,CAR e,int V)
      {
			CAR F;
			qptr p;
			sqstack s1;
		    int T,h,m;
		    m=s.size;
		    Initstack(s1,m); 
		    while((s.top!=0)&&(s.base[s.top-1].num!=e.num))
                    { --s.top;
                    F.num=s.base[s.top].num;F.AorD=s.base[s.top].AorD;
                    F.time=s.base[s.top].time;
                    push(s1, F);
                    }
            if(s.top==0)
                { while(s1.top!=0)
                     { --s1.top;
                        F.num=s1.base[s1.top].num;F.AorD=s1.base[s1.top].AorD;
                        F.time=s1.base[s1.top].time;
                       push(s,F);
                     }
                  Dequeue(Q,e);
                }
			else{
                 --s.top;
                  F.num=s.base[s.top].num;F.AorD=s.base[s.top].AorD;
                  F.time=s.base[s.top].time;
                  T=e.time-F.time;
                  h=T*V;
			      cout<<"该车在停车场内停留的时间是"<<T<<endl;
                  cout<<"该车应该付的费用是:"<<h<<"元"<<endl;
                  while(s1.top!=0)
                       {s1.top--;
                        F.num=s1.base[s1.top].num;
                        F.AorD=s1.base[s1.top].AorD;
                        F.time=s1.base[s1.top].time;
                        push(s,F);
                       }
                   free(s1.base);    
			     if( Q.front!=Q.rear)
			         {
                       p=Q.front->next;
                       Q.front->next=p->next;
                       F.num=p->date.num;
                       F.AorD=p->date.AorD;
                       F.time=e.time;
                       push(s,F);free(p);
                     }
                   }
                 }
              
                     
void main()
{
	    CAR c,e;
		int n,i,V;
		cout<<"请输入停车场的长度:"<<endl;
		cin>>n;
		cout<<"请输入停车的单价:"<<endl;
		cin>>V;
		sqstack s;
        LinkQueue Q;
		Initqueue(Q);
        Initstack(s,n);
//输入信息
do{
		cout<<"请输入该车的进入或出去的信息:"<<" "<<endl;
		cin>>c.AorD;
		cout<<"请输入该车的车牌号码："<<" "<<endl;
		cin>>c.num;
		cout<<"请输入该车的进或出的时间"<<" "<<endl;
		cin>>c.time;
			switch(c.AorD){
				case'A':
					if(!push(s,c)) Enqueue(Q,c);
				case'D':
					pop(s,Q,e,V);
			
				}
	}while(c.AorD!='E');
}