HUNANUNIVERSITY實驗報告題目：停車場管理 學(xué)生姓名李湃學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 需求分析1、設(shè)停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。2、輸入要求：每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。3、輸出要求：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。4、測試數(shù)據(jù)：設(shè)n=2，輸入數(shù)據(jù)為：（‘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á)；‘D’表示車輛離去；‘E’表示輸入結(jié)束。概要設(shè)計抽象數(shù)據(jù)類型該問題中數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。第一個數(shù)據(jù)項由題目要求，用英文大寫字符表示，故用英文字符來存儲；第二第三項為正整數(shù)，可用整數(shù)來存儲。停車場只用一個大門可供汽車進(jìn)出，為先進(jìn)先出型，所以可以用棧來模擬，記為1棧。當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場。這個過程車的進(jìn)出規(guī)則為先走后回，可用棧來保存讓路車輛信息，記為2棧。車場外便道上的車輛滿足先進(jìn)后出，可以用隊列來模擬。堆棧的基本操作包括初始化，進(jìn)棧出棧等。隊列的基本操作包括初始化、入隊出隊等。ADTStack{數(shù)據(jù)對象：D={a[i]|a[i]∈｛（字符，整數(shù)，整數(shù)）｝,i=1,2,……,n,n>=0}數(shù)據(jù)關(guān)系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,……,n}約定a[n]端為棧頂，a[1]端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧StackLength(S)初始條件：棧S已經(jīng)存在操作結(jié)果：返回S中元素個數(shù)Push(&S,e)初始條件：棧S已經(jīng)存在操作結(jié)果：將元素e插入成為新的棧頂元素Pop(&S,&e)初始條件：棧S已經(jīng)存在且非空操作結(jié)果：刪除S的棧頂元素，用e返回其值}ADTStackADTQueue{數(shù)據(jù)對象：D={a[i]|a[i]∈｛（字符，整數(shù)，整數(shù)）｝,i=1,2,……,n,n>=0}數(shù)據(jù)關(guān)系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,……,n}約定a[n]端為隊列尾，a[1]端為隊列頭。基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊列QueueLength(Q)初始條件：隊列Q已經(jīng)存在操作結(jié)果：返回Q中元素個數(shù)EnQueue（&Q，e）初始條件：隊列Q已經(jīng)存在操作結(jié)果：將元素e插入成為新的隊尾元素DeQueue(&Q,&e)初始條件：隊列Q已經(jīng)存在且非空操作結(jié)果：刪除Q的隊首元素，用e返回其值}ADTStack算法基本思想接收輸入信息。若為入場(A)，先判斷1棧中元素個數(shù)是否已經(jīng)達(dá)到規(guī)定最大值n（停車場容量），如果沒有，將該信息入1棧，否則將該信息入隊。輸出該入場車輛位置。若為出場(D)，將1棧頂元素出棧，判斷該信息所屬車輛是否為出場車輛。若否，將該信息入2棧，并重新將1棧頂元素出棧，重新判斷。若是，輸出時間差（用時間差表示應(yīng)繳納費用）。然后循環(huán)將2棧中棧頂元素出棧并進(jìn)入1棧直到2棧為空。再將隊首元素出隊入1棧。繼續(xù)接收信息并繼續(xù)判斷，做出相應(yīng)操作，直到接收到的信息為（‘E’，0，0）時退出程序。程序的流程程序由三個模塊組成：輸入模塊：完成車輛信息的儲存。操作模塊：通過判斷決定相應(yīng)操作。輸出模塊：將車輛位置信息或入場出場時間差輸出到屏幕。三、詳細(xì)設(shè)計物理數(shù)據(jù)類型由于棧和隊列中儲存元素的類型一致，所以用相同的存儲結(jié)構(gòu)比較方便。這里用順序存儲結(jié)構(gòu)，因為1棧為滿的概率很大。每個信息元素包含三個數(shù)據(jù)項，分別為字符類型和兩個整數(shù)類型，可分別用C語言中char型和int型保存。元素結(jié)構(gòu)體定義：Typedefstruct{charstate;intNo;inttime;}Elemtype;棧的順序存儲設(shè)計：#defineSTACK_INIT_SIZE10#defineSTACKINCERMENT5typedefstruct{Elemtype*base;Elemtype*top;intstacksize;}SqStack;//棧的基本操作StatusInitStack(SqStack&S){//構(gòu)造一個空棧SS.base=(Elemtype*)malloc(STACK_INIT_SIZE*sizeof(Elemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPop(SqStack&S,Elemtype&e){//若棧不空，則刪除S的棧頂元素，用e返回其值，//并返回OK;否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopStatusPush(SqStack&S,Elemtypee){//插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間S.base=(Elemtype*)realloc(S.base,(S.stacksize+STACKINCERMENT)*sizeof(Elemtype));if(!S.base)exit(OVERFLOW);//存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCERMENT;}*S.top++=e;returnOK;}//PushintStackLength(SqStack&S){//返回棧的長度returnstacksize;}隊列的順序存儲設(shè)計：#defineMAXQSIZE10typedefstruct{Elemtype*base;intfront;intrear;}SqQueue;//基本操作StatusInitQueue(SqQueue&Q){//構(gòu)造一個空隊列QQ.base=(Elemtype*)malloc(MAXqSIZE*sizeof(Elemtype));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}intQueueLength(SqQueueQ){//返回Q的元素個數(shù)，即隊列的長度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}StatusEnQueue(SqQueue&Q,Elemtypee){//插入元素e為Q的新的隊尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊列滿Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}StatusDeQueue(SqQueue&Q,Elemtype&e){//若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK；//否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}輸入輸出格式：輸入：請輸入停車場大小：//提示請輸入汽車入場出場信息：//提示偽代碼：printf("請輸入停車場大小:\n");scanf("%d",&n);getchar();if(n<1)returnERROR;printf("請輸入汽車入場出場信息：\n");輸出：//位置*車停在停車場第*個位置//或*車停在便道第*個位置//收費*車在停車場停留時間為：**偽代碼：printf("%d車停在停車場第%d個位置\n",e.No,StackLength(S1));}printf("%d車停在便道第%d個位置\n",e.No,QueueLength(Q));}printf("%d車在停車場停留時間為：%d\n",e.No,e.time-c.time);停車場問題具體實現(xiàn)步驟：while((e.state=getchar())!='E'){scanf("%d%d",&e.No,&e.time);getchar();switch(e.state){case'A':if(StackLength(S1)<n){Push(S1,e);printf("%d車停在停車場第%d個位置\n",e.No,StackLength(S1));}else{EnQueue(Q,e);printf("%d車停在便道第%d個位置\n",e.No,QueueLength(Q));}break;case'D':while(1){Pop(S1,c);if(e.No==c.No)break;if(StackLength(S1)==0)return(ERROR);Push(S2,c);}if(e.time<c.time)return(ERROR);printf("%d車在停車場停留時間為：%d\n",e.No,e.time-c.time);while(StackLength(S2)!=0){Pop(S2,c);Push(S1,c);}if(QueueLength(Q)!=0){