數(shù)據(jù)結(jié)構(gòu)實驗二：停車場管理問題

1、HUNAN UNIVERSITY課程實習報告題 目： 停車場管理問題 學生姓名 學生學號 專業(yè)班級 指導老師 李 曉 鴻 完 成 日 期 2 0 1 5年 11 月 25日 1、 需求分析1. 輸入的形式的輸入的范圍：選擇功能：1停車 2離開停車場 3離開過道若輸入1（停車），輸入當前車牌號和當前的時間；若輸入2（離開停車場），輸入車票號和當前時間；若輸入3（離開過道），輸入車牌號。2. 輸出的形式：提示選擇功能“1.停車 2離開停車場 3離開過道”。若輸入1（停車），并且輸入當前車牌號和當前的時間后，若停車場未滿，輸出“成功 停入停車場，停車場內(nèi)有n輛車，過道上有m輛車等候”;若停車場滿，輸

2、出 “停 車場已滿，請在過道等候”。 若輸入2（離開停車場），輸入車票號和當前時間，輸出“存車總計時間，收費q元， 停車場內(nèi)有n輛車，過道上有m輛車等候”；如果進停車場和出停車場時間錯誤，輸 出“時間輸入有誤，請重新輸入”；如果停車場沒有此車，輸出“車牌號有誤，請重新 輸入”。若輸入3（離開過道），輸入車牌號，輸出“此車已成功離開過道”；若無此車，輸出 “停車過道為空”。若輸入其他，則提示選擇功能“1.停車 2離開停車場 3離開過道”。3. 程序所能達到的功能：有一個可以停放n輛汽車的狹長停車場，它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達

3、的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進入停車場。停車場內(nèi)如有某輛車要開走，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進場。每輛車在離開停車場時，都應根據(jù)它在停車場內(nèi)停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，并且仍然保持在便道上等待的車輛的次序。4. 測試數(shù)據(jù)：正常的進入停車場，出停車場，離開過道的模擬輸入11（車牌）1（當前時間）輸入 12（車牌）2（當前時間）輸入22（車牌）3（當前時間）輸入1

4、3（車牌）4（當前時間）輸入14（車牌）5（當前時間）輸入34（車牌）停車場里沒有車出停車場的模擬輸入21（車牌）過道沒車出過道的模擬輸入31（車牌）進入停車場時間與出停車場時間的模擬輸入11（車牌）1（進停車場的時間）輸入21（車牌）0（出停車場的時間）停車場模擬系統(tǒng)功能輸入錯誤輸入4二.概要設(shè)計抽象數(shù)據(jù)類型：由于該停車場只有一個門供出入，并且最先進的停在停車場的最末，最先進的車輛要出停車場需要之后進入的車先出，滿足先進后出的結(jié)構(gòu)，其限制是僅允許在表的一端進行插入和刪除運算，所以用棧來模擬停車場。由于這是一個模擬的車庫，車輛出停車場，后面車輛不得不被動跟著出停車場，我們需要對這些車輛進行管理

5、，將第一輛被動出停車場的放置到一個隊伍的前端，接下來被動出停車場的車輛依次放到第一輛車之后，當需要離開的車出棧后，對被動出停車場的車輛進行管理，又隊伍的前端依次進入停車場，由于滿足只允許在表的前端進行刪除操作，而在表的后端進行插入操作，所以用隊列來模擬被動出停車場車輛的管理?；舅枷?.給定一個size為停車場的容量。2.每一輛車進棧前，儲存車輛編號和進棧的時間。3.對于棧滿的情況，再來的車輛不進棧，只記錄編號。4.對于出棧的車輛，先將出棧車輛之前的停車場內(nèi)車輛由后往前依次進入隊列中，將進棧和出棧時間相比較算出需要付的金額，之后再將隊列中的元素由前往后依次進棧。程序的流程 程序由三個模塊組成：

6、 輸入模塊：按照提示輸入 計算模塊：計算（出棧時間-進棧時間）*每小時金額。 輸出模塊：首先提示 "請選擇：1、停車；2、離開停車場；3、離開過道；" 選擇1.2提示 "請輸入車牌號和現(xiàn)在的時間：" 選擇3提示“請輸入車牌號”基本ADT?？张袆e算法int Empty_SeqStack(queue *s) if (s->top = -1)return 0;elsereturn 1;入棧算法void Push_SeqStack(queue *s, Datatype x) s->top+;s->data1s->top = x;retur

