－PAGE3－實(shí)驗(yàn)2停車場(chǎng)管理需求分析輸入的形式和輸入值的范圍：第一次輸入一個(gè)正整數(shù)，代表停車場(chǎng)容量大小。以后每一次輸入三個(gè)值，分別為字符、整形、整形，中間用逗號(hào)隔開。分別代表車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。其中字符必須為“A,D,E”三者之一。輸入格式為：“（‘A’，1，5）”、“（‘D’，1，15）”。.不對(duì)非法輸入做處理，即假設(shè)輸入都是合法的。輸出的形式：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。程序所能達(dá)到的功能：對(duì)于用戶輸入的車輛信息，可以輸出該車的停車位置或者停車時(shí)間及應(yīng)繳費(fèi)用。測(cè)試數(shù)據(jù)：請(qǐng)輸入停車場(chǎng)容量2A,1,1車停在停車場(chǎng)第1個(gè)位置A,2,2車停在停車場(chǎng)第2個(gè)位置A,3,3車停在便道第1個(gè)位置D,1,4停車時(shí)間：3繳納費(fèi)用：￥6D,2,5停車時(shí)間：3繳納費(fèi)用：￥6A,5,5車停在停車場(chǎng)第2個(gè)位置E,0,0概要設(shè)計(jì)抽象數(shù)據(jù)類型的定義：由于每一輛車包含多種信息。所以定義一個(gè)Data類來(lái)存儲(chǔ)汽車的“來(lái)去、車牌號(hào)，時(shí)間”信息。classData//每輛車的信息類{public:intlicense;//車牌號(hào)碼intarrive;//到達(dá)時(shí)間};用棧模擬停車場(chǎng)，其ADT如下：ADTstack數(shù)據(jù)對(duì)象：Data類型數(shù)據(jù)關(guān)系：線性關(guān)系基本操作： boolpush(constData&item)//入棧 boolpop(Data&item)//出棧 booltopValue(Data&it)//頂層元素值intlength()const{returntop;}//棧實(shí)際長(zhǎng)度用隊(duì)列模擬便道，其ADT如下：ADTquene數(shù)據(jù)對(duì)象：Data類型數(shù)據(jù)關(guān)系：線性關(guān)系基本操作：boolenquene(constData&it)//入隊(duì)booldequene(Data&it)//出隊(duì)virtualintlength()const{return((rear+size)-front+1)%size;}//隊(duì)列的實(shí)際長(zhǎng)度算法的基本思想：1、對(duì)于指定大小的停車場(chǎng)，其只有一端出口，先進(jìn)后出，用棧存儲(chǔ)；超過停車場(chǎng)容量的車停在便道上，先進(jìn)先出，用隊(duì)列存儲(chǔ)；當(dāng)汽車離開時(shí)，在它之后進(jìn)入的車輛必須先退出再按原次序進(jìn)入車場(chǎng)，需要一個(gè)臨時(shí)棧存儲(chǔ)。2、每進(jìn)入一輛車，進(jìn)行入棧操作，即停車場(chǎng)；如果入棧不成功則入隊(duì)列，即便道。每離開一輛車：要對(duì)在該車之后進(jìn)入的車輛進(jìn)行弾棧操作，出棧的元素依次存入另一個(gè)臨時(shí)堆棧，即為離開車輛開道。在對(duì)該車進(jìn)行出棧操作后，再將臨時(shí)堆棧的元素彈回原棧。通過離開時(shí)間與該車儲(chǔ)存在Data中的到達(dá)時(shí)間差獲得停車時(shí)間以及費(fèi)用（費(fèi)用的計(jì)算根據(jù)2元/小時(shí)）。此時(shí)如果隊(duì)列不為空，表明便道上有車待入，修改此待入車輛的到達(dá)時(shí)間為離開車的離開時(shí)間，并進(jìn)行入棧操作。當(dāng)輸入不為‘E’時(shí)，循環(huán)進(jìn)行上述操作。詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型：分別用字符型、整形、整形存儲(chǔ)用戶的輸入，并將相應(yīng)數(shù)據(jù)存入Data類。classData//每輛車的信息類{public:intlicense;//車牌號(hào)碼intarrive;//到達(dá)時(shí)間};用順序棧表實(shí)現(xiàn)棧：classStack//堆棧，模擬停車場(chǎng)以及有車輛離開時(shí)的臨時(shí)停車處{private:intsize;inttop;Data*listArray;public:Stack(intsz){size=sz;top=0;listArray=newData[sz];}~Stack(){delete[]listArray;}boolpush(constData&item)//入棧{if(top==size)returnfalse;else{listArray[top++]=item;returntrue;}}boolpop(Data&item)//出棧{if(top==0)returnfalse;else{item=listArray[--top];returntrue;}}booltopValue(Data&it)//頂層元素值{if(top==0)returnfalse;it=listArray[top-1];returntrue;}intlength()const{returntop;}//棧實(shí)際長(zhǎng)度};用循環(huán)隊(duì)列實(shí)現(xiàn)隊(duì)列：classQuene//隊(duì)列，模擬便道{private:intsize;intfront;intrear;Data*listArray;public:Quene(intsz){size=sz+1;rear=0;front=1;listArray=newData[size];}~Quene(){delete[]listArray;}boolenquene(constData&it)//入隊(duì){if((rear+2)%size==front)returnfalse;rear=(rear+1)%size;listArray[rear]=it;returntrue;}booldequene(Data&it)//出隊(duì){if(length()==0)returnfalse;it=listArray[front];front=(front+1)%size;returntrue;}virtualintlength()const{return((rear+size)-front+1)%size;}//隊(duì)列的實(shí)際長(zhǎng)度};實(shí)現(xiàn)程序的具體步驟：while(c!='E')//不退出程序{Datatop;if(c=='A')//進(jìn)入停車場(chǎng){if(park.push(d))//入棧成功{//輸出提示語(yǔ)句}Else//入棧失敗{line.enquene(d);//輸出提示語(yǔ)句}}elseif(c=='D')//離開停車場(chǎng){park.topValue(top);while(top.license!=d.license)//為車開道{park.pop(top);temp.push(top);park.topValue(top);}park.pop(top);//輸出提示語(yǔ)句while(temp.length()!=0)//回到車位{temp.pop(top);park.push(top);}if(line.length()!=0)//由便道到車庫(kù){line.dequene(top);top.arrive=d.arrive;//進(jìn)入的時(shí)間剛好是那輛車出去的時(shí)間park.push(top);}}算法的時(shí)空分析和改進(jìn)設(shè)想：對(duì)于入棧處理，時(shí)間復(fù)雜度為Θ(1)，對(duì)于出棧處理，最壞情況下的時(shí)間復(fù)雜度是Θ(n)的。輸入N次，出棧處理最多只有N/2次，所以時(shí)間復(fù)雜度最壞情況是Θ(n2)的，最好情況是Θ(n)的。停車場(chǎng)仍有空余，入棧成功stack.push()畫出函數(shù)的調(diào)用關(guān)系圖：停車場(chǎng)仍有空余，入棧成功stack.push()車輛進(jìn)入A車輛進(jìn)入A停車場(chǎng)已滿，入棧失敗，入隊(duì)列l(wèi)ine.enquene()停車場(chǎng)已滿，入棧失敗，入隊(duì)列l(wèi)ine.enquene()后來(lái)車輛進(jìn)入臨時(shí)棧temp.push(stack.pop())主程序后來(lái)車輛進(jìn)入臨時(shí)棧temp.push(stack.pop())車輛離開D該車離開stack.pop()車輛離開D該車離開stack.pop()讓道車回停車場(chǎng)，臨時(shí)棧弾棧stack.push(temp.pop())讓道車回停車場(chǎng)，臨時(shí)棧弾棧stack.push(temp.pop())便道車入棧stack.push(line.dequene())便道車入棧stack.push(line.dequene())輸入和輸出的格式：輸入：A,1,1A,2,2A,3,3D,1,4輸出：車停在停車場(chǎng)第1個(gè)位置車停在停車場(chǎng)第2個(gè)位置車停在便道第1個(gè)位置停車時(shí)間：3繳納費(fèi)用：￥6測(cè)試結(jié)果根據(jù)實(shí)際演算與輸出結(jié)果比對(duì)，證明結(jié)果正確無(wú)誤，即測(cè)試結(jié)果正確。用戶使用說(shuō)明運(yùn)行程序時(shí)1）顯示提示“請(qǐng)輸入停車場(chǎng)容量”，此時(shí)輸入的整形代表停車場(chǎng)最多可以容納的