數(shù)據(jù)結構 停車場管理

《數(shù)據(jù)結構 停車場管理》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構 停車場管理（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結構 停車場管理數(shù)據(jù)結構停車場管理2008-12-26 17：16需求分析本次數(shù)據(jù)結構課程設計的具體內(nèi)容是停車場管理系統(tǒng)，該系統(tǒng)用棧結構模擬停車場，限定停車場的容量為n，用隊列結構模擬等待的便道，空間不限制。車輛的信息包括：車牌號、汽車到達/離去標志、到達/離去時刻等。按照從終端讀入的數(shù)據(jù)序列進行模擬管理。每輛車需要三個數(shù)據(jù)，其中車輛數(shù)據(jù)為：A表示到達，D表示離去，E表示程序結束。車輛牌照為整型數(shù)據(jù)。進場或離場時間同樣為整型數(shù)據(jù)。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應交納的費用(在便道上

2、停留的時間不收費)。停車場管理系統(tǒng)主要實現(xiàn)以下幾個功能：(1)根據(jù)車輛到達停車場到車輛離開停車場時所停留的時間進行計時收費。(2)該程序設計能夠通過車牌號能查到該車輛在停車場或便道中的位置。(3)當有車輛從停車場離開時，等待的車輛按順序進入停車場停放。實現(xiàn)停車場的調(diào)度功能。該程序設計可以完整的模擬停車場的管理過程。概要設計1)為了實現(xiàn)上述程序功能，需要定義結構體數(shù)組和鏈表的抽象數(shù)據(jù)類型：ADT stack數(shù)據(jù)對象：D=ai|aicharset,i=1,2,n,n0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,n基本操作：initstack(&S,n)操作結果：構造一個空棧S,該?？纱娣舗個元素。

3、push(&S,e)初始條件：棧S已存在。操作結果：在棧S的棧頂插入新的棧頂元素e。pop(&S,&e)初始條件：棧S已存在。操作結果：刪除S的棧頂元素，并以e返回其值。DestroyStack(&S)初始條件：棧S已存在。操作結果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結果：將S清為空棧。StackLength(&S)初始條件：棧S已存在。操作結果：返回棧S的長度。StackEmpty(&S)初始條件：棧S已存在。操作結果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S已存在。操作結果：若棧S不空，則以e返回棧頂元素。Stac