7、n;出棧算法void Pop_SeqStack(queue *s, Datatype *x) *x = s->data1s->top;s->top-;return;列隊初始化C_SeQueue *Init_SeQueue() C_SeQueue *q;q = new C_SeQueue;q->front = q->rear = MAXSIZE - 1;q->num = 0;return q;入隊算法void In_SeQueue(C_SeQueue *q, Datatype x) q->rear = (q->rear + 1) % MAXSIZE

8、;q->data2q->rear = x;q->num+;return;出隊算法void Out_SeQueue(C_SeQueue *q, Datatype *x)q->front = (q->front + 1) % MAXSIZE;*x = q->data2q->front;q->num-;return;算法流程圖（進入車庫和出車庫）3 詳細設(shè)計1. 數(shù)據(jù)類型用Int型整數(shù)儲存車輛的信息.車輛進出時間.收取的費用2.算法的具體步驟車進入停車場的基本操作void Arrive(queue *s, C_SeQueue *q, int x, do

9、uble t) int y;int a = s->top;while (a != -1) /判斷將要存的車是否已存在于停車場，防止出現(xiàn)有相同車牌號的車出現(xiàn)在停車場內(nèi)；if (s->data1a = x)cout << "此車已存在停車場內(nèi)！" << endl;return;elsea-;if (Push_SeqStack1(s, x, t)cout << "此車已成功存入停車場。" << endl;elsecout << "停車場已滿，后來車輛請在便道等候。" &

10、lt;< endl;In_SeQueue(q, x);show(s, q);離開停車場的基本操作void Leave(queue *s, C_SeQueue *q, int x, double t) int y;int i = 1;double d;queue *s1;s1 = Init_SeqStack();while (s->data1s->top != x&&!Empty_SeqStack(s)Pop_SeqStack(s, &y);Push_SeqStack(s1, y);if (s->data1s->top = x) while

11、(i)if (t >= 1 && t <= 24 && t>s->times->top)d = t - s->times->top;Pop_SeqStack(s, &y);cout << "存車時間總計：" << d << "小時" << endl<< "收費為：" << d << "元" << endl;i = 0;elsecout &l

12、t;< "時間輸入有誤，請重新輸入。" << endl; /時間容錯處理；i = 1;cin >> t;elsecout << "車牌號有誤，停車場中無此車。" << endl; /容錯，離開時也要輸入正確車牌號，否則無此車，也不耽誤程序執(zhí)行；while (Empty_SeqStack(s1) != 0)Pop_SeqStack(s1, &y);Push_SeqStack(s, y);if (q->num != 0 && s->top != MINSIZE - 1)

13、Out_SeQueue(q, &y);Push_SeqStack1(s, y, t);show(s, q);return;離開過道的基本操作void Leave1(queue *s, C_SeQueue *q, int x) if (q->num = 0)cout << "停車過道為空。" << endl;return;int a = q->rear;while (q->data2a != x && (a + MAXSIZE) % MAXSIZE != q->front)a-;if (q->dat

14、a2(a + MAXSIZE) % MAXSIZE = x)while (a + MAXSIZE) % MAXSIZE != q->rear - 1)q->data2a = q->data2a + 1;a+;q->num-;cout << "此車已成功離開過道。" << endl;elsecout << "此車不在過道中。" << endl;show(s, q);3.算法的時空分析和改進設(shè)想 每次進棧的時間復雜度為O（1），當要出車輛后有n輛車時，出棧時間復雜度為O（n），也許對于一

15、個車庫來說n并不會很大，但是考慮實際這個停車場的設(shè)計非常不合理。4.輸入和輸出格式 輸入：功能選擇輸入為整數(shù)1-3，輸入車牌號為大于零的整數(shù)，時間為大于零的整數(shù)。 輸出：輸出整數(shù)型的應收的價格4 調(diào)試分析1. 為了簡化程序，采用手動輸入進棧車輛的排序.進棧時間.出棧時間。2. 同時因為需要輸入多組數(shù)據(jù)，在程序完工后又加上許多引導性的話，例如提示停車場內(nèi)有幾輛車.停車場外有多少車.車輛是否進入車庫成功.車輛是否在車庫外等候。3. 對于時間的處理過于簡陋，只用了一位數(shù)表示時間，與實際情況不太符合。4. 對于車牌處理也過于簡單，可以在車的儲存信息加入車牌號。5 測試結(jié)果情況1測試結(jié)果情況2測試情況3

16、測試情況4測試情況5測試6 試驗心得1.書上對棧的實現(xiàn)太少不詳細，查閱了許多棧的各類實現(xiàn)怎么寫。2.存車取車問題比較簡單，在程序完成后發(fā)現(xiàn)程序的容錯率為0，當不小心輸入了相同車牌時程序直接報錯，不得不添加了許多容錯代碼，容錯程序代碼很是讓人費神，現(xiàn)在容錯已完善再完善了，但還是未能完全解決問題，例如，在過道停的車輛不能保證其中沒有相同車牌號的車，還有時間處理的比較簡單原始化，這些都有待以后提高，繼續(xù)完善。3.這道題過于死板，完全是為了棧強行設(shè)計了一道門的停車場，每次有車出來后面的車都要移動位置，這種車庫，不停也罷。七代碼#include<iostream>using namespac

17、e std;#define MAXSIZE 10#define MINSIZE 2typedef int Datatype;typedef structDatatype data1MINSIZE;int top;double timeMINSIZE;queue;queue *Init_SeqStack() /棧的初始化；queue *s;s = new queue;if (!s)cout << "空間不足" << endl;return NULL;elses->top = -1;return s;int Empty_SeqStack(queue

18、 *s) /?？张袆e算法；if (s->top = -1)return 0;elsereturn 1;void Push_SeqStack(queue *s, Datatype x) /入棧算法；s->top+;s->data1s->top = x;return;int Push_SeqStack1(queue *s, Datatype x, double t) /入棧算法1；if (s->top = MINSIZE - 1)return 0;elses->top+;s->data1s->top = x;s->times->top =

