停車場管理問題

1、停車場管理問題實驗二：停車場管理問題一問題描述1. 實驗題目：設(shè)停車場是一個可停放n 輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端）。若停車場內(nèi)已經(jīng)停滿n 輛車，那么后來的車只能在門外的便道上等候。一旦有車開走，則排在便道上的第一輛車即可開入。當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場。 每輛停放在車場的車在它離開停車場時必須按它停留的時間長短繳納費用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。2. 基本要求：以

2、棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車的“到達(dá)"（'A'表示）或“離去" （'D表示）信息、汽車標(biāo)識（牌照號）以及到達(dá)或離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或者便道上的停車位置；若是車輛離去，則輸出汽車在停車場停留的時間和應(yīng)繳納的費用（便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。3. 測試數(shù)據(jù)：設(shè)n=2, 輸入數(shù)據(jù)為：（ A ，1，5） ，（ A ，2， 10） ，（ D ， 1， 15） ，（ A ， 3，2

3、0 ） ， （ A ，4，25） ， （ A ，5，30）， （ D ，2，35） ， （ D ， 4，40） ， （ E ， 0，0） 。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車 “到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，'A'表示到達(dá)；D表示離去，'E'表示輸入結(jié)束。其中：（'A', 1, 5）表示1號牌照車 在 5 這個時刻到達(dá)，而（ D ， 1， 15）表示1 號牌照車在15 這個時刻離去。二需求分析1. 程序所能達(dá)到的基本可能：程序以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實

4、現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。同時另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車。輸入數(shù)據(jù)按到達(dá)或離去的時刻有序。當(dāng)輸入數(shù)據(jù)包括數(shù)據(jù)項為汽車的“到達(dá)" （'A'表示）信息，汽車標(biāo)識（牌照號）以及到達(dá)時刻時，應(yīng)輸出汽車在停車場內(nèi)或者便道上的停車位置；當(dāng)輸入數(shù)據(jù)包括數(shù)據(jù)項為汽車的“離去"（'D'表示）信息，汽車標(biāo)識（牌照號）以及離去時刻時，應(yīng)輸出汽車在停車場停留的時間和應(yīng)繳納的費用（便道上停留的時間不收費）；當(dāng)輸入數(shù)據(jù)項為（ P ， 0， 0）時，應(yīng)輸出停車場的車數(shù)；當(dāng)輸入數(shù)據(jù)項為（ W , 0, 0 ）時，應(yīng)輸出候車場車數(shù)；當(dāng)輸入數(shù)據(jù)

5、項為（ E , 0, 0 ） ，退出程序；2. 輸入輸出形式及輸入值范圍：程序運行后進(jìn)入循環(huán)，顯示提示信息： “請輸入停車場最大容量 n=: ”，提示用戶輸入停車場最大容量，輸入后顯示提示信息：請輸入車輛信息，提示用戶輸入車輛信息（ “到達(dá)”或者“離開” ， 車牌編號，到達(dá)或者離開的時間）。 若車輛信息為 “到達(dá)A”， 車輛信息開始進(jìn)棧（ 模擬停車場），當(dāng)棧滿，車輛會進(jìn)隊列（模擬停車場旁便道），若車輛信息為“離開D”，會顯示該車進(jìn)入停車場的時間以及相應(yīng)的停車費用，若該車較部分車早進(jìn)停車場，這部分車需先退出停車場，暫時進(jìn)入一個新棧為其讓道，當(dāng)待離開車離開停車場后，這部分車會重新進(jìn)入停車場，同時便

