HUNANUNIVERSITY

課程實驗報告

題目：停車場管理

學生姓名：

學生學號：

專業(yè)班級：。

指導老師：

完畢日期:

需求分析

1.輸入形式

第一次輸入一個正整數(shù)，代表停車場容量大小。然后輸入三個值,分別

為字符、正整數(shù)、正整數(shù)，中間用空格隔開，分別代表車“到達”或“拜

別”信息、汽車牌照號碼以及到達或拜別的時刻。其中字符必須為“A,

D,E”三者之一。輸入格式為：“A15”、“D115”和“E0

0當用戶輸入的字符不是ADE或者輸入的不是正整數(shù)時，提醒用戶

輸入錯誤并重新輸入

2.輸出形式

若是車輛到達,則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車

輛拜別,則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停

留的時間不收費）。

（注:本程序中默認停車一小時收費10元）

3.程序功能

本程序可通過用戶輸入的車輛信息，輸出該車的停車位置或者停車時

間及應繳費用

4.測試數(shù)據(jù)

請輸入停車場容量：5

A11車停在停車場第1個位置

A22車停在停車場第2個位置

A66車停在停車場第3個位置

D14停車時間：3繳納費用：￥30

D26停車時間：3繳納費用：￥30

FC19.5輸入有誤，請重新輸入

E00

概要設計

1.抽象數(shù)據(jù)類型

將每輛車模擬成一個對象，每個對象具有車牌號時間等屬性,所以定義一個

Car類存儲這些信息

classCar

(

public：

intCarNumber;//車牌號碼

intArriveTime；〃到達時間

intLeaveTime；//離開時間

}

使用棧模擬停車場，其ADT設計：

ADTstack

數(shù)據(jù)對象：Car類

數(shù)據(jù)關系:線性關系

基本操作：

voidclear0；〃棧的初始化

boolpush(constCar&item);〃棧的插入操作

boolpop(Car&it);//棧的刪除操作

booltopValue(Car&it)//棧的頂層元素

intlength()const

{returnsize};//棧的實際長度

使用隊列模擬場外通道，其ADT設計如下：

ADTQueue

數(shù)據(jù)對象：Car類

數(shù)據(jù)關系:線性關系

基本操作：

voidclear();//隊歹U的初始化

boolenqueue(constCar&it)；//入隊

boo1dequeue(Car&it)；//出隊

int1ength()const

{returnsize;};〃隊列的長度

2.算法基本思想

①在該程序中，對停車場和場外通中每輛車停車的編號而言，他們有

唯一的第一個元素和最后一個元素，并且除第一個元素以外的每個元素都

有唯一的后繼，除最后一個元素以外的每個元素都有唯一的前驅(qū)。因此這

些元素具有線性關系。并且，對于停車場里面的汽車，他們邏輯順序是“先

進后此后進先出“的，且只在表頭作插入和刪除，所以可以使用棧來模擬

停車場。而在場外通道中的汽車，他們是“先進先出”的，在一端插入另

一端刪除操作，所以可以用隊列來模擬場外通道。當汽車離開時，在它之

后進入的車輛必須先退出再按原順序進入停車場，所以需要定義此外一個

臨時棧存儲這些元素。（本算法按用戶輸入的順序進行車輛的停放，不是

按車牌號碼依次停放）

②（1）當有汽車需要進停車場停車時，進行入棧操作,若停車場已滿,

即棧已滿，則將車停在場外通道里，進行入隊操作，并記下此時的時間

ArriveTime；

（2）當有汽車需要離開停車場時，對該車相應的元素進行出棧操

作，并將后面進來的車輛所相應的元素進行出棧操作，將這些元素（除了

需要離開的車相應的元素）存入此外一個棧，即為需要離開停車場的車讓

道，并記下此時的時間LeaveTime;

（3）在需要離開停車場的車成功離開停車場時，將存儲在臨時

棧的那些元素按照本來的順序依次插入本來的棧；

（4）假如隊列不為空（即停車場場外通道上有車，這些車需要進

入停車場停車），進行入棧操作，即進行（1）操作；

（5）通過LeaveTime與ArriveTime的差計算停車時間和停

車費用（本程序默認停車每小時10元）；

3.程序基本流程

程序由個基本模塊組成:

輸入模塊:輸入停車場的容量和車輛的相關信息；

停車模塊:根據(jù)車的信息,將該車相應的元素進行入棧操作；

離開模塊:根據(jù)車的信息,將該車相應的元素進行出棧操作，

并將后面的元素存入一個臨時棧中；

輸出模塊:輸出該車停車位置或停車費用；

三.具體設計

1.物理數(shù)據(jù)類型

①停車場容量為正整數(shù)，使用整型數(shù)據(jù)存儲n；

②對于剩下的輸入使用字符型、整型、整型存儲，并將相應數(shù)據(jù)存入Ca

