停車場管理系統(tǒng)的設計與實現(xiàn).docx

1、.程序設計與算法綜合訓練設計報告2學號： E11514064姓名：汪泓章年級：大一專 業(yè)：計科項目名稱：停車場管理系統(tǒng)的設計與實現(xiàn)：完成日期： 2016 年 6 月 27日一需求分析1.問題描述：設停車場是一個可停放n 輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端） 。若停車場已經(jīng)停滿n 輛車，那么后來的車只能在門外的便道上等候。一旦有車開走， 則排在便道上的第一輛車即可開入。當停車場某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入車場

2、。每輛停放在車場的車在它離開停車場時必須按它停留的時間長短繳納費用。試為停車場編制按上述要求進行管理的模擬程序。2.基本要求：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入數(shù)據(jù)的序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車的“到達”（ A 表示）或“離去” （ D 表示）信息、汽車標識（牌照號）以及到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達， 則輸出汽車在停車場或者便道上的停車位置；若是車輛離去， 則輸出汽車在停車場停留的時間和應繳納的費用（便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。專業(yè)資料.（1 ）.程序所能達到的基本可能：程

3、序以棧模擬停車場， 以隊列模擬車場外的便道，按照從終端讀入數(shù)據(jù)的序列進行模擬管理。棧以順序結(jié)構(gòu)實現(xiàn)， 隊列以鏈表結(jié)構(gòu)實現(xiàn)。同時另設一個棧， 臨時停放為給要離去的汽車讓路而從停車場退出來的汽車。 輸入數(shù)據(jù)按到達或離去的時刻有序。當輸入數(shù)據(jù)包括數(shù)據(jù)項為汽車的“到達” （ A 表示）信息，汽車標識（牌照號）以及到達時刻時，應輸出汽車在停車場或者便道上的停車位置；當輸入數(shù)據(jù)包括數(shù)據(jù)項為汽車的“離去”（ D 表示）信息，汽車標識（牌照號） 以及離去時刻時，應輸出汽車在停車場停留的時間和應繳納的費用（便道上停留的時間不收費） ；當輸入數(shù)據(jù)項為（ P， 0 ，0 ）時，應輸出停車場的車數(shù)；當輸入數(shù)據(jù)項為（

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

5、待離開車離開停車場后，這部分車會重新進入停車場，同時便道上的第一輛車進入停車場；若輸入（ P，0， 0 ），會顯示停車場的車數(shù)；若輸入（ W ，0 ，0 ），會顯示便道上的車數(shù)；若輸入（ E， 0 ，0 ），程序會跳出循環(huán)，同時程序結(jié)束。 用戶每輸入一組數(shù)據(jù)， 程序就會根據(jù)相應輸入給出輸出。輸入值第一個必須為字母，后兩個為數(shù)字，中間用逗號隔開專業(yè)資料.二概要設計1.所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT為了實現(xiàn)上述功能， 該程序以順序棧模擬停車場以及臨時停放為給要離去的汽車讓路而從停車場退出來的汽車的場地，以鏈表隊列模擬車場外的便道，因此需要棧和隊列這兩個抽象數(shù)據(jù)類型。順序棧數(shù)據(jù)類型定義typedef s

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

7、QNODE/ 隊列節(jié)點struct Node data;專業(yè)資料.QNODE *next;typedef struct linkqueue/ 隊列結(jié)構(gòu)體定義QNODE *front,*rear;int num;LinkQueue;基本操作：LinkQueue *Init_LQueue()/ 創(chuàng)建空隊列int ISEmpty_LQueue(LinkQueue *q)/ 判斷隊列是否為空，隊列為空返回1void IN_Lqueue( LinkQueue *q,struct Node s)/ 入隊struct Node Out_LQueue(LinkQueue *q)/ 出隊2.主程序流程及其模塊調(diào)

8、用關(guān)系1) 主程序模塊2) 出棧3 ）判斷棧是否為空4 ）判斷棧是否已滿5 ）判斷隊列是否為空專業(yè)資料.6 ）出隊函數(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

9、car)出棧函數(shù)中調(diào)用：Init_SeqStack();Push_SeqStack(p,s-datas-top);ISEmpty_SeqStack(p)=0三、詳細設計1. 實現(xiàn)每個操作的偽碼1 ）主程序模塊int main()專業(yè)資料.SqStack *parkstack;/parkstack為表示停車場的棧LinkQueue *parkqueue;/parkqueue為表示便道的隊列struct Node car;int n,a=0,t;/n為停車場棧的最大容量time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = lo

10、caltime (&rawtime);parkstack=Init_SeqStack();parkqueue=Init_LQueue();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 )/汽車到達的情況if(ISFULL_SeqStack(parkstack,n)=1)/ 棧滿的情況專業(yè)資料.IN_Lqueue(parkqueue,car);/ 進入隊列等待printf(這輛車在門外便道上第%d 個

11、位置 n,parkqueue-num);printf(n);printf(請輸入車輛信息n);elsePush_SeqStack(parkstack,car);/ 入棧printf(這輛車在停車場第%d 個位置 n,parkstack-num);printf(n);printf(請輸入車輛信息n);if(car.AL=D )/ 汽車離開的情況t=POP_SeqStack(parkstack,car);/出棧printf(這輛車停留時間為%dn,t);printf(n);printf(請輸入車輛信息n);if(ISEmpty_LQueue(parkqueue)=0)/ 隊列不為空需要進棧Push

12、_SeqStack(parkstack,Out_LQueue(parkqueue) );專業(yè)資料.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,parkqueue-num);printf(n);printf(請輸入車輛信息n);scanf(%c,%d,%d,&car.AL,&car.NO,&car.time);print

