數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題

數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題⒈問題描述：停車場管理問題[問題描述]設(shè)有一個(gè)可以停放n輛汽車的狹長停車場，它只有一個(gè)大門可以供車輛進(jìn)出。車輛按到達(dá)停車場時(shí)間的早晚依次從停車場最里面向大門口處停放(最先到達(dá)的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進(jìn)入停車場。停車場內(nèi)如有某輛車要開走，在它之后進(jìn)入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進(jìn)場。每輛車在離開停車場時(shí)，都應(yīng)根據(jù)它在停車場內(nèi)停留的時(shí)間長短交費(fèi)。如果停留在便道上的車未進(jìn)停車場就要離去，允許其離去，不收停車費(fèi)，并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。[實(shí)現(xiàn)要求]要求程序輸出每輛車到達(dá)后的停車位置(停車場或便道上)，以及某輛車離開停車場時(shí)應(yīng)交納的費(fèi)用和它在停車場內(nèi)停留的時(shí)間。[實(shí)現(xiàn)提示]汽車的模擬輸入信息格式可以是：(到達(dá)／離去，汽車牌照號碼，到達(dá)／離去的時(shí)刻)。例如，(‘A’，，1，5)表示1號牌照車在5這個(gè)時(shí)刻到達(dá)，而(‘D’，，5，20)表示5號牌照車在20這個(gè)時(shí)刻離去。整個(gè)程序可以在輸入信息為(‘E’，0，0)時(shí)結(jié)束。本題可用棧和隊(duì)列來實(shí)現(xiàn)。⒉設(shè)計(jì)：⑴數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和核心算法設(shè)計(jì)描述；停車場管理系統(tǒng)是充分利用數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的思想實(shí)現(xiàn)的，棧是一種只能在叫做棧的一段進(jìn)行進(jìn)?；蛘叱鰲２僮鞯木€性數(shù)據(jù)結(jié)構(gòu)。棧的主要特點(diǎn)是”后進(jìn)先出”，即后進(jìn)棧的元素先處理。停車場的容量即為棧的存儲空間，停車場的車輛的?？渴菬o秩序的，因此采用鏈?zhǔn)酱鎯Φ姆绞礁m合，也方便車輛的調(diào)度。隊(duì)列是限定僅能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。隊(duì)列中可以插入的一端稱為隊(duì)尾，可以刪除的一端稱為隊(duì)首。把一個(gè)元素插入隊(duì)列中的操作為進(jìn)隊(duì)，隊(duì)列中刪除一個(gè)元素的操作為出隊(duì)。隊(duì)列存取操作符合：先進(jìn)先出。停車場的車輛到達(dá)停車和車輛的離開的管理方式就是采用隊(duì)列的“先進(jìn)先出”的移動的思想。停車場的入口就是隊(duì)列的隊(duì)首，停車場的出口就是隊(duì)列的隊(duì)尾。⑵主控及功能模塊層次結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第1頁。2.1設(shè)定棧的抽象數(shù)據(jù)類型定義為：

ADTstack{

數(shù)據(jù)對象：D={ai|ai∈charset,i=1,2,……,n,n≥0}

數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2……,n}

基本操作：

initstack(&S,n)

操作結(jié)果：構(gòu)造一個(gè)空棧S,該?？纱娣舗個(gè)元素。

push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。

pop(&S,&e)

初始條件：棧S已存在。

操作結(jié)果：刪除S的棧頂元素，并以e返回其值。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：銷毀棧S。

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。

StackLength(&S)

初始條件：棧S已存在。

操作結(jié)果：返回棧S的長度。

StackEmpty(&S)

初始條件：棧S已存在。

操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。

GetTop(S,&e)

初始條件：棧S已存在。

操作結(jié)果：若棧S不空，則以e返回棧頂元素。

StackTraverse(S,visit())

初始條件：棧S已存在。

操作結(jié)果：從棧底到棧頂依次對S中的每個(gè)元素調(diào)用函數(shù)visit()。

}ADTstack

2.2設(shè)定隊(duì)列的抽象數(shù)據(jù)類型定義為：

ADTQueue{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}

數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2……,n}

基本操作：

InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：隊(duì)列Q被銷毀，不再存在。

ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。

