數(shù)據(jù)結(jié)構(gòu)停車場管理實驗報告

停車場管理實驗報告學(xué)院：計算機工程學(xué)院班級：計算1414 姓名：李連活一．實驗?zāi)康暮鸵笫炀殫：完犃械慕Y(jié)構(gòu)特性，掌握在實際問題背景下的應(yīng)用二．實驗主要內(nèi)容以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“達到”或“離去”信息、汽車牌照號碼以及達到或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛達到、則輸出汽車在停車場內(nèi)或便道上停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。三．實驗儀器和環(huán)境PC機Windows8.1Visualc++c語言四．實驗原理1.概要設(shè)計（1）抽象數(shù)據(jù)類型定義ADTStack{數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n;n>0}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}基本操作:InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入e為新的棧頂元素Pop(&S,&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素,并且用e返回。}ADTStackADTQueue{數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n;n>0}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…n}其中:a1為隊頭,an為隊尾基本操作:InitQueue(&Q);操作結(jié)果：構(gòu)造一個空隊列QEnQueue(&Q,&e);初始條件：對列Q已存在。操作結(jié)果：插入元素e為Q的新隊尾元素。DeQueue(&Q,&e);初始條件：對列Q已存在。操作結(jié)果：刪除Q的隊頭元素,并用e返回。}ADTQueue（2）本程序包含七個模塊：<1>主程序模塊，其中主函數(shù)為Voidmain(){初始化；構(gòu)造空棧；輸入已知數(shù)據(jù)；插入數(shù)據(jù)入棧；分析{入棧；出棧；入隊；出隊；}輸出數(shù)據(jù)；}<2>構(gòu)造棧模塊-----構(gòu)造一個空棧；棧插入模塊-----插入新的數(shù)據(jù)元素；棧刪除模塊-----刪除指定的數(shù)據(jù)元素；構(gòu)造隊列模塊-----構(gòu)造一個空隊列；隊列插入模塊-----插入新的數(shù)據(jù)元素；隊列刪除模塊-----刪除指定的數(shù)據(jù)元素；（3）各模塊之間的調(diào)用關(guān)系如下：主函數(shù)模塊主函數(shù)模塊構(gòu)造棧模塊棧插入模塊棧刪除模塊構(gòu)造隊列模塊隊列插入模塊隊列刪除模塊分析2．詳細設(shè)計<1>類型定義#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMONEY3typedefintStatus;typedefstructElemType{ chara[3]; intnum; inttime;}ElemType;typedefstructSqStack{ElemType*base;//在棧構(gòu)造之前和銷毀之后,base的值為NULLElemType*top;//棧頂指針intstacksize;//當(dāng)前已經(jīng)分配的存儲空間,以元素為單位}SqStack;//棧的表示typedefstructQNode{ ElemTypedata; structQNode*next;}QNode,*QueuePtr;//隊列的表示typedefstructLinkQueue{ QueuePtrfront;//隊頭指針 QueuePtrrear;//隊尾指針}LinkQueue;<2>棧和隊列的基本操作StatusInitStack(SqStack&S)//構(gòu)造一個空棧StatusPush(SqStack&S,ElemTypee)//插入元素e為新的棧頂元素StatusPop(SqStack&S,ElemType&e)//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORStatusInitQueue(LinkQueue&Q)//構(gòu)造一個空隊列QStatusEnQueue(LinkQueue&Q,ElemTypee)//插入元素e為Q的新隊列StatusDeQueue(LinkQueue&Q,ElemType&e)//若隊列不空,則刪除Q的對頭元素,用e返回其值,并返回Ok;否則返回ERROR;<3>部分操作的算法StatusInitStack(SqStack&S){//構(gòu)造一個空棧S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}StatusPush(SqStack&S,ElemTypee){//插入元素e為新的棧頂元素 if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間 S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base)exit(OVERFLOW);//存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACK_INIT_SIZE; } *S.top++=e; returnOK;}StatusPop(SqStack&S,ElemType&e){//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(S.top==S.base)returnOK; e=*--S.top; returnOK;}//----------------隊列StatusInitQueue(LinkQueue&Q){//構(gòu)造一個空隊列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW);//存儲分配失敗 Q.front->next=NULL; returnOK;}StatusEnQueue(LinkQueue&Q,ElemTypee){//插入元素e為Q的新隊列 p=(QueuePtr)malloc(sizeof(QNode));//存儲分配失敗 if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}StatusDeQueue(LinkQueue&Q,ElemType&e){//若隊列不空,則刪除Q的對頭元素,用e返回其值,并返回Ok;否則返回ERROR; if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}五．源程序Stop1.h:#include<stdio.h>#include<process.h>#include<malloc.h>#include<string.h>//------------------------函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineTNFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintStatus;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMONEY3Stop2.h:#include"stop1.h"typedefstructElemType{ chara[3]; intnum; inttime;}ElemType;typedefstructSqStack{ ElemType*base; ElemType*top; intstacksize;}SqStack;//棧的表示typedefstructQNode{ ElemTypedata; structQNode*next;}QNode,*QueuePtr;//隊列的表示typedefstructLinkQueue{ QueuePtrfront;//隊頭指針 QueuePtrrear;//隊尾指針 }LinkQueue;StatusInitStack(SqStack&S);//構(gòu)造空棧StatusPush(SqStack&S,ElemTypee);//進棧StatusPop(SqStack&S,ElemType&e);//出棧StatusInitQueue(LinkQueue&Q);//構(gòu)造一個空隊列StatusEnQueue(LinkQueue&Q,ElemTypee);//入隊StatusDeQueue(LinkQueue&Q,ElemType&e);//出隊Stop.cpp:#include"stop2.h"StatusInitStack(SqStack&S){//構(gòu)造空棧S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&S,ElemTypee){//插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間 S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INIT_SIZE; } *S.top++=e; returnOK;}StatusPop(SqStack&S,ElemType&e){//出棧if(S.top==S.base)returnOK;e=*--S.top;returnOK;}/***********************************************************************隊列*/StatusInitQueue(LinkQueue&Q){//構(gòu)造一個空隊列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; returnOK;}StatusEnQueue(LinkQueue&Q,ElemTypee){//插入元素e為Q的新隊列structQNode*p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}StatusDeQueue(LinkQueue&Q,ElemType&e){ structQNode*p; if(Q.front=Q.rear)returnERROR; p=Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;} Stop_main.cpp:#include"stop2.h"main(){ inti,t,f,m,n,s1_num,Q_num; structSqStacks1,s2; structLinkQueueQ; structElemTypee,e1; s1_num=0;Q_num=0;t=0;m=0; InitStack(s1);InitStack(s2);InitQueue(Q); printf("停車場的容量是:"); scanf("%d",&n); printf("輸入車輛信息（E為退出，A為進入標志，D為離開標志，車牌號時間空格隔開）：\n"); scanf("%s",e1.a);scanf("%d%d",&e1.num,&e1.time); while(strcmp(e1.a,"E")!=0){ if(strcmp(e1.a,"A")==0){//當(dāng)有車輛進來的時候 if(s1_num<n){Push(s1,e1);s1_num++; printf("此車停在停車場第%d輛\n",s1_num);} else{EnQueue(Q,e1);Q_num++; printf("此車停在便道距離門口第%d輛\n",Q_num);} } elseif(strcmp(e1.a,"D")==0){//當(dāng)有車輛離開的時候f=s1_num; for(i=0;i<f;i++){ Pop(s1,e);s1_num--; if(e1.num==e.num){ t=e1.time-e.time;m=