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

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

2、允許其離去 ，不收停車費(fèi) ，并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場(chǎng)的管理。二、實(shí)現(xiàn)要求要求程序輸出每輛車到達(dá)后的停車位置 (停車場(chǎng)或便道上 )，以及某輛車離開停車場(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ì)列來實(shí)現(xiàn) 。四、需求分析停車場(chǎng)采用棧式結(jié)構(gòu)，停車場(chǎng)外的便道采用隊(duì)列結(jié)構(gòu)（即便

3、道就是等候隊(duì)列）。停車場(chǎng)的管理流程如下 當(dāng)車輛要進(jìn)入停車場(chǎng)時(shí) ，檢查停車場(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ì)列頭取出一輛車壓入棧中 。.專業(yè) .專注.五、流程圖.專業(yè) .專注.六、詳細(xì)設(shè)計(jì)1. 本程序主要包含四個(gè)模塊1) 主程序模塊int main()Initialization();CarNode

4、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í)的回車switch(car.event)case 'A':case 'a':A

5、rrive(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è)空棧.專業(yè) .專注.S.Stacksize=0;S.base=(CarNode*)malloc(MAX)*sizeof(Car

6、Node);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）車輛到達(dá)處

7、理Status Arrive(SqStack &S,LinkQueue &Q,CarNode &e)/ 車輛到達(dá)處理if(S.top-1)->time<=e.time)/ 時(shí)間處理if(!Check_Stack(S,e)&&!Check_Queue(Q,e)/ 是否已存在if(S.top-S.base<MAX)Push(S,e);printf(" 成功進(jìn)入停車場(chǎng),在 %d 號(hào)車庫 !n",S.top-S.base);return OK;elseEnQueue(Q,e);.專業(yè) .專注.printf(" 停車

8、場(chǎng)已滿 ，車輛進(jìn)入便道 ,在%d 號(hào)車位 !n",Q.queuesize);elseprintf(" 該牌照的車已存在，輸入有誤 ，請(qǐng)重新輸入 n");return OK;elseprintf(" 時(shí)間輸入有誤 ，請(qǐng)重新輸入 !n");return FALSE;4）車輛離開處理Status Leave(SqStack &S,SqStack &TempS,LinkQueue &Q,CarNode &e)/ 車輛離開處理CarNode a;int leatime,leanum;int entertime;/ 進(jìn)入停車

9、場(chǎng)時(shí)間int cost;if(!(Check_Stack(S,e) | Check_Queue(Q,e)printf(" 數(shù)據(jù)輸入錯(cuò)誤 ，本停車場(chǎng)內(nèi)無所查詢車輛，請(qǐng)重新輸入 ！ n");return true;elseif(Check_Stack(S,e)/ 若需要離開的車輛在停車場(chǎng)if(e.num=(S.top-1)->num)/ 車輛處在棧頂.專業(yè) .專注.Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf(" 車輛進(jìn)入車庫時(shí)間:%dt現(xiàn)在（離開）時(shí)間 :%dt停留時(shí)間:%dtn&q

10、uot;,entertime,leatime,leatime-entertime);else/ 車輛處在棧中間doPop(S,a);/ 從棧中依次退出Push(TempS,a);/ 依次進(jìn)入臨時(shí)棧while(S.top-1)->num!=e.num);/直到 top 指針下一個(gè)位置的num= 車牌號(hào)Pop(S, a);/ 該車離開leatime=e.time;leanum=e.num;entertime=a.time;printf(" 車進(jìn)入停車場(chǎng)時(shí)間:%dt現(xiàn)在（離開）時(shí)間 :%dt停留時(shí)間:%dtn",entertime,leatime,leatime-enter

11、time);do / 其余車輛按原來次序返回停車場(chǎng)Pop(TempS,a);Push(S,a);while(TempS.top!=TempS.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.time<leatime)/ 便道車輛進(jìn)車庫時(shí)間應(yīng)該比車庫車輛離開時(shí)間晚.專業(yè) .專注.enterti

12、me=leatime;a.time=leatime;Push(S,a);/ 該車進(jìn)入停車場(chǎng)printf(" 車牌號(hào)為 %d 的車輛從便道上進(jìn)入 %d 號(hào)車庫 !從現(xiàn)在開始計(jì)時(shí) ，現(xiàn)在時(shí)間為 ： %dn",a.num,S.top-S.base,a.time);else if(Check_Queue(Q,e)/ 從便道直接離開doDeQueue(Q,a);EnQueue(Q,a);while(Q.front->next->data.num!=e.num);DeQueue(Q,e);/ 前面的車進(jìn)入隊(duì)尾printf(" 您的車牌號(hào)為%d 的車輛未進(jìn)入車庫從便

13、道直接離開，費(fèi)用為0!n",e.num);return true;2主要設(shè)計(jì)程序如下#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX 2/ 停車場(chǎng)容量#define price 2/ 單價(jià)#define OK 1#define FALSE 0#define TRUE 1#define ERROR -1#define OVERFLOW -2.專業(yè) .專注.typedef int Status;/=typedef struct CarNodechar event;int n

14、um;int time;CarNode;/ 車輛信息結(jié)點(diǎn)typedef struct SqStackCarNode *base;CarNode *top;int Stacksize;SqStack;/ 棧（停車場(chǎng) ）typedef struct QNodeCarNode data;struct QNode *next;QueueNode;/ 便道結(jié)點(diǎn)typedef struct LinkQueueQueueNode *front;QueueNode *rear;int queuesize;LinkQueue;/ 隊(duì)列（便道）/=Status InitStack(SqStack &S)/

15、 構(gòu)造一個(gè)空棧S.Stacksize=0;S.base=(CarNode*)malloc(MAX)*sizeof(CarNode);.專業(yè) .專注.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ǔ)

16、空間分配失敗");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).專業(yè) .專注.return ERROR;e=*-S.top;return OK;/=Status Push(SqStack &S,

17、CarNode e)/插入元素為新的棧頂元素(在棧不滿的前提下)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.queuesi

18、ze-;return OK;/=Status EnQueue(LinkQueue &Q,CarNode e)/ 插入新的隊(duì)尾元素QueueNode *p=(QueueNode*)malloc(sizeof(QueueNode);if(!p).專業(yè) .專注.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)/車輛到達(dá)時(shí)車庫內(nèi)是否有同名車CarNode *Temp

19、=S.base;while(Temp!=(S.top)&&(Temp->num!=e.num)Temp+;if(Temp=S.top)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->next;if(Temp=Q.rear) && (Tem

20、p->data.num!=e.num)return FALSE;elsereturn TRUE;/=.專業(yè) .專注.=Status Arrive(SqStack &S,LinkQueue &Q,CarNode &e)/ 車輛到達(dá)處理if(S.top-1)->time<=e.time)/ 時(shí)間處理if(!Check_Stack(S,e)&&!Check_Queue(Q,e)/ 是否已存在if(S.top-S.base<MAX)Push(S,e);printf(" 成功進(jìn)入停車場(chǎng),在 %d 號(hào)車庫 !n",S.to

21、p-S.base);return OK;elseEnQueue(Q,e);printf(" 停車場(chǎng)已滿 ，車輛進(jìn)入便道 ,在%d 號(hào)車位 !n",Q.queuesize);elseprintf(" 該牌照的車已存在，輸入有誤 ，請(qǐng)重新輸入 n");return OK;elseprintf(" 時(shí)間輸入有誤 ，請(qǐng)重新輸入 !n");return FALSE;/=Status Leave(SqStack &S,SqStack &TempS,LinkQueue &Q,CarNode &e)/ 車輛離開處理Ca

22、rNode a;int leatime,leanum;int entertime;/進(jìn)入停車場(chǎng)時(shí)間.專業(yè) .專注.int cost;if(!(Check_Stack(S,e) | Check_Queue(Q,e)printf(" 數(shù)據(jù)輸入錯(cuò)誤 ，本停車場(chǎng)內(nèi)無所查詢車輛，請(qǐng)重新輸入 ！ n");return true;elseif(Check_Stack(S,e)/ 若需要離開的車輛在停車場(chǎng)if(e.num=(S.top-1)->num)/車輛處在棧頂Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;print

23、f(" 車輛進(jìn)入車庫時(shí)間:%dt現(xiàn)在（離開）時(shí)間 :%dt停留時(shí)間:%dtn",entertime,leatime,leatime-entertime);else/ 車輛處在棧中間doPop(S,a);/ 從棧中依次退出Push(TempS,a);/ 依次進(jìn)入臨時(shí)棧while(S.top-1)->num!=e.num);/直到 top 指針下一個(gè)位置的num= 車牌號(hào)Pop(S, a);/ 該車離開leatime=e.time;leanum=e.num;entertime=a.time;printf(" 車進(jìn)入停車場(chǎng)時(shí)間:%dt現(xiàn)在（離開）時(shí)間 :%dt停留

24、時(shí)間:%dtn",entertime,leatime,leatime-entertime);.專業(yè) .專注.do / 其余車輛按原來次序返回停車場(chǎng)Pop(TempS,a);Push(S,a);while(TempS.top!=TempS.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.t

25、ime<leatime)/ 便道車輛進(jìn)車庫時(shí)間應(yīng)該比車庫車輛離開時(shí)間晚entertime=leatime;a.time=leatime;Push(S,a);/ 該車進(jìn)入停車場(chǎng)printf(" 車牌號(hào)為 %d 的車輛從便道上進(jìn)入 %d 號(hào)車庫 !從現(xiàn)在開始計(jì)時(shí) ，現(xiàn)在時(shí)間為 ： %dn",a.num,S.top-S.base,a.time);else if(Check_Queue(Q,e)/ 從便道直接離開doDeQueue(Q,a);EnQueue(Q,a);while(Q.front->next->data.num!=e.num);DeQueue(Q,e);/ 前面的車進(jìn)入隊(duì)尾printf(" 您的車牌號(hào)為%d 的車輛未進(jìn)入車庫從便道直接離開，費(fèi)用為0!n",e.num);return true;.專業(yè) .專注./=void Initialization()/初始化程序printf(" 姓名：楊智偉學(xué)號(hào)：2012040651n");printf("=n");printf("*停車場(chǎng)管理模擬程序*n");pr