1、一問題描述1.實(shí)驗(yàn)題目：設(shè)停車場(chǎng)是一個(gè)可停放 n 輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn) n 輛車，上述要求進(jìn)行管理的模擬程序。要求：根據(jù)各結(jié)點(diǎn)的信息，調(diào)用相應(yīng)的函數(shù)或者語句，將結(jié)點(diǎn)入棧入隊(duì)，出?；蛘叱鲫?duì)。二需求分析1.程序所能達(dá)到的基本可能：列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。同時(shí)另設(shè)一個(gè)棧，表示）信息，汽表示）信息，汽車標(biāo)識(shí)（牌P00W, 0, 0E, 0, 0退出程序；若輸入數(shù)據(jù)項(xiàng)不是以上所述，就輸出。2.輸入輸出形式及輸入值范圍：Please input the state,number and timeof the car:The parking place i

2、s 1P0，0W0，0E0，0ERROR個(gè)必須為字母，后兩個(gè)為數(shù)字。3.測(cè)試數(shù)據(jù)要求：用戶輸入字母時(shí)，輸入大寫或小寫，都可以被該程序識(shí)別，正常運(yùn)行。但要求用戶輸入數(shù)據(jù)時(shí)，三個(gè)數(shù)據(jù)項(xiàng)之間必須用逗號(hào)相分隔開。三概要設(shè)計(jì)隊(duì)列這兩個(gè)抽象數(shù)據(jù)類型。1.棧抽象數(shù)據(jù)類型定義：ADT SqStack數(shù)據(jù)對(duì)象：D=a ,b,c d |a int,b int,c int,d char ，iii,iiiiii=1,2,3.,n,n0數(shù)據(jù)關(guān)系：R=(a ,b,d )|a ,b d D,a ,b d struct car;iiiii,iii,i基本操作：Judge_Output(s,q,r)/根據(jù) r 中車輛信息控制車

3、輛是入棧 s 還是入隊(duì) q 以及相關(guān)操作A_cars(s,q, ；/將到達(dá)車輛 a的信息入棧 s 或者入隊(duì) qD_cars(s,q, ；/將待離開車輛 d 出棧 s，并將 q 中相應(yīng)車輛入棧并進(jìn)行相關(guān)的操作ADT SqStack22.隊(duì)列抽象數(shù)據(jù)類型定義：ADT LinkQueue數(shù)據(jù)對(duì)象：D=a ,b,c |a Qnode *,b Qnodeiiiii*,c int ,i=1,2,3.,n,n0;i數(shù)據(jù)關(guān)系：R= ；基本操作：Judge_Output(s,q,r)；/根據(jù) r中車輛信息控制車輛是入棧 s還是入隊(duì) q 以及相關(guān)操作A_cars(s,q, ；/將到達(dá)車輛 a的信息入棧 s 或者入

4、隊(duì) qD_cars(s,q, ；/將待離開車輛 d 出棧 s，并將 q 中相應(yīng)車輛入棧并進(jìn)行相關(guān)的操作ADT LinkQueue3.主要算法流程圖：Judge_Output 算法流程圖：3FF輸出TFTFT輸入為D（d）調(diào)用D_cars函數(shù)結(jié)束A_cars算法流程圖：4D_cars算法流程圖：該車是最后進(jìn)停車場(chǎng)的車FT在該車后進(jìn)的車退出停車場(chǎng)后讓其結(jié)賬離開結(jié)賬離開TF54.本程序保護(hù)模塊：主函數(shù)模塊棧單元模塊：實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型隊(duì)列單元模塊：實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型調(diào)用關(guān)系：四詳細(xì)設(shè)計(jì)1.相關(guān)頭文件庫的調(diào)用說明：#include#include#define MAXSIZE 14#define

5、 n 2#define fee 102.元素類型、結(jié)點(diǎn)類型和結(jié)點(diǎn)指針類型：struct car char bb;int num;int time;struct rangweicarint num;int time;typedef struct stackkstruct rangweicar HMAXSIZE;int topp;6SqStackk;#define QNODE struct QnodeQNODE int data;QNODE *next;3.棧類型和隊(duì)列類型：typedef struct stackstruct car Gn;int top;SqStack;typedef stru

6、ct linkqueueQNODE *front,*rear;int geshu;LinkQueue;/部分基本操作的偽碼實(shí)現(xiàn)void Judge_Output(SqStack *s,LinkQueue *q,struct car *r)if(*r).bb=E|(*r).bb=e)printf(STOP!n);else if(*r).bb=P|(*r).bb=p)printf(The number of parking cars is %dn,(s-top)+1);else if(*r).bb=W|(*r).bb=w)printf(The number of waiting cars is %

7、dn,q-geshu);else if(*r).bb=A|(*r).bb=a)A_cars(s,q,*r);else if(*r).bb=D|(*r).bb=d)D_cars(s,q,*r);elseprintf(ERROR!n);7A_cars(SqStack *s,LinkQueue *q,struct car a)QNODE *t;if(s-top!=n-1)(s-top)+;(s-Gs-top).bb=a.bb;(s-Gs-top).num=a.num;(s-Gs-top).time=a.time;elseprintf(The parking place is full!n);t=(Q

8、NODE *)malloc(sizeof(QNODE);t-data=a.num;t-next=NULL;q-rear-next=t;q-rear=t;printf(the number of the car in the access road is:%dn,q-rear-data);q-geshu+;int D_cars(SqStack *s,LinkQueue *q,struct car d)int i,j,l;float x,y;QNODE *p;SqStackk *k;if(d.num=(s-Gs-top).num)x=d.time-(s-Gs-top).time;y=fee*x;p

9、rintf(The time is %.2f hours,the fee is %.2f yuann,x,y);if(q-geshu=0)printf(The queue is empty!n);8return 0;elsep=q-front-next;q-front-next=p-next;(s-Gs-top).num=p-data;(s-Gs-top).time=d.time;free(p);q-geshu-;if(q-front-next=NULL)q-rear=q-front;return 1;elsefor(i=0;itop);i+)if(s-Gi).num!=d.num) cont

