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

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

2、隊列模擬便道。從終端讀入汽車到達(dá)或離去的數(shù)據(jù)，每組數(shù)據(jù)包括三項： 是“到達(dá)”還是“離去”； 汽車牌照號碼； “到達(dá)”或“離去”的時刻。與每組輸入信息相應(yīng)的輸出信息為：如果是到達(dá)的車輛，則輸出其在停車場中或便道上的位置；如果是離去的車輛，則輸出其在停車場中停留的時間和應(yīng)交的費用。（提示：需另設(shè)一個棧，臨時停放為讓路而從車場退出的車。）實習(xí)目的：通過實習(xí)，熟悉棧和隊列的基本特點，掌握利用棧和隊列解決具體問題的方法。實習(xí)步驟：1 實現(xiàn)順序棧的基本操作l 基本思路首先實現(xiàn)一個整型順序棧的初始化、判?？?、進(jìn)棧、出棧等基本操作，并在主程序中調(diào)用這些操作。l 基本框架#include #define TRU

3、E 1#define FALSE 0#define Stack_Size 50typedef int StackElementType;typedef struct StackElementType elemStack_Size; int top; SeqStack;/* 以下是函數(shù)原形說明。注意函數(shù)頭后面有分號。 */void InitStack(SeqStack *s);int IsEmpty(SeqStack *s);int Push(SeqStack *s, StackElementType e);int Pop(SeqStack *s, StackElementType *e);/*

4、 以下是函數(shù)定義。注意函數(shù)頭后面無分號。 */void InitStack(SeqStack *s)/* 順序棧的初始化函數(shù) */ ; int IsEmpty(SeqStack *s)/* 順序棧的判?？蘸瘮?shù) */ ; int Push(SeqStack *s, StackElementType e)/* 順序棧的進(jìn)棧函數(shù) */ ; Status Pop(SeqStack *s, StackElementType *e)/* 順序棧的出棧函數(shù) */ ; void main(void) ; l 要點提示主程序的基本過程如下：void main(void) SeqStack my_stack ;S