19、 t;return 1;void Pop_SeqStack(queue *s, Datatype *x) /出棧算法；*x = s->data1s->top;s->top-;return;typedef structDatatype data2MAXSIZE;int rear, front;int num;C_SeQueue;C_SeQueue *Init_SeQueue() /列隊初始化；C_SeQueue *q;q = new C_SeQueue;q->front = q->rear = MAXSIZE - 1;q->num = 0;return q;v

20、oid In_SeQueue(C_SeQueue *q, Datatype x) /入隊算法；q->rear = (q->rear + 1) % MAXSIZE;q->data2q->rear = x;q->num+;return;void Out_SeQueue(C_SeQueue *q, Datatype *x)/出隊算法；q->front = (q->front + 1) % MAXSIZE;*x = q->data2q->front;q->num-;return;void show(queue *s, C_SeQueue *q

21、) /顯示停車情況；cout << "停車場內(nèi)有" << s->top + 1 << "輛車。" << endl;cout << "通道上有" << q->num << "輛車在等候。" << endl;void Arrive(queue *s, C_SeQueue *q, int x, double t) /停車；int y;int a = s->top;while (a != -1) /判斷將要存的

22、車是否已存在于停車場，防止出現(xiàn)有相同車牌號的車出現(xiàn)在停車場內(nèi)；if (s->data1a = x)cout << "成功停入車場" << endl;return;elsea-;if (Push_SeqStack1(s, x, t)cout << "成功停入車場。" << endl;elsecout << "停車場已滿，后來車輛請在便道等候。" << endl;In_SeQueue(q, x);show(s, q);void Leave(queue *s, C

23、_SeQueue *q, int x, double t) /離開停車場；int y;int i = 1;double d;queue *s1;s1 = Init_SeqStack();while (s->data1s->top != x&&!Empty_SeqStack(s) Pop_SeqStack(s, &y);Push_SeqStack(s1, y);if (s->data1s->top = x) while (i)if (t >= 1 && t <= 24 && t>s->time

24、s->top)d = t - s->times->top;Pop_SeqStack(s, &y);cout << "存車時間總計：" << d << "小時" << endl<< "收費為：" << d << "元" << endl;i = 0;elsecout << "時間輸入有誤，請重新輸入。" << endl; /時間容錯處理；i = 1;cin

25、 >> t;elsecout << "車牌號有誤，停車場中無此車。" << endl; /容錯，離開時也要輸入正確車牌號，否則無此車，也不耽誤程序執(zhí)行；while (Empty_SeqStack(s1) != 0)Pop_SeqStack(s1, &y);Push_SeqStack(s, y);if (q->num != 0 && s->top != MINSIZE - 1)Out_SeQueue(q, &y);Push_SeqStack1(s, y, t);show(s, q);return;void Leave1(queue *s, C_SeQueue *q, int x) /離開過道；if (q->num = 0)cout << "停車過道為空。" << endl;return;int a = q->rear;while (q->data2a != x && (a +