數(shù)據(jù)結(jié)構(gòu) 停車場管理

數(shù)據(jù)結(jié)構(gòu) 停車場管理數(shù)據(jù)結(jié)構(gòu)停車場管理2008-12-26 17：16需求分析本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的具體內(nèi)容是停車場管理系統(tǒng)，該系統(tǒng)用棧結(jié)構(gòu)模擬停車場，限定停車場的容量為n，用隊(duì)列結(jié)構(gòu)模擬等待的便道，空間不限制。車輛的信息包括：車牌號、汽車到達(dá)/離去標(biāo)志、到達(dá)/離去時刻等。按照從終端讀入的數(shù)據(jù)序列進(jìn)行模擬管理。每輛車需要三個數(shù)據(jù)，其中車輛數(shù)據(jù)為：A表示到達(dá)，D表示離去，E表示程序結(jié)束。車輛牌照為整型數(shù)據(jù)。進(jìn)場或離場時間同樣為整型數(shù)據(jù)。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用(在便道上停留的時間不收費(fèi))。停車場管理系統(tǒng)主要實(shí)現(xiàn)以下幾個功能：(1)根據(jù)車輛到達(dá)停車場到車輛離開停車場時所停留的時間進(jìn)行計時收費(fèi)。(2)該程序設(shè)計能夠通過車牌號能查到該車輛在停車場或便道中的位置。(3)當(dāng)有車輛從停車場離開時，等待的車輛按順序進(jìn)入停車場停放。實(shí)現(xiàn)停車場的調(diào)度功能。該程序設(shè)計可以完整的模擬停車場的管理過程。概要設(shè)計1)為了實(shí)現(xiàn)上述程序功能，需要定義結(jié)構(gòu)體數(shù)組和鏈表的抽象數(shù)據(jù)類型：ADT stack數(shù)據(jù)對象：D=ai|aicharset,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)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。StackTraverse(S,visit()初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit()。ADT stack 1.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已存在。操作結(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返回其值。QueueTraverse(Q,visit()初始條件：Q已存在且非空。操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADT Queue 2)本程序圖示結(jié)構(gòu)(保密)詳細(xì)設(shè)計1.車輛信息類型typedef struct nodeint passport；/存儲車輛牌照信息int time；/存儲進(jìn)場時間信息node；2.棧類型(停車場)typedef struct stacknode*base；node*top；int stacksize；stack；void initstack(stack&S,int n)/構(gòu)造空棧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.base)=S.stacksize)EnQueue(Q,e)；/如果棧滿，調(diào)用入隊(duì)函數(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.隊(duì)列類型(便道)typedef struct Qnodenode Qdata；struct Qnode*next；Qnode；typedef structQnode*front；Qnode*rear；LinkQueue；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-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)elsee.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.全局變量及編譯預(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ù)的C+算法void main()int n,exit；float money；char info；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("停車場費(fèi)率：")；cin money；while(exit！=OK)printf("n請輸入車輛數(shù)據(jù)nA到達(dá)D離去E結(jié)束：")；cin info；printf("請輸入車輛牌照：")；cin pass；if(info='A'|info='E')printf("請輸入進(jìn)場時間：")；if(info='D')printf("請輸入離場時間：")；cin 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；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,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！='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)存錯誤的原因：即在建立隊(duì)頭指針與隊(duì)尾指針時沒有對指針進(jìn)行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。(2)在Wait函數(shù)中的If語句處，一開始的算法有些問題，導(dǎo)致實(shí)現(xiàn)的功能與設(shè)想的有出入，無法得到正確的結(jié)果。原條件為：S.top-S.base=S.stacksize后改為：(S.top-S.base)=(S.stacksize-1)&&count！=0該函數(shù)的功能得以正確實(shí)現(xiàn)。(3)在EnQueue函數(shù)中，一開始用的是建立實(shí)體結(jié)點(diǎn)，用隊(duì)頭隊(duì)尾指針指向該實(shí)體的方法來創(chuàng)建隊(duì)列。在調(diào)試過程中發(fā)現(xiàn)，忽略了生存期，導(dǎo)致隊(duì)列并沒有被創(chuàng)建。改為創(chuàng)建指針，并為指針分配空間，再給頭指針和尾指針賦值的方式解決問題。雖然指針也有生存期，但為它分配的空間卻并沒有被收回，于是隊(duì)列創(chuàng)建成功，問題解決。(4)本程序中：車輛到達(dá),離去時的時間復(fù)雜度均為：O(n)。本程序空間復(fù)雜度為：O(n)。(5)經(jīng)驗(yàn)體會：借助DEBUG和Watch，可以更快的找到程序中的非語法錯誤。在聲明一個指針后，要對指針進(jìn)行初始化，并且0可以作為地址使用。注意生存期對程序的影響。用戶使用說明(1)輸入車輛數(shù)據(jù)：A為到達(dá)，D為離去，E為結(jié)束程序。(2)接著輸入車輛的牌照信息(3)若為到達(dá)的車輛，輸入進(jìn)場信息，若為離去的車輛，輸入離場信息。(4)若車輛到達(dá)，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時間(在便道上的停放時間除外)，以及應(yīng)該交納的費(fèi)用。(5)本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時，程序結(jié)束。測試結(jié)果測試數(shù)據(jù)：設(shè)n=2輸入數(shù)據(jù)：2輸出：停車場容量：2停車場費(fèi)率：6 A，1，5停車位置(停車場內(nèi))：1 A，2，10停車位置(停車場內(nèi))：2 D，1，15停留時間：10需交費(fèi)：60.00 A，3，20停車位置(停車場內(nèi))：2 A，4，25停車位置(便道)：1 A，5，30停車位置(便道)：2 D，2，35停留時間：25需交費(fèi)：150.00 D，4，40停留時間：5需交費(fèi)：30.00