} 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));
char a[3]; int num; int time; }ElemType; typedef struct SqStack{ ElemType *base; ElemType *top; int stacksize; }SqStack;//栈的表示 typedef struct QNode{ ElemType data; struct QNode *next; }QNode,*QueuePtr;//队列的表示 typedef struct LinkQueue{ QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue; Status InitStack(SqStack &S);//构造空栈 Status Push(SqStack &S,ElemType e);//进栈 Status Pop(SqStack &S,ElemType &e);//出栈 Status InitQueue(LinkQueue &Q);//构造一个空队列 Status EnQueue(LinkQueue &Q,ElemType e);//入队 Status DeQueue(LinkQueue &Q,ElemType &e);//出队
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; }
//构造一个空栈 Status Push(SqStack &S,ElemType e) //插入元素 e 为新的栈顶元素 Status Pop(SqStack &S,ElemType &e) //若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR Status InitQueue(LinkQueue &Q) //构造一个空队列 Q Status EnQueue(LinkQueue &Q,ElemType e) //插入元素 e 为 Q 的新队列 Status DeQueue(LinkQueue &Q,ElemType &e) //若队列不空,则删除 Q 的对头元素,用 e 返回其值,并返回 Ok; 否则返回 ERROR; <3>部分操作的算法 Status InitStack(SqStack &S){//构造一个空栈
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 的 新队列 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;
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){//构造一个空队列
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;
数据结构
课程设计
题目 停车场管理器设计
专业：计算机科学与技术 班级：1401 姓名：彭旭
学号：143230135
实验主要内容
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读
入的输入数据序列进行模拟管理。每一组输入数据包括三个数据
项：汽车“达到”或“离去”信息、汽车牌照号码以及达到或离
去的时刻。对每一组输入数据进行操作后的输出信息为：若是车
InitQueue(&Q); 操作结果：构造一个空队列 Q EnQueue(&Q,&e); 初始条件：对列 Q 已存在。 操作结果：插入元素 e 为 Q 的新队尾元素。 DeQueue(&Q,&e); 初始条件：对列 Q 已存在。 操作结果：删除 Q 的队头元素, 并用 e 返回。 }ADT Queue （2）本程序包含七个模块： <1>主程序模块，其中主函数为 Void main(){ 初始化；
free(p);
return OK;
}
源程序
Stop1.h: #include <stdio.h> #include <process.h> #include <malloc.h> #include <string.h> //------------------------函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define TNFEASIBLE -1 #define OVERFLOW -2 //Status 是函数的类型，其值是函数结果状态代码 typedef int Status; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MONEY 3 Stop2.h: #include"stop1.h" typedef struct ElemType{
构造空栈； 输入已知数据； 插入数据入栈； 分析 {入栈；出栈；入队；出队；} 输出数据； } <2>构造栈模块-----构造一个空栈； 栈插入模块-----插入新的数据元素； 栈删除模块-----删除指定的数据元素； 构造队列模块-----构造一个空队列； 队列插入模块-----插入新的数据元素； 队列删除模块-----删除指定的数据元素； （3）各模块之间的调用关系图解：
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 为新的栈顶元 素
Stop.cpp: #include"stop2.h"
Status InitStack(SqStack &S){//构造空栈 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;
主函数模块
分析
构造栈模块
栈插入模块
栈删除模块 构造队列模块 队列插入模块 队列删除模块
2．详细设计 <1>类型定义
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MONEY 3
typedef int Status; typedef struct ElemType{
if(S.top-S.base>=S.stacksize){//栈满，追加存储空间 S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemT ype));