r類

classCar

(

public:

intCarNumber;//車牌號碼

intArriveTime；〃到達時間

intLeaveTime;〃離開時間

}

③定義一個Link類用來存儲元素值e1ement及下一個存儲表中下一個

節(jié)點指針的next域,其ADT設計如下：

ternplate<classCar>c1assLink

public:

。Carelement;

Link*next;

Link(constCar&elemval,Link*nextva1=

NULL)

0(

。element=e1emval；

gnext=nextva1;

)

。Link(Link*nextval=NULL)

(

匕next=nextva1；

0)

}；

④由于停車場容量一定，即?？臻g大小不變，所以可以選用順序表實現(xiàn)棧

classAStck:pub1icStack<Car>//

(

private:

intsize;〃棧的長度

inttop；〃棧頂元素

Car*listArray；〃順序表保存棧元素

public：

AStack(intsz)

{size=sz；top=0;1istArray=newCar[sz]；}

//構造函數(shù)

~AStack(){delete[]listArray；}〃析構函數(shù)

voidclear0{top=0;}〃棧的清空

boolpush(constCar&item)

(

if(top==size)returnfalse;

else

{1istArray[top++]=item;returntr

ue;}

}//棧的插入

boolpop(Car&item)

(

if(top==0)returnfalse;

else

(

item=1istArray[—top];retu

rntrue;

)

)〃棧的刪除

booltopVa1ue(Car&it)const

if(top==0)returnfaIse;

else

{it=1istArray[top-1]；returntru

e；)

)//獲取棧頂元素

intlengthOconst{returntop；}

//棧的長度

)；

⑤由于該隊列中元素添加操作和刪除操作比較多，所以使用鏈式隊列實

現(xiàn)隊列：

template<classCar>classQueue:publieLink<

Car>

(

private:

intsize;

Link<Car>*front；

Link<Car>*rear;

pub1ic:

LQueue(intsz){front=NULL；rear=NUL

L;size=0}

^Lqueue(){de1ete[]front;delete[]rear；};

voidclear()

{whi1e(front!=NULL)

{rear=front;

front=front->next;

deleterear；

}

rear=NULL；size=0;

}//隊列的清空

boo1enqueue(constCar&it)

(

if(rear=NULL)

front=rear=newLink<Car>(itNULL);

else

I

rear->next=newLink<Car>(it,NULL)；

rear=rear->next；

)

size++;

returntrue；

)〃入隊

booldequeue(￡ar&it)

(

if(size==0)returnfalse；

it=front->element;

Link<Car>*1temp=front；

front=front->next

de1eteItemp;

if(front=NULL)rear=NULL;

siz一；

returntrue;

}//出隊

int1ength()const{returnsize;}//隊列的長

度

)

2.算法具體環(huán)節(jié)

(park為停車場相應的棧,out指臨時棧,line指隊列)

charc;

input(c);〃輸入汽車停車或者離開或者結束；

input(num);〃輸入汽車編號

input(time);//輸入汽車進入或離開時間

CarC[100];//Car的對象數(shù)組

whiIe(l)//停車

(

switch(c)

case('A')//進入停車場

if(parkisFULL)//停車場已滿

{enqueue(C[num-l]);output(1in

e.length())}

//輸出停車位置

else{

8。park.push(C[a-1])；

*C[a-l].ArriveTime=b；

。8C[a—1].carNumber=a;

output(park.length())〃輸出停車位置

}OddOO

}break；

case('D')〃離開

C[a-1].LeaveTime=b;

C[a-1].carNumber=a；//進來與離開

時間

for(inti=0；i<a-1;i++)

//為要離開的車開道

80{

8。park.pop(C[i])；//先刪除前面的元素

-out.push(CEi1);//將前面的元素存至臨時棧中

000park,topValue(C[i]);//

while(out.length()!=0)〃將車復原

for(inti=0;i<a-1;i++)

00{

aout.pop(C[i])；

gpark.push(C[i]);

8}

}

if(line.length()!=0)〃將在通道內(nèi)的車停進停車

場

{

for(intj=a；j<a+line.lengthO

—1；j++)

8{

*line.dequeue(C[j]);

z>park.push(C[j]);}

output(C[a-1].LeaveTime-C[a-1].ArriveTim

e)；

//輸出停留時間

boutput(10*(C[a—1].LeaveTime-C[a—

11.ArriveTime))；

〃輸出停車費用

}break;

case：return0；//輸入時結束

)

3.算法時空分析

在該程序中，棧的插入的時間復雜度為0(1),而對棧中元素進行

刪除時，需要對該元素后面的所有元素都進行刪除，并將他們存入此外

一個臨時棧中，到該元素順利刪除完畢時又重新存入原棧中，所以棧的