QueueEmpty(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。

QueueLength(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。

GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：用e返回Q的隊(duì)頭元素。

EnQueue(&Q,e)

數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第2頁。初始條件：隊(duì)列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。

DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。

QueueTraverse(Q,visit())

初始條件：Q已存在且非空。

操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對Q的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。

數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第2頁。2.3詳細(xì)設(shè)計(jì)車輛信息類型

typedefstructnode{

intpassport;//存儲車輛牌照信息

inttime;//存儲進(jìn)場時(shí)間信息

}node;

2．棧類型（停車場）

typedefstructstack{//定義停車場棧類型 node*base; node*top; intstacksize;}stack;voidinitstack(stack&S,intn){//構(gòu)造空棧 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}

voidpush(stack&S,nodee){//入棧函數(shù) if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果棧滿則調(diào)用入隊(duì)函數(shù) else{ S.top->passport=e.passport; S.top->time=e.time; S.top++; }}voidwait(stack&S){ if((S.top-S.base)==(S.stacksize-1)&&count!=0){ nodetemp; DeQueue(Q,temp); temp.time=times; push(S,temp); }}數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第3頁。 if(S.top==S.base)returnERROR;//如果?？談t返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}3．隊(duì)列類型（便道）

typedefstructQnode{//定義便道隊(duì)列類型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;voidEnQueue(LinkQueue&Q,nodee){//入隊(duì)函數(shù) Qnode*q; q=(Qnode*)malloc(sizeof(Qnode)); q->Qdata.passport=e.passport; q->Qdata.time=e.time; q->next=NULL; if(count==0){Q.front=q;count++;}//若創(chuàng)建節(jié)點(diǎn)前隊(duì)空，頭指針指向節(jié)點(diǎn) Q.rear->next=q; Q.rear=q;}voidDeQueue(LinkQueue&Q,node&e){//出隊(duì)函數(shù) if(Q.rear==NULL){} else{ e.passport=Q.front->Qdata.passport; e.time=Q.front->Qdata.time; Q.front=Q.front->next; if(Q.front==NULL){Q.rear=Q.front;count=0;} }}4．全局變量及編譯預(yù)處理語句

#defineERROR0

#defineOK1

#defineNULL0

intcount=0;//隊(duì)列是否為空的標(biāo)志inttimes;stacks,temp;//初始化棧數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第4頁。5．主函數(shù)及其他函數(shù)的算法

voidmain(){ intn,exit; floatmoney; charinfo; intpass; Q.front=NULL; Q.rear=(Qnode*)malloc(sizeof(Qnode)); Q.rear->next=Q.rear; printf("停車場容量:"); scanf("%d",&n); initstack(s,n); initstack(temp,n); printf("停車場費(fèi)率(元/小時(shí)):"); scanf("%f",&money); while(exit!=OK){ printf("\n請選擇車輛狀態(tài)\n1到達(dá)2離去3結(jié)束:");getchar(); scanf("%c",&info); printf("請輸入車輛牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("請輸入進(jìn)場時(shí)間:"); if(info=='2')printf("請輸入離場時(shí)間:"); scanf("%d",×); if(info=='3'){exit=OK;} elseif(info=='1'){ inti,j; nodea; a.passport=pass; a.time=times; push(s,a); for(i=1;i<=n;i++){ if(s.base[i-1].passport==a.passport){ printf("停車位置(停車場內(nèi)):%d\n",i); } } Qnode*tp; tp=Q.front; if(tp==NULL){} else{ j=1; while(tp!=Q.rear){ tp=tp->next;數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第5頁。 數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第5頁。 } printf("停車位置(便道):%d\n",j); } } elseif(info=='2'){ noded; inttp,counter=0; do{ counter++; tp=pop(s,d); while(tp!=ERROR){ if(d.passport==pass){ floatm; m=-(times-d.time)*money; printf("停留時(shí)間:%d需交費(fèi):%f\n",-(times-d.time)*(-1),m*(-1)); while(temp.base!=temp.top){ pop(temp,d); push(s,d); } wait(s); d.passport=9999; tp=ERROR; } else{ push(temp,d); d.passport=0; tp=ERROR; } } }while(d.passport==0||counter>n); } elseif(info!='1'&&info!='2'&&info!='3'){} }}數(shù)據(jù)結(jié)構(gòu)報(bào)告數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第6頁。⑶主要功能模塊的輸入、處理(算法框架描述)和輸出；⑷功能模塊之間的調(diào)用與被調(diào)用關(guān)系等。（1）輸入車輛數(shù)據(jù)：1為到達(dá)，2為離去，3為結(jié)束程序。（2）接著輸入車輛的牌照信息

（3）若為到達(dá)的車輛，輸入進(jìn)場信息，若為離去的車輛，輸入離場信息。（4）若車輛到達(dá)，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時(shí)間（在便道上的停放時(shí)間除外），以及應(yīng)該交納的費(fèi)用。（5）本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時(shí)，程序結(jié)束。⒊測試：測試范例，測試結(jié)果，測試結(jié)果的分析與討論，測試過程中遇到的主要問題及所采用的解決措施。測試數(shù)據(jù)：設(shè)n=2

輸入數(shù)據(jù)：2輸出：

停車場容量:2

停車場費(fèi)率:6

A，1，5停車位置(停車場內(nèi)):1

A，2，10停車位置(停車場內(nèi)):2

D，1，15停留時(shí)間:10需交費(fèi):60.00

A，3，20停車位置(停車場內(nèi)):2

A，4，25停車位置(便道):1

A，5，30停車位置(便道):2

D，2，35停留時(shí)間:25需交費(fèi):150.00

D，4，40停留時(shí)間:5需交費(fèi):30.00

E，0，0數(shù)據(jù)結(jié)構(gòu)報(bào)告數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第7頁。運(yùn)行結(jié)果（1）進(jìn)入停車場離開停車場等待停車數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第8頁。程序源代碼#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineNULL0typedefstructnode{//定義車輛信息數(shù)據(jù)結(jié)構(gòu) intpassport;//存儲車輛牌照信息 inttime;//存儲進(jìn)場時(shí)間信息}node;typedefstructstack{//定義停車場棧類型 node*base; node*top; intstacksize;}stack;typedefstructQnode{//定義便道隊(duì)列類型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;intcount=0;//隊(duì)列是否為空的標(biāo)志inttimes;stacks,temp;//初始化棧LinkQueueQ;//初始化隊(duì)列voidinitstack(stack&S,intn){//構(gòu)造空棧 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}voidEnQueue(LinkQueue&Q,nodee);//入隊(duì)函數(shù)voidDeQueue(LinkQueue&Q,node&e);//出隊(duì)函數(shù)voidpush(stack&S,nodee){//入棧函數(shù) if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果棧滿則調(diào)用入隊(duì)函數(shù) else{ S.top->passport=e.passport;數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第9頁。 數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第9頁。 S.top++; }}intpop(stack&S,node&e){//出棧函數(shù) if(S.top==S.base)returnERROR;//如果?？談t返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}voidwait(stack&S){ if((S.top-S.base)==(S.stacksize-1)&&count!=0){ nodetemp; DeQueue(Q,temp); temp.time=times; push(S,temp); }}voidEnQueue(LinkQueue&Q,nodee){//入隊(duì)函數(shù) Qnode*q; q=(Qnode*)malloc(sizeof(Qnode)); q->Qdata.passport=e.passport; q->Qdata.time=e.time; q->next=NULL; if(count==0){Q.front=q;count++;}//若創(chuàng)建節(jié)點(diǎn)前隊(duì)空，頭指針指向節(jié)點(diǎn) Q.rear->next=q; Q.rear=q;}voidDeQueue(LinkQueue&Q,node&e){//出隊(duì)函數(shù) if(Q.rear==NULL){} else{ e.passport=Q.front->Qdata.passport; e.time=Q.front->Qdata.time; Q.front=Q.front->next; if(Q.front==NULL){Q.rear=Q.front;count=0;} }}voidmain(){ intn,exit; floatmoney; charinfo; intpass; Q.front=NULL;數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第10頁。 數(shù)據(jù)結(jié)構(gòu)報(bào)告-停車場問題全文共12頁，當(dāng)前為第10頁。 Q.rear->next=Q.rear; printf("停車場容量:"); scanf("%d",&n); initstack(s,n); initstack(temp,n); printf("停車場費(fèi)率(元/小時(shí)):"); scanf("%f",&money); while(exit!=OK){ printf("\n請選擇車輛狀態(tài)\n1到達(dá)2離去3結(jié)束:"); scanf("%c",&info); printf("請輸入車輛牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("請輸入進(jìn)場時(shí)間:"); if(info=='2')printf("請輸入離場時(shí)間:"); scanf("%d",×); if(info=='3'){exit=OK;} elseif(info=='1'){ inti,j; nodea; a.passport=pass; a.time=times; push(s,a); for(i=1;i<=n;i++){ if(s.base[i-1].passport==a.passport){ printf("停車位置(停車場內(nèi)):%d\n",i); } } Qnode*tp; tp=Q.front; if(tp==NULL){} else{ j=1; while(tp!=Q.rear){ tp=tp->next; j++; } printf("停車位置(便道):%d\n",j); } } elseif(