1、程序設(shè)計(jì)與算法綜合訓(xùn)練設(shè)計(jì)報(bào)告2學(xué)號(hào)：E11514064 姓名：汪泓章 年級(jí)： 大一 專 業(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)識(shí)（牌照號(hào)）以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(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á)到的基本可能：程序以棧模擬停車場，以隊(duì)列

3、模擬車場外的便道，按照從終端讀入數(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)識(shí)（牌照號(hào)）以及到達(dá)時(shí)刻時(shí)，應(yīng)輸出汽車在停車場內(nèi)或者便道上的停車位置；當(dāng)輸入數(shù)據(jù)包括數(shù)據(jù)項(xiàng)為汽車的“離去”（D表示）信息，汽車標(biāo)識(shí)（牌照號(hà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)為（

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

5、（P，0，0），會(huì)顯示停車場的車數(shù)；若輸入（W，0，0），會(huì)顯示便道上的車數(shù)；若輸入（E，0，0），程序會(huì)跳出循環(huán)，同時(shí)程序結(jié)束。用戶每輸入一組數(shù)據(jù)，程序就會(huì)根據(jù)相應(yīng)輸入給出輸出。輸入值第一個(gè)必須為字母，后兩個(gè)為數(shù)字，中間用逗號(hào)隔開二概要設(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;基

6、本操作：SqStack *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.鏈表隊(duì)列數(shù)據(jù)類型定義QNODE /隊(duì)列節(jié)點(diǎn)struct Node data;QNODE *next;typedef struct linkqu

7、eue /隊(duì)列結(jié)構(gòu)體定義QNODE *front,*rear;int num;LinkQueue;基本操作：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ù)中

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

9、pty_SeqStack(p)=0三、 詳細(xì)設(shè)計(jì) 1. 實(shí)現(xiàn)每個(gè)操作的偽碼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=

