停車場管理問題

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

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

3、入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車 “到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時(shí)刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。其中：（A，1，5）表示1號牌照車在5這個(gè)時(shí)刻到達(dá)，而（D，1，15）表示1號牌照車在15這個(gè)時(shí)刻離去。二需求分析1.程序所能達(dá)到的基本可能：程序以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入數(shù)據(jù)的序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。同時(shí)另設(shè)一個(gè)棧，臨時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車。輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。當(dāng)輸入數(shù)據(jù)包括數(shù)據(jù)項(xiàng)為汽車的“到達(dá)”（A表示）信息，汽車標(biāo)識（牌照號）以及到達(dá)時(shí)刻時(shí)，應(yīng)輸出汽車在停車場內(nèi)或

4、者便道上的停車位置；當(dāng)輸入數(shù)據(jù)包括數(shù)據(jù)項(xiàng)為汽車的“離去”（D表示）信息，汽車標(biāo)識（牌照號）以及離去時(shí)刻時(shí)，應(yīng)輸出汽車在停車場停留的時(shí)間和應(yīng)繳納的費(fèi)用（便道上停留的時(shí)間不收費(fèi)）；當(dāng)輸入數(shù)據(jù)項(xiàng)為（P，0，0）時(shí)，應(yīng)輸出停車場的車數(shù)；當(dāng)輸入數(shù)據(jù)項(xiàng)為（W, 0, 0）時(shí)，應(yīng)輸出候車場車數(shù)；當(dāng)輸入數(shù)據(jù)項(xiàng)為（E, 0, 0），退出程序；2.輸入輸出形式及輸入值范圍：程序運(yùn)行后進(jìn)入循環(huán)，顯示提示信息：“請輸入停車場最大容量n=:”，提示用戶輸入停車場最大容量，輸入后顯示提示信息：請輸入車輛信息，提示用戶輸入車輛信息（“到達(dá)”或者“離開”，車牌編號，到達(dá)或者離開的時(shí)間）。若車輛信息為“到達(dá)A”，車輛信息開始進(jìn)

5、棧(模擬停車場），當(dāng)棧滿，車輛會進(jìn)隊(duì)列（模擬停車場旁便道），若車輛信息為“離開D”，會顯示該車進(jìn)入停車場的時(shí)間以及相應(yīng)的停車費(fèi)用，若該車較部分車早進(jìn)停車場，這部分車需先退出停車場，暫時(shí)進(jìn)入一個(gè)新棧為其讓道，當(dāng)待離開車離開停車場后，這部分車會重新進(jìn)入停車場，同時(shí)便道上的第一輛車進(jìn)入停車場；若輸入（P，0，0），會顯示停車場的車數(shù)；若輸入（W，0，0），會顯示便道上的車數(shù)；若輸入（E，0，0），程序會跳出循環(huán)，同時(shí)程序結(jié)束。用戶每輸入一組數(shù)據(jù)，程序就會根據(jù)相應(yīng)輸入給出輸出。輸入值第一個(gè)必須為字母，后兩個(gè)為數(shù)字，中間用逗號隔開3.測試數(shù)據(jù)要求：設(shè)n=2,輸入數(shù)據(jù)為：（A，1，5），（A，2，10），

6、（D，1，15），（A，3， 20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。三概要設(shè)計(jì)1. 所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT 為了實(shí)現(xiàn)上述功能，該程序以順序棧模擬停車場以及臨時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車的場地，以鏈表隊(duì)列模擬車場外的便道，因此需要棧和隊(duì)列這兩個(gè)抽象數(shù)據(jù)類型。順序棧數(shù)據(jù)類型定義typedef struct Stack struct NodedataMaxSize;int top;int num;SqStack;基本操作：SqStack *Init_SeqStack()/置空棧int ISEmpty_SeqStack(

7、SqStack *s)/判斷棧是否為空，棧為空返回1int ISFULL_SeqStack(SqStack *s,int n)/判斷棧是否已滿，若棧滿返回1 void Push_SeqStack(SqStack *p,struct Node s) /入棧int POP_SeqStack(SqStack *s,struct Node car)/出棧2.鏈表隊(duì)列數(shù)據(jù)類型定義QNODE /隊(duì)列節(jié)點(diǎn)struct Node data;QNODE *next;typedef struct linkqueue /隊(duì)列結(jié)構(gòu)體定義QNODE *front,*rear;int num;LinkQueue;基本操作

8、：LinkQueue *Init_LQueue() /創(chuàng)建空隊(duì)列int ISEmpty_LQueue(LinkQueue *q)/判斷隊(duì)列是否為空，隊(duì)列為空返回1void IN_Lqueue(LinkQueue *q,struct Node s) /入隊(duì)struct Node Out_LQueue(LinkQueue *q) /出隊(duì)2. 主程序流程及其模塊調(diào)用關(guān)系 1)主程序模塊2) 出棧3） 判斷棧是否為空4） 判斷棧是否已滿5） 判斷隊(duì)列是否為空6） 出隊(duì)函數(shù)調(diào)用： main()函數(shù)中調(diào)用：ISFULL_SeqStack(parkstack,n)，IN_Lqueue(parkqueue,c

9、ar); Push_SeqStack(parkstack,car); t=POP_SeqStack(parkstack,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è)計(jì) 1. 實(shí)現(xiàn)每個(gè)操作的偽碼，重點(diǎn)語句加注

