停車場管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

1、程序設(shè)計(jì)與算法綜合訓(xùn)練設(shè)計(jì)報(bào)告學(xué)號：E11514064 姓名：汪泓章 年級： 大一 專 業(yè)：計(jì)科項(xiàng)目名稱：停車場管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)：完成日期：2016年6月27日一. 需求分析1問題描述：設(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)入車場

2、。每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短繳納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。2.基本要求：以棧模擬停車場，以隊(duì)列模擬車場外的便道，按照從終端讀入數(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)。（1）.程序所能達(dá)到的基本可能：程序以棧模擬停

3、車場，以隊(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)或者便道上的停車位置；當(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

4、 , 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)棧(模 擬停車場)，當(dāng)棧滿，車輛會進(jìn)隊(duì)列(模擬停車場旁便道)，若車輛信息為“離開D”，會顯示該車進(jìn)入停車場的時(shí)間以及相應(yīng)的停車費(fèi)用，若該車較部分車早進(jìn)停車場，這部分車需先退出停車場，暫時(shí)進(jìn)入一個(gè)新棧為其讓道，當(dāng)待離開

5、車離開停車場后，這部分車會重新進(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ù)字，中間用逗號隔開二. 概要設(shè)計(jì)1. 所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT為了實(shí)現(xiàn)上述功能，該程序以順序棧模擬停車場以及臨時(shí)停放為給要離去的汽車讓路而從停 車場退出來的汽車的場地，以鏈表隊(duì)列模擬車場外的便道，因此需要棧和隊(duì)列這兩個(gè)抽象數(shù)據(jù)類型。順序棧數(shù)據(jù)類型定義typedef str

6、uct Stackstruct Node dataMaxSize;int top;int num;SqStack;基本操作：SqStack *lnit_SeqStack()/ 置空棧int ISEmpty_SeqStack(SqStack *s)/判斷棧是否為空，棧為空返回1int ISFULL_SeqStack(SqStack *s,int n)/ 判斷棧是否已滿，若棧滿返回1void Push_SeqStack(SqStack *p,struct Node s) /入棧int POP_SeqStack(SqStack *s,struct Node car)/出棧2. 鏈表隊(duì)列數(shù)據(jù)類型定義Q

7、NODEII隊(duì)列節(jié)點(diǎn)struct Node data;QNODE *n ext;typedef struct lin kqueue II隊(duì)列結(jié)構(gòu)體定義QNODE *fron t,*rear;int num;Lin kQueue;基本操作：Lin kQueue *In it_LQueue()/創(chuàng)建空隊(duì)列int ISEmpty_LQueue(LinkQueue *q)/判斷隊(duì)列是否為空，隊(duì)列為空返回1void IN_Lqueue( Lin kQueue *q,struct Node s) /入隊(duì)struct Node Out_LQueue(L in kQueue *q) /出隊(duì)2.主程序流程及其模

8、塊調(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,car);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

9、)出棧函數(shù)中調(diào)用：In it_SeqStack();Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0三、詳細(xì)設(shè)計(jì)1.實(shí)現(xiàn)每個(gè)操作的偽碼1) 主程序模塊int mai n()SqStack *parkstack;Lin kQueue *parkqueue; struct Node car;int n, a=0,t;time_t rawtime; struct tm * timei nfo;/parkstack/parkqueuen為表示停車場的棧為表示便道的隊(duì)列為停車場棧的最大容量time (&rawtime);time

10、i nfo = localtime (&rawtime);parkstack= Ini t_SeqStack();parkqueue=Ini t_LQueue();printf("請輸入停車場最大容量n=n");scan f("%d",&n);printf("請輸入車輛信息n");scan f("%c,%d,%d", &car.AL,&car.NO,&car.time);while(car.AL!='E')if(car.AL='A')/汽車到達(dá)

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

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

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

