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

《數(shù)據(jù)結(jié)構(gòu) 停車場管理》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) 停車場管理（14頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

2、和應(yīng)交納的費(fèi)用(在便道上停留的時(shí)間不收費(fèi))。 停車場管理系統(tǒng)主要實(shí)現(xiàn)以下幾個(gè)功能： (1)根據(jù)車輛到達(dá)停車場到車輛離開停車場時(shí)所停留的時(shí)間進(jìn)行計(jì)時(shí)收費(fèi)。 (2)該程序設(shè)計(jì)能夠通過車牌號(hào)能查到該車輛在停車場或便道中的位置。 (3)當(dāng)有車輛從停車場離開時(shí)，等待的車輛按順序進(jìn)入停車場停放。實(shí)現(xiàn)停車場的調(diào)度功能。 該程序設(shè)計(jì)可以完整的模擬停車場的管理過程。 概要設(shè)計(jì) 1)為了實(shí)現(xiàn)上述程序功能，需要定義結(jié)構(gòu)體數(shù)組和鏈表的抽象數(shù)據(jù)類型： ADT stack{ 數(shù)據(jù)對(duì)象：D={ai|ai∈charset,i=1,2,…,n,n≥0} 數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2…,n}

3、 基本操作： initstack(&S,n) 操作結(jié)果：構(gòu)造一個(gè)空棧S,該?？纱娣舗個(gè)元素。 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) 初始條件：

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

5、構(gòu)造一個(gè)空隊(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的元素個(gè)數(shù)，即隊(duì)列的長度。 GetHead(Q,&e) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：用e返回Q的隊(duì)頭元素。 EnQueue(&Q,e) 初始條件：隊(duì)列Q已存在。 操作

6、結(jié)果：插入元素e為Q的新的隊(duì)尾元素。 DeQueue(&Q,&e) 初始條件：Q為非空隊(duì)列。 操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。 QueueTraverse(Q,visit()) 初始條件：Q已存在且非空。 操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對(duì)Q的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。 }ADT Queue 2)本程序圖示結(jié)構(gòu) (保密) 詳細(xì)設(shè)計(jì) 1.車輛信息類型 typedef struct node{ int passport；//存儲(chǔ)車輛牌照信息 int time；//存儲(chǔ)進(jìn)場時(shí)間信息 }node； 2.棧類型(停車場)

7、 typedef struct stack{ node*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ù) else{ S.top-passport=

8、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 Qnode{ node Qdata； struct Qnode*next； }Qnode； typedef struct{ Qnode*

9、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){

10、//出隊(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；} } } 4.全局變量及編譯預(yù)處理語句 #define ERROR 0 #define OK 1 #define NULL 0 int count=0；//隊(duì)列是否為空的標(biāo)志 int times； stack s,temp；//初始化棧 LinkQue

11、ue 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ù)

12、據(jù)\nA到達(dá)D離去E結(jié)束：")； cin info； printf("請輸入車輛牌照：")； cin pass； if(info=='A'||info=='E')printf("請輸入進(jìn)場時(shí)間：")； if(info=='D')printf("請輸入離場時(shí)間：")； 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.base[i-1].pass

13、port==a.passport){ printf("停車位置(停車場內(nèi))：%d\n",i)； } } Qnode*tp； tp=Q.front； if(tp==NULL){} else{ j=1； while(tp！=Q.rear){ tp=tp-next； j++； } printf("停車位置(便道)：%d\n",j)； } } else if(info=='D'){ node d； int tp,counter=0； do{ counter++； tp=pop(s,d)； while(tp！=ERROR){ if(d.passport==p

14、ass){ float m； m=(times-d.time)*money； printf("停留時(shí)間：%d需交費(fèi)：%f\n",times-d.time,m)； while(temp.base！=temp.top){ pop(temp,d)； push(s,d)； } wait(s)； d.passport=9999； tp=ERROR； } else{ push(temp,d)； d.passport=0； tp=ERROR； } } }while(d.passport==0||counter n)； } else if(info！='A'&&info

15、！='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)試程序時(shí)遇到了內(nèi)存錯(cuò)誤，經(jīng)過DEBUG，找到了引起內(nèi)存錯(cuò)誤的原因：即在建立隊(duì)頭指針與隊(duì)尾指針時(shí)沒有對(duì)指針進(jìn)行初始化(沒有為指針動(dòng)態(tài)分配空間)。問題得到解決。 (2)在Wait函數(shù)中的If語句處，一開始的算法有些問題，導(dǎo)致實(shí)現(xiàn)的功能與設(shè)想的有出入，

16、無法得到正確的結(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á),離去時(shí)的時(shí)間復(fù)雜度均為：O(n)。本程序空間復(fù)雜度為

17、：O(n)。 (5)經(jīng)驗(yàn)體會(huì)：借助DEBUG和Watch，可以更快的找到程序中的非語法錯(cuò)誤。在聲明一個(gè)指針后，要對(duì)指針進(jìn)行初始化，并且0可以作為地址使用。注意生存期對(duì)程序的影響。 用戶使用說明 (1)輸入車輛數(shù)據(jù)：A為到達(dá)，D為離去，E為結(jié)束程序。 (2)接著輸入車輛的牌照信息 (3)若為到達(dá)的車輛，輸入進(jìn)場信息，若為離去的車輛，輸入離場信息。 (4)若車輛到達(dá)，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時(shí)間(在便道上的停放時(shí)間除外)，以及應(yīng)該交納的費(fèi)用。 (5)本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時(shí)，程序結(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停留時(shí)間：10需交費(fèi)：60.00 A，3，20停車位置(停車場內(nèi))：2 A，4，25停車位置(便道)：1 A，5，30停車位置(便道)：2 D，2，35停留時(shí)間：25需交費(fèi)：150.00 D，4，40停留時(shí)間：5需交費(fèi)：30.00