4、kTraverse(S,visit()初始條件：棧S已存在。操作結果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit()。ADT stack 1.2設定隊列的抽象數(shù)據(jù)類型定義為：ADT Queue數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,n基本操作：InitQueue(&Q)操作結果：構造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列Q已存在。操作結果：隊列Q被銷毀，不再存在。ClearQueue(&Q)初始條件：隊列Q已存在。操作結果：將Q清為空隊列。QueueEmpty(&Q)初始條件：隊列Q已存在。操作結果：

5、若Q為空隊列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊列Q已存在。操作結果：返回Q的元素個數(shù)，即隊列的長度。GetHead(Q,&e)初始條件：Q為非空隊列。操作結果：用e返回Q的隊頭元素。EnQueue(&Q,e)初始條件：隊列Q已存在。操作結果：插入元素e為Q的新的隊尾元素。DeQueue(&Q,&e)初始條件：Q為非空隊列。操作結果：刪除Q的隊頭元素，并用e返回其值。QueueTraverse(Q,visit()初始條件：Q已存在且非空。操作結果：從隊頭到隊尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADT Q

6、ueue 2)本程序圖示結構(保密)詳細設計1.車輛信息類型typedef struct nodeint passport；/存儲車輛牌照信息int time；/存儲進場時間信息node；2.棧類型(停車場)typedef struct stacknode*base；node*top；int stacksize；stack；void initstack(stack&S,int n)/構造空棧S.base=(node*)malloc(n*sizeof(node)；S.top=S.base；S.stacksize=n；void push(stack&S,node e)/入棧函數(shù)if(S.top-S

7、.base)=S.stacksize)EnQueue(Q,e)；/如果棧滿，調(diào)用入隊函數(shù)elseS.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；/如果?？眨祷谽RROR-S.top；e.passport=S.top-passport；e.time=S.top-time；return OK；3.隊列類型(便道)typedef struct Qnodenode Qdata；struct Qnode*next；Qnode；typed

8、ef structQnode*front；Qnode*rear；LinkQueue；void EnQueue(LinkQueue&Q,node e)/入隊函數(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é)點前隊空，頭指針指向節(jié)點Q.rear-next=q；Q.rear=q；void DeQueue(LinkQueue&Q,node&e)/出隊函數(shù)if(Q.rear=NULL)el

9、see.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；4.全局變量及編譯預處理語句#define ERROR 0#define OK 1#define NULL 0int count=0；/隊列是否為空的標志int times；stack s,temp；/初始化棧LinkQueue Q；/初始化隊列5.主函數(shù)及其他函數(shù)的C+算法void main()int n,exit；float money；char i

10、nfo；int pass；Q.front=NULL；Q.rear=(Qnode*)malloc(sizeof(Qnode)；Q.rear-next=Q.rear；printf(停車場容量：)；cin n；initstack(s,n)；initstack(temp,n)；printf(停車場費率：)；cin money；while(exit！=OK)printf(n請輸入車輛數(shù)據(jù)nA到達D離去E結束：)；cin info；printf(請輸入車輛牌照：)；cin pass；if(info=A|info=E)printf(請輸入進場時間：)；if(info=D)printf(請輸入離場時間：)；c

11、in times；if(info=E)exit=OK；else if(info=A)int i,j；node a；a.passport=pass；a.time=times；push(s,a)；for(i=1；i=n；i+)if(s.basei-1.passport=a.passport)printf(停車位置(停車場內(nèi))：%dn,i)；Qnode*tp；tp=Q.front；if(tp=NULL)elsej=1；while(tp！=Q.rear)tp=tp-next；j+；printf(停車位置(便道)：%dn,j)；else if(info=D)node d；int tp,counter=0

12、；docounter+；tp=pop(s,d)；while(tp！=ERROR)if(d.passport=pass)float m；m=(times-d.time)*money；printf(停留時間：%d需交費：%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|counter n)；else if(info！=A&info！=

13、D&info！=E)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)；調(diào)試分析(1)一開始在調(diào)試程序時遇到了內(nèi)存錯誤，經(jīng)過DEBUG，找到了引起內(nèi)存錯誤的原因：即在建立隊頭指針與隊尾指針時沒有對指針進行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。(2)在Wait函數(shù)中的If語句處，一開始的算法有些問題，導致實現(xiàn)的功能與設想的有出入，無法得到正確的結果。原條件為：S.top-S.base=S.stacksize后改

14、為：(S.top-S.base)=(S.stacksize-1)&count！=0該函數(shù)的功能得以正確實現(xiàn)。(3)在EnQueue函數(shù)中，一開始用的是建立實體結點，用隊頭隊尾指針指向該實體的方法來創(chuàng)建隊列。在調(diào)試過程中發(fā)現(xiàn)，忽略了生存期，導致隊列并沒有被創(chuàng)建。改為創(chuàng)建指針，并為指針分配空間，再給頭指針和尾指針賦值的方式解決問題。雖然指針也有生存期，但為它分配的空間卻并沒有被收回，于是隊列創(chuàng)建成功，問題解決。(4)本程序中：車輛到達,離去時的時間復雜度均為：O(n)。本程序空間復雜度為：O(n)。(5)經(jīng)驗體會：借助DEBUG和Watch，可以更快的找到程序中的非語法錯誤。在聲明一個指針后，要對

15、指針進行初始化，并且0可以作為地址使用。注意生存期對程序的影響。用戶使用說明(1)輸入車輛數(shù)據(jù)：A為到達，D為離去，E為結束程序。(2)接著輸入車輛的牌照信息(3)若為到達的車輛，輸入進場信息，若為離去的車輛，輸入離場信息。(4)若車輛到達，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時間(在便道上的停放時間除外)，以及應該交納的費用。(5)本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時，程序結束。測試結果測試數(shù)據(jù)：設n=2輸入數(shù)據(jù)：2輸出：停車場容量：2停車場費率：6 A，1，5停車位置(停車場內(nèi))：1 A，2，10停車位置(停車場內(nèi))：2 D，1，15停留時間：10需交費：60.00 A，3，20停車位置(停車場內(nèi))：2 A，4，25停車位置(便道)：1 A，5，30停車位置(便道)：2 D，2，35停留時間：25需交費：150.00 D，4，40停留時間：5需交費：30.00