14、;);scan f("%c,%d,%d",&car.AL,&car.NO,&car.time);printf("輸入結(jié)束 n");return 1;2) 置空棧模塊SqStack *lnit_SeqStack()/ 置空棧SqStack *s;s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;s->num=O;return s;3) 創(chuàng)建空隊(duì)列模塊Lin kQueue *In it_LQueue()/創(chuàng)建空隊(duì)列Lin kQueue *q;QNODE *p;q=(L in kQue

15、ue*)malloc(sizeof(L in kQueue);p=(QNODE*)malloc(sizeof(QNODE);p-> next=NULL;q->fro nt=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_SeqStack(SqStack *s,int n)/ 判斷棧是否已滿，若棧滿返回1if(s->to

16、p=n-1)return 1;elsereturn 0;6) 判斷隊(duì)列是否為空模塊int ISEmpty_LQueue(LinkQueue *q)/判斷隊(duì)列是否為空，隊(duì)列為空返回1if(q->fron t=q_>rear)return 1;elsereturn 0;7) 入隊(duì)模塊void IN_Lqueue( Lin kQueue *q,struct Node s) /入隊(duì)QNODE *p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q_>nu m+;p-> next=NULL;q->rear- >n ext =p

17、;q->rear =p;8) 入棧模塊void Push_SeqStack(SqStack *p,struct Node s) /入棧p->top +;p->datap->top=s;p_>nu m+;9) 出棧模塊int POP_SeqStack(SqStack *s,struct Node car)/出棧SqStack *p;int t;p=I nit_SeqStack();while(s->datas->top.NO !=car.NO)找到車牌號為 P.NO 的車，Push_SeqStack(p,s->datas->top);s-&g

18、t;top-; s->nu m-;t=car.time-s->datas->top.time;s->top-;s_>nu m_;while(ISEmpty_SeqStack(p)=O)Push_SeqStack(s,p->datap->top);p->top-;p_>nu m_;return t;10) 出隊(duì)模塊struct Node Out_LQueue(L in kQueue *q) /出隊(duì)QNODE *p;p=q->front_>n ext;q->front->n ext=p->n ext;q_>n

19、um -;if( q->fro nt- >n ext=NULL)q->rear=q->front;return p->data;free(p);四、測試與分析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 這句話中我編的代碼是s->data.NO !

20、=car.NO'程序報(bào)錯(cuò).NO' : left opera nd poi nts 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. 主要算法的時(shí)間復(fù)雜度分析主函數(shù)中 對每次輸入的車輛信

21、息只選擇其中一個(gè)執(zhí)行，時(shí)間復(fù)雜度0( 1)；空間復(fù)雜度 O(1)；入棧入隊(duì)列函數(shù)根據(jù)判斷條件將數(shù)據(jù)入?；蛉腙?duì)列，時(shí)間復(fù)雜度0( 1)；空間復(fù)雜度0( 1)；出棧數(shù)據(jù)不在最頂端需將n個(gè)數(shù)據(jù)先出該棧，再入新棧，再回舊棧，時(shí)間復(fù)雜度O(n)；空間復(fù)雜度0( 1)；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'

22、 4，40), (' E' 0，0)。每一組輸入數(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í)刻離去。4. 測試結(jié)果停車場管理程序青選擇(A, D, E): A 1 5青輸入車牌號*進(jìn)場的時(shí)刻:該車應(yīng)停在第1號車道.停車場管理程序青選擇(打D,E); A 2 10 青輸入車牌號，進(jìn)場的時(shí)刻;該車應(yīng)停在第馮車道.停車場管理程序青選擇(打口 E): D

23、 1 15青輸入車牌號乂岀場的時(shí)刻:停車費(fèi)為20,占用車位數(shù)為1停車場管理程序青選擇(A, D, E): A 3 20 青輸入車牌號：迸場的時(shí)刻:該車應(yīng)停在第2號車道.停車場管理程序請選擇A 4 25請輸入車牌號；進(jìn)場的時(shí)刻:該車應(yīng)停在第3號車道.停車場管理程序請選擇（扎D,E）: D 2 35請輸入車牌號：岀場的時(shí)刻:停車費(fèi)為50,占用車位數(shù)為2停車場管理程序請選擇D, E） ： E 0 0五.總結(jié)在這個(gè)程序中還有一個(gè)問題，就是定義的結(jié)構(gòu)體數(shù)組有些多，容易混亂，所以我選擇每定義一個(gè)結(jié)構(gòu)體都將其畫出一個(gè)圖，這樣編寫的時(shí)候就不至于太混亂。這個(gè)停車管理系統(tǒng)的設(shè)計(jì)過程，還是慢慢在適應(yīng)模塊化程序的編寫

