數(shù)據(jù)結(jié)構(gòu)上機(jī)-停車場管理問題

實(shí)習(xí)指導(dǎo)[實(shí)習(xí)題目]：停車場管理。[實(shí)習(xí)內(nèi)容]：第一，實(shí)現(xiàn)棧和隊(duì)列的基本操作，在此基礎(chǔ)上，實(shí)現(xiàn)停車場管理。停車場管理問題描述：設(shè)停車場是一個(gè)可停放n輛車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。在停車場內(nèi)，汽車按到達(dá)的先后次序，由北向南依次排列（假設(shè)大門在最南端）若車場內(nèi)已停滿n輛車，則此后的汽車需在門外的便道上等候，當(dāng)有車開走時(shí)，便道上的第一輛車即可開入。當(dāng)停車場內(nèi)某輛車要走開時(shí)，在它此后進(jìn)入的車輛必定先退出車場為它讓路，待該輛車開出大門后，其他車輛再按原次序返回車場。每輛車走開停車場時(shí)，應(yīng)按其停

。留時(shí)間的長短交費(fèi)（在便道上停留的時(shí)間不收費(fèi)）。試編寫程序，模擬上述管理過程。要求以次序棧模擬停車場，以鏈隊(duì)列模擬便道。從終端讀入汽車到達(dá)或走開的數(shù)據(jù)，每組數(shù)據(jù)包括三項(xiàng)：①是“到達(dá)”還是“走開”；②汽車牌照號(hào)碼；③“到達(dá)”或“走開”的時(shí)辰。與每組輸入信息相應(yīng)的輸出信息為：若是是到達(dá)的車輛，則輸出其在停車場中或便道上的地址；若是是走開的車輛，則輸出其在停車場中停留的時(shí)間和應(yīng)交的花銷。（提示：需另設(shè)一個(gè)棧，臨時(shí)停放為讓路而從車場退出的車。）[實(shí)習(xí)目的]：經(jīng)過實(shí)習(xí)，熟悉棧和隊(duì)列的基本特點(diǎn)，掌握利用棧和隊(duì)列解決詳盡問題的方法。[實(shí)習(xí)步驟]：1．實(shí)現(xiàn)次序棧的基本操作基本思路第一實(shí)現(xiàn)一個(gè)整型次序棧的初始化、判棧空、進(jìn)棧、出棧等基本操作，并在主程序中調(diào)用這些操作。基本框架#include<>#defineTRUE1#defineFALSE0#defineStack_Size50typedefintStackElementType;typedefstruct{StackElementTypeelem[Stack_Size];inttop;}SeqStack;/*以下是函數(shù)原形說明。注意函數(shù)頭后邊有分號(hào)。*/voidInitStack(SeqStack*s);intIsEmpty(SeqStack*s);intPush(SeqStack*s,StackElementTypee);intPop(SeqStack*s,StackElementType*e);/*以下是函數(shù)定義。注意函數(shù)頭后邊無分號(hào)。*/voidInitStack(SeqStack*s)/*次序棧的初始化函數(shù)*/{;}intIsEmpty(SeqStack*s)/*次序棧的判?？蘸瘮?shù)*/{;}intPush(SeqStack*s,StackElementTypee)/*次序棧的進(jìn)棧函數(shù)*/{;}StatusPop(SeqStack*s,StackElementType*e)/*次序棧的出棧函數(shù)*/{;}voidmain(void){;}要點(diǎn)提示主程序的基本過程以下：voidmain(void){SeqStackmy_stack;StackElementTypex;StackElementTypey;InitStack(&my_stack);if(IsEmpty(&my_stack))打印：“my_stack已被初始化為空?！?提示輸入10個(gè)正整數(shù)；循環(huán)10次，執(zhí)行下面操作：{讀入整數(shù)x;Push(&my_stack,x);}while(!IsEmpty(&my_stack)){Pop(&my_stack,&y);打印y;}}測試數(shù)據(jù)讀入數(shù)據(jù)：19，14，23，01，68，20，84，27，55，11打印結(jié)果：讀入序列的逆序。2．同時(shí)實(shí)現(xiàn)次序棧和鏈隊(duì)列的基本操作基本思路在前面已經(jīng)實(shí)現(xiàn)的整型次序棧的基礎(chǔ)上，進(jìn)一步實(shí)現(xiàn)一個(gè)整型鏈隊(duì)列的基本操作?；究蚣?）在上述程序框架的前面，增加以下包括語句：#include<>2）在上述程序框架的種類定義部分，增加以下鏈隊(duì)列定義：typedefintQueueElementType;typedefstructNode{QueueElementTypedata;structNode*next;/*

