1、數據結構設計：停車場管理1 問題描述設停車場是一個可停放n 輛汽車的狹長通道， 且只有一個門可供出入。 汽車在停車場內按車輛到達時間的先后順序， 依次由北向南排列 （門在最南端， 最先到達的第一輛車停放在車場的最北端） ，若車場內已停滿n 輛汽車，則后來的汽車只能在門外的便道上等候， 一旦有車開走， 則排在便道上的第一輛汽車即可開入； 當停車場內某輛車要離開時， 在它之后進入的車輛必須先退出車場為它讓路， 待該輛車開出大門外，其他車輛再按原順序進入車場， 每輛停放在車場的車在它離開停車場時必須按它停留 的時間長短交納費用。2 需求分析( 1)根據車輛到達停車場到車輛離開停車場時所停留的時間進行

2、計時收費。( 2)當有車輛從停車場離開時，等待的車輛按順序進入停車場停放。實現停車 場的調度功能。( 3)用順序棧來表示停車場，鏈隊表示停車場外的便道。( 4)顯示停車場信息和便道信息。( 5)程序執行的命令為： 車輛進入停車場 車輛離開停車場 顯示停車 場的信息。3 概要設計4 1 抽象數據類型定義( 1)棧的抽象數據類型定義AST Stack數據對象：D=ai|ai 6 ElemSet,i=1,2，,n, n >0數據關系：R1=<ai-1,ai>|ai-1,ai 6 D, i=2,n約定 an 端為棧頂， a1 端為棧底 。基本操作：InitStack(&S)操

