《數(shù)據(jù)結(jié)構(gòu)報(bào)告 停車場問題》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)報(bào)告 停車場問題（12頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、
⒈ 問題描述：停車場管理問題
[問題描述] 設(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)，并且仍
2、然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。
[實(shí)現(xiàn)要求] 要求程序輸出每輛車到達(dá)后的停車位置(停車場或便道上)，以及某輛車離開停車場時(shí)應(yīng)交納的費(fèi)用和它在停車場內(nèi)停留的時(shí)間。
[實(shí)現(xiàn)提示] 汽車的模擬輸入信息格式可以是：(到達(dá)／離去，汽車牌照號(hào)碼，到達(dá)／離去的時(shí)刻)。例如，(‘A’，，1，5)表示1號(hào)牌照車在5這個(gè)時(shí)刻到達(dá)，而(‘D’，，5，20)表示5號(hào)牌照車在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)
3、的，棧是一種只能在叫做棧的一段進(jìn)行進(jìn)棧或者出棧操作的線性數(shù)據(jù)結(jié)構(gòu)。棧的主要特點(diǎn)是”后進(jìn)先出”，即后進(jìn)棧的元素先處理。停車場的容量即為棧的存儲(chǔ)空間，停車場的車輛的?？渴菬o秩序的，因此采用鏈?zhǔn)酱鎯?chǔ)的方式更適合，也方便車輛的調(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)先出”的移動(dòng)的思想。停車場的入口就是隊(duì)列的隊(duì)首，停車場的出口就是隊(duì)列的隊(duì)尾。
⑵ 主控及功能模塊
4、層次結(jié)構(gòu)；
2.1設(shè)定棧的抽象數(shù)據(jù)類型定義為：
ADT stack{
數(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,該棧可存放n個(gè)元素。
push(&S, e)
初始條件：棧S已存在。
操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。
pop(&S, &e)
初始條件：棧S已存在。
操作結(jié)果：刪除S的棧頂元素，并以e返回其值。
DestroyStack(&S)
初始條件：棧S已存在。
操作結(jié)果：銷毀棧S。
5、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()。
}ADT stack
2.2 設(shè)定隊(duì)列的抽象數(shù)據(jù)類
6、型定義為：
ADT Queue{
數(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)
7、
初始條件：隊(duì)列Q已存在。
操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長度。
GetHead(Q, &e)
初始條件：Q為非空隊(duì)列。
操作結(jié)果：用e返回Q的隊(duì)頭元素。
EnQueue(&Q, e)
初始條件：隊(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()失敗，則操作失敗。
}ADT Queue
8、
2.3詳細(xì)設(shè)計(jì)
車輛信息類型
typedef struct node{
int passport; //存儲(chǔ)車輛牌照信息
int time; //存儲(chǔ)進(jìn)場時(shí)間信息
}node;
2．棧類型（停車場）
typedef struct stack{ //定義停車場棧類型
node *base;
node *top;
int stacksize;
}stack;
void initstack(stack &S,int n){ //構(gòu)造空棧
S.base=(node *)malloc(n*sizeof(node));
S.top=S.base;
9、
S.stacksize=n;
}
void push(stack &S,node e){ //入棧函數(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++;
}
}
void wait(stack &S){
if((S.top-S.base)==(S.stacksize-1)&&count!=0){
node temp;
DeQueu
10、e(Q,temp);
temp.time=times;
push(S,temp);
}
}
int pop(stack &S,node &e){ //出棧函數(shù)
if(S.top==S.base)return ERROR; //如果?？談t返回ERROR
--S.top;
e.passport=S.top->passport;
e.time=S.top->time;
return OK;
}
3．隊(duì)列類型（便道）
typedef struct Qnode{ //定義便道隊(duì)列類型
node Qdata;
struct Qnode
11、*next;
}Qnode;
typedef struct {
Qnode *front;
Qnode *rear;
}LinkQueue;
void EnQueue(LinkQueue &Q,node e){ //入隊(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)
12、 Q.rear->next=q;
Q.rear=q;
}
void DeQueue(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ù)處理語句
#define ERROR 0
#define O
13、K 1
#define NULL 0
int count=0; //隊(duì)列是否為空的標(biāo)志
int times;
stack s,temp; //初始化棧
LinkQueue Q; //初始化隊(duì)列
5．主函數(shù)及其他函數(shù)的算法
void main(){
int n,exit;
float money;
char info;
int pass;
Q.front=NULL;
Q.rear=(Qnode *)malloc(sizeof(Qnode));
Q.rear->next=Q.rear;
printf("停車場容量:");
scanf("
14、%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
15、')printf("請輸入離場時(shí)間:");
scanf("%d",×);
if(info=='3'){exit=OK;}
else if(info=='1'){
int i,j;
node a;
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 *t
16、p;
tp=Q.front;
if(tp==NULL){}
else{
j=1;
while(tp!=Q.rear){
tp=tp->next;
j++;
}
printf("停車位置(便道):%d\n",j);
}
}
else if(info=='2'){
node d;
int tp,counter=0;
do{
counter++;
tp=pop(s,d);
while(tp!=ERROR){
if(d.passp
17、ort==pass){
float m;
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{
pus
18、h(temp,d);
d.passport=0;
tp=ERROR;
}
}
}while(d.passport==0||counter>n);
}
else if(info!='1'&&info!='2'&&info!='3'){}
}
}
⑶ 主要功能模塊的輸入、處理(算法框架描述)和輸出；
⑷ 功能模塊之間的調(diào)用與被調(diào)用關(guān)系等。
（1）輸入車輛數(shù)據(jù)：1為到達(dá)，2為離去，3為結(jié)束程序。
（2）接著輸入車輛的牌照信息
（3）若為到達(dá)的車輛，輸入進(jìn)場信息，若為離去的車輛
19、，輸入離場信息。
（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
20、 停車位置(便道):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
4. 運(yùn)行結(jié)果
（1）進(jìn)入停車場
(2) 離開停車場
(3) 等待停車
5. 程序源代碼
#include
#include
#define ERROR 0
#define OK 1
#define NULL 0
typedef struct node{ //定義車輛信息數(shù)據(jù)結(jié)構(gòu)
21、 int passport; //存儲(chǔ)車輛牌照信息
int time; //存儲(chǔ)進(jìn)場時(shí)間信息
}node;
typedef struct stack{ //定義停車場棧類型
node *base;
node *top;
int stacksize;
}stack;
typedef struct Qnode{ //定義便道隊(duì)列類型
node Qdata;
struct Qnode *next;
}Qnode;
typedef struct {
Qnode *front;
Qnode *rear;
}LinkQ
22、ueue;
int count=0; //隊(duì)列是否為空的標(biāo)志
int times;
stack s,temp; //初始化棧
LinkQueue Q; //初始化隊(duì)列
void initstack(stack &S,int n){ //構(gòu)造空棧
S.base=(node *)malloc(n*sizeof(node));
S.top=S.base;
S.stacksize=n;
}
void EnQueue(LinkQueue &Q,node e); //入隊(duì)函數(shù)
void DeQueue(LinkQueue &Q,node &e
23、); //出隊(duì)函數(shù)
void push(stack &S,node e){ //入棧函數(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++;
}
}
int pop(stack &S,node &e){ //出棧函數(shù)
if(S.top==S.base)return ERROR; //如果棧空則返回ERROR
--S.top;
24、e.passport=S.top->passport;
e.time=S.top->time;
return OK;
}
void wait(stack &S){
if((S.top-S.base)==(S.stacksize-1)&&count!=0){
node temp;
DeQueue(Q,temp);
temp.time=times;
push(S,temp);
}
}
void EnQueue(LinkQueue &Q,node e){ //入隊(duì)函數(shù)
Qnode *q;
q=(Qnode *)malloc(sizeof(
25、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;
}
void DeQueue(LinkQueue &Q,node &e){ //出隊(duì)函數(shù)
if(Q.rear==NULL){}
else {
e.passport=Q.front->Qdata.passport;
e.time=Q.fron
26、t->Qdata.time;
Q.front=Q.front->next;
if(Q.front==NULL){Q.rear=Q.front;count=0;}
}
}
void main(){
int n,exit;
float money;
char info;
int pass;
Q.front=NULL;
Q.rear=(Qnode *)malloc(sizeof(Qnode));
Q.rear->next=Q.rear;
printf("停車場容量:");
scanf("%d",&n);
initstack(s,n);
27、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",×);
28、if(info=='3'){exit=OK;}
else if(info=='1'){
int i,j;
node a;
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{
29、
j=1;
while(tp!=Q.rear){
tp=tp->next;
j++;
}
printf("停車位置(便道):%d\n",j);
}
}
else if(info=='2'){
node d;
int tp,counter=0;
do{
counter++;
tp=pop(s,d);
while(tp!=ERROR){
if(d.passport==pass){
float m;
m=(times-d.ti
30、me)*money;
printf("停留時(shí)間:%d 需交費(fèi):%f\n",times-d.time,m);
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;
}
31、}
}while(d.passport==0||counter>n);
}
else if(info!='1'&&info!='2'&&info!='3'){}
}
}
6. 心得體會(huì)
（1）一開始在調(diào)試程序時(shí)遇到了內(nèi)存錯(cuò)誤，經(jīng)過調(diào)試，找到了引起內(nèi)存錯(cuò)誤的原因：即在建立隊(duì)頭指針與隊(duì)尾指針時(shí)沒有對指針進(jìn)行初始化(沒有為指針動(dòng)態(tài)分配空間)。問題得到解決。
（2）在Wait函數(shù)中的If語句處，一開始的算法有些問題，導(dǎo)致實(shí)現(xiàn)的功能與設(shè)想的有出入，無法得到正確的結(jié)果。
（3）本程序中：車輛到達(dá),離去時(shí)的時(shí)間復(fù)雜度均為：O(n)。本程序空間復(fù)雜度為：O(n)。
（4）在本次課程設(shè)計(jì)中不僅加深了對棧和隊(duì)列等數(shù)據(jù)結(jié)構(gòu)的理解和掌握，同時(shí)一定程度上提高了自己程序設(shè)計(jì)和閱讀程序的能力。本次課程設(shè)計(jì)提高了我們的專業(yè)知識(shí)，使自己所學(xué)的內(nèi)容運(yùn)用到實(shí)際中來，也增強(qiáng)了實(shí)際操作能力，為以后的工作學(xué)習(xí)提供了一個(gè)良好的鋪墊。
數(shù)據(jù)結(jié)構(gòu)報(bào)告 停車場問題