6、道上的第一輛車進(jìn)入停車場；若輸入（ P ， 0， 0） ，會顯示停車場的車數(shù)；若輸入（ W ， 0， 0） ，會顯示便道上的車數(shù)；若輸入（ E ， 0， 0） ，程序會跳出循環(huán)，同時程序結(jié)束。用戶每輸入一組數(shù)據(jù)，程序就會根據(jù)相應(yīng)輸入給出輸出。輸入值第一個必須為字母，后兩個為數(shù)字，中間用逗號隔開3. 測試數(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） 。三概要設(shè)計1. 所用到得

7、數(shù)據(jù)結(jié)構(gòu)及其ADT為了實現(xiàn)上述功能，該程序以順序棧模擬停車場以及臨時停放為給要離去的汽車讓路而從停車場退出來的汽車的場地，以鏈表隊列模擬車場外的便道，因此需要棧和隊列這兩個抽象數(shù)據(jù)類型。順序棧數(shù)據(jù)類型定義typedef struct Stackstruct Node dataMaxSize;int top;int num;SqStack;基本操作：SqStack *Init_SeqStack（）/ 置空棧int ISEmpty_SeqStack（SqStack *s）/ 判斷棧是否為空，棧為空返回1int ISFULL_SeqStack（SqStack *s,int n）/ 判斷棧是否已滿，若

8、棧滿返回1void Push_SeqStack（SqStack *p,struct Node s） /入棧int POP_SeqStack（SqStack *s,struct Node car）/出棧2. 鏈表隊列數(shù)據(jù)類型定義QNODE / 隊列節(jié)點 struct Node data;3 / 19停車場管理問題QNODE *next;；typedef struct linkqueue /隊列結(jié)構(gòu)體定義QNODE *front,*rear;int num;LinkQueue;基本操作:LinkQueue *Init_LQueue() /創(chuàng)建空隊列int ISEmpty_LQueue(LinkQu

9、eue *q)/判斷隊列是否為空，隊列為空返回void IN_Lqueue( LinkQueue *q,struct Node s) /入隊struct Node Out_LQueue(LinkQueue *q) /出隊2.主程序流程及其模塊調(diào)用關(guān)系1）主程序模塊開始初始界面顯示輸入停車場最大容量n輸入車輛信息N* car.AL='A'car.AL='D'car.AL='P； car.NO=0 car.time=0N car.AL='W；car.NO=Qcar.time=0N- car.AL!='E'棧滿Y出棧，輸出車輛停留時間J

10、'顯示停車場的車數(shù)顯示候車場的車數(shù)車輛在停車場的位置進(jìn)入隊列輸出車輛在便道的位置輸入車輛信息進(jìn)棧，車輛從便道進(jìn)入停車場*輸入結(jié)束結(jié)束2）出棧9 / 19開始13）判斷棧是否為空開始s->top =-1棧空返回 1棧不為空返回0結(jié)束4）判斷棧是否已滿s->top =n-1棧不滿返回05)判斷隊列是否為空隊列空返回1隊列不為空返回6)出隊函數(shù)調(diào)用:main()函數(shù)中調(diào)用:ISFULL_SeqStack(parkstack,n) ,IN_Lqueue(parkqueue,car);Push_SeqStack(parkstack,car);t=POP_SeqStack(parkst

11、ack,car);ISEmpty_LQueue(parkqueue)=0 ;Push_SeqStack(parkstack,Out_LQueue(parkqueue);POP_SeqStack(SqStack *s,struct Node car)出棧函數(shù)中調(diào)用:Init_SeqStack();Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0函數(shù)調(diào)用關(guān)系圖詳細(xì)設(shè)計四、1.實現(xiàn)每個操作的偽碼，重點語句加注釋1）主程序模塊 int main()SqStack *parkstack;/parkstack 為表示停車場的棧LinkQu

12、eue *parkqueue; /parkqueue為表示便道的隊歹Ustruct Node car;停車場管理問題為停車場棧的最大容量int n,a=0,t;/ntime_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);parkstack=Init_SeqStack();parkqueue=Init_LQueue();15 / 19printf("/*/n"); /初始界面printf("學(xué)號： 031350102n");pri