24、，但有的程序還是喜歡寫在一起，使得一個(gè)子程序會很長，這個(gè)問題希望在之后的問題再繼續(xù)慢慢改進(jìn)六附錄：源程序清單#i nclude<stdio.h>#in clude<stdlib.h>#in clude<malloc.h>/函數(shù)返回狀態(tài)代碼#defi ne OK 1#defi ne ERROR 0#defi ne TRUE 1#defi ne FALSE 0#defi ne INFEASIBLE -1#defi ne OVERFLOW -2#defi ne SIZE 5停車場位置數(shù)typedef int Status;/棧,模擬停車場typedef struc

25、t Car1車int nu mber;/汽車車號int ar_time;/ 汽車到達(dá)時(shí)間CarNode;typedef struct/ 停車場CarNode *base;/ 停車場的堆棧底CarNode *top;停車場的堆棧頂int stacksize;Park;/隊(duì)列，模擬便道typedef struct Car2車int nu mber;/汽車車號int ar_time;/汽車到達(dá)時(shí)間struct Car2 *n ext;*CarPtr;typedef struct便道CarPtr fron t;/便道的隊(duì)列的對頭CarPtr rear;/便道的隊(duì)列的隊(duì)尾in t le ngth;Sho

26、rtcut;Status In itStack(Park & P)初始化停車場P.base=(CarNode*)malloc(SIZE*sizeof(Car1);if(!P.base) exit(OVERFLOW);P.top=P.base;P.stacksize=0;return OK;Status Push(Park & P,CarNode e)/車進(jìn)入停車場*P.top+=e;+P.stacksize;return OK;Status Pop(Park & P,CarNode &e)/車離開停車場if(P.top=P.base)printf("停

27、車場為空.");elsee=*-P.top;-P.stacksize;return OK;Status Ini tQueue(Shortcut & S)初始化便道S.fro nt=S.rear=(CarPtr)malloc(sizeof(Ca )；if(!S.fro nt|!S.rear) exit(OVERFLOW);S.fro nt-> next=NULL;S.le ngth=0;return OK;車進(jìn)入便道Status En Queue(Shortcut &S,i nt nu mber,i nt ar_time)CarPtr p;p=(CarPtr)ma

28、lloc(sizeof(Ca )；if(!p) exit(OVERFLOW);p->nu mber =nu mber;p->ar_time=ar_time;p-> next=NULL;S.rear- >n ext=p;S.rear=p;+S.le ngth;return OK;Status DeQueue(Shortcut & S,CarPtr &w)車離開便道if(S.le ngth = 0)printf("通道為空.");elsew = S.front->n ext;S.fro nt-> next=S.fr on t-

29、> next-next;-S.le ngth;return OK;Status Arrival(Park & P,Shortcut & S)/對進(jìn)站車輛的處理int nu mber,ar_time;prin tf("請輸入車牌號：");sca nf("%d",&nu mber);printf("進(jìn)場的時(shí)刻：”)；sea nf("%d",&ar_time);if(P.stacksize<SIZE)CarNode c;c.nu mber= nu mber;c.ar_time=ar_ti

30、me;Push(P,c);printf("該車應(yīng)停在第 d號車道.n",P.stacksize);elseEn Queue(S, nu mber,ar_time);printf("停車場已滿，請暫時(shí)停在便道的第d個(gè)位置.n",S.length);return OK;Status Leave(Park & P,Park & P1,Shortcut & S)對離站車輛的處理int nu mber,le_time,flag=1,m on ey,ar_time;prin tf("請輸入車牌號：");sca nf("%d",&nu mber);printf("出場的