數據結構停車場問題實驗報告.docVIP

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