10、inue;else break;if(i=(s-top)printf(ERROR!n);return -1;x=d.time-(s-Gi).time;y=fee*x;printf(The time is %.2f hours,the fee is %.2f yuann,x,y);k=(SqStackk *)malloc(sizeof(SqStackk);k-topp=-1;for(j=(s-top);ji;j-)k-topp+; (k-Hk-topp).num=(s-Gj).num;(k-Hk-topp).time=(s-Gj).time;9s-top-;for(l=0;ltopp);l+)p

11、rintf(the information(number and time) in the new stack is:n);printf(%d,%dn,(k-Hl).num,(k-Hl).time);s-top-;while(k-topp=0)s-top+;(s-Gs-top).bb=A;(s-Gs-top).num=(k-Hk-topp).num;(s-Gs-top).time=(k-Hk-topp).time;k-topp-;if(q-geshu=0)printf(The access road is empty!n);return 2;elses-top+;p=q-front-next;

12、q-front-next=p-next;(s-Gs-top).num=p-data;(s-Gs-top).time=d.time;free(p);q-geshu-;if(q-front-next=NULL)q-rear=q-front;return 3;104.主函數(shù)的偽碼：main()SqStack *s;LinkQueue *q;QNODE *p;struct car aaMAXSIZE;int i;s=(SqStack *)malloc(sizeof(SqStack);s-top=-1;q=(LinkQueue *)malloc(sizeof(LinkQueue);p=(QNODE *)

13、malloc(sizeof(QNODE);p-next=NULL;q-front=q-rear=p;q-geshu=0;printf(*n);printf(*n);printf(*n);printf(*n);停 車 場(chǎng) 管 理 系 統(tǒng)printf(*n);for(i=0;iMAXSIZE;i+)printf(Please input the state,number and time of the car:n);scanf(%c,%d,%d,&(aai.bb),&(aai.num),&(aai.time);getchar();Judge_Output(s,q,&aai);if(aai.bb=E

14、|aai.bb=e) break;115.函數(shù)調(diào)用關(guān)系：五測(cè)試分析：1.出現(xiàn)問題及解決辦法：入字符時(shí)由于回車鍵也是字符，回車鍵總會(huì)被讀入，導(dǎo)致經(jīng)常輸出“ERROR后來找到原因后在 scanf 函數(shù)后緊接著加了一個(gè) 常。2.方法優(yōu)缺點(diǎn)分析：優(yōu)點(diǎn)：用棧和隊(duì)列來模擬停車場(chǎng)讓整個(gè)問題顯得簡單，易于實(shí)現(xiàn)；它讓路，因此無法用棧的“后進(jìn)先出”原則來模擬；而且沒有考慮便道上的車在擬。3.主要算法的時(shí)間和空間復(fù)雜度分析：（1）由于算法 Judge_Output 函數(shù)根據(jù)判斷條件，每次只選擇一個(gè)程序段執(zhí)行，所以其時(shí)間復(fù)雜度是 ；12（2）由于算法A_cars 函數(shù)根據(jù)判斷條件，將數(shù)據(jù)入?；蛉腙?duì)列，所以其時(shí)間復(fù)雜度也是 ；（3）由于算法D_cars 函數(shù)在出棧數(shù)據(jù)不在最頂端時(shí)需將 n 個(gè)數(shù)據(jù)先出該棧，再入新棧，再回舊棧的操作，故其時(shí)間復(fù)雜度是 ；（4）所有算法的空間復(fù)雜度都是 。六使用說明會(huì)根據(jù)車輛的狀態(tài)信息調(diào)用相應(yīng)的函數(shù)，并輸出用戶想得到的信息。七調(diào)試結(jié)果A1，5A