數據結構報告-停車場問題

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

ADTstack{

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

數據關系：R1={|ai-1,ai∈D,i=2……,n}

基本操作：

initstack(&S,n)

操作結果：構造一個空棧S,該?？纱娣舗個元素。

push(&S,e)

初始條件：棧S已存在。

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

pop(&S,&e)

初始條件：棧S已存在。

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

DestroyStack(&S)

初始條件：棧S已存在。

操作結果：銷毀棧S。

ClearStack(&S)

初始條件：棧S已存在。

操作結果：將S清為空棧。

StackLength(&S)

初始條件：棧S已存在。

操作結果：返回棧S的長度。

StackEmpty(&S)

初始條件：棧S已存在。

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

GetTop(S,&e)

初始條件：棧S已存在。

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

StackTraverse(S,visit())

初始條件：棧S已存在。

操作結果：從棧底到棧頂依次對S中的每個元素調用函數visit()。

}ADTstack

2.2設定隊列的抽象數據類型定義為：

ADTQueue{

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

數據關系：R1={|ai-1,ai∈D,i=2……,n}

基本操作：

InitQueue(&Q)

操作結果：構造一個空隊列Q。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結果：隊列Q被銷毀，不再存在。

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結果：將Q清為空隊列。

QueueEmpty(&Q)

初始條件：隊列Q已存在。

操作結果：若Q為空隊列，則返回TRUE，否則返回FALSE。

QueueLength(Q)

初始條件：隊列Q已存在。

操作結果：返回Q的元素個數，即隊列的長度。

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結果：用e返回Q的隊頭元素。

EnQueue(&Q,e)

數據結構報告-停車場問題全文共12頁，當前為第2頁。初始條件：隊列Q已存在。

操作結果：插入元素e為Q的新的隊尾元素。

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結果：刪除Q的隊頭元素，并用e返回其值。

QueueTraverse(Q,visit())

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

操作結果：從隊頭到隊尾，依次對Q的每個數據元素調用函數visit()。一旦visit()失敗，則操作失敗。

數據結構報告-停車場問題全文共12頁，當前為第1頁。數據結構報告-停車場問題全文共12頁，當前為第2頁。2.3詳細設計車輛信息類型

typedefstructnode{

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

inttime;//存儲進場時間信息

}node;

2．棧類型（停車場）

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

voidpush(stack&S,nodee){//入棧函數 if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果棧滿則調用入隊函數 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); }}數據結構報告-停車場問題全文共12頁，當前為第3頁。數據結構報告-停車場問題全文共12頁，當前為第3頁。 if(S.top==S.base)returnERROR;//如果?？談t返回ERROR --S.top; e.passport=S.top->passport; e.time=S.top->time; returnOK;}3．隊列類型（便道）

typedefstructQnode{//定義便道隊列類型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;voidEnQueue(LinkQueue&Q,nodee){//入隊函數 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é)點前隊空，頭指針指向節(jié)點 Q.rear->next=q; Q.rear=q;}voidDeQueue(LinkQueue&Q,node&e){//出隊函數 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．全局變量及編譯預處理語句

#defineERROR0

#defineOK1

#defineNULL0

intcount=0;//隊列是否為空的標志inttimes;stacks,temp;//初始化棧數據結構報告-停車場問題全文共12頁，當前為第4頁。數據結構報告-停車場問題全文共12頁，當前為第4頁。5．主函數及其他函數的算法

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("停車場費率(元/小時):"); scanf("%f",&money); while(exit!=OK){ printf("\n請選擇車輛狀態(tài)\n1到達2離去3結束:");getchar(); scanf("%c",&info); printf("請輸入車輛牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("請輸入進場時間:"); if(info=='2')printf("請輸入離場時間:"); 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("停車位置(停車場內):%d\n",i); } } Qnode*tp; tp=Q.front; if(tp==NULL){} else{ j=1; while(tp!=Q.rear){ tp=tp->next;數據結構報告-停車場問題全文共12頁，當前為第5頁。 數據結構報告-停車場問題全文共12頁，當前為第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("停留時間:%d需交費:%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'){} }}數據結構報告數據結構報告-停車場問題全文共12頁，當前為第6頁。⑶主要功能模塊的輸入、處理(算法框架描述)和輸出；⑷功能模塊之間的調用與被調用關系等。（1）輸入車輛數據：1為到達，2為離去，3為結束程序。（2）接著輸入車輛的牌照信息

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

輸入數據：2輸出：

停車場容量:2

停車場費率:6

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

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

D，1，15停留時間:10需交費:60.00

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

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

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

D，2，35停留時間:25需交費:150.00

D，4，40停留時間:5需交費:30.00

E，0，0數據結構報告數據結構報告-停車場問題全文共12頁，當前為第7頁。運行結果（1）進入停車場離開停車場等待停車數據結構報告-停車場問題全文共12頁，當前為第8頁。數據結構報告-停車場問題全文共12頁，當前為第8頁。程序源代碼#include<stdio.h>#include<stdlib.h>#defineERROR0#defineOK1#defineNULL0typedefstructnode{//定義車輛信息數據結構 intpassport;//存儲車輛牌照信息 inttime;//存儲進場時間信息}node;typedefstructstack{//定義停車場棧類型 node*base; node*top; intstacksize;}stack;typedefstructQnode{//定義便道隊列類型 nodeQdata; structQnode*next;}Qnode;typedefstruct{ Qnode*front; Qnode*rear;}LinkQueue;intcount=0;//隊列是否為空的標志inttimes;stacks,temp;//初始化棧LinkQueueQ;//初始化隊列voidinitstack(stack&S,intn){//構造空棧 S.base=(node*)malloc(n*sizeof(node)); S.top=S.base; S.stacksize=n;}voidEnQueue(LinkQueue&Q,nodee);//入隊函數voidDeQueue(LinkQueue&Q,node&e);//出隊函數voidpush(stack&S,nodee){//入棧函數 if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);}//如果棧滿則調用入隊函數 else{ S.top->passport=e.passport;數據結構報告-停車場問題全文共12頁，當前為第9頁。 數據結構報告-停車場問題全文共12頁，當前為第9頁。 S.top++; }}intpop(stack&S,node&e){//出棧函數 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){//入隊函數 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é)點前隊空，頭指針指向節(jié)點 Q.rear->next=q; Q.rear=q;}voidDeQueue(LinkQueue&Q,node&e){//出隊函數 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;數據結構報告-停車場問題全文共12頁，當前為第10頁。 數據結構報告-停車場問題全文共12頁，當前為第10頁。 Q.rear->next=Q.rear; printf("停車場容量:"); scanf("%d",&n); initstack(s,n); initstack(temp,n); printf("停車場費率(元/小時):"); scanf("%f",&money); while(exit!=OK){ printf("\n請選擇車輛狀態(tài)\n1到達2離去3結束:"); scanf("%c",&info); printf("請輸入車輛牌照:"); scanf("%d",&pass); if(info=='1'||info=='3')printf("請輸入進場時間:"); if(info=='2')printf("請輸入離場時間:"); 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("停車位置(停車場內):%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(