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

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

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

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

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

6、ack *Init_SeqStack()/置空棧int ISEmpty_SeqStack(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.鏈表隊列數(shù)據(jù)類型定義QNODE /隊列節(jié)點struct Node data;QNODE *next;typedef struct linkqueue /隊列結(jié)

7、構(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)用關(guān)系 1)主程序模塊2) 出棧3） 判斷棧是否為空4） 判斷棧是否已滿5） 判斷隊列是否為空6） 出隊函數(shù)調(diào)用： main()函數(shù)中調(diào)用：ISFUL

8、L_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)出棧函數(shù)中調(diào)用：Init_SeqStack();Push_SeqStack(p,s-datas-top);ISEmpty_SeqStack(p)=

9、0三、 詳細設(shè)計 1. 實現(xiàn)每個操作的偽碼1）主程序模塊int main()SqStack *parkstack;/parkstack為表示停車場的棧LinkQueue *parkqueue; /parkqueue為表示便道的隊列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(請輸入

10、停車場最大容量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)/棧滿的情況 IN_Lqueue(parkqueue,car);/進入隊列等待 printf(這輛車在門外便道上第%d個位置n,parkqueue-num);printf(n);printf(請輸入車輛信息n); else Push_SeqStack(parkstack,car);

11、/入棧printf(這輛車在停車場內(nèi)第%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_SeqStack(parkstack,Out_LQueue(parkqueue) ); if(car.AL=P&car.NO=0&car.time=0 )/

12、顯示停車場的車數(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);printf(輸入結(jié)束n);return 1;2）置空棧模塊SqStack *Init_SeqStack()/置空棧SqStack *s;s=(SqStack*)m

13、alloc(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=0;return q;4）判斷棧是否為空模塊int ISEmpty_SeqStack(SqStack *s)/判斷棧是否為空，棧為空返回1if(s-top =-1

14、)return 1;elsereturn 0;5）判斷棧是否已滿模塊int ISFULL_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;else return 0;7）入隊模塊void IN_Lqueue(LinkQueue *q,struct Node s) /入隊QNODE *p;p=(QNODE*)malloc

15、(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)/出棧SqStack *p;int t; p=Init_SeqStack();while(s-datas-top.NO !=car.NO)/找到車牌號為P.NO的車， Push_SeqStack(p

16、,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) /出隊QNODE *p;p=q-front-next;q-front-next=p-next;q-num -;if(q-front-next=NULL)q-rear=q-front;return p-data;f

17、ree(p);四、 測試與分析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 operand points to struct, use -，這就是因為定義的太多了，忘記了當初定義的停車場棧是：struct Nodedat

18、aMaxSize;就是像程序中s-datas-top.time這樣的定義因為太長了經(jīng)常會搞混，再次像IN_Lqueue(parkqueue,car);， Push_SeqStack(parkstack,car);這種涉及函數(shù)調(diào)用的尤其要注意代的應(yīng)該是什么。2. 主要算法的時間復(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）；3.測試數(shù)據(jù).設(shè)n=2,輸入數(shù)據(jù)為：

19、（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表示到達；D表示離去，E表示輸入結(jié)束。其中：（A，1，5）表示1號牌照車在5這個時刻到達，而（D，1，15）表示1號牌照車在15這個時刻離去。4. 測試結(jié)果 五總結(jié)在這個程序中還有一個問題，就是定義的結(jié)構(gòu)體數(shù)組有些多，容易混亂，所以我選擇每定義一個結(jié)構(gòu)體都將其畫出一個圖，這樣編寫的時候就不至于太混亂。這個停車管理系統(tǒng)的設(shè)計過程，還是慢慢在

20、適應(yīng)模塊化程序的編寫，但有的程序還是喜歡寫在一起，使得一個子程序會很長，這個問題希望在之后的問題再繼續(xù)慢慢改進六附錄：源程序清單#include#include#include/函數(shù)返回狀態(tài)代碼#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 5/停車場位置數(shù)typedef int Status;/棧,模擬停車場typedef struct Car1/車int number;/汽車車號int ar_time;/汽車到達時間Car

21、Node;typedef struct/停車場CarNode *base;/停車場的堆棧底CarNode *top;/停車場的堆棧頂int stacksize;Park;/隊列,模擬便道typedef struct Car2/車int number;/汽車車號int ar_time;/汽車到達時間struct Car2 *next;*CarPtr;typedef struct/便道CarPtr front;/便道的隊列的對頭CarPtr rear;/便道的隊列的隊尾int length;Shortcut;Status InitStack(Park &P)/初始化停車場P.base=(CarNo

22、de*)malloc(SIZE*sizeof(Car1);if(!P.base) exit(OVERFLOW);P.top=P.base;P.stacksize=0;return OK;Status 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;Status InitQueue(Shortcut &S)/初始

23、化便道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(Shortc