13、ntf("姓名：王亞文n");printf("停車場管理問題n");printf("/*/n");printf(" 請輸入停車場最大容量n=n");scanf("%d",&n);printf(" 請輸入車輛信息n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);while(car.AL!='E')if(car.AL='A' )/ 汽車到達(dá)的情況if(

14、ISFULL_SeqStack(parkstack,n)=1)/ 棧滿的情況IN_Lqueue(parkqueue,car);/ 進(jìn)入隊列等待printf("這輛車在門外便道上第外位置n",parkqueue->num);printf("n");printf(" 請輸入車輛信息n");else Push_SeqStack(parkstack,car);/ 入棧printf("這輛車在停車場內(nèi)第 d個位置n",parkstack->num);printf("n");printf(&qu

15、ot; 請輸入車輛信息n");if(car.AL='D' )/ 汽車離開的情況t=POP_SeqStack(parkstack,car);/出棧printf(" 這輛車停留時間為%dn",t);printf("n");printf(" 請輸入車輛信息n");if(ISEmpty_LQueue(parkqueue)=0) /隊列不為空需要進(jìn)棧Push_SeqStack(parkstack,Out_LQueue(parkqueue) ); if(car.AL='P'&&car.NO

16、=0&&car.time=0 )/顯示停車場的車數(shù)printf("停車場的車數(shù)為%dn",parkstack->num);printf("n");printf("請輸入車輛信息n");if(car.AL='W'&&car.NO=0&&car.time=0 )/顯示候車場的車數(shù)printf(" 候車場的車數(shù)為%dn",parkqueue->num);printf("n");printf(" 請輸入車輛信息n&qu

17、ot;);scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);printf(" 輸入結(jié)束n");return 1;2)置空棧模塊SqStack *Init_SeqStack()/ 置空棧SqStack *s;s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;s->num=0;return s;3)創(chuàng)建空隊列模塊LinkQueue *Init_LQueue() /創(chuàng)建空隊列LinkQueue *q;QNODE *p;q=(LinkQueue*)m

18、alloc(sizeof(LinkQueue);p=(QNODE*)malloc(sizeof(QNODE);p->next=NULL;q->front=q->rear=p;q->num=0;return q;4)判斷棧是否為空模塊int ISEmpty_SeqStack(SqStack *s)if(s->top =-1)return 1;elsereturn 0;5)判斷棧是否已滿模塊int ISFULL_SeqStack(SqStack *s,int n)if(s->top=n-1)return 1;elsereturn 0;6)判斷隊列是否為空模塊in

19、t ISEmpty_LQueue(LinkQueue *q)/ 判斷棧是否為空，棧為空返回1/ 判斷棧是否已滿，若棧滿返回1/ 判斷隊列是否為空，隊列為空返回1if(q->front=q->rear)return 1;elsereturn 0;7)入隊模塊void IN_Lqueue( LinkQueue *q,struct Node s) /入隊QNODE *p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q->num+;p->next=NULL;q->rear->next =p;q->rear =p;8)

20、入棧模塊void Push_SeqStack(SqStack *p,struct Node s) /入棧p->top +;p->datap->top=s;p->num+;9)出棧模塊int POP_SeqStack(SqStack *s,struct Node car)/出棧SqStack *p;int t;p=Init_SeqStack();while(s->datas->top.NO !=car.NO)找到車牌號為 P.NO 的車,Push_SeqStack(p,s->datas->top);s->top-;s->num-;t=c

21、ar.time-s->datas->top.time;s->top-;s->num-;while(ISEmpty_SeqStack(p)=0) Push_SeqStack(s,p->datap->top);p->top-;p->num-; return t;10)出隊模塊struct Node Out_LQueue(LinkQueue *q) / 出隊QNODE *p;p=q->front->next;q->front->next=p->next;q->num -;if( q->front->nex

22、t=NULL) q->rear=q->front;return p->data;free(p);五、 調(diào)試分析1 . 設(shè)計與調(diào)試過程中遇到的問題分析、體會1)編寫代碼時，由于對棧和隊列不熟悉，經(jīng)常會一些問題，該程序定義了車輛信息，停車場的順序棧，便道上的鏈表隊列，所以在函數(shù)代值時會出現(xiàn)代值的問題，例如在出棧的程序POP_SeqStack(SqStack *s,struct Node car) 中一開始在s->datas->top.NO !=car.NO這句話中我編的代碼是s->data.NO !=car.NO' 程序報錯.NO' : left

