數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-停車場管理問題未完

1、停車場管理實驗報告 專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 班 級 121092 學(xué) 生 賀鈺植 學(xué) 號 20091001979 實驗題目：停車場管理系統(tǒng)一、需求分析1.問題描述停車場是一條可以停放n輛車的狹窄通道，且只有一個大門汽車停放安到達時間的先后依次由北向南排列（大門在最南端，最先到達的第一輛車停在最北端）若停車場已經(jīng)停滿n輛車，后來的汽車在便道上等候，一旦有車開走，排在便道上的第一輛車可以開入；當(dāng)停車場的某輛車要離開時，停在他后面的車要先后退為他讓路，等它開出后其他車在按照原次序開入車場，每兩停在車場的車要安時間長短繳費。 要求：以棧模擬停車場，以隊列車場外的便道，按照從終端輸入的數(shù)據(jù)序列進行模擬管

2、理。每一組數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼、以及到達或離去的時刻。對每一組數(shù)據(jù)進行操作后的信息為：若是車輛到達，則輸出汽車在停車場的內(nèi)或便道上的位置：若是車輛離去則輸出汽車在停車場內(nèi)的停留時間和應(yīng)繳納的費用（在便道上的停留時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)2.基本要求以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項；汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽

3、車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。測試數(shù)據(jù)： 設(shè)n=2,輸入數(shù)據(jù)為：（A，1，5），（A，2，10），（D，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。3.拓展內(nèi)容（1）汽車可有不同種類，則它們的占地面積不同，收費標(biāo)準也不同。 （2）汽車可以直接從便道上開走，此時排在它前面的汽車要先開走讓路，然后再依次排到隊尾。 （3）停放在便道上的汽車也收費，收費標(biāo)準比停放在停車場的車低，請思考如何修改結(jié)構(gòu)以滿足這種要求。二、設(shè) 計 1.設(shè)計思想由于停車場是一個狹窄

4、通道，而且只有一個大門可供汽車進出，問題要求汽車停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列。由此很容易聯(lián)想到數(shù)據(jù)結(jié)構(gòu)中的堆棧模型，因此可首先設(shè)計一個堆棧，以堆棧來模擬停車場，我設(shè)計用順序存儲結(jié)構(gòu)來存儲停車場內(nèi)的車輛信息，并給車輛按進棧順序編號，當(dāng)停車場內(nèi)某輛車要離開時，在他之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進入停車場。這是個一退一進的過程，而且讓道的汽車必須保持原有的先后順序，因此可再設(shè)計一個堆棧，以之來暫時存放為出站汽車暫時讓道的汽車。當(dāng)停車場滿后，繼續(xù)進來的汽車需要停放在停車場旁邊的便道上等候，若停車場有汽車開走，則按排隊的先后順序依次進站

5、，最先進入便道的汽車將會最先進入停車場，這完全是一個先進先出模型，因此可設(shè)計一個隊列來模擬便道，隊列中的數(shù)據(jù)元素設(shè)計成汽車的車牌號，并以鏈表的形式存儲。另外，停車場根據(jù)汽車在停車場內(nèi)停放的總時長來收費的，在便道上的時間不計費，因此必須記錄車輛進入停車場時的時間和車輛離開停車場時的時間，然后計算、顯示費用情況。2.概要設(shè)計（1）Status InitStack(SqStack &s)構(gòu)造一個空棧，用以表示車輛信息。（2）Status Push(SqStack &s,SElemType e)向棧中插入元素，表示車輛進入信息（3）Status Pop(SqStack &s,S

6、ElemType &e)若棧不空，則刪除s的棧頂元素，用e返回其值，并返回OK，否則返回ERROR,用以表示車輛開出的信息。 （4）Status InitQueue(LinkQueue &Q)構(gòu)造一個空隊列表示便道車輛信息。（5）Status EnQueue(LinkQueue &Q,SElemType e)隊列的插入表示車輛進入便道等候的信息。（6）Status DeQueue(LinkQueue &Q,SElemType &e)若隊列不空，則刪除Q的對頭元素，用e返回其值，并返回OK，否則返回ERROR，表示車輛開出便道進入停車場。（7）void C

