《數(shù)據(jù)結(jié)構(gòu)報告 停車場問題》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)報告 停車場問題（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 問題描述：停車場管理問題問題描述 設(shè)有一個可以停放n輛汽車的狹長停車場，它只有一個大門可以供車輛進(jìn)出。車輛按到達(dá)停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達(dá)的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進(jìn)入停車場。停車場內(nèi)如有某輛車要開走，在它之后進(jìn)入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進(jìn)場。每輛車在離開停車場時，都應(yīng)根據(jù)它在停車場內(nèi)停留的時間長短交費(fèi)。如果停留在便道上的車未進(jìn)停車場就要離去，允許其離去，不收停車費(fèi)，并且仍然保持在便道上等

2、待的車輛的次序。編制一程序模擬該停車場的管理。實(shí)現(xiàn)要求 要求程序輸出每輛車到達(dá)后的停車位置(停車場或便道上)，以及某輛車離開停車場時應(yīng)交納的費(fèi)用和它在停車場內(nèi)停留的時間。實(shí)現(xiàn)提示 汽車的模擬輸入信息格式可以是：(到達(dá)離去，汽車牌照號碼，到達(dá)離去的時刻)。例如，(A，1，5)表示1號牌照車在5這個時刻到達(dá)，而(D，5，20)表示5號牌照車在20這個時刻離去。整個程序可以在輸入信息為(E，0，0)時結(jié)束。本題可用棧和隊(duì)列來實(shí)現(xiàn)。 設(shè)計： 數(shù)據(jù)結(jié)構(gòu)設(shè)計和核心算法設(shè)計描述；停車場管理系統(tǒng)是充分利用數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的思想實(shí)現(xiàn)的，棧是一種只能在叫做棧的一段進(jìn)行進(jìn)?；蛘叱鰲２僮鞯木€性數(shù)據(jù)結(jié)構(gòu)。棧的主要特點(diǎn)

3、是”后進(jìn)先出”，即后進(jìn)棧的元素先處理。停車場的容量即為棧的存儲空間，停車場的車輛的?？渴菬o秩序的，因此采用鏈?zhǔn)酱鎯Φ姆绞礁m合，也方便車輛的調(diào)度。隊(duì)列是限定僅能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。隊(duì)列中可以插入的一端稱為隊(duì)尾，可以刪除的一端稱為隊(duì)首。把一個元素插入隊(duì)列中的操作為進(jìn)隊(duì)，隊(duì)列中刪除一個元素的操作為出隊(duì)。隊(duì)列存取操作符合：先進(jìn)先出。停車場的車輛到達(dá)停車和車輛的離開的管理方式就是采用隊(duì)列的“先進(jìn)先出”的移動的思想。停車場的入口就是隊(duì)列的隊(duì)首，停車場的出口就是隊(duì)列的隊(duì)尾。 主控及功能模塊層次結(jié)構(gòu)；2.1設(shè)定棧的抽象數(shù)據(jù)類型定義為：ADT stack數(shù)據(jù)對象：D=ai|aic