10、釋 1）主程序模塊int main()SqStack *parkstack;/parkstack為表示停車場的棧LinkQueue *parkqueue; /parkqueue為表示便道的隊(duì)列struct Node car;int n,a=0,t; /n為停車場棧的最大容量time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);parkstack=Init_SeqStack();parkqueue=Init_LQueue();printf("/*/n&quo

11、t;); /初始界面 printf(" 學(xué)號：031350102n"); printf(" 姓名：王亞文n"); printf(" 停車場管理問題n"); printf("/*/n");printf("請輸入停車場最大容量n=n");scanf("%d",&n);printf("請輸入車輛信息n"); scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);while(ca

12、r.AL!='E') if(car.AL='A' ) /汽車到達(dá)的情況 if(ISFULL_SeqStack(parkstack,n)=1)/棧滿的情況 IN_Lqueue(parkqueue,car);/進(jìn)入隊(duì)列等待 printf("這輛車在門外便道上第%d個(gè)位置n",parkqueue->num);printf("n");printf("請輸入車輛信息n"); else Push_SeqStack(parkstack,car);/入棧printf("這輛車在停車場內(nèi)第%d個(gè)位置n&q

13、uot;,parkstack->num);printf("n");printf("請輸入車輛信息n"); if(car.AL='D' )/汽車離開的情況 t=POP_SeqStack(parkstack,car);/出棧printf("這輛車停留時(shí)間為%dn",t);printf("n");printf("請輸入車輛信息n"); if(ISEmpty_LQueue(parkqueue)=0) /隊(duì)列不為空需要進(jìn)棧 Push_SeqStack(parkstack,Out_LQ

14、ueue(parkqueue) ); if(car.AL='P'&&car.NO=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",parkqu

15、eue->num);printf("n");printf("請輸入車輛信息n"); 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)建空隊(duì)列模塊LinkQueue

16、 *Init_LQueue() /創(chuàng)建空隊(duì)列LinkQueue *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;4）判斷棧是否為空模塊int ISEmpty_SeqStack(SqStack *s)/判斷棧是否為空，棧為空返回1if(s->top =-1)return 1;elsereturn 0;5）判斷棧是否已滿模塊int ISFULL_Se

17、qStack(SqStack *s,int n)/判斷棧是否已滿，若棧滿返回1if(s->top=n-1)return 1;elsereturn 0;6）判斷隊(duì)列是否為空模塊int ISEmpty_LQueue(LinkQueue *q)/判斷隊(duì)列是否為空，隊(duì)列為空返回1if(q->front=q->rear)return 1;else return 0;7）入隊(duì)模塊void IN_Lqueue(LinkQueue *q,struct Node s) /入隊(duì)QNODE *p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q->n

18、um+;p->next=NULL;q->rear->next =p;q->rear =p;8）入棧模塊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的車， Pu

19、sh_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;10）出隊(duì)模塊struct Node Out_LQueue(LinkQueue *q) /出隊(duì)QNODE *p;p=q->front->next;q->fron

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

21、話中我編的代碼是s->data.NO !=car.NO'程序報(bào)錯(cuò).NO' : left operand points to 'struct', use '->'，這就是因?yàn)槎x的太多了，忘記了當(dāng)初定義的停車場棧是：struct NodedataMaxSize;就是像程序中s->datas->top.time這樣的定義因?yàn)樘L了經(jīng)常會搞混，再次像IN_Lqueue(parkqueue,car);， Push_SeqStack(parkstack,car);這種涉及函數(shù)調(diào)用的尤其要注意代的應(yīng)該是什么。2）這個(gè)程序設(shè)計(jì)時(shí)還有一個(gè)