/*

數(shù)據(jù)域*/指針域

*/}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;3）在上述程序框架的函數(shù)原型說明部分，增加以下鏈隊(duì)列的操作函數(shù)原型說明：intInitQueue(LinkQueue*Q);intEmptyQueue(LinkQueueQ);intEnterQueue(LinkQueue*Q,QueueElementTypex);intDeleteQueue(LinkQueue*Q,QueueElementType*x);4）在上述程序框架的函數(shù)定義部分，增加上述鏈隊(duì)列的操作函數(shù)定義。5）在上述程序框架的主程序中，增加調(diào)用鏈隊(duì)列操作函數(shù)的有關(guān)語句。要點(diǎn)提示主程序的基本過程以下：voidmain(void){SeqStackmy_stack;LinkQueuemy_queue;intx;InitStack(&my_stack);InitQueue(&my_queue);if(IsEmpty(&my_stack))打?。骸皸榭铡?提示輸入10個(gè)正整數(shù)；循環(huán)10次，執(zhí)行下面操作：{讀入整數(shù)x;Push(&my_stack,x);}while(!IsEmpty(&my_stack)){Pop(&my_stack,&x);將x加入隊(duì)列my_queue;}while(隊(duì)列my_queue非空){刪除my_queue的隊(duì)首元素，并送給x;打印x;}}注意指針參數(shù)的調(diào)用方法。測試數(shù)據(jù)讀入數(shù)據(jù)：19，14，23，01，68，20，84，27，55，11打印結(jié)果：讀入序列的逆序。3．實(shí)現(xiàn)停車場管理問題基本思路停車場管理問題可以用以下簡圖說明：車庫臨時(shí)退車道便道將“車庫”和“臨時(shí)退車道”定義為兩個(gè)棧，將“便道”定義為一個(gè)隊(duì)列。在前面程序的基礎(chǔ)上，進(jìn)行以下更正：1）定義一個(gè)表示“車輛信息”的結(jié)構(gòu)體種類。2）將棧元素種類和隊(duì)列元素種類均改為“車輛信息”結(jié)構(gòu)體指針種類（或“車輛信息”結(jié)構(gòu)體種類），并相應(yīng)更正有關(guān)函數(shù)。3）定義一個(gè)“車輛到達(dá)辦理”函數(shù)和“車輛走創(chuàng)辦理”函數(shù)?；究蚣?）在上述程序框架的種類定義部分，增加一個(gè)表示“車輛信息”的結(jié)構(gòu)體種類定義，設(shè)置兩個(gè)數(shù)據(jù)域：牌照號(hào)碼、到達(dá)時(shí)辰。牌照號(hào)碼用字符串表示，到達(dá)時(shí)辰可先用正整數(shù)表示（參后邊測試數(shù)據(jù)）。2）在上述程序框架的函數(shù)原型說明部分，增加“車輛到達(dá)辦理”函數(shù)和“車輛走創(chuàng)辦理”函數(shù)的原型說明。3）在上述程序框架的函數(shù)定義部分，增加“車輛到達(dá)辦理”函數(shù)和“車輛走創(chuàng)辦理”函數(shù)的函數(shù)定義。4）為了簡化參數(shù)傳達(dá)，可以先將有關(guān)的棧和隊(duì)列定義為全局變量，調(diào)通后再改為用參數(shù)傳達(dá)。要點(diǎn)提示主程序的基本過程以下：voidmain(void){重復(fù)以下過程，直到讀入結(jié)束標(biāo)志：{提示輸入一輛車的信息（到達(dá)/走開，牌照號(hào)碼，目前時(shí)辰）；讀入這輛車的信息;若是是到達(dá)車輛，則調(diào)用“車輛到達(dá)辦理”函數(shù)；否則調(diào)用“車輛走創(chuàng)辦理”函數(shù)。}}“車輛走創(chuàng)辦理”函數(shù)的基本過程以下：voidleave(牌照號(hào)碼，走開時(shí)辰){當(dāng)“車庫”棧不空，并且棧頂車輛不是要走開的車時(shí)，重復(fù)下面操作：{將“車庫”棧的棧頂車輛退出；讓退出的車輛進(jìn)入“臨時(shí)退車道”棧；}若是找到要走開的車輛，則計(jì)算并輸出停車花銷；將“臨時(shí)退車道”棧中的車輛倒回“車庫”棧；若是“便道”隊(duì)列不空，則隊(duì)頭車輛出隊(duì)，并進(jìn)入“車庫”棧；}注意將“出隊(duì)車輛”的到達(dá)時(shí)辰改為“走開車輛”的走開時(shí)辰。測試數(shù)據(jù)假設(shè)用0表示車輛走開，1表示車輛到達(dá)，-1表示程序結(jié)束；用字符串表示車輛的牌照號(hào)碼；用正整數(shù)表示時(shí)辰，每單位時(shí)間的停車花銷是5元；停車場大小n=2。則運(yùn)行結(jié)果如下：輸入數(shù)據(jù)：1，A001，5輸出結(jié)果：A001目前停放在車庫1號(hào)位輸入數(shù)據(jù)：1，B002，10輸出結(jié)果：B002目前停放在車庫2號(hào)位輸入數(shù)據(jù)：0，A001，15輸出結(jié)果：A001停放時(shí)間為10，停車花銷為50元輸入數(shù)據(jù)：1，C003，20輸出結(jié)果：C003目前停放在車庫2號(hào)位輸入數(shù)據(jù)：1，D004，25輸出結(jié)果：D004目前停放在便道1號(hào)位輸入數(shù)據(jù)：1，E005，30輸出結(jié)果：E005目前停放在便道2號(hào)位輸入數(shù)據(jù)：0，B002，35輸出結(jié)果：B002停放時(shí)間為25，停車花銷為125元便道上的D004進(jìn)入車庫，入庫時(shí)辰為35，目前停放在車庫2號(hào)位輸入數(shù)據(jù)：0，D004，40輸出結(jié)果：D004停放時(shí)間為5，停車花銷為25元便道上的E005進(jìn)入車庫，入庫時(shí)辰為40，目前停放在車庫輸入數(shù)據(jù)：-1，#000，0輸出結(jié)果：目前車庫中還有2輛車，便道上無車。再見！

