數(shù)據(jù)結(jié)構(gòu)-停車場管理課程設(shè)計報告

課程設(shè)計報告一、需求分析1、以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。2、用戶輸入汽車信息后，程序?qū)γ恳唤M輸入數(shù)據(jù)進行操作后的輸出信息為：假設(shè)是車輛到達(dá)，那么輸出汽車在停車場內(nèi)或便到上的停車位置；假設(shè)是車輛離去，那么輸出汽車在停車場內(nèi)停留的時間和應(yīng)繳納的費用〔在便道上停留的時間不收費〕。3、本程序要求棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。4、測試數(shù)據(jù)：設(shè)n=2，輸入數(shù)據(jù)為：〔“A”，1，5〕，〔“A”，2，10〕，〔“D”，1，15〕，〔“A”3，20〕，〔“A”，4，25〕，〔“A”，5，30〕，〔“D”，2，35〕，〔“D”，4，40〕，〔“E”，0，0〕。其中：“A”表示到達(dá)〔Aiiival〕；“D”表示離去〔Departure〕；“E”表示輸入結(jié)束〔End〕。5、程序執(zhí)行的命令為：1〕創(chuàng)立停車場；2〕創(chuàng)立便到；3〕執(zhí)行對車輛的運算；4〕輸出所需的數(shù)據(jù)。二、概要設(shè)計1、設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack{ 數(shù)據(jù)對象：D={ai｜ai∈CharSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}根本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：假設(shè)棧S為空棧，那么返回TURE,否那么FALSE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個數(shù)，即棧的長度。GetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。StackTraverse(S,visit())初始條件：棧S已存在且非空。操作結(jié)果：從棧底到棧頂依次對S的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，那么操作失敗。}ADTStack2、設(shè)定隊列的抽象數(shù)據(jù)類型定義：ADTQueue{數(shù)據(jù)對象：D={ai｜ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}約定其中a1端為隊列頭，an端為隊列尾根本操作：InitQueue(&Q)操作結(jié)果：構(gòu)造一個空隊列Q。QueueEmpty(Q)初始條件：隊列Q已存在。操作結(jié)果：假設(shè)Q為空隊列，那么返回TURE，否那么FALSE。QueueLength(Q)初始條件：隊列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()失敗，那么操作失敗。}ADTQueue3、設(shè)定停車場的抽象數(shù)據(jù)類型為：ADT數(shù)據(jù)對象：D={ai｜ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}根本操作：Arrival(Park&P,Shortcut&S,intn)初始條件：棧S存在。操作結(jié)果：在輸入車牌號和進場時間后，輸出停車的車道。Leave(Park&P,Park&P1,Shortcut&S,intcost)初始條件：棧S存在且非空。操作結(jié)果：在輸入車牌號和離場時間后，輸出車停留時間以及費用。}ADT4、設(shè)定便到的抽象數(shù)據(jù)類型為：ADTCarPtr{數(shù)據(jù)對象：D={ai｜ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<a(i-1),ai>｜a(i-1),ai∈D,i=2,…,n}根本操作：EnQueue(S,number,ar_time)初始條件：停車場已滿，隊列存在。操作結(jié)果：在輸入車牌號和進場時間后，輸出車停留在便道上的位置。DeQueue(S,w)初始條件：停車場有車輛離開。操作結(jié)果：輸出由便到進入停車場的汽車車牌號DeQueue(S,q)初始條件：便道上有車離開。操作結(jié)果：輸出離開車輛車牌以及停留時間。}ADTCarPtr5、本程序包含五個模塊1〕主程序模塊：Voidmain(){初始化；Do{接受命令；處理命令；}while(“命令”=”退出”)；}2〕棧模塊——實現(xiàn)棧抽象數(shù)據(jù)類型3〕隊列模塊——實現(xiàn)隊列抽象數(shù)據(jù)類型4〕停車場模塊——實現(xiàn)停車場抽象數(shù)據(jù)類型5〕便道模塊——實現(xiàn)便到抽象數(shù)據(jù)類型各模塊之間的調(diào)用關(guān)系如下：主程序模塊↓棧模塊↓隊列模塊↓停車場模塊↓便道模塊三、詳細(xì)設(shè)計1、車輛類型typedefstructCar1{//車intnumber;//汽車車號intar_time;//汽車到達(dá)時間}CarNode;2、棧類型typedefstruct{//停車場CarNode*base;//停車場的堆棧底CarNode*top;//停車場的堆棧頂intstacksize;}Park;棧的根本操作設(shè)置如下：VoidInitStack(Stack&S)//初始化，設(shè)S為空棧IntStackLength(StackS)//返回棧S的長度S.sizeStatusGetTop(StackS)//假設(shè)S為空棧，那么返回TURE；否那么返回FALSEStatusGetTop(StackS,ElemTypee)//假設(shè)棧S不空，那么以e帶回棧頂元素并返回TURE，否那么返回FALSEStatusPush(Stack&S,ElemTypee)//假設(shè)分配空間成功，那么在S的棧頂插入新的棧頂元素e，并返回TURE//否那么棧不變，并返回FALSEStatusPop(Stack&S,ElemType&e)//假設(shè)棧不空，那么刪除S的棧頂元素并以e帶回其值，且返回TURE//否那么返回FALSEVoidStackTraverse(StackS,Status(*visit)(ElemTypee))//從棧底到棧頂依次對S中的每個結(jié)點調(diào)用函數(shù)visit其中局部操作的算法：voidInitStack(Park&P,intn){//初始化停車場P.top=P.base=(CarNode*)malloc(n*sizeof(Car1));P.stacksize=0;}voidPush(Park&P,CarNodee){//車進入停車場*P.top=e;P.top++;++P.stacksize;}voidPop(Park&P,CarNode&e){//車離開停車場--P.top;e=*P.top;--P.stacksize;}3、隊列類型typedefstructCar2{//車intnumber;//汽車車號intar_time;//汽車到達(dá)時間structCar2*next;}*CarPtr;typedefstruct{//便道CarPtrfront;//便道的隊列的對頭CarPtrrear;//便道的隊列的隊尾intlength;}Shortcut;隊列的根本操作設(shè)置如下：StatusTnitQueue(LinkQueue&Q)//構(gòu)造一個空列QStatusQueueEmpty(LinkQueueQ)//假設(shè)隊列Q為空隊列，那么返回TURE，否那么返回FALSEStatusQueueLength(LinkQueueQ)//返回Q的元素個數(shù)，即為隊列的長度StatusGetHead(LinkQueueQ,QElemType&e)//假設(shè)隊列不空，那么用e返回Q的隊頭元素，并返回OK；否那么返回ERRORStatusEnQueue(LinkQueue&Q,QElemTypee)//插入元素e為Q的新的隊尾元素StatusDeQueue(LinkQueueQ,QElemType&e)//假設(shè)隊列不空，那么刪除Q的隊頭元素，用e返回其值，并返回OK;//否那么返回ERRORStatusQueueTraverse(LinkQueueQ,visit())//從隊頭到隊尾依次對隊列Q中每個元素調(diào)用函數(shù)visit()，一旦visit失敗，那么操作失敗。其中局部操作的算法：voidInitQueue(Shortcut&S){//初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2));S.front->next=NULL;S.length=0;}voidEnQueue(Shortcut&S,intnumber,intar_time){//車進入便道CarPtrp;p=(CarPtr)malloc(sizeof(Car2));p->number=number;p->ar_time=ar_time;p->next=NULL;S.rear->next=p;//相連S.rear=p;++S.length;}voidDeQueue(Shortcut&S,CarPtr&w){//車離開便道if(S.length!=0){w=S.front->next;S.front->next=S.front->next->next;--S.length;}}4、停車場、便道的類型其中局部操作的算法：voidArrival(Park&P,Shortcut&S,intn){//對進站車輛的處理intnumber,ar_time;printf("請輸入車牌號：");scanf("%d",&number);printf("進場的時刻:");scanf("%d",&ar_time);if(P.stacksize<n){CarNodec;c.number=number;c.ar_time=ar_time;Push(P,c);printf("該車應(yīng)停在第%d號車道。\n",P.stacksize);}else{EnQueue(S,number,ar_time);printf("停車場已滿，請暫時停在便道的第%d個位置。\n",S.length);}}voidLeave(Park&P,Park&P1,Shortcut&S,intcost){//對離站車輛的處理intnumber,le_time,flag,money;CarPtrc,q;inttimes;printf("請輸入車牌號：");scanf("%d",&number);printf("出場的時刻:");scanf("%d",&le_time);CarNodee,m;CarPtrw;while(P.stacksize){Pop(P,e);if(e.number==number){flag=0;money=(le_time-e.ar_time)*cost;times=le_time-e.ar_time;break;}Push(P1,e);}while(P1.stacksize){Pop(P1,e);Push(P,e);}//車從停車場中出if(flag==0){if(S.length!=0){DeQueue(S,w);m.ar_time=le_time;m.number=w->number;Push(P,m);free(w);printf("車牌號為%d的車已由便道進入停車場\n",m.number);}printf("停車費為%d,停車時間為%d\n",money,times);}else{printf("停車場不存在牌號為%d的車,在便道上找\n",number);c=S.front;if(S.length!=0){ while(c->next!=NULL) { if(c->next->number==number) { printf("%d車從便道上離開，停留時間%d\n",c->next->number,le_time-c->next->ar_time); c->next=c->next->next; --S.length; break;}c=c->next;DeQueue(S,q);S.rear->next=q;S.rear=q;}} }}五、主函數(shù)的算法：voidmain(){intn,cost;charflag;//選項ParkP,Q;printf("輸入停車場的規(guī)模:"); scanf("%d",&n); printf("每小時收費:"); scanf("%d",&cost);ShortcutS;InitStack(P,n);//初始化InitStack(Q,n);InitQueue(S);while(1){cout<<"請選擇〔A,D,E〕：\n"; cin>>flag;switch(flag){case'A':case'a':Arrival(P,S,n);break;//車進入停車場case'D':case'd':Leave(P,Q,S,cost);break;//車離開停車場case'E':case'e':return0;break;default:printf("Inputerror!\n");break;}}}六、函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：四、調(diào)試分析1、由于剛開始對隊列元素刪除的不了解，使得程序的操作直接對隊列中的元素刪除，而不是刪除對頭元素，這違背了題目要求。經(jīng)過修改后，這一問題得到解決。2、棧的元素中step域沒有太多用處，可以省略。3、StackTravers在調(diào)試過程中很有用，它可以插入在算法中多處，以觀察停車場管理中車輛走動的次序是否正確，但對最后的執(zhí)行版本么有用。五、用戶手冊1、本程序的運行環(huán)境為Windows，執(zhí)行文件為：停車場管理.exe2、進入演示程序后，即顯示文本方式的用戶界面：3、進入車輛輸入信息的命令后，程序開始運行。4、按回車后程序輸出相應(yīng)的結(jié)果。六、測試結(jié)果 七、附錄#include<stdio.h>#include<malloc.h>#include<iostream.h>//棧，模擬停車場typedefstructCar1{//車intnumber;//汽車車號intar_time;//汽車到達(dá)時間}CarNode;typedefstruct{//停車場CarNode*base;//停車場的堆棧底CarNode*top;//停車場的堆棧頂intstacksize;}Park;//隊列，模擬便道typedefstructCar2{//車intnumber;//汽車車號intar_time;//汽車到達(dá)時間structCar2*next;}*CarPtr;typedefstruct{//便道CarPtrfront;//便道的隊列的對頭CarPtrrear;//便道的隊列的隊尾intlength;}Shortcut;voidInitStack(Park&P,intn){//初始化停車場P.top=P.base=(CarNode*)malloc(n*sizeof(Car1));P.stacksize=0;}voidPush(Park&P,CarNodee){//車進入停車場*P.top=e;P.top++;++P.stacksize;}voidPop(Park&P,CarNode&e){//車離開停車場--P.top;e=*P.top;--P.stacksize;}voidInitQueue(Shortcut&S){//初始化便道S.front=S.rear=(CarPtr)malloc(sizeof(Car2));S.front->next=NULL;S.length=0;}voidEnQueue(Shortcut&S,intnumber,intar_time){//車進入便道CarPtrp;p=(CarPtr)malloc(sizeof(Car2));p->number=number;p->ar_time=ar_time;p->next=NULL;S.rear->next=p;//相連S.rear=p;++S.length;}voidDeQueue(Shortcut&S,CarPtr&w){//車離開便道if(S.length!=0){w=S.front->next;S.front->next=S.front->next->next;--S.length;}}voidArrival(Park&P,Shortcut&S,intn){//對進站車輛的處理intnumber,ar_time;printf("請輸入車牌號：");scanf("%d",&number);printf("進場的時刻:");scanf("%d",&ar_time);if(P.stacksize<n){CarNodec;c.number=number;c.ar_time=ar_time;Push(P,c);printf("該車應(yīng)停在第%d號車道。\n",P.stacksize);}else{EnQueue(S,number,ar_time);printf("停車場已滿，請暫時停在便道的第%d個位置。\n",S.length);}}voidLeave(Park&P,Park&P1,Shortcut&S,intcost){//對離站車輛的處理intnumber,le_time,flag,money;CarPtrc,q;inttimes;printf("請輸入車牌號：");scanf("%d",&number);printf("出場的時刻:");scanf("%d",&le_time);CarNodee,m;CarPtrw;while(P.stacksize){Pop(P,e);if(e.number==number){flag=0;money=(le_time-e.ar_time)*cost;times=le_time-e.ar_time;break;}Push(P1,e);}while(P1.stacksize){Pop(P1,e);Push(P,e);}printf("停車費為%d,停車時間為%d\n",money,times);//車從停車場中出While(S.stacksize){DeQueue(S,w);m.ar_time=le_time;m.number=w->number;Push(P,m);