數據構造

設計：停車場管理

姓名：韋邦權

專業：2013級計算機科學與技術

學號：13224624

班級：13052316

完成日期：2013.12.19

1問題描述

設停車場是一個可停放n輛汽車的狹長通道，且只有一個門可供出入。汽車在停

車場內按車輛到達時間的先后順序，依次由北向南排列(門在最南端，最先到達的第

一輛車停放在車場的最北端)，假設車場內已停滿n輛汽車，那么后來的汽車只能在

門外的便道上等候，一旦有車開走，那么排在便道上的第一輛汽車即可開入；當停車

場內某輛車要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出

大門外，其他車輛再按原順序進入車場，每輛停放在車場的車在它離開停車場時必須

按它停留的時間長短交納費用。

2需求分析

(1)根據車輛到達停車場到車輛離開停車場時所停留的時間進展計時收費。

(2)當有車輛從停車場離開時，等待的車輛按順序進入停車場停放。實現停車

場的調度功能。

(3)用順序棧來表示停車場，鏈隊表示停車場外的便道。

(4)顯示停車場信息和便道信息。

(5)程序執行的命令為：①車輛進入停車場②車輛離開停車場③顯示停車

場的信息。

3概要設計

3.1抽象數據類型定義

U)棧的抽象數據類型定義

ASTStack{

數據對象：D={ai|aiGElemSet,i=ln>0}

數據關系:Rl={<ai-l,ai>|ai-l,ai￡D,i=2,...,n}

約定an端為棧頂，al端為棧底。

基本操作：

InitStack(&S)

操作結果：構造一個空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結果：棧S被銷毀。

ClearStack(&S)

初始條件：棧S已存在。

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

StackEmpty(S)

初始條件：棧S已存在。

操作結果：假設棧S為空棧，那么返回TRUE,否那么FALSE。

StackLength(s)

初始條件:棧S已存在。

操作結果：返回S的元素個數，既棧的長度。

GetTop(S,&e)

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

操作結果：用e返回S的棧頂元素。

Push(&S,e)

初始條件：棧S已存在。

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

Pop(&S,&e)

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

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

StackTraverse(S,visit())

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

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

失敗，那么操作失效。

}ADTStack

(2)隊列的抽象數據類型定義

ADTQueue{

數據對象：D={ai|aiGElemSet,i=l,2,...,n,n>0}

數據關系:Rl={<ai-l,ai>|ai-l,aieD,i=2,...,n}

約定其中al端為隊列頭，an為隊列尾。

基本操作：

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返回的隊頭元素。

EnQueue(&Q,e)

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

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

DeQueue(&Q,&e)

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

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

QueueTraverse(Q,visit())

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

操作結果:從隊頭到隊尾,依次對Q的每個數據元素調用函數visit。。一旦visit。

失敗，那么操作失敗。

}ADTQueue

3.2模塊劃分

本程序包括六個模塊：

(1)主程序模塊

voidmain()

(

初始化停車站；

初始化讓路的臨時棧；

初始化通道；

輸出主菜單：車輛到達、車輛離開與計費、查看停車場信息；

)

(2)入場模塊

intarrive(SqStack*In,LinkQueue*W)

(

車輛進入停車場；

計算停車費用

}

(3)出場模塊

voidleave(SqStack*In,SqStack*Out,LinkQueue*W)

(

車輛離開停車場；

)

(4)輸出模塊

voidinfo(SqStackS,LinkQueueW)

輸出停車場信息；

}

(5)棧模塊——實現棧的抽象數據類型

(6)隊列模塊——實現隊列的抽象數據類型

4詳細設計

4.1數據類型的定義

intMAX;/*定義一個全局變量用來存儲車庫最大容量*/

floatprice;/*定義一個全局變量用來存儲每車每小時的費用*/

typedefstructtime

(

inthour;

intmin;

}Time;/*時間結點*/

typedefstructnode