13、f(輸入結(jié)束 n);return 1;2 ）置空棧模塊SqStack *Init_SeqStack()/ 置空棧專業(yè)資料.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*)malloc(sizeof(LinkQueue);p=(QNODE*)malloc(sizeof(QNODE);p-next=NULL;q-front=q-rear=p;q-num

14、=0;return q;4 ）判斷棧是否為空模塊int ISEmpty_SeqStack(SqStack *s)/ 判斷棧是否為空，棧為空返回1專業(yè)資料.if(s-top =-1)return 1;elsereturn 0;5 ）判斷棧是否已滿模塊intISFULL_SeqStack(SqStack *s,int n)/ 判斷棧是否已滿，若棧滿返回1if(s-top=n-1)return 1;elsereturn 0;6 ）判斷隊列是否為空模塊int ISEmpty_LQueue(LinkQueue *q)/ 判斷隊列是否為空，隊列為空返回1if(q-front=q-rear)return 1

15、;elsereturn 0;7 ）入隊模塊專業(yè)資料.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 ）入棧模塊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

16、)/出棧SqStack *p;int t;專業(yè)資料.p=Init_SeqStack();while(s-datas-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;10 ）出隊模塊struct Node Out_LQueue(LinkQueue *q)/

17、出隊QNODE *p;專業(yè)資料.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);四、測試與分析1. 設計與調(diào)試過程中遇到的問題分析、體會1 ）編寫代碼時，由于對棧和隊列不熟悉，經(jīng)常會一些問題，該程序定義了車輛信息，停車場的順序棧， 便道上的鏈表隊列， 所以在函數(shù)代值時會出現(xiàn)代值的問題，例如在出棧的程序POP_SeqStack(SqStack *s,struct Node car)中一開始在s-datas-top.NO !=car.NO這句話中

18、我編的代碼是s-data.NO!=car.NO程序報錯 .NO: leftoperandpointstostruct, use -，這就是因為定義的太多了，忘記了當初定義的停車場棧是：struct NodedataMaxSize;就是像程序中s-datas-top.time這樣的定義因為太長了經(jīng)常會搞混，再次像IN_Lqueue(parkqueue,car);， Push_SeqStack(parkstack,car);這 種 涉 及 函數(shù)調(diào)用的尤其要注意代的應該是什么。2.主要算法的時間復雜度分析主函數(shù)中對每次輸入的車輛信息只選擇其中一個執(zhí)行，時間復雜度O（ 1 ）；空間復雜度O（1 ）；入

19、棧入隊列函數(shù)根據(jù)判斷條件將數(shù)據(jù)入?；蛉腙犃校瑫r間復雜度O （ 1）；空間復雜度 O （1 ）；出棧數(shù)據(jù)不在最頂端需將n 個數(shù)據(jù)先出該棧，再入新棧，再回舊棧，時間復雜專業(yè)資料.度 O （ n ）；空間復雜度O （ 1 ）；3.測試數(shù)據(jù) .設 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ù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照及到達或離去的時刻，其中，A 表示到達；

20、 D 表示離去， E表示輸入結(jié)束。其中：（ A ， 1 ， 5）表示 1 號牌照車在 5 這個時刻到達，而（ D ，1 ，15 ）表示 1 號牌照車在15 這個時刻離去。4. 測試結(jié)果專業(yè)資料.五總結(jié)在這個程序中還有一個問題，就是定義的結(jié)構(gòu)體數(shù)組有些多，容易混亂， 所以我選擇每定義一個結(jié)構(gòu)體都將其畫出一個圖，這樣編寫的時候就不至于太混亂。這個停車管理系統(tǒng)的設計過程， 還是慢慢在適應模塊化程序的編寫，但有的程序還是喜歡寫在一起，使得一個子程序會很長，這個問題希望在之后的問題再繼續(xù)慢慢改進六附錄：源程序清單#include#include#include/ 函數(shù)返回狀態(tài)代碼#define OK 1

21、#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2專業(yè)資料.#define SIZE 5/停車場位置數(shù)typedef int Status;/ 棧 ,模擬停車場typedef struct Car1/車int number;/汽車車號int ar_time;/汽車到達時間CarNode;typedef struct/停車場CarNode *base;/停車場的堆棧底CarNode *top;/停車場的堆棧頂int stacksize;Park;/ 隊列 ,模擬便道typedef

22、 struct Car2/車int number;/汽車車號int ar_time;/汽車到達時間struct Car2 *next;*CarPtr;typedef struct/便道CarPtr front;/便道的隊列的對頭CarPtr rear;/便道的隊列的隊尾int length;專業(yè)資料.Shortcut;Status InitStack(Park &P)/初始化停車場P.base=(CarNode*)malloc(SIZE*sizeof(Car1);if(!P.base) exit(OVERFLOW);P.top=P .base;P.stacksize=0;return OK;S

23、tatus Push(Park &P,CarNode e)/車進入停車場*P.top+=e;+P .stacksize;return OK;Status Pop(Park &P,CarNode &e)/車離開停車場if(P.top=P.base)printf(停車場為空 .);elsee=*-P .top;-P .stacksize;return OK;專業(yè)資料.Status InitQueue(Shortcut &S)/初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2);if(!S.front|!S.rear) exit(OVERFLOW);S.front-next=NULL;S.length=0;return OK;Status EnQueue(Shortcut &S,int number,int ar_time)/車進入便道CarPtr p;p=(CarPtr)malloc(sizeof(Car2);if(!p) exit(OVERFLOW);p-number=number;p-ar_time=ar_time;p-next=NULL;S.rear-next=p;S.rear=p;+S.length;return OK;Status DeQueue(Shortcut &S,Car