數(shù)據(jù)結(jié)構(gòu)停車場(chǎng)問(wèn)題實(shí)驗(yàn)報(bào)告（一）.doc

1、數(shù)據(jù)結(jié)構(gòu)停車場(chǎng)問(wèn)題實(shí)驗(yàn)報(bào)告（一）1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)停車場(chǎng)管理問(wèn)題姓名：學(xué)號(hào)：?jiǎn)栴}描述設(shè)有一個(gè)可以停放n輛汽車的狹長(zhǎng)停車場(chǎng)，它只有一個(gè)大門(mén)可以供車輛進(jìn)出。車輛按到達(dá)停車場(chǎng)時(shí)間的早晚依次從停車場(chǎng)最里面向大門(mén)口處停放(最先到達(dá)的第一輛車放在停車場(chǎng)的最里面)。如果停車場(chǎng)已放滿n輛車，則后來(lái)的車輛只能在停車場(chǎng)大門(mén)外的便道上等待，一旦停車場(chǎng)內(nèi)有車開(kāi)走，則排在便道上的第一輛車就進(jìn)入停車場(chǎng)。停車場(chǎng)內(nèi)如有某輛車要開(kāi)走，在它之后進(jìn)入停車場(chǎng)的車都必須先退出停車場(chǎng)為它讓路，待其開(kāi)出停車場(chǎng)后，這些車輛再依原來(lái)的次序進(jìn)場(chǎng)。每輛車在離開(kāi)停車場(chǎng)時(shí)，都應(yīng)根據(jù)它在停車場(chǎng)內(nèi)停留的時(shí)間長(zhǎng)短交費(fèi)。如果停留在便道上的車未進(jìn)停車場(chǎng)就要離去

2、，允許其離去，不收停車費(fèi)，并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場(chǎng)的管理。實(shí)現(xiàn)要求要求程序輸出每輛車到達(dá)后的停車位置(停車場(chǎng)或便道上)，以及某輛車離開(kāi)停車場(chǎng)時(shí)應(yīng)交納的費(fèi)用和它在停車場(chǎng)內(nèi)停留的時(shí)間。實(shí)現(xiàn)提示汽車的模擬輸入信息格式可以是：(到達(dá)離去，汽車牌照號(hào)碼，到達(dá)離去的時(shí)刻)。例如，(A，1，5)表示1號(hào)牌照車在5這個(gè)時(shí)刻到達(dá)，而(D，5，20)表示5號(hào)牌照車在20這個(gè)時(shí)刻離去。整個(gè)程序可以在輸入信息為(E，0，0)時(shí)結(jié)束。本題可用棧和隊(duì)列來(lái)實(shí)現(xiàn)。需求分析停車場(chǎng)采用棧式結(jié)構(gòu)，停車場(chǎng)外的便道采用隊(duì)列結(jié)構(gòu)（即便道就是等候隊(duì)列）。停車場(chǎng)的管理流程如下當(dāng)車輛要進(jìn)入停車場(chǎng)時(shí)，檢查停車