刪除的時間復雜度為9(/);

4.輸入輸出格式

(停車費用每小時10元)

輸入：

5

A11

A66

D14

E00

輸出：

車停在停車場第1個位置

車停在場外通道第2個位置

停車時間：3繳納費用：￥30

四.調(diào)試分析

在使用類模板時,第一次沒有使用模板參數(shù)列表，導致程序運營犯錯,后

來將Car改成classCar后糾正了這個錯誤

五.測試結果

:e

天

停軍

場{

亶.0f

請

^9輸\

信

容

>，o

場

<車0

：

天

息

人

喜^

:A工2

簟

車

置

停z

善

t1位

差

關

入

心3

螯w:A4

置

停

/位

、

車2r,

善

車：

入

型

輛

關T25

心:

1y用

重

7?

1暫

，

H?

爵

9相

KW;D14

關

H心

間

-停

需

為

車

納

用20-

71

程序測試時界面截圖如下

六.用戶使用說明

1.本程序用來解決停車場的問題；

2.運營程序后，需要規(guī)定進行輸入，如若輸入錯誤，系統(tǒng)提醒輸入錯誤請

重新輸入，第一次輸入停車場容量,接下來請輸入車輛相關信息；

3.車輛相關信息中用空格隔開，第一個輸入'A'或'D，或'E，,分別

表達停車,車離開停車場和結束程序，第二個輸入車牌號碼，第三個

輸入到達停車場時間或離開停車場時間。

七.實驗心得

通過這次實驗,我掌握了棧和隊列的ADT設計，以及如何用它們來解決

問題

附錄代碼：

#include<iostream>

usingnamespacestd;

intjudge();

cIassCar

{

public:

intcarNumber;

。intArriveTime；

intLeaveTime;

);

classStack

(

private：

。intsize；

inttop；

Car*IistArray;

public:

。intmaxsize(){returnsize;};

。Stack(intsz)

°(

。size=sz;

。top=0；

?6listArray=newCar[sz]；

6}

o~Stack()

6(

。delete[]IistArray；

0)

。voidclear()

°{

o。top=0；

0)

。voidpush(constCar&it)

(

oif(top==size);

。。elselistArray[top++]=

}

voidpop(Car&it)

。。if(top0);

a?elseit=1istArray[-top];

。}

。voidtopVaiue(Car&it)const

。(

。。if(top==0)

000■

。elseit=listArray[top_1];

6)

sintIength(){returntop;}

)；

tempIate<classCar>classLink

(

pubIic:

Carelement;

Link*next；

Link(constCar&elemvaI,Link*nextvaI=NULL)

°{

。element=e1emva1;

o。next=nextval;

)

。Link(Link*nextva1=NULL)

°{

。next=nextval;

°}

)；

tempIate<cIassCar>classQueue:publicLink<Car>

(

private:

eintsize；

Link*fron1;

oLink*rear；

public:

。QueueQ{front=NULL;rear=NULL；size=0;}

?Queue。

(

edelete[]front;

edelete口rear；

。}；

voidclear()

。。while(front!=NULL)

。。。rear=front;

。。。front=front->next;

。deleterear；

6t>}

e。rear=NULL;size=0;

。}〃隊列的清空

evoidenqueue(constCar&it)

0(

。。if(rear==NULL)

o。。front=rear=newLink<Car>(it,N(JLL);

。。eIse

0b(

。。。rear->next=newLink<Car>(it,NULL);

。。orear=rear->next；

O0}

size++；

。}〃入隊

voiddequeue(Car&it)

if(size==0)

。it=front->element；

-Link<Ca=front；

。。front=front—>next；

。ode1ete[]ltemp;

。。if(front==NULL)rear=NULL；

。。size-

。}//出隊

intlength0const{returnsize;}

};〃隊列的長度

intmain()

(

。intn;

。cout?n請輸入停車場容量:"；

。n=judgeQ;

。while(n<=0)

(

。。cout<<"輸入有誤,請重新輸入。\n請輸入停車場容量:";

n=judge();

。CarC[100];Stackpark=Stack(n);Stackout=Stack(n);Queue

<Car>line;

。CartopCar；

。while(1)〃停車

(

66charc;//停車or離開

inta;〃汽車車牌號碼

。。intb;〃到達時間or離開時間

。coutvv”請輸入車輛相關信息：”；

。。cin>>c>>a?b；

。。switch(c)

°{

。。caseA1:

06{

oeoif(park.Iength()<n+1)

0000{

。。。park.push(C[a—1]);

°°oooC[a-l].ArriveTime=b;

C[a-1].carNumber=a;

ocout<<"該車停在第停車場第"?park,length。

?"個位置\n"；

000。}

。。。。。elseif(park.lengthO==n+1)

00。{

。。line.enqueue(C[a-1])；〃停車場已滿

。。