4、harset, i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n基本操作：initstack(&S, n)操作結(jié)果：構(gòu)造一個空棧S,該?？纱娣舗個元素。push(&S, e)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。pop(&S, &e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(&S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長度。StackEmpty(&S)初

5、始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S, &e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。StackTraverse(S, visit()初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit()。ADT stack2.2 設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義為：ADT Queue數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=|ai-1,aiD,i=2,n基本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊(duì)列Q。DestroyQueue(&Q)初始條件：隊(duì)列Q已

6、存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個數(shù)，即隊(duì)列的長度。GetHead(Q, &e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。EnQueue(&Q, e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q, &e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。Q

7、ueueTraverse(Q, visit()初始條件：Q已存在且非空。操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADT Queue2.3詳細(xì)設(shè)計車輛信息類型typedef struct nodeint passport; /存儲車輛牌照信息int time; /存儲進(jìn)場時間信息node;2棧類型（停車場）typedef struct stack /定義停車場棧類型node *base;node *top;int stacksize;stack;void initstack(stack &S,int n) /構(gòu)造空棧S.base=

8、(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksize=n;void push(stack &S,node e) /入棧函數(shù)if(S.top-S.base)=S.stacksize)EnQueue(Q,e); /如果棧滿則調(diào)用入隊(duì)函數(shù)else S.top-passport=e.passport;S.top-time=e.time;S.top+;void wait(stack &S)if(S.top-S.base)=(S.stacksize-1)&count!=0)node temp;DeQueue(Q,temp);temp.time=tim

9、es;push(S,temp);int pop(stack &S,node &e) /出棧函數(shù)if(S.top=S.base)return ERROR; /如果?？談t返回ERROR-S.top;e.passport=S.top-passport;e.time=S.top-time;return OK;3隊(duì)列類型（便道）typedef struct Qnode /定義便道隊(duì)列類型node Qdata;struct Qnode *next;Qnode;typedef struct Qnode *front;Qnode *rear;LinkQueue;void EnQueue(LinkQueue &

10、Q,node e) /入隊(duì)函數(shù)Qnode *q;q=(Qnode *)malloc(sizeof(Qnode);q-Qdata.passport=e.passport;q-Qdata.time=e.time;q-next=NULL;if(count=0)Q.front=q;count+; /若創(chuàng)建節(jié)點(diǎn)前隊(duì)空，頭指針指向節(jié)點(diǎn)Q.rear-next=q;Q.rear=q;void DeQueue(LinkQueue &Q,node &e) /出隊(duì)函數(shù)if(Q.rear=NULL)else e.passport=Q.front-Qdata.passport;e.time=Q.front-Qdata.

11、time;Q.front=Q.front-next;if(Q.front=NULL)Q.rear=Q.front;count=0;4全局變量及編譯預(yù)處理語句#define ERROR 0#define OK 1#define NULL 0int count=0; /隊(duì)列是否為空的標(biāo)志int times;stack s,temp; /初始化棧LinkQueue Q; /初始化隊(duì)列5主函數(shù)及其他函數(shù)的算法void main()int n,exit;float money;char info;int pass;Q.front=NULL;Q.rear=(Qnode *)malloc(sizeof(Qn

12、ode);Q.rear-next=Q.rear;printf(停車場容量:);scanf(%d,&n);initstack(s,n);initstack(temp,n);printf(停車場費(fèi)率(元/小時):);scanf(%f,&money);while(exit!=OK)printf(n請選擇車輛狀態(tài)n1到達(dá) 2離去 3結(jié)束:); getchar();scanf(%c,&info);printf(請輸入車輛牌照:);scanf(%d,&pass);if(info=1|info=3)printf(請輸入進(jìn)場時間:);if(info=2)printf(請輸入離場時間:);scanf(%d,&t

13、imes);if(info=3)exit=OK;else if(info=1)int i,j;node a;a.passport=pass;a.time=times;push(s,a);for(i=1;inext;j+;printf(停車位置(便道):%dn,j);else if(info=2)node d;int tp,counter=0;docounter+;tp=pop(s,d);while(tp!=ERROR)if(d.passport=pass)float m;m=-(times-d.time)*money;printf(停留時間:%d 需交費(fèi):%fn,-(times-d.time)

14、*(-1),m*(-1);while(temp.base!=temp.top)pop(temp,d);push(s,d);wait(s);d.passport=9999;tp=ERROR;elsepush(temp,d);d.passport=0;tp=ERROR;while(d.passport=0|countern);else if(info!=1&info!=2&info!=3) 主要功能模塊的輸入、處理(算法框架描述)和輸出； 功能模塊之間的調(diào)用與被調(diào)用關(guān)系等。（1）輸入車輛數(shù)據(jù)：1為到達(dá)，2為離去，3為結(jié)束程序。（2）接著輸入車輛的牌照信息（3）若為到達(dá)的車輛，輸入進(jìn)場信息，若為離去

15、的車輛，輸入離場信息。（4）若車輛到達(dá)，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時間（在便道上的停放時間除外），以及應(yīng)該交納的費(fèi)用。（5）本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時，程序結(jié)束。 測試： 測試范例，測試結(jié)果，測試結(jié)果的分析與討論，測試過程中遇到的主要問題及所采用的解決措施。測試數(shù)據(jù)：設(shè)n=2輸入數(shù)據(jù)：2輸出：停車場容量:2停車場費(fèi)率:6A，1，5 停車位置(停車場內(nèi)):1A，2，10 停車位置(停車場內(nèi)):2D，1，15 停留時間:10 需交費(fèi):60.00A，3，20 停車位置(停車場內(nèi)):2A，4，25 停車位置(便道):1A，5，30 停車位置(便

16、道):2D，2，35 停留時間:25 需交費(fèi):150.00D，4，40 停留時間:5 需交費(fèi):30.00E，0，04. 運(yùn)行結(jié)果（1）進(jìn)入停車場(2) 離開停車場(3) 等待停車5. 程序源代碼#include #include #define ERROR 0#define OK 1#define NULL 0typedef struct node /定義車輛信息數(shù)據(jù)結(jié)構(gòu)int passport; /存儲車輛牌照信息int time; /存儲進(jìn)場時間信息node;typedef struct stack /定義停車場棧類型node *base;node *top;int stacksize;s

17、tack;typedef struct Qnode /定義便道隊(duì)列類型node Qdata;struct Qnode *next;Qnode;typedef struct Qnode *front;Qnode *rear;LinkQueue;int count=0; /隊(duì)列是否為空的標(biāo)志int times;stack s,temp; /初始化棧LinkQueue Q; /初始化隊(duì)列void initstack(stack &S,int n) /構(gòu)造空棧S.base=(node *)malloc(n*sizeof(node);S.top=S.base;S.stacksize=n;void EnQ

18、ueue(LinkQueue &Q,node e); /入隊(duì)函數(shù)void DeQueue(LinkQueue &Q,node &e); /出隊(duì)函數(shù)void push(stack &S,node e) /入棧函數(shù)if(S.top-S.base)=S.stacksize)EnQueue(Q,e); /如果棧滿則調(diào)用入隊(duì)函數(shù)else S.top-passport=e.passport;S.top-time=e.time;S.top+;int pop(stack &S,node &e) /出棧函數(shù)if(S.top=S.base)return ERROR; /如果?？談t返回ERROR-S.top;e.p

19、assport=S.top-passport;e.time=S.top-time;return OK;void wait(stack &S)if(S.top-S.base)=(S.stacksize-1)&count!=0)node temp;DeQueue(Q,temp);temp.time=times;push(S,temp);void EnQueue(LinkQueue &Q,node e) /入隊(duì)函數(shù)Qnode *q;q=(Qnode *)malloc(sizeof(Qnode);q-Qdata.passport=e.passport;q-Qdata.time=e.time;q-nex

20、t=NULL;if(count=0)Q.front=q;count+; /若創(chuàng)建節(jié)點(diǎn)前隊(duì)空，頭指針指向節(jié)點(diǎn)Q.rear-next=q;Q.rear=q;void DeQueue(LinkQueue &Q,node &e) /出隊(duì)函數(shù)if(Q.rear=NULL)else e.passport=Q.front-Qdata.passport;e.time=Q.front-Qdata.time;Q.front=Q.front-next;if(Q.front=NULL)Q.rear=Q.front;count=0;void main()int n,exit;float money;char info;

21、int pass;Q.front=NULL;Q.rear=(Qnode *)malloc(sizeof(Qnode);Q.rear-next=Q.rear;printf(停車場容量:);scanf(%d,&n);initstack(s,n);initstack(temp,n);printf(停車場費(fèi)率(元/小時):);scanf(%f,&money);while(exit!=OK)printf(n請選擇車輛狀態(tài)n1到達(dá) 2離去 3結(jié)束:);scanf(%c,&info);printf(請輸入車輛牌照:);scanf(%d,&pass);if(info=1|info=3)printf(請輸入進(jìn)場

22、時間:);if(info=2)printf(請輸入離場時間:);scanf(%d,×);if(info=3)exit=OK;else if(info=1)int i,j;node a;a.passport=pass;a.time=times;push(s,a);for(i=1;inext;j+;printf(停車位置(便道):%dn,j);else if(info=2)node d;int tp,counter=0;docounter+;tp=pop(s,d);while(tp!=ERROR)if(d.passport=pass)float m;m=(times-d.time)*mo

23、ney;printf(停留時間:%d 需交費(fèi):%fn,times-d.time,m);while(temp.base!=temp.top)pop(temp,d);push(s,d);wait(s);d.passport=9999;tp=ERROR;elsepush(temp,d);d.passport=0;tp=ERROR;while(d.passport=0|countern);else if(info!=1&info!=2&info!=3)6. 心得體會（1）一開始在調(diào)試程序時遇到了內(nèi)存錯誤，經(jīng)過調(diào)試，找到了引起內(nèi)存錯誤的原因：即在建立隊(duì)頭指針與隊(duì)尾指針時沒有對指針進(jìn)行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。 （2）在Wait函數(shù)中的If語句處，一開始的算法有些問題，導(dǎo)致實(shí)現(xiàn)的功能與設(shè)想的有出入，無法得到正確的結(jié)果。 （3）本程序中：車輛到達(dá),離去時的時間復(fù)雜度均為：O(n)。本程序空間復(fù)雜度為：O(n)。 （4）在本次課程設(shè)計中不僅加深了對棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)的理解和掌握，同時一定程度上提高了自己程序設(shè)計和閱讀程序的能力。本次課程設(shè)計提高了我們的專業(yè)知識，使自己所學(xué)的內(nèi)容運(yùn)用到實(shí)際中來，也增強(qiáng)了實(shí)際操作能力，為以后的工作學(xué)習(xí)提供了一個良好的鋪墊。