22、問題就是有關(guān)結(jié)構(gòu)體的輸入問題，一開始我的程序是printf("請輸入車輛狀態(tài)信息n");scanf("%c",&car.AL);printf("請輸入車輛車牌號n");scanf(“%d",&car.NO,);printf("請輸入車輛時(shí)間n"); scanf("%d",&car.time）；程序沒有報(bào)錯(cuò)，但在輸入時(shí)就有問題了 后來將程序改為printf("請輸入車輛信息n"); scanf("%c,%d,%d",&

23、;car.AL,&car.NO,&car.time);之后程序可以正常運(yùn)行了3） 再次本程序由于多次涉及到程序調(diào)用。一開始我比較喜歡把所有的語句全寫在主程序中，在簡單的程序這種方法是可行的，但是這個(gè)程序由于有些函數(shù)像Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0會多次用到，所以考慮寫子程序，這樣減少了程序的復(fù)雜性，主函數(shù)也更加簡單明了。 2. 主要算法的時(shí)間復(fù)雜度分析 主函數(shù)中 對每次輸入的車輛信息只選擇其中一個(gè)執(zhí)行，時(shí)間復(fù)雜度O（1）；空間復(fù)雜度O（1）；入棧入隊(duì)列函數(shù)根據(jù)判斷條件將數(shù)據(jù)入?；蛉腙?duì)列，時(shí)間復(fù)

24、雜度O（1）；空間復(fù)雜度O（1）；出棧數(shù)據(jù)不在最頂端需將n個(gè)數(shù)據(jù)先出該棧，再入新棧，再回舊棧，時(shí)間復(fù)雜度O（n）；空間復(fù)雜度O（1）；六、 使用說明程序運(yùn)行后進(jìn)入循環(huán)，顯示提示信息：“請輸入停車場最大容量n=:”，提示用戶輸入停車場最大容量，輸入后顯示提示信息：請輸入車輛信息，提示用戶輸入車輛信息（“到達(dá)”或者“離開”，車牌編號，到達(dá)或者離開的時(shí)間）。若車輛信息為“到達(dá)A”，車輛信息開始進(jìn)棧(模擬停車場），當(dāng)棧滿，車輛會進(jìn)隊(duì)列（模擬停車場旁便道），若車輛信息為“離開D”，會顯示該車進(jìn)入停車場的時(shí)間以及相應(yīng)的停車費(fèi)用，若該車較部分車早進(jìn)停車場，這部分車需先退出停車場，暫時(shí)進(jìn)入一個(gè)新棧為其讓道，當(dāng)

25、待離開車離開停車場后，這部分車會重新進(jìn)入停車場，同時(shí)便道上的第一輛車進(jìn)入停車場；若輸入（P，0，0），會顯示停車場的車數(shù)；若輸入（W，0，0），會顯示便道上的車數(shù)；若輸入（E，0，0），程序會跳出循環(huán)，同時(shí)程序結(jié)束。用戶每輸入一組數(shù)據(jù)，程序就會根據(jù)相應(yīng)輸入給出輸出。輸入值第一個(gè)必須為字母，后兩個(gè)為數(shù)字，中間用逗號隔開七、 測試結(jié)果 八、 附錄 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> typedef int ElemType;#defi

26、ne MaxSize 100#define QNODE struct QNodetypedef struct Node/車輛信息char AL;int NO;int time;Node;typedef struct Stack/棧定義 struct NodedataMaxSize;int top;int num;SqStack;QNODE /隊(duì)列節(jié)點(diǎn)struct Node data;QNODE *next;typedef struct linkqueue /隊(duì)列結(jié)構(gòu)體定義QNODE *front,*rear;int num;LinkQueue;SqStack *Init_SeqStack()/

27、置空棧SqStack *s;s=(SqStack*)malloc(sizeof(SqStack); s->top=-1;s->num=0;return s;LinkQueue *Init_LQueue() /創(chuàng)建空隊(duì)列LinkQueue *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

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

29、p;p=(QNODE*)malloc(sizeof(QNODE);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->da

30、tas->top.NO !=car.NO)/找到車牌號為P.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) /出隊(duì)QNODE *p

31、;p=q->front->next;q->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為表示便道的隊(duì)列struct Node car;int n,a=0,t; /n為停車場棧的最大容量time_t rawtime;struct tm *

32、 timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);parkstack=Init_SeqStack();parkqueue=Init_LQueue(); /初始界面 printf(" 實(shí)驗(yàn)名稱：實(shí)驗(yàn)二 停車場管理問題求解n");printf(" 學(xué)號：031350102n"); printf(" 姓名：王亞文n"); printf("=n");printf("程序運(yùn)行開始，");printf("Curren

33、t local time and date:%s",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)=

34、1)/棧滿的情況 IN_Lqueue(parkqueue,car);/進(jìn)入隊(duì)列等待 printf("這輛車在門外便道上第%d個(gè)位置n",parkqueue->num);printf("n");printf("請輸入車輛信息n"); else Push_SeqStack(parkstack,car);/入棧printf("這輛車在停車場內(nèi)第%d個(gè)位置n",parkstack->num);printf("n");printf("請輸入車輛信息n"); if(car.AL='D' )/汽車離開的情況 t=POP_SeqStack(parkstack,car);/出棧printf("這輛車停留時(shí)間為%dn",t);printf("n");printf("請輸入車輛信息n"); if(ISEmpty_L