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

數(shù)據(jù)結(jié)構(gòu)課 程 設(shè) 計題目 停車場管理器設(shè)計 專業(yè)：計算機科學與技術(shù)班級：1401姓名：彭旭學號：143230135實驗主要內(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)境 Windows 10 Visual c+ c語言實驗原理1.概要設(shè)計（1）抽象數(shù)據(jù)類型定義ADT Stack 數(shù)據(jù)對象:D=ai|ai ElemSet, i=1,2,n;n0 數(shù)據(jù)關(guān)系:R1=|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返回。 ADT Stack ADT Queue 數(shù)據(jù)對象:D=ai|ai ElemSet, i=1,2,n; n0 數(shù)據(jù)關(guān)系:R1=|ai-1,ai D, i=2,n其中:a1為隊頭, an為隊尾 基本操作: InitQueue(&Q); 操作結(jié)果：構(gòu)造一個空隊列Q EnQueue(&Q,&e);初始條件：對列Q已存在。操作結(jié)果：插入元素e為Q的新隊尾元素。 DeQueue(&Q,&e); 初始條件：對列Q已存在。操作結(jié)果：刪除Q的隊頭元素, 并用e返回。ADT Queue （2）本程序包含七個模塊：主程序模塊，其中主函數(shù)為 Void main() 初始化； 構(gòu)造空棧； 輸入已知數(shù)據(jù)； 插入數(shù)據(jù)入棧； 分析 入棧；出棧；入隊；出隊；輸出數(shù)據(jù)； 構(gòu)造棧模塊-構(gòu)造一個空棧； 棧插入模塊-插入新的數(shù)據(jù)元素； 棧刪除模塊-刪除指定的數(shù)據(jù)元素；構(gòu)造隊列模塊-構(gòu)造一個空隊列； 隊列插入模塊-插入新的數(shù)據(jù)元素； 隊列刪除模塊-刪除指定的數(shù)據(jù)元素；（3）各模塊之間的調(diào)用關(guān)系圖解：主函數(shù)模塊構(gòu)造棧模塊棧插入模塊棧刪除模塊構(gòu)造隊列模塊隊列插入模塊隊列刪除模塊分析2詳細設(shè)計類型定義#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MONEY 3typedef int Status;typedef struct ElemTypechar a3;int num;int time;ElemType;typedef struct SqStack ElemType *base;/在棧構(gòu)造之前和銷毀之后,base的值為NULL ElemType *top;/棧頂指針 int stacksize;/當前已經(jīng)分配的存儲空間,以元素為單位SqStack;/棧的表示typedef struct QNodeElemType data; struct QNode *next;QNode,*QueuePtr;/隊列的表示typedef struct LinkQueue QueuePtr front;/隊頭指針QueuePtr rear;/隊尾指針LinkQueue;棧和隊列的基本操作Status InitStack(SqStack &S)/構(gòu)造一個空棧Status Push(SqStack &S,ElemType e)/插入元素e為新的棧頂元素Status Pop(SqStack &S,ElemType &e)/若棧不空，則刪除S的棧頂元素，用e 返回其值，并返回OK；否則返回ERRORStatus InitQueue(LinkQueue &Q)/構(gòu)造一個空隊列QStatus EnQueue(LinkQueue &Q,ElemType e)/插入元素e為Q的新隊列Status DeQueue(LinkQueue &Q,ElemType &e)/若隊列不空,則刪除Q的對頭元素,用e返回其值,并返回Ok;否則返回ERROR;部分操作的算法Status InitStack(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; return OK;Status Push(SqStack &S,ElemType e)/插入元素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;return OK;Status Pop(SqStack &S,ElemType &e)/若棧不空，則刪除S的棧頂元素，用e 返回其值，并返回OK；否則返回ERRORif(S.top=S.base) return OK;e=*-S.top;return OK;/-隊列Status InitQueue(LinkQueue &Q)/構(gòu)造一個空隊列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit (OVERFLOW);/存儲分配失敗Q.front-next=NULL;return OK;Status EnQueue(LinkQueue &Q,ElemType e)/插入元素e為Q的新隊列p=(QueuePtr)malloc(sizeof(QNode);/存儲分配失敗if(!p) exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;Status DeQueue(LinkQueue &Q,ElemType &e)/若隊列不空,則刪除Q的對頭元素,用e返回其值,并返回Ok;否則返回ERROR;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;源程序Stop1.h:#include #include #include #include /-函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define TNFEASIBLE -1#define OVERFLOW -2/Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Status;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MONEY 3Stop2.h:#includestop1.htypedef struct ElemTypechar a3;int num;int time;ElemType;typedef struct SqStackElemType *base;ElemType *top;int stacksize;SqStack;/棧的表示typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;/隊列的表示 typedef struct LinkQueue QueuePtr front;/隊頭指針 QueuePtr rear;/隊尾指針 LinkQueue; Status InitStack(SqStack &S);/構(gòu)造空棧 Status Push(SqStack &S,ElemType e);/進棧 Status Pop(SqStack &S,ElemType &e);/出棧 Status InitQueue(LinkQueue &Q);/構(gòu)造一個空隊列 Status EnQueue(LinkQueue &Q,ElemType e);/入隊 Status DeQueue(LinkQueue &Q,ElemType &e);/出隊Stop.cpp: #includestop2.hStatus InitStack(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; return OK;Status Push(SqStack &S,ElemType e)/插入元素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;return OK;Status Pop(SqStack &S,ElemType &e)/出棧 if (S.top=S.base) return OK; e=*-S.top; return OK;/*隊列*/Status InitQueue(LinkQueue &Q)/構(gòu)造一個空隊列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next=NULL;return OK; Status EnQueue(LinkQueue &Q,ElemType e)/插入元素e為Q的新隊列 struct QNode *p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK; Status DeQueue(LinkQueue &Q,ElemType &e)struct QNode *p;if(Q.front=Q.rear) return ERROR;p=Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;Stop_main.cpp: #includestop2.h main()int i,t,f,m,n,s1_num,Q_num;struct SqStack s1,s2;struct LinkQueue Q;struct ElemType e,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) /當有車輛進來的時候 if(s1_numn) Push(s1,e1);s1_num+; printf(此車停在停車場第%d輛n,s1_num); else EnQueue(Q,e1);Q_num+; printf(此車停在便道距離門口第%d輛n,Q_num);else if(strcmp(e1.a,D)=0) /當有車輛離開的時候 f=s1_num;for(i=0;if;i+)Pop(s1,e);s1_num-;if(e1.num=e.num)t=e1.time-e.time;m=MONEY*t