7、arArrival(SqStack &s,LinkQueue &Q)對汽車到達時處理，記下車號到達時刻，車號等等的信息。（8）void CarDeparture(SqStack &s,LinkQueue &Q)車輛在停車場整個過程的信息，其中包括收費信息。3詳細設(shè)計下面是整個程序的算法的設(shè)計框架。開始初始化兩個棧和及一個隊列。進入主菜單車到達車離開退出停車場前車輛進臨時棧對對車輛計費便道車信息車場內(nèi)信息判便道是否有車車場是否為空列表顯示棧元素出棧隊列中元素進棧隊列中元素出隊元素進棧便道車進車場元素進隊列判斷棧是否為滿結(jié)束退出列表顯示是否否是否是三、源程序清單#i

8、nclude<stdio.h>#include<stdlib.h>#include<iostream.h>typedef int Status; /元素類型int flag=0;typedef structint carnumber; /車號int time; /汽車“到”或“離”的時刻SElemType;/以下是對棧數(shù)據(jù)類型的定義#define STACK_INIT_SIZE 2#define STACKINCREMENT 1typedef structSElemType *base; SElemType *top; int stacksize; SqSt

9、ack;Status InitStack(SqStack &s) /構(gòu)造一個空棧Ss.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!s.base) exit(0);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return 1;Status Push(SqStack &s,SElemType e)/插入元素e為新的棧頂元素if(s.top-s.base>=s.stacksize)/棧滿s.base=(SElemType * ) realloc(s.ba

10、se,(s.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!s.base) exit(0); /存儲分配失敗s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return 1;Status Pop(SqStack &s,SElemType &e)/若棧不空，則刪除s的棧頂元素，用e返回其值，并返回OK，否則返回ERRORif(s.top=s.base) return 0;e=*-s.top;return 1;typedef struct QNodeSE

11、lemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue &Q) /構(gòu)造一個空隊列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(0);Q.front->next=NULL;return 1;Status EnQueue(LinkQueue &Q,SElemType e) /插入元素e為新的隊尾元

12、素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return 1;Status DeQueue(LinkQueue &Q,SElemType &e)/若隊列不空，則刪除Q的對頭元素，用e返回其值，并返回OK，否則返回ERRORQueuePtr p;if(Q.front=Q.rear) return 0;p=Q.front->next;e=p->data; p->next=NULL

13、;Q.front->next=p->next;if(Q.rear=p) Q.rear=Q.front;free(p);return 1; /對汽車到達時的處理void CarArrival(SqStack &s,LinkQueue &Q)SElemType e;cout<<"請輸入車號:"cin>>e.carnumber;cout<<"請輸入到達時刻:"cin>>e.time;if(s.top-s.base>s.stacksize)EnQueue(Q,e);cout<

14、<"-n"cout<<"|車號| 停車位置 | 到達時刻 |n"cout<<"-n"cout<<"|"<<e.carnumber<<"| 停在便道上等待|"<<e.time<<" |"<<"n"cout<<"-n"elsePush(s,e);*s.top+=e;cout<<"-n"cout&l

15、t;<"|車號| 停車位置 | 到達時刻 |n"cout<<"-n"cout<<"|"<<e.carnumber<<"| 停在停場內(nèi)"<<+flag<<"號位|"<<e.time<<" |"<<"n"cout<<"-n"void CarDeparture(SqStack &s,LinkQueue &

16、;Q)SqStack T; /臨時倒車處int money;/停留時刻SElemType a,e;int carnumber,time;InitStack(T);/構(gòu)造臨時倒車處cout<<"請輸入車號:"<<endl;cin>>carnumber;cout<<"請輸入離去時刻:"<<endl;cin>>time;a=*(s.top-1);doPop(s,e);Push(T,e);*s.top-=e;a=*(s.top-1);while(e.carnumber!=carnumber)

17、;Pop(s,e); money=time-e.time;cout<<"武昌停車場收費單 n"cout<<"-n"cout<<"|車號 |到達時刻 |離去時刻 |停留時刻 |費用(元) |n"cout<<"-n"cout<<"|"<<carnumber<<"|"<<e.time<<" |"<<time<<"|&quo

18、t;<<money<<" |"<<money*2<<" |"<<"n"cout<<"-n"flag-;while(T.base!=T.top)Pop(T,e);*s.top+=e;while(Q.front!=Q.rear)if(s.top-s.base<s.stacksize)DeQueue(Q,e); Push(s,e);*s.top+=e;if(s.top-s.base> STACK_INIT_SIZE)cout<<"n便道上有車進入停車場!"<<"n此車停在"<<+flag<<"車位"<<endl; void shurujiesu()cout<<"nn輸入結(jié)束（END)!nn"void main() cha