2號(hào)位[改進(jìn)建議]：1．每次輸出結(jié)果中，打印整個(gè)車庫和整個(gè)便道的目前停車狀況一覽表。2．將車庫”棧、“臨時(shí)退車道”棧改為對(duì)頂棧，共享同一空間。3．依照車輛種類，分別收費(fèi)。4．便道上的車可以直接開走，此時(shí)排在它前面的車要依次開出，并排到隊(duì)尾。5．停放在便道上的車也收費(fèi)，但收費(fèi)標(biāo)準(zhǔn)較低。6．將時(shí)間改為時(shí)、分表示法。7．到達(dá)時(shí)辰和走開時(shí)辰采用本機(jī)系統(tǒng)時(shí)間。8．用隨機(jī)數(shù)模擬車輛到達(dá)間隔和停車時(shí)間。9．用動(dòng)畫演示運(yùn)行過程。源代碼：#include<>#include<>#include""#defineTRUE1#defineFALSE0#defineStack_Size2/**************車輛信息******************/typedefstructCar{charNumber[10];inttime;/*

/*

車牌號(hào)*/到達(dá)時(shí)辰*/}Car;/******************車庫棧定義**********************/typedefstruct{Carelem[Stack_Size];inttop;}SeqStack;/******************暫退車道棧定義**********************/typedefstruct{Carelem2[Stack_Size];inttop2;}SeqStack2;/*****************隊(duì)列定義******************/typedefstructNode{Cardata;/*數(shù)據(jù)域structNode*next;/*

*/

指針域

*/}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;intlength;}LinkQueue;/*以下是函數(shù)原形說明。注意函數(shù)頭后邊有分號(hào)。*/voidInitStack(SeqStack*s);intIsEmpty(SeqStack*s);intPush(SeqStack*s,Care);intPop(SeqStack*s,Car*e);intInitQueue(LinkQueue*Q);intEmptyQueue(LinkQueueQ);intEnterQueue(LinkQueue*Q,Carx);intDeleteQueue(LinkQueue*Q,Car*x);intCarArrive(SeqStack*s,LinkQueue*Q,charnum[],intarrivetime);intCarLeave(SeqStack*s,LinkQueue*Q,SeqStack*s2,char[],intleavetime);/**********以下是函數(shù)定義。注意函數(shù)頭后邊無分號(hào)。********/voidInitStack(SeqStack*s)/*次序棧的初始化函數(shù)*/{s->top=-1;}intIsEmpty(SeqStack*s)/*次序棧的判?？蘸瘮?shù)*/{if(s->top==-1)return(TRUE);elsereturn(FALSE);}intIsFull(SeqStack*s)/*次序棧的判棧滿函數(shù)*/{if(s->top==Stack_Size)return(TRUE);elsereturn(FALSE);}intPush(SeqStack*s,Car*e)/*次序棧的進(jìn)棧函數(shù)*/{if(s->top==Stack_Size-1)return(FALSE);else{s->top++;s->elem[s->top]=*e;return(TRUE);}}intPop(SeqStack*s,Car*e)/*次序棧的出棧函數(shù)*/{if(s->top==-1)return(FALSE);else{*e=s->elem[s->top];s->top--;return(TRUE);}}intInitQueue(LinkQueue*Q)/*鏈隊(duì)列的初始化*/{Q->length=0;Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(TRUE);}elsereturn(FALSE);/*溢出*/}intEmptyQueue(LinkQueue*Q)/*鏈隊(duì)列的判空*/{if(Q->front==Q->rear)return(TRUE);elsereturn(FALSE);}intEnterQueue(LinkQueue*Q,Car*x)/*鏈隊(duì)列的入隊(duì)操作，將數(shù)據(jù)元素x插入到隊(duì)列中*/{LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode->data=*x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;Q->length++;return(TRUE);}elsereturn(FALSE);umber,num)))當(dāng)"車庫"棧不空，并且棧頂車輛不是要走開的車時(shí)，重復(fù)下面操作：{將"車庫"棧的棧頂車輛退出；Pop(s,Acar);讓退出的車輛進(jìn)入"臨時(shí)退車道"棧；Push(&s2,Acar);}若是找到要走開的車輛，則計(jì)算并輸出停車花銷；Pop(s,Acar);parktime=leavetime-Acar->time;money=5*parktime;printf("-------------------------------------\n");printf("%s的停車時(shí)間為%d，停車花銷為%d\n",num,parktime,money);將"臨時(shí)退車道"棧中的車輛倒回"車庫"棧；while(!IsEmpty(&s2)){Pop(&s2,Acar);Push(s,Acar);}若是"便道"隊(duì)列不空，則隊(duì)頭車輛出隊(duì)，并進(jìn)入"車庫"棧；if(!EmptyQueue(Q)){Car*Bcar;//出便道進(jìn)車庫的車Bcar=(Car*)malloc(sizeof(Car));DeleteQueue(Q,Bcar);Bcar->time=leavetime;//將"出隊(duì)車輛"的到達(dá)時(shí)辰改為"走開車輛"的走開時(shí)辰。Push(s,Bcar);printf("便道上的%s進(jìn)入車庫，入庫時(shí)刻為%d，目前停放在車庫%d號(hào)位\n",Bcar->Number,Bcar->time,s->top+1);}}/***********************車庫停車狀況一覽表函數(shù)*******************************************/voidprintfstack(SeqStacks){Car*Ccar;Ccar=(Car*)malloc(sizeof(Car));if==-1)printf("車庫無車\n");else{while!=-1){*Ccar=[];;printf("%s%d\n",Ccar->Number,Ccar->time);}//endwhile}//ENDELSE}/***********************便道停車狀況一覽表函數(shù)*******************************************/intprintfQueen(LinkQueueQ){Car*Dcar;Dcar=(Car*)malloc(sizeof(Car));LinkQueueNode*p;p=>next;if=={printf("便道無車\n");return(FALSE);}while!={*Dcar=p->data;if==p)/*若是對(duì)中只有一個(gè)元素p，則p出對(duì)后成為空隊(duì)*/=;printf("%s%d\n",Dcar->Number,Dcar->time);p=p->next;free(p);/*釋放儲(chǔ)藏空間*/}return(TRUE);}/***************************

主

函

數(shù)**************************************************/voidmain(void){charch;SeqStackmy_stack;LinkQueuemy_queue;InitStack(&my_stack);InitQueue(&my_queue);while(1){intt;printf("*************************************\n");printf("

WELCO