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

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

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

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

3、 基本操作： initstack(&S,n) 操作結果：構造一個空棧S,該棧可存放n個元素。 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) 初始條件：

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

5、構造一個空隊列Q。 DestroyQueue(&Q) 初始條件：隊列Q已存在。 操作結果：隊列Q被銷毀，不再存在。 ClearQueue(&Q) 初始條件：隊列Q已存在。 操作結果：將Q清為空隊列。 QueueEmpty(&Q) 初始條件：隊列Q已存在。 操作結果：若Q為空隊列，則返回TRUE，否則返回FALSE。 QueueLength(Q) 初始條件：隊列Q已存在。 操作結果：返回Q的元素個數(shù)，即隊列的長度。 GetHead(Q,&e) 初始條件：Q為非空隊列。 操作結果：用e返回Q的隊頭元素。 EnQueue(&Q,e) 初始條件：隊列Q已存在。 操作

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

7、 typedef struct stack{ node*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.base)=S.stacksize){EnQueue(Q,e)；}//如果棧滿，調用入隊函數(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；//如果?？?，返回ERROR --S.top； e.passport=S.top-passport； e.time=S.top-time； return OK； } 3.隊列類型(便道) typedef struct Qnode{ node Qdata； struct Qnode*next； }Qnode； typedef struct{ Qnode*

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

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

11、ue Q；//初始化隊列 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("停車場費率：")； cin money； while(exit！=OK){ printf("\n請輸入車輛數(shù)

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

13、port==a.passport){ printf("停車位置(停車場內)：%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("停留時間：%d需交費：%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)； } 調試分析 (1)一開始在調試程序時遇到了內存錯誤，經(jīng)過DEBUG，找到了引起內存錯誤的原因：即在建立隊頭指針與隊尾指針時沒有對指針進行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。 (2)在Wait函數(shù)中的If語句處，一開始的算法有些問題，導致實現(xiàn)的功能與設想的有出入，

16、無法得到正確的結果。 原條件為：S.top-S.base==S.stacksize 后改為：(S.top-S.base)==(S.stacksize-1)&&count！=0 該函數(shù)的功能得以正確實現(xiàn)。 (3)在EnQueue函數(shù)中，一開始用的是建立實體結點，用隊頭隊 尾指針指向該實體的方法來創(chuàng)建隊列。在調試過程中發(fā)現(xiàn)，忽略了生存期，導致隊列并沒有被創(chuàng)建。改為創(chuàng)建指針，并為指針分配空間，再給頭指針和尾指針賦值的方式解決問題。雖然指針也有生存期，但為它分配的空間卻并沒有被收回，于是隊列創(chuàng)建成功，問題解決。 (4)本程序中：車輛到達,離去時的時間復雜度均為：O(n)。本程序空間復雜度為

17、：O(n)。 (5)經(jīng)驗體會：借助DEBUG和Watch，可以更快的找到程序中的非語法錯誤。在聲明一個指針后，要對指針進行初始化，并且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停車位置(停車場內)：1 A，2，10停車位置(停車場內)：2 D，1，15停留時間：10需交費：60.00 A，3，20停車位置(停車場內)：2 A，4，25停車位置(便道)：1 A，5，30停車位置(便道)：2 D，2，35停留時間：25需交費：150.00 D，4，40停留時間：5需交費：30.00