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

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

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

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

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

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

6、 輸入模塊：按照提示輸入 計(jì)算模塊：計(jì)算（出棧時(shí)間-進(jìn)棧時(shí)間）*每小時(shí)金額。 輸出模塊：首先提示 "請選擇：1、停車；2、離開停車場；3、離開過道；" 選擇1.2提示 "請輸入車牌號和現(xiàn)在的時(shí)間：" 選擇3提示“請輸入車牌號”基本ADT棧空判別算法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;列隊(duì)初始化C_SeQueue *Init_SeQueue() C_SeQueue *q;q = new C_SeQueue;q->front = q->rear = MAXSIZE - 1;q->num = 0;return q;入隊(duì)算法void In_SeQueue(C_SeQueue *q, Datatype x) q->rear = (q->rear + 1) % MAXSIZE

8、;q->data2q->rear = x;q->num+;return;出隊(duì)算法void Out_SeQueue(C_SeQueue *q, Datatype *x)q->front = (q->front + 1) % MAXSIZE;*x = q->data2q->front;q->num-;return;算法流程圖（進(jìn)入車庫和出車庫）3 詳細(xì)設(shè)計(jì)1. 數(shù)據(jù)類型用Int型整數(shù)儲存車輛的信息.車輛進(jìn)出時(shí)間.收取的費(fèi)用2.算法的具體步驟車進(jìn)入停車場的基本操作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 << "停車場已滿，后來車輛請?jiān)诒愕赖群颉?quot; &

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 << "存車時(shí)間總計(jì)：" << d << "小時(shí)" << endl<< "收費(fèi)為：" << d << "元" << endl;i = 0;elsecout &l

12、t;< "時(shí)間輸入有誤，請重新輸入。" << endl; /時(shí)間容錯(cuò)處理；i = 1;cin >> t;elsecout << "車牌號有誤，停車場中無此車。" << endl; /容錯(cuò)，離開時(shí)也要輸入正確車牌號，否則無此車，也不耽誤程序執(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í)空分析和改進(jìn)設(shè)想 每次進(jìn)棧的時(shí)間復(fù)雜度為O（1），當(dāng)要出車輛后有n輛車時(shí)，出棧時(shí)間復(fù)雜度為O（n），也許對于一

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

16、測試情況4測試情況5測試6 試驗(yàn)心得1.書上對棧的實(shí)現(xiàn)太少不詳細(xì)，查閱了許多棧的各類實(shí)現(xiàn)怎么寫。2.存車取車問題比較簡單，在程序完成后發(fā)現(xiàn)程序的容錯(cuò)率為0，當(dāng)不小心輸入了相同車牌時(shí)程序直接報(bào)錯(cuò)，不得不添加了許多容錯(cuò)代碼，容錯(cuò)程序代碼很是讓人費(fèi)神，現(xiàn)在容錯(cuò)已完善再完善了，但還是未能完全解決問題，例如，在過道停的車輛不能保證其中沒有相同車牌號的車，還有時(shí)間處理的比較簡單原始化，這些都有待以后提高，繼續(xù)完善。3.這道題過于死板，完全是為了棧強(qiáng)行設(shè)計(jì)了一道門的停車場，每次有車出來后面的車都要移動位置，這種車庫，不停也罷。七代碼#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) /棧空判別算法；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() /列隊(duì)初始化；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) /入隊(duì)算法；q->rear = (q->rear + 1) % MAXSIZE;q->data2q->rear = x;q->num+;return;void Out_SeQueue(C_SeQueue *q, Datatype *x)/出隊(duì)算法；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 << "停車場已滿，后來車輛請?jiān)诒愕赖群颉?quot; << 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 << "存車時(shí)間總計(jì)：" << d << "小時(shí)" << endl<< "收費(fèi)為：" << d << "元" << endl;i = 0;elsecout << "時(shí)間輸入有誤，請重新輸入。" << endl; /時(shí)間容錯(cuò)處理；i = 1;cin

25、 >> t;elsecout << "車牌號有誤，停車場中無此車。" << endl; /容錯(cuò)，離開時(shí)也要輸入正確車牌號，否則無此車，也不耽誤程序執(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 +