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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)停車(chē)場(chǎng)管理問(wèn)題 姓名： 學(xué)號(hào)：1、 問(wèn)題描述設(shè)有一個(gè)可以停放n輛汽車(chē)的狹長(zhǎng)停車(chē)場(chǎng)，它只有一個(gè)大門(mén)可以供車(chē)輛進(jìn)出。車(chē)輛按到達(dá)停車(chē)場(chǎng)時(shí)間的早晚依次從停車(chē)場(chǎng)最里面向大門(mén)口處停放(最先到達(dá)的第一輛車(chē)放在停車(chē)場(chǎng)的最里面)。如果停車(chē)場(chǎng)已放滿(mǎn)n輛車(chē)，則后來(lái)的車(chē)輛只能在停車(chē)場(chǎng)大門(mén)外的便道上等待，一旦停車(chē)場(chǎng)內(nèi)有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)就進(jìn)入停車(chē)場(chǎng)。停車(chē)場(chǎng)內(nèi)如有某輛車(chē)要開(kāi)走，在它之后進(jìn)入停車(chē)場(chǎng)的車(chē)都必須先退出停車(chē)場(chǎng)為它讓路，待其開(kāi)出停車(chē)場(chǎng)后，這些車(chē)輛再依原來(lái)的次序進(jìn)場(chǎng)。每輛車(chē)在離開(kāi)停車(chē)場(chǎng)時(shí)，都應(yīng)根據(jù)它在停車(chē)場(chǎng)內(nèi)停留的時(shí)間長(zhǎng)短交費(fèi)。如果停留在便道上的車(chē)未進(jìn)停車(chē)場(chǎng)就要離去，允許其離去，不收停車(chē)費(fèi)，并且仍然保持在便道上等待的車(chē)輛的次序。編制一程序模擬該停車(chē)場(chǎng)的管理。2、 實(shí)現(xiàn)要求要求程序輸出每輛車(chē)到達(dá)后的停車(chē)位置(停車(chē)場(chǎng)或便道上)，以及某輛車(chē)離開(kāi)停車(chē)場(chǎng)時(shí)應(yīng)交納的費(fèi)用和它在停車(chē)場(chǎng)內(nèi)停留的時(shí)間。3、 實(shí)現(xiàn)提示汽車(chē)的模擬輸入信息格式可以是：(到達(dá)離去，汽車(chē)牌照號(hào)碼，到達(dá)離去的時(shí)刻)。例如，(A，1，5)表示1號(hào)牌照車(chē)在5這個(gè)時(shí)刻到達(dá)，而(D，5，20)表示5號(hào)牌照車(chē)在20這個(gè)時(shí)刻離去。整個(gè)程序可以在輸入信息為(E，0，0)時(shí)結(jié)束。本題可用棧和隊(duì)列來(lái)實(shí)現(xiàn)。4、 需求分析 停車(chē)場(chǎng)采用棧式結(jié)構(gòu)，停車(chē)場(chǎng)外的便道采用隊(duì)列結(jié)構(gòu)（即便道就是等候隊(duì)列）。停車(chē)場(chǎng)的管理流程如下 當(dāng)車(chē)輛要進(jìn)入停車(chē)場(chǎng)時(shí)，檢查停車(chē)場(chǎng)是否已滿(mǎn)，如果未滿(mǎn)則車(chē)輛進(jìn)棧（車(chē)輛進(jìn)入停車(chē)場(chǎng)）；如果停車(chē)場(chǎng)已滿(mǎn)，則車(chē)輛進(jìn)入等候隊(duì)列（車(chē)輛進(jìn)入便道等候）。 當(dāng)車(chē)輛要求出棧時(shí)，該車(chē)到棧頂?shù)哪切┸?chē)輛先彈出棧（在它之后進(jìn)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路），再讓該車(chē)出棧，其他車(chē)輛再按原次序進(jìn)棧（進(jìn)入車(chē)場(chǎng)）。當(dāng)車(chē)輛出棧完畢后，檢查等候隊(duì)列（便道）中是否有車(chē)，有車(chē)則從隊(duì)列頭取出一輛車(chē)壓入棧中。5、 流程圖6、 詳細(xì)設(shè)計(jì) 1.本程序主要包含四個(gè)模塊 1) 主程序模塊 int main() Initialization(); CarNode car; SqStack Park,TempPark; LinkQueue Q; InitStack(Park); InitStack(TempPark); InitQueue(Q); while(scanf(%c%d%d,&car.event,&car.num,&car.time)&(car.event!=e&car.event!=E) getchar(); /除去輸入結(jié)束時(shí)的回車(chē) 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); return 0; 2）分別構(gòu)造空棧和空隊(duì)列棧：Status InitStack(SqStack &S) /構(gòu)造一個(gè)空棧 S.Stacksize=0; S.base=(CarNode*)malloc(MAX)*sizeof(CarNode); if(!S.base) exit(OVERFLOW); printf(存儲(chǔ)空間分配失敗); S.top=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) exit(OVERFLOW); printf(存儲(chǔ)空間分配失敗); Q.front-next=NULL; Q.queuesize=0; return OK; 3）車(chē)輛到達(dá)處理 Status Arrive(SqStack &S,LinkQueue &Q,CarNode &e) /車(chē)輛到達(dá)處理 if(S.top-1)-time=e.time) /時(shí)間處理 if(!Check_Stack(S,e)&!Check_Queue(Q,e) /是否已存在 if(S.top-S.basenum) /車(chē)輛處在棧頂 Pop(S, a); leatime=e.time; leanum=e.num; entertime=a.time; printf(車(chē)輛進(jìn)入車(chē)庫(kù)時(shí)間:%dt現(xiàn)在（離開(kāi)）時(shí)間:%dt停留時(shí)間:%dtn,entertime,leatime,leatime-entertime); else /車(chē)輛處在棧中間 do Pop(S,a); /從棧中依次退出 Push(TempS,a); /依次進(jìn)入臨時(shí)棧 while(S.top-1)-num!=e.num);/直到top指針下一個(gè)位置的num=車(chē)牌號(hào) Pop(S, a); /該車(chē)離開(kāi) leatime=e.time; leanum=e.num; entertime=a.time; printf(車(chē)進(jìn)入停車(chē)場(chǎng)時(shí)間:%dt現(xiàn)在（離開(kāi)）時(shí)間:%dt停留時(shí)間:%dtn,entertime,leatime,leatime-entertime); do /其余車(chē)輛按原來(lái)次序返回停車(chē)場(chǎng) Pop(TempS,a); Push(S,a); while(TempS.top!=TempS.base);/條件與上面不同，此時(shí)是全部回去 cost=(leatime-entertime)*price; if(cost=0) printf(您的車(chē)牌號(hào)為 %d 的車(chē)應(yīng)交納的費(fèi)用是:%dn,leanum,cost); if(Q.front!=Q.rear) /隊(duì)列不空的話從便道進(jìn)停車(chē)場(chǎng) DeQueue(Q,a); if(a.timenext-data.num!=e.num); DeQueue(Q,e); /前面的車(chē)進(jìn)入隊(duì)尾 printf(您的車(chē)牌號(hào)為 %d 的車(chē)輛未進(jìn)入車(chē)庫(kù)從便道直接離開(kāi)，費(fèi)用為0!n,e.num); return true;2主要設(shè)計(jì)程序如下#include#include#include#define MAX 2 /停車(chē)場(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 CarNode char event; int num; int time;CarNode; /車(chē)輛信息結(jié)點(diǎn)typedef struct SqStack CarNode *base; CarNode *top; int Stacksize;SqStack; /棧（停車(chē)場(chǎng)）typedef struct QNode CarNode data; struct QNode *next;QueueNode; /便道結(jié)點(diǎn)typedef struct LinkQueue QueueNode *front; QueueNode *rear; int queuesize;LinkQueue; /隊(duì)列（便道）/=Status InitStack(SqStack &S) /構(gòu)造一個(gè)空棧 S.Stacksize=0; S.base=(CarNode*)malloc(MAX)*sizeof(CarNode); if(!S.base) exit(OVERFLOW); printf(存儲(chǔ)空間分配失敗); S.top=S.base; return OK;/=Status InitQueue(LinkQueue &Q) /構(gòu)造一個(gè)空隊(duì)列（帶頭結(jié)點(diǎn)） Q.front=Q.rear=(QueueNode*)malloc(sizeof(QueueNode); if(!Q.front) exit(OVERFLOW); printf(存儲(chǔ)空間分配失敗); Q.front-next=NULL; Q.queuesize=0; return OK;/=Status GetTop(SqStack S,CarNode &e) /返回棧頂元素 if(S.top=S.base) return ERROR; e=*(S.top-1); return TRUE;/=Status Pop(SqStack &S,CarNode &e) /刪除棧頂元素 if(S.top=S.base) return ERROR; e=*-S.top; return OK;/=Status Push(SqStack &S,CarNode e)/插入元素為新的棧頂元素(在棧不滿(mǎn)的前提下) if(S.top-S.base=MAX) return FALSE; *S.top+=e; return OK;/=Status DeQueue(LinkQueue &Q,CarNode &e) /刪除隊(duì)頭元素(帶頭結(jié)點(diǎn)) if(Q.rear=Q.front) return ERROR; QueueNode *p=Q.front-next; e=p-data; Q.front-next=p-next; 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) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; Q.queuesize+; return OK;/=Status Check_Stack(SqStack &S,CarNode e)/車(chē)輛到達(dá)時(shí)車(chē)庫(kù)內(nèi)是否有同名車(chē) CarNode *Temp=S.base; while(Temp!=(S.top)&(Temp-num!=e.num) Temp+; if(Temp=S.top) return FALSE; else return TRUE;/=Status Check_Queue(LinkQueue &Q,CarNode e)/車(chē)輛到達(dá)時(shí)便道上是否有同名車(chē) QueueNode *Temp=Q.front; while(Temp!=Q.rear) & (Temp-data.num!=e.num) Temp=Temp-next; if(Temp=Q.rear) & (Temp-data.num!=e.num) return FALSE; else return TRUE;/=Status Arrive(SqStack &S,LinkQueue &Q,CarNode &e) /車(chē)輛到達(dá)處理 if(S.top-1)-time=e.time) /時(shí)間處理 if(!Check_Stack(S,e)&!Check_Queue(Q,e) /是否已存在 if(S.top-S.basenum) /車(chē)輛處在棧頂 Pop(S, a); leatime=e.time; leanum=e.num; entertime=a.time; printf(車(chē)輛進(jìn)入車(chē)庫(kù)時(shí)間:%dt現(xiàn)在（離開(kāi)）時(shí)間:%dt停留時(shí)間:%dtn,entertime,leatime,leatime-entertime); else /車(chē)輛處在棧中間 do Pop(S,a); /從棧中依次退出 Push(TempS,a); /依次進(jìn)入臨時(shí)棧 while(S.top-1)-num!=e.num);/直到top指針下一個(gè)位置的num=車(chē)牌號(hào) Pop(S, a); /該車(chē)離開(kāi) leatime=e.time; leanum=e.num; entertime=a.time; printf(車(chē)進(jìn)入停車(chē)場(chǎng)時(shí)間:%dt現(xiàn)在（離開(kāi)）時(shí)間:%dt停留時(shí)間:%dtn,entertime,leatime,leatime-entertime); do /其余車(chē)輛按原來(lái)次序返回停車(chē)場(chǎng) Pop(TempS,a); Push(S,a); while(TempS.top!=TempS.base);/條件與上面不同，此時(shí)是全部回去 cost=(leatime-entertime)*price; if(cost=0) printf(您的車(chē)牌號(hào)為 %d 的車(chē)應(yīng)交納的費(fèi)用是:%dn,leanum,cost); if(Q.front!=Q.rear) /隊(duì)列不空的話從便道進(jìn)停車(chē)場(chǎng) DeQueue(Q,a); if(a.timenext-data.num!=e.num); DeQueue(Q,e); /前面的車(chē)進(jìn)入隊(duì)尾 printf(您的車(chē)牌號(hào)為 %d 的車(chē)輛未進(jìn)入車(chē)庫(kù)從便道直接離開(kāi)，費(fèi)用為0!n,e.num); return true;/=void Initialization() /初始化程序 printf(姓名：楊智偉 學(xué)號(hào)：2012040651n); printf(=n); printf(* 停車(chē)場(chǎng)管理模擬程序 *n); printf(=n); printf(請(qǐng)依次輸入車(chē)輛到達(dá)(A/a)/離去(D/d)/結(jié)束(E/e)信息、車(chē)牌號(hào)以及當(dāng)前時(shí)間：nn);/=int mai