(

charnum[10J;

Timereach;

Timeleave;

}Car;/*車輛信息結點*/

typedefstructNODE

(

Car*stack[100];

inttop;

}SqStack;/*停車站*/

typedefstructcar

Car*data;

structcar*next;

JQNode;

typedefstructNode

(

QNode*head;

QNode*rear;

}LinkQueue;/*通道*/

4.2主要模塊的算法描述

本程序主要分為四局部：(1)主函數及程序框架、(2)車輛到達模塊、(3)車

輛離開模塊、(4)顯示車輛信息模塊，

(1)主函數

voidmain()

(

SqStackIn,Out;LinkQueueWait;

intch;

InitStack(&In);/*初始化停車站*/

InitStack(&Out);/*初始化讓路的臨時棧*/

InitQueue(&Wait);/*初始化通道*/

while(l)

(

printf("-------------------歡迎使用停車場管理系統

-------------------\n")；

printf("\t本系統由5011工作室開發，作者:鄧春國、段慶龍、梁偉明、丁

磊。\n\n");

printf("請輸入停車場的容量:")；

scanf("%d",&MAX);

printf("請輸入停車場的收費標準(元/小時

scanf("%f',&price);

printf("您輸入的停車場容量為％d位，費用為％2.1f元/小時。

\n",MAX,price);

printf("\n(l)車輛到達\n(2)車輛離開\n(3)停車場信息\n(4)退出系統3請

選擇\n");

while(l)

(

ch=getch();

switch(ch)

(

case49:arrive(&In,&Wait);break;/*車輛到達*/

case50:leave(&In,&Out,&Wait);break;/*車輛離開*/

case51:info(In,Wait);break;/*輸出車站信息*/

case52:{printf("謝謝使用!");exit(O);}/*退出主程序*/

default:printf("\n按鍵無效，請重新按鍵選擇！")；

}/*49-52分別表示“1"-"4"這四個按鍵的鍵值*/

system("CLS");

printf("---------------------歡迎使用停車場管理系統

---------------------\n")；

printf("\t本系統由CG工作室開發，作者:鄧春國、段慶龍、梁偉明、

丁磊。\n\n\n");

printf("您輸入的停車場容量為％d位，費用為％2.1f元/小時。

\n",MAX,price);

printf("\n(l)車輛到達\n(2)車輛離開\11(3)停車場信息\n(4)退出系統

\n請選擇\n");

)

}

12)車輛離開模塊

①算法分析

voidleave(SqStack*In,SqStack*Out,LinkQueue*W)/*車輛離開*/

(

introom;

Car*p,*t;QNode*q;

/*開場定義一個整型變量room,用來記錄要離開的車輛在停車場的位置，定義

車輛結點指針p和t和隊列結點指針q。*/

if(ln->top>0)/*有車*/

(

while(l)

(

printf("\n請輸入車在停車場的位置(l-%d)：",In->top);

scanf("%d",&room);

if(room>=l&&room<=In->top)break;

)

/*判斷停車場內是否有車，如果有車，就輸入要離開的車輛在停車場的位置，

否那么就提示停車場沒車。這里用了while循環語句，如果輸入的車輛位置超出范

圍，就要重新輸入。*/

while(In->top>room)/*車輛離開*/

(

Out->top++；

Out->stack[Out->top]=In->stack[In->top];

In->stack[In->top]=NULL;In->top-;

)

/*如果棧頂位置In->top大于要離開的車位置room(即要離開的車不在停車場

的門口)的話，在要離開的車輛前面的車就要先離開，開到臨時停車場，即臨時棧中，

因此Out所表示的臨時棧的棧頂top加1,用來表示臨時停車場增加1輛車；接著

把該車的信息拷貝到棧Out中，然后刪除棧In的棧頂(即這輛車開走)。*/

p=In->stack[In->top];

In->stack[In->top]=NULL;In->top—;

while(Out->top>=1)

In->top++;In->stack[In->top]=Out->stack[Out->top];

Out->stack[Out->top]=NULL;Out->top—;

)

/*直到要離開的車輛前面的車都開到臨時停車場之后，該車才離開，離開之后,

該車的信息結點In->stack[In->top]置空，然后棧頂In->top減1。之后就判斷臨時

停車場是否有車，有車就一輛一輛的開回停車場里面，因此停車場的棧頂In->top加

1,然后就把臨時停車場的車結點的信息拷貝到停車場的車結點上，接著刪除臨時停

車場車的結點(即Out->stack[Out->top]=NULL;Out->top--;)。*/

PRINT(p,room);

if((W->head!=W->rear)&&In->top<MAX)

(

q=W->head->next;t=q->data;In->top++；

printf("\n便道的％s號車進入車場第％d號停車位。

",t->num,In->top);

printf("\n請輸入現在的時間(格式“**:**"

scanf("%d:%d",&(t->reach.hour),&(t->reach.min));

W->head->next=q->next;

if(q==W->rear)W->rear=W->head;

In->stack[In->top]=t;

free(q);

)

/*判斷(W->head!=W->rear)&&In->top<MAX(即通道上是否有車及停車場

是否已滿)，如果便道有車且停車場未滿，通道的車便可進入停車場，此時指針q指

向便道的頭，即隊頭，然后停車場的棧頂In->top加1以便增加新的車輛，接著輸

入隊頭的車輛信息，即要進去停車場的車的信息，然后便道隊列的頭結點指向q1即

剛進入停車場的車的結點）的后繼結點，即原隊列中第二輛車的結點，接著判斷剛離

開的車是否是最后一輛車，如果是，就把隊列置空，即隊頭等于隊尾；之后就把結點

t（即要進入停車場的車）的信息拷貝到停車場棧頂的車中，最后釋放p的空間，即

原隊頭結點。*/

）

elseprintf（"\n停車場里沒有車\n"）;/*沒車*/

printf（"請按任意鍵返回"）；

getch();

②leave函數流程圖如圖4.1所示:

5測試分析

（開場）

測試數據及結果如Er

定義必要的變量

輸入2輛人的信息，如圖如2所示:

莖生場是否有否

再輸入2輛

"C:\Users\Administrator.PC-20141024YLPI\Desktop\Debug\Cppl.exe*

**停車場管理程序**

A-汽車進車場D--汽車出車場**

E-----退出程序

I辜里辛MA.D.E〉：A

1號車道

停車場管理程序Z

重;fi-汽車進車場D--汽車出車場**

停:E-----退出程序

［請選擇：＜A,D,E＞：A

|車牌為：2

賽場的時刻：2

該車已趺薦車場在：2號車道

E-----退出程序

蠡■該車先停在便道的第2個位置上

最后選擇車輛離開，輸入第2輛車離開，如圖

6課程設計總結

通過這次課程設計使我充分的理解了用棧和隊列實現模擬停車場的基本原理，

知道了棧的順序存儲構造和隊列的鏈式存儲構造的定義和算法描述，同時也學會了編

寫停車場問題的程序。雖然此次的程序不是很完備，沒有參加一些更完善的功能，但

是總體還是一個比較能表達數據構造知識點能力的程序了，當然只是相對于我這個初

學者來說。在剛開場編程的時候，我感到有點無從下手，但經過對題目的詳細分析和

思考之后，我就知道具體應該做什么，怎么做了。經過幾天和同學的一起研究，我完

成這個程序，我學到了很多東西，這是在課堂上無法做到的。

源程序

#include<stdio.h>

#include<stdlib.h>

#include<iostream.h>

#include<string.h>

#include<math.h>

#definesize1//停車場位置數

//模擬停車場的堆棧的性質；

typedefstructzanlind{

intnumber;〃汽車車號

intar_time;〃汽車到達時間

Jzanlnode;

typedefstruct{

zanlnode*base;〃停車場的堆棧底

zanlnode*top;〃停車場的堆棧頂

intstacksize_curren;

}stackhead;

〃堆棧的基本操作；

voidinitstack(stackhead&L)〃構造一個空棧

(

L.base=(zanlnode*)malloc(size*sizeof(zanlind));

if(!L.base)exit(O);

L.top=L.base;

L.stacksize_cuiTen=O;

)

voidpush(stackhead&L,zanlnodee)〃把元素e壓入s棧

*L.top++=e;

L.stacksize_curren++;

voidpop(stackhead&L,zanInode&e)〃把元素e彈出s棧

(

if(L.top==L.base)

(

coutvv”停車場為空!!*';

return;

)

e=*-L.top;

L.stacksize_curren—;

)

〃模擬便道的隊列的性質；

typedefstructduiiie{

intnumber;〃汽車車號

intar_time;〃汽車到達時間

structduilie*next;

}*queueptr;

typedefstruct{

queueptrfront;〃便道的隊列的對頭

queueptrrear;//便道的隊列的隊尾

intlength;

}linkqueue;

〃隊列的基本操作；

voidinitqueue(linkqueue&q)〃構造一個空隊列

(

q.front=q,rear=(queueptr)malloc(sizeof(duilie));

if(!q.front||!q.rear)

exit(O);

q.front->next=NULL;

q.length=0;

)

voidenqueue(linkqueue&q,intnumber,intar_time)〃把元素的插入隊歹lj(屬性為number,ar_time)

{

queueptrp;

p=(queueptr)malloc(sizeof(duilie));

if(!p)exit(O);

p->number=number;

p->ar_time=ar_time;

p->next=NULL;

q.rear->next=p;

q.rear=p;

q.length++;

voidpopqueue(linkqueue&q,queueptr&w)//把元素的插入隊列(屬性為number,ar_time)

{

queueptrp;

if(q.front==q.rear)

(

cout?”停車場的通道為空!!n?endl;

return;

)

p=q.front->next;

w二p;

q.front->next=p->next;

q.length-;

if(q.rear==p)q.front=q.rear;

)

voidjinru(stackhead&st,linkqueue&q)〃對進入停車場的汽車的處理；

{

intnumber,time_a;

cout<〈”車牌為：°;

cin?number;

cout<<”進場的時刻六

cin?time_a;

if(st.stacksize_curren<2)

(

zanlnodee;

e.number=number;

e.ar_time=time_a;

push(st,e);

cout?n該車已進入停車場在：n?st.stacksize_curren?"號車道”<vendl?endl;

)

else

(

enqueue(q,number,time_a);

coutvv”停車場已滿，該車先停在便道的第”<vq.length?”個位置上”<vendl;

)

)

voidlikai(stackhead&st,stackhead&sl,linkqueue&q)〃對離開的汽車的處理;

{//st堆棧為停車場，si堆棧為倒車場

intnumber,time_d,flag=1,money,arrivaltime;//q為便道隊歹U

coutvv”車牌為:"；

cin?number;

cout?n出場的時刻：

cin?time_d;

zanlnodee,q_to_s;

queueptrw;

while(flag)〃找到要開出的車，并彈出停車場棧

pop(st,e);

push(sl,e);

if(e.number二二number)

(

f!ag=O;

money=(time_d-e.ar_time)*2;

arrivaltime=e.ar_time;

)

)

pop(sl,e);〃把臨時堆棧的第一輛車(要離開的)去掉；

while(sLstacksize_curren)〃把倒車場的車倒回停車場

(

pop(sl,e);

push(st,e);

)

if(st.stacksize_curren<2&&q.1ength!=0)〃停車場有,空位，便道上的車開進入停車場

(

popqueue(q,w);

q_to_s.ar_time=time_d;

q_to_s.number=w->number;

push(st,q_to_s);

cout?n車牌為"《q_to_s.numberv<”的車已從通道進入停車場，所在的停車位

^9："?st.stacksize_curren?endl?endl;

)

cout?"\n收據"<<endl;

cout?u======================車牌號：n?number?endl;

cout?u===================================================n?e