10、Init_LQueue();printf("請(qǐng)輸入停車場最大容量n=n");scanf("%d",&n);printf("請(qǐng)輸入車輛信息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(parkqueue,car);/

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

12、ack(parkstack,car);/出棧printf("這輛車停留時(shí)間為%dn",t);printf("n");printf("請(qǐng)輸入車輛信息n"); if(ISEmpty_LQueue(parkqueue)=0) /隊(duì)列不為空需要進(jìn)棧 Push_SeqStack(parkstack,Out_LQueue(parkqueue) ); if(car.AL='P'&&car.NO=0&&car.time=0 )/顯示停車場的車數(shù) printf("停車場的車數(shù)為%dn"

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

14、p;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 *Init_LQueue() /創(chuàng)建空隊(duì)列LinkQueue *q; QNODE *p; q=(LinkQueue*)malloc(sizeof(LinkQueue); p=(QNODE*)malloc(sizeof(QNODE);p-

15、>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_SeqStack(SqStack *s,int n)/判斷棧是否已滿，若棧滿返回1if(s->top=n-1)return 1;elsereturn 0;6）判斷隊(duì)列是否為空模塊int ISEmpty_LQueue(LinkQueue

16、*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->num+;p->next=NULL;q->rear->next =p;q->rear =p;8）入棧模塊void Push_SeqStack(SqStack *p,struct Node s) /入棧p->to

17、p +;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)/找到車牌號(hào)為P.NO的車， Push_SeqStack(p,s->datas->top);s->top-;s->num-;t=car.time-s->datas->top.time;s->top-;s->num-;whil

18、e(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->front->next=p->next;q->num -;if(q->front->next=NULL)q->rear=q->front;return p->data;free(p);四、 測試與分

19、析1. 設(shè)計(jì)與調(diào)試過程中遇到的問題分析、體會(huì) 1）編寫代碼時(shí)，由于對(duì)棧和隊(duì)列不熟悉，經(jīng)常會(huì)一些問題，該程序定義了車輛信息，停車場的順序棧，便道上的鏈表隊(duì)列，所以在函數(shù)代值時(shí)會(huì)出現(xiàn)代值的問題，例如在出棧的程序POP_SeqStack(SqStack *s,struct Node car)中一開始在s->datas->top.NO !=car.NO這句話中我編的代碼是s->data.NO !=car.NO'程序報(bào)錯(cuò).NO' : left operand points to 'struct', use '->'，這就是因?yàn)槎x的

20、太多了，忘記了當(dāng)初定義的停車場棧是：struct NodedataMaxSize;就是像程序中s->datas->top.time這樣的定義因?yàn)樘L了經(jīng)常會(huì)搞混，再次像IN_Lqueue(parkqueue,car);， Push_SeqStack(parkstack,car);這種涉及函數(shù)調(diào)用的尤其要注意代的應(yīng)該是什么。2. 主要算法的時(shí)間復(fù)雜度分析 主函數(shù)中 對(duì)每次輸入的車輛信息只選擇其中一個(gè)執(zhí)行，時(shí)間復(fù)雜度O（1）；空間復(fù)雜度O（1）；入棧入隊(duì)列函數(shù)根據(jù)判斷條件將數(shù)據(jù)入?；蛉腙?duì)列，時(shí)間復(fù)雜度O（1）；空間復(fù)雜度O（1）；出棧數(shù)據(jù)不在最頂端需將n個(gè)數(shù)據(jù)先出該棧，再入新棧，再回舊

21、棧，時(shí)間復(fù)雜度O（n）；空間復(fù)雜度O（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，4，40），（E，0，0）。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車 “到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，其中，A表示到達(dá)；D表示離去，E表示輸入結(jié)束。其中：（A，1，5）表示1號(hào)牌照車在5這個(gè)時(shí)刻到達(dá)，而（D，1，15）表示1號(hào)牌照車在15這個(gè)時(shí)刻離去。4. 測試結(jié)果 五總結(jié)在這個(gè)程序中還有一個(gè)問題，就是定義的結(jié)構(gòu)體數(shù)組有些多，容易混亂，所以我選擇每定義一個(gè)結(jié)構(gòu)體都將其

22、畫出一個(gè)圖，這樣編寫的時(shí)候就不至于太混亂。這個(gè)停車管理系統(tǒng)的設(shè)計(jì)過程，還是慢慢在適應(yīng)模塊化程序的編寫，但有的程序還是喜歡寫在一起，使得一個(gè)子程序會(huì)很長，這個(gè)問題希望在之后的問題再繼續(xù)慢慢改進(jìn)六附錄：源程序清單#include<stdio.h>#include<stdlib.h>#include<malloc.h>/函數(shù)返回狀態(tài)代碼#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 5/停車場位置

23、數(shù)typedef int Status;/棧,模擬停車場typedef struct Car1/車int number;/汽車車號(hào)int ar_time;/汽車到達(dá)時(shí)間CarNode;typedef struct/停車場CarNode *base;/停車場的堆棧底CarNode *top;/停車場的堆棧頂int stacksize;Park;/隊(duì)列,模擬便道typedef struct Car2/車int number;/汽車車號(hào)int ar_time;/汽車到達(dá)時(shí)間struct Car2 *next;*CarPtr;typedef struct/便道CarPtr front;/便道的隊(duì)列的對(duì)

24、頭CarPtr rear;/便道的隊(duì)列的隊(duì)尾int length;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;Status Push(Park &P,CarNode e)/車進(jìn)入停車場*P.top+=e;+P.stacksize;return OK;Status Pop(Park &P,CarNode &e)/車離開

25、停車場if(P.top=P.base)printf("停車場為空.");elsee=*-P.top;-P.stacksize;return OK;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)/車

26、進(jìn)入便道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,CarPtr &w)/車離開便道if(S.length = 0)printf("通道為空.");elsew = S.front->next;S.front->

27、next=S.front->next->next;-S.length;return OK;Status Arrival(Park &P,Shortcut &S)/對(duì)進(jìn)站車輛的處理int number,ar_time;printf("請(qǐng)輸入車牌號(hào)：");scanf("%d",&number);printf("進(jìn)場的時(shí)刻:");scanf("%d",&ar_time);if(P.stacksize<SIZE)CarNode c;c.number=number;c.ar_

28、time=ar_time;Push(P,c);printf("該車應(yīng)停在第%d號(hào)車道.n",P.stacksize);elseEnQueue(S,number,ar_time);printf("停車場已滿,請(qǐng)暫時(shí)停在便道的第%d個(gè)位置.n",S.length);return OK;Status Leave(Park &P,Park &P1,Shortcut &S)/對(duì)離站車輛的處理int number,le_time,flag=1,money,ar_time;printf("請(qǐng)輸入車牌號(hào)：");scanf("%d",&number);printf("出場的時(shí)刻:");scanf("%d",&le_time);CarN