23、 operand points to'struct', use '->' ， 這就是因為定義的太多了，忘記了當(dāng)初定義的停車場棧是：struct NodedataMaxSize; 就是像程序中s->datas->top.time 這樣的定義因為太長了經(jīng)常會搞混，再次像IN_Lqueue(parkqueue,car); ， Push_SeqStack(parkstack,car); 這 種 涉 及 函數(shù)調(diào)用的尤其要注意代的應(yīng)該是什么。2)這個程序設(shè)計時還有一個問題就是有關(guān)結(jié)構(gòu)體的輸入問題，一開始我的程序是printf("停車場管理問題請輸

24、入車輛狀 態(tài)信息n");scanf("%c",&car.AL);printf("請輸入車輛車牌號n");scanf( "%d",&car.NO,);printf(" 請輸入車輛時間 n"); scanf("%d",&car.time );程 序 沒 有 報 錯， 但 在 輸 入 時 就 有 問 題 了，Y7"rtln''i CuF'rent ILocail tine 或nd daite 卓車場最大容量L需驗名禰：實驗二停車場管理

25、問題求解 學(xué)號工0313501呢后來將程序改為 printf(" 請輸入車輛信息 n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);之后程序可以正常運行了3)再次本程序由于多次涉及到程序調(diào)用。一開始我比較喜歡把所有的語句全寫在主程序中，在簡單的程序這種方法是可行的，但是這個程序由于有些函數(shù)像 Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0會多次用到，所以考慮寫子程序，這樣減少了程序的復(fù)雜性，主函數(shù)也更加簡單明了。2

26、.主要算法的時間復(fù)雜度分析主函數(shù)中 對每次輸入的車輛信息只選擇其中一個執(zhí)行，時間復(fù)雜度 O (1);空間復(fù)雜度 O (1);入棧入隊列函數(shù)根據(jù)判斷條件將數(shù)據(jù)入?；蛉腙犃?，時間復(fù)雜度O (1);空間復(fù)雜度O (1);出棧數(shù)據(jù)不在最頂端需將n個數(shù)據(jù)先出該棧，再入新棧，再回舊棧，時間復(fù)雜度O(n);空間復(fù)雜度O (1);六、使用說明程序運行后進(jìn)入循環(huán)，顯示提示信息：“請輸入停車場最大容量 n=:"，提示用戶輸入停車場最大容量，輸入后顯示提示信息：請輸入車輛信息，提示用戶輸入車輛信息(“到達(dá)”或者“離開”，車牌編號，到達(dá)或者離開的時間)。若車輛信息為“到達(dá)A”，車輛信息開始進(jìn)棧(模 擬停車場

27、)，當(dāng)棧滿，車輛會進(jìn)隊列(模擬停車場旁便道)，若車輛信息為“離開D”，會顯示該車進(jìn)入停車場的時間以及相應(yīng)的停車費用，若該車較部分車早進(jìn)停車場，這部分車需先退出停車場，暫時進(jìn)入一個新棧為其讓道，當(dāng)待離開車離開停車場后，這部分車會重新進(jìn)入停車場，同時便道上的第一輛車進(jìn)入停車場；若輸入('P', 0, 0),會顯示停車場的車數(shù)；若輸入(W, 0, 0),會顯示便道上的車數(shù)；若輸入('E', 0, 0),程序會跳出循環(huán)，同時 程序結(jié)束。用戶每輸入一組數(shù)據(jù)，程序就會根據(jù)相應(yīng)輸入給出輸出。輸入值第一個必須為字母，后兩個為數(shù)字，中間用逗號隔開 七、測試結(jié)果*C:UiEk&am

28、p;ADMlNl£TFLATORDE5K7OPVCipebugCl.eJte-等驗名掰 實驗二 停車場管理問題求解學(xué)號：031350102姓名；王業(yè)文 程序運行開始，Current Locdtl t ine and date ：Tue Nuv S3 IS：03 ：47 2815請輸入盜車場最大容量n=工輸入車輛信息尚翻冬在停車場內(nèi)第1個位置請輸入車輛信息這輛車在停車場內(nèi)第2個位置請輸入車輛信息苣東皇停留時間為豈請輸入車輛信息ft,3,20這輛車在停車場內(nèi)第2個位置請輸入車輛信息ft,4.25這輛車在門外便道上第1個位置請輸入車輛信息ft,5.30這輛車在門外便道上第2個位置請輸入車輛

29、信息H2.35這輛車停留時間為如請輸入車輛信息D.4M0這輛車停留時間為1E清輸入車輛信息E, 0, 0輸入結(jié)束Gwrrent loc<il tine and datc；Tue Nov 陰 3 16 ； 03 = 4? 2015八、附錄#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <time.h> typedef int ElemType;#define MaxSize 10017 / 19停車場管理問題#define QNODE struct QNodet

30、ypedef struct Node/ 車輛信息char AL;int NO;int time;Node;typedef struct Stack/ 棧定義struct Node dataMaxSize;int top;int num;SqStack;QNODE / 隊列節(jié)點 struct Node data;QNODE *next;typedef struct linkqueue /隊列結(jié)構(gòu)體定義QNODE *front,*rear;int num;LinkQueue;SqStack *Init_SeqStack()/ 置空棧SqStack *s;s=(SqStack*)malloc(siz

31、eof(SqStack);s->top=-1;s->num=0;return s;LinkQueue *Init_LQueue() /創(chuàng)建空隊列24 / 19LinkQueue *q;QNODE *p;q=(LinkQueue*)malloc(sizeof(LinkQueue);p=(QNODE*)malloc(sizeof(QNODE);p->next=NULL;q->front=q->rear=p;q->num=0;return q;int ISEmpty_SeqStack(SqStack *s)if(s->top =-1)return 1;els

32、ereturn 0;int ISFULL_SeqStack(SqStack *s,int n)if(s->top=n-1)return 1;elsereturn 0;int ISEmpty_LQueue(LinkQueue *q)if(q->front=q->rear)return 1;elsereturn 0;void IN_Lqueue( LinkQueue *q,struct Node s) / 判斷棧是否為空，棧為空返回1/ 判斷棧是否已滿，若棧滿返回1/ 判斷隊列是否為空，隊列為空返回1入隊QNODE *p;p=(QNODE*)malloc(sizeof(QNODE

33、);p->data=s;q->num+;p->next=NULL;q->rear->next =p;q->rear =p;void Push_SeqStack(SqStack *p,struct Node s) /入棧p->top +;p->datap->top=s;p->num+;int POP_SeqStack(SqStack *s,struct Node car)/出棧SqStack *p;int t;p=Init_SeqStack();while(s->datas->top.NO !=car.NO)找到車牌號為 P

34、.NO 的車,Push_SeqStack(p,s->datas->top);s->top-;s->num-;t=car.time-s->datas->top.time;s->top-;s->num-;while(ISEmpty_SeqStack(p)=0)Push_SeqStack(s,p->datap->top);p->top-;p->num-;return t;struct Node Out_LQueue(LinkQueue *q) / 出隊QNODE *p; p=q->front->next;q->

35、front->next=p->next;q->num -;if( q->front->next=NULL) q->rear=q->front;return p->data; free(p);int main()SqStack *parkstack;/parkstack 為表示停車場的棧LinkQueue *parkqueue; /parkqueue為表示便道的隊列struct Node car;int n,a=0,t;/n為停車場棧的最大容量time_t rawtime;struct tm * timeinfo;time (&rawtim

36、e);timeinfo = localtime (&rawtime); parkstack=Init_SeqStack();parkqueue=Init_LQueue(); / 初始界面printf(" 實驗名稱：實驗二停車場管理問題求解n");printf(" 學(xué)號： 031350102n");printf(" 姓名：王亞文n");printf("=n");printf(" 程序運行開始，");printf("Current local time and date:%s&qu

37、ot;,asctime(timeinfo);printf(" 請輸入停車場最大容量n=n");scanf("%d",&n);printf(" 請輸入車輛信息n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time); while(car.AL!='E') if(car.AL='A' )/ 汽車到達(dá)的情況if(ISFULL_SeqStack(parkstack,n)=1)/ 棧滿的情況IN_Lqueue(parkque

38、ue,car);/ 進(jìn)入隊列等待printf("這輛車在門外便道上第外位置n",parkqueue->num);printf("n");printf(" 請輸入車輛信息n"); elsePush_SeqStack(parkstack,car);/ 入棧printf("這輛車在停車場內(nèi)第 d個位置n",parkstack->num);printf("n");printf(" 請輸入車輛信息n");if(car.AL='D' )/ 汽車離開的情況t=POP_SeqSta