停車場管理實驗報告.doc

.HUNAN UNIVERSITY課程實驗報告題目：停車場管理學(xué)生姓名： 學(xué)生學(xué)號：專業(yè)班級：指導(dǎo)老師： 完成日期： 一 需求分析1. 輸入形式 第一次輸入一個正整數(shù)，代表停車場容量大小。然后輸入三個值，分別為字符、正整數(shù)、正整數(shù)，中間用空格隔開，分別代表車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。其中字符必須為“A,D,E”三者之一。 輸入格式為：“A 1 5”、“D 1 15”和“E 0 0“。 當(dāng)用戶輸入的字符不是ADE或者輸入的不是正整數(shù)時，提示用戶輸入錯誤并重新輸入2. 輸出形式 若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。 （注：本程序中默認(rèn)停車一小時收費10元）3. 程序功能本程序可通過用戶輸入的車輛信息，輸出該車的停車位置或者停車時間及應(yīng)繳費用4. 測試數(shù)據(jù)請輸入停車場容量：5A 1 1 車停在停車場第 1 個位置A 2 2 車停在停車場第 2 個位置 A 6 6 車停在停車場第 3 個位置D 1 4 停車時間：3 繳納費用：￥30D 2 6 停車時間：3 繳納費用：￥30F C 19.5 輸入有誤，請重新輸入E 0 0 二 概要設(shè)計1. 抽象數(shù)據(jù)類型將每輛車模擬成一個對象，每個對象具有車牌號時間等屬性，所以定義一個Car類存儲這些信息class Carpublic: int CarNumber;/車牌號碼 int ArriveTime;/到達(dá)時間 int LeaveTime;/離開時間使用棧模擬停車場，其ADT設(shè)計：ADT stack 數(shù)據(jù)對象：Car類 數(shù)據(jù)關(guān)系：線性關(guān)系 基本操作： void clear();/棧的初始化 bool push(const Car& item);/棧的插入操作 bool pop(Car& it);/棧的刪除操作 bool topValue(Car& it)/棧的頂層元素 int length() constreturn size;/棧的實際長度使用隊列模擬場外通道，其ADT設(shè)計如下： ADT Queue 數(shù)據(jù)對象：Car類 數(shù)據(jù)關(guān)系：線性關(guān)系 基本操作： void clear();/隊列的初始化 bool enqueue(const Car& it);/入隊 bool dequeue(Car& it);/出隊 int length() constreturn size;/隊列的長度 2.算法基本思想 在該程序中，對停車場和場外通中每輛車停車的編號而言，他們有唯一的第一個元素和最后一個元素，而且除第一個元素以外的每個元素都有唯一的后繼，除最后一個元素以外的每個元素都有唯一的前驅(qū)。因此這些元素具有線性關(guān)系。而且，對于停車場里面的汽車，他們邏輯次序是“先進(jìn)后出，后進(jìn)先出“的，且只在表頭作插入和刪除，所以可以使用棧來模擬停車場。而在場外通道中的汽車，他們是”先進(jìn)先出”的，在一端插入另一端刪除操作，所以可以用隊列來模擬場外通道。當(dāng)汽車離開時，在它之后進(jìn)入的車輛必須先退出再按原次序進(jìn)入停車場，所以需要定義另外一個臨時棧存儲這些元素。(本算法按用戶輸入的順序進(jìn)行車輛的停放，不是按車牌號碼依次停放) （1）當(dāng)有汽車需要進(jìn)停車場停車時，進(jìn)行入棧操作，若停車場已滿，即棧已滿，則將車停在場外通道里，進(jìn)行入隊操作，并記下此時的時間ArriveTime； （2）當(dāng)有汽車需要離開停車場時，對該車對應(yīng)的元素進(jìn)行出棧操作，并將后面進(jìn)來的車輛所對應(yīng)的元素進(jìn)行出棧操作，將這些元素（除了需要離開的車對應(yīng)的元素）存入另外一個棧，即為需要離開停車場的車讓道，并記下此時的時間LeaveTime； （3）在需要離開停車場的車成功離開停車場時，將存儲在臨時棧的那些元素按照原來的順序依次插入原來的棧； （4） 如果隊列不為空（即停車場場外通道上有車，這些車需要進(jìn)入停車場停車），進(jìn)行入棧操作,即進(jìn)行（1）操作；（5）通過LeaveTime 與ArriveTime的差計算停車時間和停車費用（本程序默認(rèn)停車每小時10元）；3.程序基本流程 程序由個基本模塊組成： 輸入模塊：輸入停車場的容量和車輛的相關(guān)信息； 停車模塊：根據(jù)車的信息，將該車對應(yīng)的元素進(jìn)行入棧操作； 離開模塊：根據(jù)車的信息，將該車對應(yīng)的元素進(jìn)行出棧操作，并將后面的元素存入一個臨時棧中； 輸出模塊：輸出該車停車位置或停車費用；三 詳細(xì)設(shè)計1. 物理數(shù)據(jù)類型 停車場容量為正整數(shù)，使用整型數(shù)據(jù)存儲n； 對于剩下的輸入使用字符型、整型、整型存儲，并將相應(yīng)數(shù)據(jù)存入Car類class Carpublic: int CarNumber;/車牌號碼 int ArriveTime;/到達(dá)時間 int LeaveTime;/離開時間定義一個Link類用來存儲元素值element及下一個存儲表中下一個節(jié)點指針的next域，其ADT設(shè)計如下： template class Link public: Car element; Link *next; Link(const Car & elemval, Link* nextval = NULL) element = elemval; next = nextval; Link(Link *nextval = NULL) next = nextval; ;由于停車場容量一定，即?？臻g大小不變，所以可以選用順序表實現(xiàn)棧class AStck:public Stack/ private: int size;/棧的長度 int top;/棧頂元素Car *listArray;/ 順序表保存棧元素 public: AStack(int sz)size=sz;top=0;listArray=new Carsz; /構(gòu)造函數(shù) AStack()delete listArray; /析構(gòu)函數(shù)void clear()top=0;/棧的清空 bool push(const Car&item) if(top=size) return false; elselistArraytop+=item; return true; /棧的插入 bool pop(Car& item) if(top=0) return false; elseitem=listArray-top;return true; /棧的刪除 bool topValue(Car & it) const if(top=0) return false; else it=listArraytop-1; return true; /獲取棧頂元素 int length()const return top; /棧的長度 ;由于該隊列中元素添加操作和刪除操作比較多，所以使用鏈?zhǔn)疥犃袑崿F(xiàn)隊列：template class Queue :public Link private:int size;Link* front;Link* rear; public: LQueue(int sz)front=NULL; rear=NULL;size=0 Lqueue()deletefront; deleterear; void clear() while(front!=NULL) rear=front; front=front-next; delete rear; rear=NULL;size=0; /隊列的清空 bool enqueue(const Car& it) if(rear=NULL) front=rear=new Link(it NULL); else rear-next=new Link(it ,NULL); rear=rear-next; size+; return true;/入隊bool dequeue(Car& it) if(size=0) return false; it=front-element;Link* ltemp=front;front=front-nextdelete ltemp;if(front=NULL) rear=NULL;siz-;return true;/出隊int length() const return size; /隊列的長度 2. 算法具體步驟(park為停車場對應(yīng)的棧，out指臨時棧，line指隊列)char c; input(c);/輸入汽車停車或者離開或者結(jié)束；input(num);/輸入汽車編號input(time);/輸入汽車進(jìn)入或離開時間Car C100;/Car的對象數(shù)組while(1) /停車 switch(c)case(A)/進(jìn)入停車場 if(park is FULL) /停車場已滿 enqueue(Cnum-1);output(line.length()/輸出停車位置else park.push(Ca - 1);Ca - 1.ArriveTime = b;Ca - 1.carNumber = a;output（park.length()）/輸出停車位置 break; case(D)/離開 Ca - 1.LeaveTime = b; Ca - 1.carNumber = a; /進(jìn)來與離開時間 for (int i = 0; i a - 1; i+)/為要離開的車開道 park.pop(Ci);/ 先刪除前面的元素 out.push(Ci);/將前面的元素存至臨時棧中 park.topValue(Ci);/ while(out.length()!=0)/將車復(fù)原 for (int i = 0; i a - 1; i+) out.pop(Ci); park.push(Ci); if(line.length()!=0)/將在通道內(nèi)的車停進(jìn)停車場 for (int j = a; j a + line.length() - 1; j+)line.dequeue(Cj);park.push(Cj);output（Ca - 1.LeaveTime - Ca - 1.ArriveTime）； /輸出停留時間 output（10*（Ca - 1.LeaveTime - Ca - 1.ArriveTime）； /輸出停車費用break;case E:return 0;/輸入E時結(jié)束 3. 算法時空分析在該程序中，棧的插入的時間復(fù)雜度為（1），而對棧中元素進(jìn)行刪除時，需要對該元素后面的所有元素都進(jìn)行刪除，并將他們存入另外一個臨時棧中，到該元素順利刪除完畢時又重新存入原棧中，所以棧的刪除的時間復(fù)雜度為（n2）；4.輸入輸出格式（停車費用每小時10元）輸入：5A 1 1 A 6 6 D 1 4 E 0 0 輸出：車停在停車場第 1個位置車停在場外通道第 2 個位置停車時間：3 繳納費用：￥30四 調(diào)試分析在使用類模板時，第一次沒有使用模板參數(shù)列表，導(dǎo)致程序運行出錯，后來將Car改成class Car后糾正了這個錯誤五 測試結(jié)果程序測試時界面截圖如下：六 用戶使用說明1. 本程序用來處理停車場的問題；2. 運行程序后，需要要求進(jìn)行輸入，如若輸入錯誤，系統(tǒng)提示輸入錯誤請重新輸入，第一次輸入停車場容量，接下來請輸入車輛相關(guān)信息；3. 車輛相關(guān)信息中用空格隔開，第一個輸入A或D或E，分別表示停車，車離開停車場和結(jié)束程序，第二個輸入車牌號碼，第三個輸入到達(dá)停車場時間或離開停車場時間。七 實驗心得通過這次實驗，我掌握了棧和隊列的ADT設(shè)計，以及如何用它們來解決問題附錄代碼：#include using namespace std; int judge(); class Car public: int carNumber; int ArriveTime; int LeaveTime; ; class Stack private: int size; int top; Car*listArray; public: int maxsize() return size; ; Stack(int sz) size = sz; top = 0; listArray = new Carsz; Stack() delete listArray; void clear() top = 0; void push(const Car&it) if (top = size) ; else listArraytop+ = it; void pop(Car&it) if (top = 0); else it=listArray-top; void topValue(Car&it)const if (top = 0) ; else it=listArraytop - 1; int length() return top; ; template class Link public: Car element; Link *next; Link(const Car & elemval, Link* nextval = NULL) element = elemval; next = nextval; Link(Link *nextval = NULL) next = nextval; ; template class Queue :public Link private: int size; Link* front; Link* rear; public: Queue() front = NULL; rear = NULL; size = 0; Queue() deletefront; deleterear; ; void clear() while (front != NULL) rear = front; front = front-next; delete rear; rear = NULL; size = 0; /隊列的清空 void enqueue(const Car& it) if (rear =NULL) front = rear =new Link(it,NULL) ; else rear-next = new Link(it, NULL); rear = rear-next; size+; /入隊 void dequeue(Car& it) if (size = 0) ; it = front-element; Link* ltemp = front; front = front-next; delete ltemp; if (front = NULL) rear = NULL; size-; /出隊 int length() const return size; ;/隊列的長度 int main() int n; cout 請輸入停車場容量：; n=judge(); while (n = 0) cout 輸入有誤，請重新輸入。n請輸入停車場容量：; n = judge(); Car C100; Stack park = Stack(n); Stack out = Stack(n); Queue line; Car topCar; while (1) /停車 char c;/停車or離開 int a;/汽車車牌號碼 int b;/到達(dá)時間or離開時間 cout cab; switch (c) case A: if (park.length()n + 1) park.push(Ca - 1); Ca - 1.ArriveTime = b; Ca - 1.carNumber = a; cout 該車停在第停車場第 park.length() 個位置n; else