第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
数据结构 停车场模拟管理系统实验报告.doc
停车场模拟管理系统实验报告
班级：08-01 姓名： 学号： 日期：2010-6-16
一、 需求分析：
1. 程序功能：
用顺序栈模拟停车位和辅助栈，用顺序队模拟便道。来车显示停车位置，离车显示
车辆调度情况及应交的停车费。判断栈空，来车时车入栈，若车场已停满车则栈满，
再来的车便在便道等待，即入队。一旦有车开走，则排在便道上的第一辆车即可开
入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，
即出栈进入临时栈，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停
放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
2. 演示程序以用户与计算机交互方式执行，即在计算机终端上显示"提示信息"之后，
由用户在键盘上输入演示程序中规定的运算命令；
3. 程序执行的命令包括：
（1）构造栈（构造一个空栈、判断栈空、入栈、出栈）。
（2）构造临时栈（构造一个空栈、判断栈空、入栈、出栈）。
（3）构造链队列（构造一个队列、判断队空、入队、出队）。
（4）构造计费函数。
1 表示车辆到达登记（来车时输入车牌号和车辆到达时间）
2 表示车辆离开登记（走时输入所在停车位的位置和离开时间并根据车辆停留时间
计费）
3 表示车辆列表显示
4 退出；
4. 测试数据：
（1） 来车： 001 到 008
（2） 离车： 001, 007
（3） 车辆列表显示
（4） 退出
二、 概要设计：
为实现上述程序功能，需要两个抽象数据类型：顺序栈，顺序队；
1. 栈的抽象数据类型的定义：
ADT Stack{
数据对象：D={ai|ai∈ElemSet,i=1,2,…，n,n≥0}
数据关系：R1={＜ai-1,ai＞|ai-1,ai∈D,i=1,2,…，n﹜
约定 an 端为栈顶，ai 端为栈底
基本操作：
InitStack(&S)
操作结果：构造一个空栈 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 已存在
操作结果：插入元素 S 的栈顶元素，并用 e 返回其值
StackTraverse(S,visit())
初始条件：栈 S 存在且非空
操作结果：从栈底到栈顶依次对 S 的每个数据元素调用函数 visit()。一旦
visit()失败，则操作失败
}ADT Stack
2. 队列的抽象数据类型的定义：
ADT Queue{
数据对象：D={ai|ai∈ElemSet,i=1,2,…，n,n≥0}
数据关系：R1={＜ai-1,ai＞|ai-1,ai∈D,i=1,2,…，n﹜
约定 an 端为栈顶，ai 端为栈底
基本操作：
InitQueue(&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 返回 Q 的队头元素
EnQueue(&Q,e)
初始条件：队列 Q 已存在
操作结果：插入元素 e 返回 Q 的队尾元素
DeQueue(&Q,&e)
初始条件:Q 为非空队列
操作结果：删除 Q 的队头元素，并用 e 返回其值
QueueTraverse(Q,visit())
初始条件：队列 Q 存在且非空
操作结果：从队头到队尾，依次对 Q 的每个数据元素调用函数 visit()。一
旦 visit()失败，则操作失败
}ADT Queue
3. 本程序包含九个模块：
（1）void main(){
初始化
while{
接受命令：
处理命令；
//输入 1 时有车辆进入车场即入栈，再次输入来车的车牌号和进入时间；栈满时
车辆入队即在便道等待；
//输入 2 时有车辆离开即出栈，输入车位和车离开的时间并根据车在停车场的时
间计费；便道上的车进入车场，记录上进入时间；
//输入 3 时查看车场和便道上的停车列表；
//输入 4 时退出程序；
}("命令"!="退出")
（2）void InitStack(SeqStackCar *);
（3）int InitQueue(LinkQueueCar *);
（4）void PRINT(CarNode,int room)；
（5）int Arrival(SeqStackCar *,LinkQueueCar *);
（6）void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *);
（7）void List1(SeqStackCar)；
（8）void List2(LinkQueueCar)；
（9）void List(SeqStackCar,LinkQueueCar);
三.详细设计：
1.栈采用结构体存储结构：
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base 的值为 NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
Status InitStack(SqStack *S)
{ /* 构造一个空栈 S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
2.单链队列－－队列的链式存储结构：
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列 Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
3.栈和队列的基本操作
void InitStack(SeqStackCar *);
//构造一个空栈
int InitQueue(LinkQueueCar *);
//构造一个空队列
void PRINT(CarNode,int room)；
//计费函数，根据车辆在停车场所在时间收费
int Arrival(SeqStackCar *,LinkQueueCar *);
//来车函数，判断栈空，有车来时进栈，若不空则入队，即在便道等候
void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *);
//离车函数，车场里的车出栈，位于其车后面的车先进入临时栈，待车离去，其它车入栈
void List1(SeqStackCar)；
//车场内车辆列表
void List2(LinkQueueCar)；
//便道车辆列表
void List(SeqStackCar,LinkQueueCar);
//车场列表和便道列表的菜单
//初始化栈，主栈和临时栈（调用
4. 栈和队列的基本操作的实现
void InitStack(SeqStackCar *s){
两次）
int i;
s->top=0;
for(i=0;i<=MAX;i++)
s->stack[s->top]=NULL;
}
int InitQueue(LinkQueueCar *Q){
Q->head=(QueueNode *)malloc(sizeof(QueueNode));
if(Q->head!=NULL)
{
//初始化队
Q->head->next=NULL;
Q->rear=Q->head;
return(1);
}
else return(-1);
}
void PRINT(CarNode *p,int room){
//计费函数
int A1,A2,B1,B2;
printf("\n 车辆离开的时间(例如 00:00）");
scanf("%d:%d",&(p->leave.hour),&(p->leave.min));
printf("\n 离开车辆的车牌号为:");
puts(p->num);
printf("\n 其到达时间为: %d:%d",p->reach.hour,p->reach.min);
printf("离开时间为: %d:%d",p->leave.hour,p->leave.min);
A1=p->reach.hour;
A2=p->reach.min;
B1=p->leave.hour;
B2=p->leave.min;
printf("\n 应交费用为: %2.1f 元",((B1-A1)*60+(B2-A2))*price);
free(p);
}
int Arrival(SeqStackCar *Enter,LinkQueueCar *W){
//来车函数
CarNode *p;
QueueNode *t;
p=(CarNode *)malloc(sizeof(CarNode));
flushall();
printf("\n 请输入车牌号(例如 0000):");
gets(p->num);
if(Enter->toptop++;
printf("\n 车辆在车场第%d 位置.",Enter->top);
//入栈
printf("\n 车辆到达时间(例如 00:00):");
scanf("%d:%d",&(p->reach.hour),&(p->reach.min));
Enter->stack[Enter->top]=p;
return(1);
}
else
{
printf("\n 该车须在便道等待!有车位时进入车场");
//入队
t=(QueueNode *)malloc(sizeof(QueueNode));
t->data=p;
t->next=NULL;
W->rear->next=t;
W->rear=t;
return(1);
}
}
void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W)
//离
车函数
{
int room;
CarNode *p,*t;
QueueNode *q;
if(Enter->top>0)
{
while(1)
{
printf("\n 请输入车在车场的位置/1--%d/：",Enter->top);
scanf("%d",&room);
if(room>=1&&room<=Enter->top) break;
}
while(Enter->top>room)
{
Temp->top++;
Temp->stack[Temp->top]=Enter->stack[Enter->top];
//暂入辅助栈
Enter->stack[Enter->top]=NULL;
Enter->top--;
}
p=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
while(Temp->top>=1)
{
Enter->top++;
Enter->stack[Enter->top]=Temp->stack[Temp->top];
//由辅助栈返回停车位
Temp->stack[Temp->top]=NULL;
Temp->top--;
}
PRINT(p,room);
if((W->head!=W->rear)&&Enter->tophead->next;
t=q->data;
Enter->top++;
//由便道进入停车位
printf("\n 便道的%s 号车进入车场第%d 位置.",t->num,Enter->top);
printf("\n 请输入%s 号车进入车场的时间:",t->num);
scanf("%d:%d",&(t->reach.hour),&(t->reach.min));
W->head->next=q->next;
if(q==W->rear) W->rear=W->head;
Enter->stack[Enter->top]=t;
free(q);
}
else printf("\n 便道里没有车.\n");
}
else printf("\n 车场里没有车.");
}
void List1(SeqStackCar *S)
{
int i;
if(S->top>0)
{
printf("\n 车场:");
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
