### 問題描述 汽車輪渡口，過江渡船每次能載10輛車過江。過江車分為客車和貨車類，上渡船有如下規定： 1).同類車先到先上船； 2).客車先于貨車上渡船，其每上4輛客車，才允許放上一輛貨車； 3).若等待客車不足4輛，則以貨車代替； 4).若無貨車等待，允許客車都上船。 試設計一個算法模擬渡口管理 ## 算法思想 經過分析，發現此題實際上就是隊列的基本操作，唯一的不同就是在入隊的時候，對于順序進行了限制。 - 使用隊列Q表示每次載渡的車輛，隊列Qp表示客車，Qt表示貨車隊列； - 如果Qp中元素足夠，則每從隊列Qp中出隊4個元素，從隊列Qt中出隊1元素，直到隊列Q的長度為10； - 若隊列Qp中元素不充分，則直接使用隊列Qt中的元素補齊。 ## 算法描述 ~~~ void manager(){ if(IsEmpty(&Qp)!=0&&car<4){ DeQueue(&Qp,&e); EnQueue(&Q,e); car++; count++; }else if(car==4&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); car=0; count++; }else{ while(count<=MaxSize&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); count++; } } if(IsEmpty(&Qt)==0&&IsEmpty(&Qp)==0){ count=11; } } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #define MaxSize 10 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int front, rear; }SqQueue; void InitQueue(SqQueue*); void EnQueue(SqQueue*, ElemType); void DeQueue(SqQueue*, ElemType*); int IsEmpty(SqQueue*); void Mangager(SqQueue*, SqQueue*, SqQueue*); void PrintQueue(SqQueue); int main(int argc,char* argv[]) { SqQueue Q; SqQueue Qp;//客車 SqQueue Qt;//貨車 InitQueue(&Q); InitQueue(&Qp); InitQueue(&Qt); ElemType x='P'; for(int i=0;i<6;i++){ EnQueue(&Qp,x); } ElemType y='T'; for(int i=0;i<6;i++){ EnQueue(&Qt,y); } int count=0; int car=0; ElemType e; //渡口模擬 while(count<=MaxSize){ if(IsEmpty(&Qp)!=0&&car<4){ DeQueue(&Qp,&e); EnQueue(&Q,e); car++; count++; }else if(car==4&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); car=0; count++; } else{ while(count<=MaxSize&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); count++; } } if(IsEmpty(&Qt)==0&&IsEmpty(&Qp)==0) { count=11; } } PrintQueue(Q); return 0; } /*---------------------------------------------------------------*/ void InitQueue(SqQueue* Q) { Q->front=0; Q->rear=0; } void EnQueue(SqQueue* Q, ElemType x) { if(Q->rear==MaxSize-1){ return; } Q->data[Q->rear++]=x; } void DeQueue(SqQueue* Q, ElemType *x) { if(Q->front==Q->rear&&Q->front==0){ return; } *x=Q->data[Q->front++]; } ~~~