数据结构与算法实验报告
实验题目(如:停车场管理)
学号:
姓名:
教师点评:
成绩:
一、目的与要求
实验一选择第 1 章至第 5 章的实验,或由学生自拟内容涉及第 1 章至第 5 章的实验;实
验二选择第 6 章至第 11 章的实验,,或由学生自拟内容涉及第 6 章至第 11 的实验;描述实验
项目应达到的具体目标,以及实现要求。
二、工具/准备工作
在开始做实验项目前,应回顾或复习的相关内容;需要的硬件设施与需要安装哪些 C++
集成开发环境软件。
三、分析
分析实验项目的实现方法,并写出类声明与核心算法实现代码。
四、实现步骤
详细介绍实验项目的操作步骤。
五、测试与结论
运行实验程序的屏幕显示,并加以简单的文字说明,注意程序运行要覆盖算法的各种情
况,最后说明实验程序是否满足实验题目的要求。
六、实验总结
主要说明程序的特点,你进行了哪些功能扩展,特别是重点说明独创或创新的部分,相
关实验项目最有价值的内容,在哪些方面需要进一步了解或得到帮助,以及编程实现实验的
感悟等内容。
注:如没有某些内容(例如没有功能扩展),则可省略相应内容。
1.设计题目:《停车管理系统》
2.设计目的:(1)根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。
(2)当有车辆从停车场离开时,等待的车辆按顺序进入停车场停放。实现停车场的调度功
能。(3)用顺序栈来表示停车场,链队表示停车场外的便道。(4)显示停车场信息和便道信
息。(5)操作提示界面。算法思想分析(1)、模拟停车场的车辆进出需要输入车辆的信息,
比如车辆的车牌号码、自动匹配本地时间,因此,可以定义一个车辆信息结点类型和一个时
间节点类型,在链式栈、链式队列中定义结点类型为车辆信息结点类型。(2)、车辆离开时,
需要打印输出车辆的车位号、到达时间、离开时间以及应缴纳的费用。定义 expenses 函数实
现。(3)、车辆到达时要输入车辆的信息,并以此存放在停车场内;每进入一辆车,要判断
停车场(链式栈)是否已经停满,若已满,则提示该车要在便道上等待;若未满,则进行进
栈操作。(4)、车辆的离开,要另外设计一个辅助栈,当一辆汽车要离开时,在其后的车辆
要给其让路,让路的汽车就暂时停放在这个栈中。车辆离开后,要判断便道上是否有车辆在
等待,若有则进行入栈操作,即将车辆的信息结点进行入栈操作。(5)、车辆的查询,既可
以查询停车场内的车辆,也可以查询便道上等待的车辆,查询显示车辆的当前情况。算法思
想分析(1)、模拟停车场的车辆进出需要输入车辆的信息,比如车辆的车牌号码、自动匹配
本地时间,因此,可以定义一个车辆信息结点类型和一个时间节点类型,在链式栈、链式队
列中定义结点类型为车辆信息结点类型。(2)、车辆离开时,需要打印输出车辆的车位号、
到达时间、离开时间以及应缴纳的费用。定义 expenses 函数实现。(3)、车辆到达时要输入
车辆的信息,并以此存放在停车场内;每进入一辆车,要判断停车场(链式栈)是否已经停
满,若已满,则提示该车要在便道上等待;若未满,则进行进栈操作。(4)、车辆的离开,
要另外设计一个辅助栈,当一辆汽车要离开时,在其后的车辆要给其让路,让路的汽车就暂
时停放在这个栈中。车辆离开后,要判断便道上是否有车辆在等待,若有则进行入栈操作,
即将车辆的信息结点进行入栈操作。(5)、车辆的查询,既可以查询停车场内的车辆,也可
以查询便道上等待的车辆,查询显示车辆的当前情况。
算法思想分析
(1)、模拟停车场的车辆进出需要输入车辆的信息,比如车辆的车牌号码、自动匹配本
地时间,因此,可以定义一个车辆信息结点类型和一个时间节点类型,在链式栈、链式队列
中定义结点类型为车辆信息结点类型。
(2)、车辆离开时,需要打印输出车辆的车位号、到达时间、离开时间以及应缴纳的费
用。定义 expenses 函数实现。
(3)、车辆到达时要输入车辆的信息,并以此存放在停车场内;每进入一辆车,要判断
停车场(链式栈)是否已经停满,若已满,则提示该车要在便道上等待;若未满,则进行进
栈操作。(
4)、车辆的离开,要另外设计一个辅助栈,当一辆汽车要离开时,在其后的车辆要给其
让路,让路的汽车就暂时停放在这个栈中。车辆离开后,要判断便道上是否有车辆在等待,
若有则进行入栈操作,即将车辆的信息结点进行入栈操作。
(5)、车辆的查询,既可以查询停车场内的车辆,也可以查询便道上等待的车辆,查询
显示车辆的当前情况。
五、算法主要功能函数及实现
typedef struct
int day;
{
int hour;
int min;
int sec;}
//时间结构图
TIME;
//时间结点
typedef struct{
char num[10];
//车牌号
TIME time;
//进入停车场的时间
int n;
//进入停车场的位置}
information;
typedef struct node
{
information data;
struct node *next;
}
stacknode;
stacknode *top1,*top2,*top3; //栈结构体定义
typedef struct {
information data;
stacknode *front,*rear;
//队列结构体定义
}
LQueue;LQueue *Q;
stacknode *into(stacknode *top1,LQueue *Q);
{
time_t rawtime;
struct tm *timeinfo;
//调用系统时间函数
//时间结点
//初始化车辆进入
time( &rawtime);
timeinfo = localtime( &rawtime); p = (stacknode *)malloc(sizeof(stacknode));
if(p == NULL)
{
printf(" 内存分配失败");
return top1;
}
printf(" 请输入进入停车场车辆的车牌号:");
scanf("%s", p->data.num);
q = top1; while(q!= NULL)
{
if(strcmp(p->data.num, q->data.num) == 0)
{
printf("车牌号输入有误,该车已进入!");
return top1;
}
q = q->next;
}
p->data.time.day = timeinfo->tm_mday;
p->data.time.hour = timeinfo->tm_hour;
p->data.n = b;if(b > maxs)
{
printf("停车场已满,请在便道等候!\n");
wait(Q,p);
return top1;
}
if(top1 == NULL)
{
p->next = NULL;
top1 = p;
}
Else
{
p->next = top1;
top1 = p;
}
b++;printf(" 车 牌 为 %s 的 汽 车 驶 入 时 间 为 :%d 号 %d 点 %d 分 %d 秒
\n",top1->data.num,);
return top1;
}
int expenses(stacknode *p,int x,int y); //停车费用计算函数{if(x3!= 0)
w = (x1*24+x2+1-(p->data.time.day*24+p->data.time.hour))*price;
else w = (x1*24+x2-(p->data.time.day*24+p->data.time.hour))*price;
return w;
}
stacknode
{
*leave(stacknode
*top1,char
str[],LQueue
*Q);
//车辆驶出出场函数 if(top1 == NULL)
{
printf("停车场没有车辆!\n");
return top1;
}
q = (stacknode *)malloc(sizeof(stacknode));
if(p == NULL)
{printf("内存分配失败");return top1;
}
q = top1; while(q!= NULL)
{if(strcmp(q->data.num,str) == 0)
break;
q = q->next;
}
{
printf("输入有误,该车辆不在停车场!\n");
if(q == NULL)
return top1;
}
for(i = top1->data.n; i > q->data.n; i--)
{p = (stacknode *)malloc(sizeof(stacknode));
strcpy(p->data.num,top1->data.num);
p->data.time = top1->data.time;
p->data.n
= top1->data.n-1;
top1 = top1->next;
if(top2 == NULL)
{p->next = NULL;top2 = p;
}
else
{p->next = top2;top2 = p;}}
top1 = top1->next;
while( top2!= NULL)
{p=(stacknode*)malloc(sizeof(stacknode));
if(p==NULL){printf("内存分配失败");return top1;}
p->data.n = top2->data.n;
strcpy(p->data.num,top2->data.num);
top1 = p;
p->next = top1;
top2 = top2->next;}
= out(Q);p->data.n--;top1 = LQinto(p,top1);}
else b--;
驶出时间为:%d 号%d 点%d 分%d 秒\n", q->data.num,);
为%f 小时\n",
expenses(q));return top1;}LQueue *wait(LQueue *q,stacknode *s);
车 便 道 函 数 {s->next = NULL;q->rear->next = s;q->rear = s;return q;}
EmptyLQue(LQueue *q);
*out(LQueue *q);
p->data.time = top2->data.time;
if(EmptyLQue(Q))
{p
printf("车牌为%s 的汽车
printf(" 汽 车 停 留 的 时 间
printf(" 车 辆 驶 出 停 车 场 需 要 缴 纳 的 费 用 为:%d 元\n",
//车辆进入候
int
//判断候车便道有无等待车辆函数 stacknode
time(q));
//候车区车辆出队{
{q->rear = q->front;return p;}
p = q->front->next;
else
位置\n");
%d 号%d 点%d 分 第%d 位
\n",top1->data.num,);top1 = top1->next;}} }void T_shou(LQueue *Q);
// 显 示 候 车 区 信 息 double time(stacknode *p,int x1,int x2,int x3,int x4);
//计算停留时间{
->rear = Q->rear;printf("
q = (LQueue *)malloc(sizeof(LQueue));q ->front = Q->front;
q
候车区信息\n");if(q->front == q->rear)
printf(" 候
if(q->front->next == q->rear)
q->front->next
=
p->next;p->next
stacknode *LQinto(stacknode *p,stacknode *top1);
进入停车场函数 p->next = top1;top1 = p;return top1; }
*top1);
表\n");
{
while(top1!= NULL)
进入时间
{printf(" %s
if(top1 == NULL)
printf("车牌号
=
p;}
{//从候车便道
void show(stacknode
//显示停车场所有信息函数{printf(" 停车场内全部车辆信息
NULL;return
printf(" 停车场内无车!\n");
else
else
{q->front = q->front->next;printf("车牌号
车区没有车辆!\n");
时间\n");while(q->front!= NULL)
\n",q->front->data.num,q->front->data.time.day,q->front->data.time.hour,q->front->data.ti
me.min);q->front = q->front->next;}
进入
%d 号 %d 点 %d 分
{printf("%s