3、場(chǎng)是否已滿，如果未滿則車輛進(jìn)棧（車輛進(jìn)入停車場(chǎng)）；如果停車場(chǎng)已滿，則車輛進(jìn)入等候隊(duì)列（車輛進(jìn)入便道等候）。當(dāng)車輛要求出棧時(shí)，該車到棧頂?shù)哪切┸囕v先彈出棧（在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路），再讓該車出棧，其他車輛再按原次序進(jìn)棧（進(jìn)入車場(chǎng)）。當(dāng)車輛出棧完畢后，檢查等候隊(duì)列（便道）中是否有車，有車則從隊(duì)列頭取出一輛車壓入棧中。流程圖詳細(xì)設(shè)計(jì)1.本程序主要包含四個(gè)模塊1) 主程序模塊int main()Initialization();CarNode car;SqStack Park,TempPark;LinkQueue Q;InitStack(Park);InitStack(TempPar

4、k);InitQueue(Q);while(scanf(“cdd”,car.event,car.num,car.time)(car.event!=#;e#;car.event!=#;E#;)getchar(); /除去輸入結(jié)束時(shí)的回車switch(car.event)case #;A#;:case #;a#;:Arrive(Park,Q,car);break;case #;D#;:case #;d#;:Leave(Park,TempPark,Q,car);break;default: printf(“您的第一個(gè)數(shù)據(jù)輸入有誤!n”);break;printf(“程序結(jié)束，謝謝使用!n”);ret

5、urn 0;2）分別構(gòu)造空棧和空隊(duì)列棧：Status InitStack(SqStack S) /構(gòu)造一個(gè)空棧S.Stacksize=0;S.base=(CarNode_)malloc(MA_)_sizeof(CarNode);if(!S.base)e_it(OVERFLOW);printf(“存儲(chǔ)空間分配失敗”);S.=S.base;return OK;隊(duì)列：Status InitQueue(LinkQueue Q) /構(gòu)造一個(gè)空隊(duì)列（帶頭結(jié)點(diǎn)）Q.front=Q.rear=(QueueNode_)malloc(sizeof(QueueNode);if(!Q.front)? e_it(OVE

6、RFLOW);? printf(“存儲(chǔ)空間分配失敗”);Q.front->ne_t=NULL;Q.queuesize=0;return OK;3）車輛到達(dá)處理Status Arrive(SqStack S,LinkQueue Q,CarNode e)? /車輛到達(dá)處理if(S.-1)->timenum) /車輛處在棧頂Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf(“車輛進(jìn)入車庫(kù)時(shí)間:dt現(xiàn)在（離開(kāi)）時(shí)間:dt停留時(shí)間:dtn”,entertime,leatime,leatime-entertime);el

7、se? /車輛處在棧中間doPop(S,a); /從棧中依次退出Push(TempS,a);? /依次進(jìn)入臨時(shí)棧while(S.-1)->num!=e.num);/直到指針下一個(gè)位置的num=車牌號(hào)Pop(S, a); /該車離開(kāi)leatime=e.time;leanum=e.num;entertime=a.time;printf(“車進(jìn)入停車場(chǎng)時(shí)間:dt現(xiàn)在（離開(kāi)）時(shí)間:dt停留時(shí)間:dtn”,entertime,leatime,leatime-entertime);do /其余車輛按原來(lái)次序返回停車場(chǎng)Pop(TempS,a);Push(S,a);while(TempS.!=TempS

8、.base);/條件與上面不同，此時(shí)是全部回去cost=(leatime-entertime)_price;if(cost>=0)printf(“您的車牌號(hào)為 d 的車應(yīng)交納的費(fèi)用是:dn”,leanum,cost);if(Q.front!=Q.rear) /隊(duì)列不空的話從便道進(jìn)停車場(chǎng)DeQueue(Q,a);if(a.timene_t->data.num!=e.num);DeQueue(Q,e);? /前面的車進(jìn)入隊(duì)尾printf(“您的車牌號(hào)為 d 的車輛未進(jìn)入車庫(kù)從便道直接離開(kāi)，費(fèi)用為0!n”,e.num);return true;2主要設(shè)計(jì)程序如下#include#incl

9、ude#include#define MA_ 2 /停車場(chǎng)容量#define price 2 /單價(jià)#define OK 1#define FALSE 0#define TRUE 1#define ERROR -1#define OVERFLOW -2typedef int Status;/=typedef struct CarNodechar event;int num;int time;CarNode; /車輛信息結(jié)點(diǎn)typedef struct SqStackCarNode _base;CarNode _;int Stacksize;SqStack; /棧（停車場(chǎng)）typedef str

10、uct QNodeCarNode data;struct QNode _ne_t;QueueNode; /便道結(jié)點(diǎn)typedef struct LinkQueueQueueNode _front;QueueNode _rear;int queuesize;LinkQueue; /隊(duì)列（便道）/=Status InitStack(SqStack S) /構(gòu)造一個(gè)空棧S.Stacksize=0;S.base=(CarNode_)malloc(MA_)_sizeof(CarNode);if(!S.base)e_it(OVERFLOW);printf(“存儲(chǔ)空間分配失敗”);S.=S.base;ret

11、urn OK;/=Status InitQueue(LinkQueue Q) /構(gòu)造一個(gè)空隊(duì)列（帶頭結(jié)點(diǎn)）Q.front=Q.rear=(QueueNode_)malloc(sizeof(QueueNode);if(!Q.front)e_it(OVERFLOW);printf(“存儲(chǔ)空間分配失敗”);Q.front->ne_t=NULL;Q.queuesize=0;return OK;/=Status Get(SqStack S,CarNode e)? /返回棧頂元素if(S.=S.base)return ERROR;e=_(S.-1);return TRUE;/=Status Pop(

12、SqStack S,CarNode e) /刪除棧頂元素if(S.=S.base)return ERROR;e=_-S.;return OK;/=Status Push(SqStack S,CarNode e)/插入元素為新的棧頂元素(在棧不滿的前提下)if(S.-S.base>=MA_)return FALSE;_S.+=e;return OK;/=Status DeQueue(LinkQueue Q,CarNode e) /刪除隊(duì)頭元素(帶頭結(jié)點(diǎn))if(Q.rear=Q.front)return ERROR;QueueNode _p=Q.front->ne_t;e=p->

13、data;Q.front->ne_t=p->ne_t;if(p=Q.rear)Q.rear=Q.front;free(p);Q.queuesize-;return OK;/=Status EnQueue(LinkQueue Q,CarNode e) /插入新的隊(duì)尾元素QueueNode _p=(QueueNode_)malloc(sizeof(QueueNode);if(!p)e_it(OVERFLOW);p->data=e;p->ne_t=NULL;Q.rear->ne_t=p;Q.rear=p;Q.queuesize+;return OK;/=Status C

14、heck_Stack(SqStack S,CarNode e)/車輛到達(dá)時(shí)車庫(kù)內(nèi)是否有同名車CarNode _Temp=S.base;while(Temp!=(S.)(Temp->num!=e.num)Temp+;if(Temp=S.)return FALSE;elsereturn TRUE;/=Status Check_Queue(LinkQueue Q,CarNode e)/車輛到達(dá)時(shí)便道上是否有同名車QueueNode? _Temp=Q.front;while(Temp!=Q.rear) (Temp->data.num!=e.num)Temp=Temp->ne_t;if

15、(Temp=Q.rear) (Temp->data.num!=e.num)return FALSE;elsereturn TRUE;/=Status Arrive(SqStack S,LinkQueue Q,CarNode e)? /車輛到達(dá)處理if(S.-1)->timenum) /車輛處在棧頂Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf(“車輛進(jìn)入車庫(kù)時(shí)間:dt現(xiàn)在（離開(kāi)）時(shí)間:dt停留時(shí)間:dtn”,entertime,leatime,leatime-entertime);else? /車輛處在棧中

16、間doPop(S,a); /從棧中依次退出Push(TempS,a);? /依次進(jìn)入臨時(shí)棧while(S.-1)->num!=e.num);/直到指針下一個(gè)位置的num=車牌號(hào)Pop(S, a); /該車離開(kāi)leatime=e.time;leanum=e.num;entertime=a.time;printf(“車進(jìn)入停車場(chǎng)時(shí)間:dt現(xiàn)在（離開(kāi)）時(shí)間:dt停留時(shí)間:dtn”,entertime,leatime,leatime-entertime);do /其余車輛按原來(lái)次序返回停車場(chǎng)Pop(TempS,a);Push(S,a);while(TempS.!=TempS.base);/條件與

17、上面不同，此時(shí)是全部回去cost=(leatime-entertime)_price;if(cost>=0)printf(“您的車牌號(hào)為 d 的車應(yīng)交納的費(fèi)用是:dn”,leanum,cost);if(Q.front!=Q.rear) /隊(duì)列不空的話從便道進(jìn)停車場(chǎng)DeQueue(Q,a);if(a.timene_t->data.num!=e.num);DeQueue(Q,e);? /前面的車進(jìn)入隊(duì)尾printf(“您的車牌號(hào)為 d 的車輛未進(jìn)入車庫(kù)從便道直接離開(kāi)，費(fèi)用為0!n”,e.num);return true;/=void Initialization()? /初始化程序pr

18、intf(“姓名：楊智偉 學(xué)號(hào)：20_40651n”);printf(“=n”);printf(“_? 停車場(chǎng)管理模擬程序 _n”);printf(“=n”);printf(“請(qǐng)依次輸入車輛到達(dá)(A/a)/離去(D/d)/結(jié)束(E/e)信息、車牌號(hào)以及當(dāng)前時(shí)間：nn”);/=int main()Initialization();CarNode car;SqStack Park,TempPark;LinkQueue Q;InitStack(Park);InitStack(TempPark);InitQueue(Q);while(scanf(“cdd”,car.event,car.num,car.time)(car.event!=#;e#;car.event!=#;E#;)getchar(); /除去輸入結(jié)束時(shí)的回車switch(car.event)case #;A#;:case #;a#;:Arrive(Park,Q,car);break;case #;D#;:case #;d#;:Leave(Park,