《數(shù)據(jù)結(jié)構(gòu)報告 停車場問題》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結(jié)構(gòu)報告 停車場問題（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
⒈ 問題描述：停車場管理問題
[問題描述] 設有一個可以停放n輛汽車的狹長停車場，它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進入停車場。停車場內(nèi)如有某輛車要開走，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進場。每輛車在離開停車場時，都應根據(jù)它在停車場內(nèi)停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，并且仍
2、然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。
[實現(xiàn)要求] 要求程序輸出每輛車到達后的停車位置(停車場或便道上)，以及某輛車離開停車場時應交納的費用和它在停車場內(nèi)停留的時間。
[實現(xiàn)提示] 汽車的模擬輸入信息格式可以是：(到達／離去，汽車牌照號碼，到達／離去的時刻)。例如，(‘A’，，1，5)表示1號牌照車在5這個時刻到達，而(‘D’，，5，20)表示5號牌照車在20這個時刻離去。整個程序可以在輸入信息為(‘E’，0，0)時結(jié)束。本題可用棧和隊列來實現(xiàn)。
⒉ 設計：
⑴ 數(shù)據(jù)結(jié)構(gòu)設計和核心算法設計描述；
停車場管理系統(tǒng)是充分利用數(shù)據(jù)結(jié)構(gòu)中棧和隊列的思想實現(xiàn)
3、的，棧是一種只能在叫做棧的一段進行進?；蛘叱鰲２僮鞯木€性數(shù)據(jù)結(jié)構(gòu)。棧的主要特點是”后進先出”，即后進棧的元素先處理。停車場的容量即為棧的存儲空間，停車場的車輛的?？渴菬o秩序的，因此采用鏈式存儲的方式更適合，也方便車輛的調(diào)度。
隊列是限定僅能在表的一端進行插入，在表的另一端進行刪除的線性表。隊列中可以插入的一端稱為隊尾，可以刪除的一端稱為隊首。把一個元素插入隊列中的操作為進隊，隊列中刪除一個元素的操作為出隊。隊列存取操作符合：先進先出。停車場的車輛到達停車和車輛的離開的管理方式就是采用隊列的“先進先出”的移動的思想。停車場的入口就是隊列的隊首，停車場的出口就是隊列的隊尾。
⑵ 主控及功能模塊
4、層次結(jié)構(gòu)；
2.1設定棧的抽象數(shù)據(jù)類型定義為：
ADT stack{
數(shù)據(jù)對象：D={ai|ai∈charset, i=1,2,……,n,n≥0}
數(shù)據(jù)關系：R1={|ai-1,ai∈D,i=2……,n}
基本操作：
initstack(&S, n)
操作結(jié)果：構(gòu)造一個空棧S,該棧可存放n個元素。
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中的每個元素調(diào)用函數(shù)visit()。
}ADT stack
2.2 設定隊列的抽象數(shù)據(jù)類
6、型定義為：
ADT Queue{
數(shù)據(jù)對象：D={ai|ai∈ElemSet, i=1,2,……,n,n≥0}
數(shù)據(jù)關系：R1={|ai-1,ai∈D,i=2……,n}
基本操作：
InitQueue(&Q)
操作結(jié)果：構(gòu)造一個空隊列Q。
DestroyQueue(&Q)
初始條件：隊列Q已存在。
操作結(jié)果：隊列Q被銷毀，不再存在。
ClearQueue(&Q)
初始條件：隊列Q已存在。
操作結(jié)果：將Q清為空隊列。
QueueEmpty(&Q)
初始條件：隊列Q已存在。
操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。
QueueLength(Q)
7、
初始條件：隊列Q已存在。
操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。
GetHead(Q, &e)
初始條件：Q為非空隊列。
操作結(jié)果：用e返回Q的隊頭元素。
EnQueue(&Q, e)
初始條件：隊列Q已存在。
操作結(jié)果：插入元素e為Q的新的隊尾元素。
DeQueue(&Q, &e)
初始條件：Q為非空隊列。
操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。
QueueTraverse(Q, visit())
初始條件：Q已存在且非空。
操作結(jié)果：從隊頭到隊尾，依次對Q的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。
}ADT Queue
8、
2.3詳細設計
車輛信息類型
typedef struct node{
int passport; //存儲車輛牌照信息
int time; //存儲進場時間信息
}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)用入隊函數(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．隊列類型（便道）
typedef struct Qnode{ //定義便道隊列類型
node Qdata;
struct Qnode
11、*next;
}Qnode;
typedef struct {
Qnode *front;
Qnode *rear;
}LinkQueue;
void EnQueue(LinkQueue &Q,node e){ //入隊函數(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é)點前隊空，頭指針指向節(jié)點
12、 Q.rear->next=q;
Q.rear=q;
}
void DeQueue(LinkQueue &Q,node &e){ //出隊函數(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．全局變量及編譯預處理語句
#define ERROR 0
#define O
13、K 1
#define NULL 0
int count=0; //隊列是否為空的標志
int times;
stack s,temp; //初始化棧
LinkQueue Q; //初始化隊列
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("停車場費率(元/小時):");
scanf("%f",&money);
while(exit!=OK){
printf("\n請選擇車輛狀態(tài)\n1到達 2離去 3結(jié)束:");
getchar();
scanf("%c",&info);
printf("請輸入車輛牌照:");
scanf("%d",&pass);
if(info==1||info==3)printf("請輸入進場時間:");
if(info==2)prin
15、tf("請輸入離場時間:");
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 *tp;
tp=
16、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.passport==pass){
17、
float m;
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);
18、 d.passport=0;
tp=ERROR;
}
}
}while(d.passport==0||counter>n);
}
else if(info!=1&&info!=2&&info!=3){}
}
}
⑶ 主要功能模塊的輸入、處理(算法框架描述)和輸出；
⑷ 功能模塊之間的調(diào)用與被調(diào)用關系等。
（1）輸入車輛數(shù)據(jù)：1為到達，2為離去，3為結(jié)束程序。
（2）接著輸入車輛的牌照信息
（3）若為到達的車輛，輸入進場信息，若為離去的車輛，輸入離場信息。
（4）若車輛到達
19、，可得到車輛的停放位置信息，若車輛離去，可得到車輛的停放時間（在便道上的停放時間除外），以及應該交納的費用。
（5）本程序不斷循環(huán)要求輸入車輛信息，直到輸入的車輛數(shù)據(jù)為E時，程序結(jié)束。
⒊ 測試： 測試范例，測試結(jié)果，測試結(jié)果的分析與討論，測試過程中遇到的主要問題及所采用的解決措施。
測試數(shù)據(jù)：設n=2
輸入數(shù)據(jù)：2
輸出：
停車場容量:2
停車場費率:6
A，1，5 停車位置(停車場內(nèi)):1
A，2，10 停車位置(停車場內(nèi)):2
D，1，15 停留時間:10 需交費:60.00
A，3，20 停車位置(停車場內(nèi)):2
A，4，25 停車位置(便道):1
A，5，3
20、0 停車位置(便道):2
D，2，35 停留時間:25 需交費:150.00
D，4，40 停留時間:5 需交費:30.00
E，0，0
4. 運行結(jié)果
（1）進入停車場
(2) 離開停車場
(3) 等待停車
5. 程序源代碼
#include
#include
#define ERROR 0
#define OK 1
#define NULL 0
typedef struct node{ //定義車輛信息數(shù)據(jù)結(jié)構(gòu)
int passport;
21、 //存儲車輛牌照信息
int time; //存儲進場時間信息
}node;
typedef struct stack{ //定義停車場棧類型
node *base;
node *top;
int stacksize;
}stack;
typedef struct Qnode{ //定義便道隊列類型
node Qdata;
struct Qnode *next;
}Qnode;
typedef struct {
Qnode *front;
Qnode *rear;
}LinkQueue;
int count
22、=0; //隊列是否為空的標志
int times;
stack s,temp; //初始化棧
LinkQueue Q; //初始化隊列
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); //入隊函數(shù)
void DeQueue(LinkQueue &Q,node &e); //出隊函數(shù)
void p
23、ush(stack &S,node e){ //入棧函數(shù)
if((S.top-S.base)>=S.stacksize){EnQueue(Q,e);} //如果棧滿則調(diào)用入隊函數(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; //如果?？談t返回ERROR
--S.top;
e.passport=S.top->
24、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){ //入隊函數(shù)
Qnode *q;
q=(Qnode *)malloc(sizeof(Qnode));
q->Qdat
25、a.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;
}
void DeQueue(LinkQueue &Q,node &e){ //出隊函數(shù)
if(Q.rear==NULL){}
else {
e.passport=Q.front->Qdata.passport;
e.time=Q.front->Qdata.time;
26、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);
initstack(temp,n);
27、
printf("停車場費率(元/小時):");
scanf("%f",&money);
while(exit!=OK){
printf("\n請選擇車輛狀態(tài)\n1到達 2離去 3結(jié)束:");
scanf("%c",&info);
printf("請輸入車輛牌照:");
scanf("%d",&pass);
if(info==1||info==3)printf("請輸入進場時間:");
if(info==2)printf("請輸入離場時間:");
scanf("%d",×);
if(info==3){exit=OK;}
28、 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{
j=1;
while(tp!=Q.r
29、ear){
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.time)*money;
printf("停留時間
30、:%d 需交費:%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;
}
}
}while(d.passport==0||co
31、unter>n);
}
else if(info!=1&&info!=2&&info!=3){}
}
}
6. 心得體會
（1）一開始在調(diào)試程序時遇到了內(nèi)存錯誤，經(jīng)過調(diào)試，找到了引起內(nèi)存錯誤的原因：即在建立隊頭指針與隊尾指針時沒有對指針進行初始化(沒有為指針動態(tài)分配空間)。問題得到解決。
（2）在Wait函數(shù)中的If語句處，一開始的算法有些問題，導致實現(xiàn)的功能與設想的有出入，無法得到正確的結(jié)果。
（3）本程序中：車輛到達,離去時的時間復雜度均為：O(n)。本程序空間復雜度為：O(n)。
（4）在本次課程設計中不僅加深了對棧和隊列等數(shù)據(jù)結(jié)構(gòu)的理解和掌握，同時一定程度上提高了自己程序設計和閱讀程序的能力。本次課程設計提高了我們的專業(yè)知識，使自己所學的內(nèi)容運用到實際中來，也增強了實際操作能力，為以后的工作學習提供了一個良好的鋪墊。
數(shù)據(jù)結(jié)構(gòu)報告 停車場問題