3、作結果：構造一個空棧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(&

4、amp;S,&e)初始條件：棧S 已存在且非空。操作結果：刪除S的棧頂元素，并用e返回其值。StackTraverse(S,visit()初始條件：棧S 已存在且非空。操作結果： 從棧底到棧頂依次對S 的每個數據元素調用函數visit() 。 一旦 visit()失敗，則操作失效。ADT Stack( 2)隊列的抽象數據類型定義ADT Queue數據對象：D=ai|ai 6 ElemSet,i=1,2，,n,n>0數據關系：R1=<ai-1,ai>|ai-1,ai 6 D,i=2,n約定其中 a1 端為隊列頭， an 為隊列尾。基本操作：InitQueue(&

5、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 已存在。

6、操作結果：插入元素 e 為 Q 的新的隊尾元素。DeQueue(&Q,&e)初始條件： Q 為非空隊列。操作結果：刪除Q的隊頭元素，并用e返回其值。QueueTraverse(Q,visit()初始條件： Q 已存在且非空。操作結果：從隊頭到隊尾，依次對Q 的每個數據元素調用函數visit() 。一旦visit() 失敗，則操作失敗。ADT Queue3 2 模塊劃分本程序包括六個模塊：( 1)主程序模塊void main()初始化停車站；初始化讓路的臨時棧；初始化通道；輸出主菜單：車輛到達、車輛離開與計費、查看停車場信息；（ 2）入場模塊int arrive（SqStack

7、*In,LinkQueue *W）車輛進入停車場；計算停車費用（ 3）出場模塊void leave（SqStack *In,SqStack *Out,LinkQueue *W）車輛離開停車場；（ 4）輸出模塊void info（SqStack S,LinkQueue W）輸出停車場信息；（ 5）棧模塊 實現棧的抽象數據類型（ 6）隊列模塊 實現隊列的抽象數據類型124 詳細設計4 1 數據類型的定義int MAX; /* 定義一個全局變量用來存儲車庫最大容量*/float price;/* 定義一個全局變量用來存儲每車每小時的費用 */ typedef struct time int hour

8、;int min;Time; /* 時間結點 */ typedef struct node char num10;Time reach;Time leave;Car; /* 車輛信息結點 */typedef struct NODECar *stack100;int top;SqStack; /*停車站 */ typedef struct car Car *data;struct car *next;QNode;typedef struct Node QNode *head;QNode *rear;LinkQueue; /* 通道 */4 2 主要模塊的算法描述本程序主要分為四部分： ( 1)主

9、函數及程序框架、( 2)車輛到達模塊、( 3)車輛離開模塊、( 4 )顯示車輛信息模塊，( 1)主函數void main()SqStack In,Out; LinkQueue Wait;int ch;InitStack(&In); /* 初始化停車站*/InitStack(&Out); /* 初始化讓路的臨時棧*/InitQueue(&Wait); /* 初始化通道 */while(1)printf(" 歡迎使用停車場管理系統n");printf("t 本系統由5011工作室開發，作者:鄧春國、段慶龍、梁偉明、丁磊。 nn");p

10、rintf(" 請輸入停車場的容量:");scanf("%d",&MAX);printf(" 請輸入停車場的收費標準(元/小時 ):");scanf("%f",&price);printf("您輸入的停車場容量為d位，費用為2.1f元/小時。n",MAX,price);printf("n (1)車輛到達n(2)車輛離開n(3)停車場信息n(4)退出系統n請選擇 n");while(1)ch=getch();switch(ch)case 49:arrive(&a

11、mp;In,&Wait);break; /* 車輛到達 */case 50:leave(&In,&Out,&Wait);break; /* 車輛離開 */case 51:info(In,Wait);break; /*輸出車站信息*/case 52:printf("謝謝使用！ ");exit(0); /* 退出主程序 */ default:printf("n 按鍵無效，請重新按鍵選擇！ ");/*49 -52分別表示“1 ” -“4”這四個按鍵的鍵值*/system("CLS");printf("

12、; 歡迎使用停車場管理系統n");printf("t本系統由CG工作室開發，作者：鄧春國、段慶龍、梁偉明、丁磊。 nnn");printf("您輸入的停車場容量為 d位，費用為2.1f元/小時。n",MAX,price);printf("n (1)車輛到達n(2)車輛離開n(3)停車場信息n(4)退出系統 n請選擇n");( 2)車輛離開模塊算法分析void leave(SqStack *In,SqStack *Out,LinkQueue *W) /* 車輛離開 */int room;Car *p,*t;QNode *q;/

13、* 開始定義一個整型變量room， 用來記錄要離開的車輛在停車場的位置， 定義車輛結點指針 p 和 t 和隊列結點指針 q。 */if(In->top>0) /* 有車 */while(1) printf("n 請輸入車在停車場的位置(1-%d) ： ",In->top);scanf("%d",&room);if(room>=1&&room<=In->top) break;/* 判斷停車場內是否有車，如果有車，就輸入要離開的車輛在停車場的位置，否則就提示停車場沒車。這里用了 while 循環語句

14、，如果輸入的車輛位置超出范圍，就要重新輸入。 */while(In->top>room) /* 車輛離開 */ Out->top+;Out->stackOut->top=In->stackIn->top; In->stackIn->top=NULL;In->top-;/*如果棧頂位置In->top大于要離開的車位置room(即要離開的車不在停車場 的門口) 的話， 在要離開的車輛前面的車就要先離開， 開到臨時停車場， 即臨時棧中， 因此Out所表示的臨時棧的棧頂top力口1,用來表示臨時停車場增加1輛車；接著 把該車的信息拷貝到

15、棧Out 中，然后刪除棧In 的棧頂(即這輛車開走) 。 */p=In->stackIn->top;In->stackIn->top=NULL;In->top-;while(Out->top>=1) In->top+;In->stackIn->top=Out->stackOut->top; Out->stackOut->top=NULL; Out->top-;/* 直到要離開的車輛前面的車都開到臨時停車場之后，該車才離開，離開之后，該車的信息結點 In->stackIn->top 置空，然后棧

16、頂In->top 減 1。 之后就判斷臨時停車場是否有車， 有車就一輛一輛的開回停車場里面， 因此停車場的棧頂In->top 加1 ，然后就把臨時停車場的車結點的信息拷貝到停車場的車結點上，接著刪除臨時停車場車的結點(即 Out->stackOut->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便道的$

17、號車進入車場第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->stackIn->top=t;free(q);/* 判斷 (W->head!=W->rear)&&

18、In->top<MAX (即通道上是否有車及停車場是否已滿) ，如果便道有車且停車場未滿，通道的車便可進入停車場，此時指針 q 指向便道的頭，即隊頭，然后停車場的棧頂 In->top 加 1 以便增加新的車輛，接著輸入隊頭的車輛信息，即要進去停車場的車的信息，然后便道隊列的頭結點指向q (即剛進入停車場的車的結點) 的后繼結點， 即原隊列中第二輛車的結點， 接著判斷剛離開的車是否是最后一輛車，如果是，就把隊列置空，即隊頭等于隊尾；之后就把結點t (即要進入停車場的車)的信息拷貝到停車場棧頂的車中，最后釋放p的空間，即原隊頭結點。 */else printf("n 停

19、車場里沒有車n"); /* 沒車 */printf("請按任意鍵返回");getch()；5測試分析測試數據及結果如下：輸入2輛車的信息，如圖5.2所示:再輸入2輛車的信息，如圖最后選擇車輛離開，輸入第 2輛車離開，如圖請選擇停車場甘珅程.序進車場所在的停車位為車牌號進車場時刻：出車場時刻：停留時間,CAUsers Adm nii-trat?r.PC-20141024YLPr Des let g pDeb dgC16課程設計總結通過這次課程設計使我充分的理解了用棧和隊列實現模擬停車場的基本原理，知道了棧的順序存儲結構和隊列的鏈式存儲結構的定義和算法描述，同時也學會

20、了編寫停車場問題的程序。雖然此次的程序不是很完備，沒有加入一些更完善的功能，但是 總體還是一個比較能體現數據結構知識點能力的程序了，當然只是相對于我這個初學者來說。在剛開始編程的時候，我感到有點無從下手，但經過對題目的詳細分析和思 考之后，我就知道具體應該做什么，怎么做了。經過幾天和同學的一起研究，我完成 這個程序，我學到了很多東西，這是在課堂上無法做到的。源程序#include<stdio.h>#include <stdlib.h>#include<iostream.h>#include<string.h>#include<math.h&

21、gt;#define size 1/ 停車場位置數/模擬停車場的堆棧的性質；typedef struct zanlindint number;/汽車車號int ar_time;/ 汽車到達時間zanInode;typedef structzanInode *base; /停車場的堆棧底zanInode *top; /停車場的堆棧頂int stacksize_curren;stackhead;/堆棧的基本操作；void initstack(stackhead &L)/構造一個空棧L.base=(zanInode*)malloc(size*sizeof(zanlind);if(!L.bas

22、e) exit(0);L.top=L.base;L.stacksize_curren=0;void push(stackhead &L,zanInode e) / 把元素 e 壓入 s 棧*L.top+=e;L.stacksize_curren+;void pop(stackhead &L,zanInode &e)/把元素 e 彈出 s 棧if(L.top=L.base)cout<<" 停車場為空!"return;e=*-L.top;L.stacksize_curren-;/模擬便道的隊列的性質；typedef struct duilie

23、int number;/汽車車號int ar_time;/汽車到達時間struct duilie *next;*queueptr;typedef structqueueptr front;/便道的隊列的對頭queueptr rear;/便道的隊列的隊尾int length;linkqueue;/隊列的基本操作；void initqueue(linkqueue &q) / 構造一個空隊列 q.front=q.rear=(queueptr)malloc(sizeof(duilie);if(!q.front|!q.rear)exit(0);q.front->next=NULL;q.le

24、ngth=0;void enqueue(linkqueue &q,int number,int ar_time) / 把元素的插入隊列(屬性為 number ， ar_time ) queueptr p;p=(queueptr)malloc(sizeof(duilie);if(!p) exit(0);p->number=number;p->ar_time=ar_time;p->next=NULL;q.rear->next=p;q.rear=p;q.length+;void popqueue(linkqueue &q,queueptr &w) /

25、把元素的插入隊列(屬性為number， ar_time )queueptr p;if(q.front=q.rear)cout<<" 停車場的通道為空! !"<<endl;return;p=q.front->next;w=p;q.front->next=p->next;q.length-;if(q.rear=p) q.front=q.rear;void jinru(stackhead &st,linkqueue &q)/對進入停車場的汽車的處理；int number,time_a;cout<<"

26、車牌為： "cin>>number;cout<<" 進場的時刻 :"cin>>time_a;if(st.stacksize_curren<2)zanInode e;e.number=number;e.ar_time=time_a;push(st,e);cout<< " 該車已進入停車場在 : "<<st.stacksize_curren<<" 號車道 "<<endl<<endl;elseenqueue(q,number,ti

27、me_a);cout<<" 停車場已滿，該車先停在便道的第"<<q.length<<" 個位置上 "<<endl;void likai(stackhead &st,stackhead &sl,linkqueue &q) / 對離開的汽車的處理；/st 堆棧為停車場， sl 堆棧為倒車場int number,time_d,flag=1,money,arrivaltime; /q 為便道隊列cout<<" 車牌為： "cin>>number;c

28、out<<" 出場的時刻： "cin>>time_d;zanInode e,q_to_s;queueptr w;while(flag)/找到要開出的車，并彈出停車場棧pop(st,e);push(sl,e);if(e.number=number)flag=0;money=(time_d-e.ar_time)*2;arrivaltime=e.ar_time;pop(sl,e);/把臨時堆棧的第一輛車(要離開的)去掉；while(sl.stacksize_curren) / 把倒車場的車倒回停車場pop(sl,e);push(st,e);if(st.st

29、acksize_curren<2&&q.length!=0) / 停車場有空位，便道上的車開進入停車場(popqueue(q,w);q_to_s.ar_time=time_d;q_to_s.number=w->number;push(st,q_to_s);cout<<"車牌為"<<q_to_s.number<<"的車 已從通道進入停車場，所在 的停車位 為:"<<st.stacksize_curren<<endl<<endl;cout<<"n收 據"<<endl;cout<<"= 車牌號："<<number<<endl;cout<<"="<<endl;cout<<"|進車場時刻|出車場時刻|停留時間|應付(元)|"<<endl;c