5、tackElementType x;StackElementType y;InitStack(&my_stack );if(IsEmpty(&my_stack) 打?。骸癿y_stack已被初始化為空棧”; 提示輸入10個正整數(shù)；循環(huán)10次，執(zhí)行下面操作： 讀入整數(shù)x;Push(&my_stack, x); while(!IsEmpty(&my_stack)Pop(&my_stack, &y);打印y;l 測試數(shù)據(jù)讀入數(shù)據(jù)：19，14，23，01，68，20，84，27，55，11打印結(jié)果：讀入序列的逆序。2 同時實現(xiàn)順序棧和鏈隊列的基本操作l 基本思路在前面已經(jīng)實現(xiàn)的整型順序棧的基礎(chǔ)上，進(jìn)一

6、步實現(xiàn)一個整型鏈隊列的基本操作。l 基本框架（1）在上述程序框架的前面，增加如下包含語句：#include （2）在上述程序框架的類型定義部分，增加如下鏈隊列定義：typedef int QueueElementType;typedef struct Node QueueElementType data; /*數(shù)據(jù)域*/ struct Node *next; /*指針域*/ LinkQueueNode;typedef struct LinkQueueNode * front; LinkQueueNode * rear; LinkQueue;（3）在上述程序框架的函數(shù)原型說明部分，增加如下鏈隊列

7、的操作函數(shù)原型說明：int InitQueue(LinkQueue * Q);int EmptyQueue(LinkQueue Q);int EnterQueue(LinkQueue *Q, QueueElementType x);int DeleteQueue(LinkQueue * Q, QueueElementType *x);（4）在上述程序框架的函數(shù)定義部分，增加上述鏈隊列的操作函數(shù)定義。（5）在上述程序框架的主程序中，增加調(diào)用鏈隊列操作函數(shù)的有關(guān)語句。l 要點提示主程序的基本過程如下：void main(void) SeqStack my_stack ;LinkQueue my_q

8、ueue;int x;InitStack(&my_stack );InitQueue(&my_queue );if(IsEmpty(&my_stack) 打?。骸皸榭铡? 提示輸入10個正整數(shù)；循環(huán)10次，執(zhí)行下面操作： 讀入整數(shù)x;Push(&my_stack, x); while(!IsEmpty(&my_stack)Pop(&my_stack, &x);將x加入隊列my_queue;while(隊列my_queue非空)刪除my_queue的隊首元素，并送給x;打印x;注意指針參數(shù)的調(diào)用方法。l 測試數(shù)據(jù)讀入數(shù)據(jù)：19，14，23，01，68，20，84，27，55，11打印結(jié)果：讀入

9、序列的逆序。3 實現(xiàn)停車場管理問題l 基本思路停車場管理問題可以用如下簡圖說明：車庫便 道暫 時 退 車 道 將“車庫”和“暫時退車道”定義為兩個棧，將“便道”定義為一個隊列。在前面程序的基礎(chǔ)上，進(jìn)行如下修改：（1）定義一個表示“車輛信息”的結(jié)構(gòu)體類型。（2）將棧元素類型和隊列元素類型均改為“車輛信息”結(jié)構(gòu)體指針類型（或“車輛信息”結(jié)構(gòu)體類型），并相應(yīng)修改有關(guān)函數(shù)。（3）定義一個“車輛到達(dá)處理”函數(shù)和“車輛離開處理”函數(shù)。l 基本框架（1）在上述程序框架的類型定義部分，增加一個表示“車輛信息”的結(jié)構(gòu)體類型定義，設(shè)置兩個數(shù)據(jù)域：牌照號碼、到達(dá)時刻。牌照號碼用字符串表示，到達(dá)時刻可先用正整數(shù)表示（

10、參后面測試數(shù)據(jù)）。（2）在上述程序框架的函數(shù)原型說明部分，增加“車輛到達(dá)處理”函數(shù)和“車輛離開處理”函數(shù)的原型說明。（3）在上述程序框架的函數(shù)定義部分，增加“車輛到達(dá)處理”函數(shù)和“車輛離開處理”函數(shù)的函數(shù)定義。（4）為了簡化參數(shù)傳遞，可以先將有關(guān)的棧和隊列定義為全局變量，調(diào)通后再改為用參數(shù)傳遞。l 要點提示主程序的基本過程如下：void main(void) 重復(fù)如下過程，直到讀入結(jié)束標(biāo)志： 提示輸入一輛車的信息（到達(dá)/離開，牌照號碼，當(dāng)前時刻）； 讀入這輛車的信息; 如果是到達(dá)車輛，則調(diào)用“車輛到達(dá)處理”函數(shù)； 否則調(diào)用“車輛離開處理”函數(shù)。 “車輛離開處理”函數(shù)的基本過程如下：void l

11、eave(牌照號碼，離開時刻) 當(dāng)“車庫”棧不空，并且棧頂車輛不是要離開的車時，重復(fù)下面操作： 將“車庫”棧的棧頂車輛退出；讓退出的車輛進(jìn)入“暫時退車道”棧； 如果找到要離開的車輛，則計算并輸出停車費用； 將“暫時退車道”棧中的車輛倒回“車庫”棧； 如果“便道”隊列不空，則隊頭車輛出隊，并進(jìn)入“車庫”棧；注意將“出隊車輛”的到達(dá)時刻改為“離開車輛”的離開時刻。l 測試數(shù)據(jù)假設(shè)用0表示車輛離開，1表示車輛到達(dá)，-1表示程序結(jié)束；用字符串表示車輛的牌照號碼；用正整數(shù)表示時刻，每單位時間的停車費用是5元；停車場大小n=2。則運行結(jié)果如下：輸入數(shù)據(jù)：1，A001，5輸出結(jié)果：A001當(dāng)前停放在車庫1號

12、位輸入數(shù)據(jù)：1，B002，10輸出結(jié)果：B002當(dāng)前停放在車庫2號位輸入數(shù)據(jù)：0，A001，15輸出結(jié)果：A001停放時間為10，停車費用為50元輸入數(shù)據(jù)：1，C003，20輸出結(jié)果：C003當(dāng)前停放在車庫2號位輸入數(shù)據(jù)：1，D004，25輸出結(jié)果：D004當(dāng)前停放在便道1號位輸入數(shù)據(jù)：1，E005，30輸出結(jié)果：E005當(dāng)前停放在便道2號位輸入數(shù)據(jù)：0，B002，35輸出結(jié)果：B002停放時間為25，停車費用為125元 便道上的D004進(jìn)入車庫，入庫時刻為35，當(dāng)前停放在車庫2號位輸入數(shù)據(jù)：0，D004，40輸出結(jié)果：D004停放時間為5，停車費用為25元 便道上的E005進(jìn)入車庫，入庫時刻

13、為40，當(dāng)前停放在車庫2號位輸入數(shù)據(jù)：-1，#000，0輸出結(jié)果：當(dāng)前車庫中還有2輛車，便道上無車。再見！改進(jìn)建議：1 每次輸出結(jié)果中，打印整個車庫和整個便道的當(dāng)前停車情況一覽表。2 將車庫”棧、“暫時退車道”棧改為對頂棧，共享同一空間。3 根據(jù)車輛類型，分別收費。4 便道上的車可以直接開走，此時排在它前面的車要依次開出，并排到隊尾。5 停放在便道上的車也收費，但收費標(biāo)準(zhǔn)較低。6 將時間改為時、分表示法。7 到達(dá)時刻和離開時刻采用本機系統(tǒng)時間。8 用隨機數(shù)模擬車輛到達(dá)間隔和停車時間。9 用動畫演示運行過程。源代碼：/ parking.cpp : Defines the entry point

14、for the console application.#include #include #include string.h#define TRUE 1#define FALSE 0#define Stack_Size 2/*車輛信息*/typedef struct Car char Number10; /*車牌號*/ int time; /*到達(dá)時刻*/ Car;/*車庫棧定義*/typedef struct Car elemStack_Size; int top; SeqStack;/*暫退車道棧定義*/typedef struct Car elem2Stack_Size; int to

15、p2; SeqStack2;/*隊列定義*/typedef struct Node Car data; /*數(shù)據(jù)域*/ struct Node *next; /*指針域*/ LinkQueueNode;typedef struct LinkQueueNode * front; LinkQueueNode * rear;int length; LinkQueue;/* 以下是函數(shù)原形說明。注意函數(shù)頭后面有分號。 */void InitStack(SeqStack *s);int IsEmpty(SeqStack *s);int Push(SeqStack *s, Car e);int Pop(S

16、eqStack *s, Car *e);int InitQueue(LinkQueue * Q);int EmptyQueue(LinkQueue Q);int EnterQueue(LinkQueue *Q, Car x);int DeleteQueue(LinkQueue * Q, Car *x);int CarArrive(SeqStack *s,LinkQueue *Q,char num,int arrivetime);int CarLeave(SeqStack *s,LinkQueue * Q,SeqStack *s2,char,int leavetime );/* 以下是函數(shù)定義。

17、注意函數(shù)頭后面無分號。*/void InitStack(SeqStack *s)/* 順序棧的初始化函數(shù) */ s-top =-1; int IsEmpty(SeqStack *s)/* 順序棧的判棧空函數(shù) */ if(s-top =-1)return(TRUE);elsereturn(FALSE);int IsFull(SeqStack *s)/* 順序棧的判棧滿函數(shù) */ if(s-top =Stack_Size)return(TRUE);elsereturn(FALSE);int Push(SeqStack *s, Car *e)/* 順序棧的進(jìn)棧函數(shù) */ if(s-top=Stack

18、_Size-1)return(FALSE);elses-top +;s-elem s-top=*e;return(TRUE); int Pop(SeqStack *s, Car *e)/* 順序棧的出棧函數(shù) */if(s-top =-1)return(FALSE);else*e=s-elem s-top;s-top-;return(TRUE); int InitQueue(LinkQueue * Q)/*鏈隊列的初始化*/ Q-length=0;Q-front=( LinkQueueNode*)malloc(sizeof( LinkQueueNode);if(Q-front!=NULL)Q-r

19、ear=Q-front;Q-front-next=NULL;return(TRUE);elsereturn(FALSE); /*溢出*/int EmptyQueue(LinkQueue *Q)/*鏈隊列的判空*/if(Q-front=Q-rear)return(TRUE);elsereturn(FALSE);int EnterQueue(LinkQueue *Q,Car *x)/*鏈隊列的入隊操作，將數(shù)據(jù)元素x插入到隊列中*/LinkQueueNode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);if(NewNo

20、de!=NULL)NewNode-data=*x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;Q-length+;return(TRUE);else return(FALSE);/溢出int DeleteQueue(LinkQueue * Q,Car *x)/*鏈隊列的出隊操作，對頭出列，并存放到x所指的儲存空間中*/ LinkQueueNode * p;if(Q-front=Q-rear)return(FALSE);p=Q-front-next;Q-front-next=p-next; /*對頭元素p出列*/if(Q-rear=p

21、) /*如果對中只有一個元素p，則p出對后成為空隊*/Q-rear=Q-front; *x=p-data;free(p); /*釋放存儲空間*/Q-length-;return(TRUE);/*車輛到達(dá)函數(shù)*/int CarArrive(SeqStack *s,LinkQueue *Q,char num,int arrivetime) Car *come; come=(Car*)malloc(sizeof(Car); strcpy(come-Number,num);/到達(dá)車輛的車牌號come-time =arrivetime;/到達(dá)車輛的時間if(s-toptop+1);elseEnterQu

22、eue(Q, come);/*若車庫已滿，就入隊列*/ printf(-n); printf(車輛%s停在便道%d號位上n,num,Q-length); return 0;/*車輛離開函數(shù)*/void Carleave(SeqStack *s,LinkQueue * Q,char num,int leavetime) SeqStack s2; InitStack(&s2 );Car *Acar;/要離開車輛Acar=(Car*)malloc(sizeof(Car);int money,parktime;while(!IsEmpty(s)&(strcmp(s-elems-top.Number,n

23、um) /當(dāng)車庫棧不空，并且棧頂車輛不是要離開的車時，重復(fù)下面操作： / 將車庫棧的棧頂車輛退出； Pop(s, Acar);/讓退出的車輛進(jìn)入暫時退車道棧；Push(&s2,Acar); /如果找到要離開的車輛，則計算并輸出停車費用； Pop(s, Acar); parktime=leavetime-Acar-time;money=5*parktime; printf(-n);printf(%s的停車時間為%d，停車費用為%dn,num,parktime,money); /將暫時退車道棧中的車輛倒回車庫棧； while(!IsEmpty(&s2) Pop(&s2, Acar); Push(s

24、, Acar); / 如果便道隊列不空，則隊頭車輛出隊，并進(jìn)入車庫棧； if(!EmptyQueue(Q) Car *Bcar;/出便道進(jìn)車庫的車 Bcar=(Car*)malloc(sizeof(Car);DeleteQueue(Q,Bcar);Bcar-time=leavetime;/將出隊車輛的到達(dá)時刻改為離開車輛的離開時刻。Push(s,Bcar);printf(便道上的%s進(jìn)入車庫，入庫時刻為%d，當(dāng)前停放在車庫%d號位n,Bcar-Number,Bcar-time,s-top+1);/*車庫停車情況一覽表函數(shù)*/void printfstack(SeqStack s) Car *C

25、car;Ccar=(Car*)malloc(sizeof(Car);if(s.top =-1)printf(車庫無車n);elsewhile(s.top !=-1)*Ccar=s.elem s.top;s.top-;printf(%s %dn,Ccar-Number,Ccar-time);/end while/END ELSE/*便道停車情況一覽表函數(shù)*/int printfQueen(LinkQueue Q)Car *Dcar;Dcar=(Car*)malloc(sizeof(Car); LinkQueueNode * p;p=Q.front-next;if(Q.front=Q.rear)printf(便道無車n); return(FALSE);while(Q.front!=Q.rear) *Dcar=p-data;if(Q.rear=p) /*如果對中只有一個元素p，則p出對后成為空隊*/ Q.rear=Q.front; p