创新课程设计实践报告
- 格式：doc
- 大小：37.00 KB
- 文档页数：8
百度文库 - 让每个人平等地提升自我 1 《创新课程设计实践报告》
学院：软件学院 学号 ：4 班级 ：06 (1)班 姓名：郑志敏
2008-6-11 百度文库 - 让每个人平等地提升自我
2 停车场管理问题 问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。 实现要求：要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。 一． 需求分析 （1）要实现停车场管理的功能，建立两个栈s,dcc和一个队列Q，其中栈s模拟停车场，另一个栈s临时存放给要离开的汽车让路而从停车场退出的汽车，队列Q用来模拟停车便道。
（2）定义栈和队列的结构体，实现队列和栈的初始化以及栈，压车元素进栈，取车元素出栈，车元素入列，队头元素出列和取出队列中车元素操作。
（3）当车辆到达时，首先检查停车场是否是满的，若不满则放入停车场内，若停车场是满的，则放在便道上。即若栈是不满的就入栈，否则就入队列。
（4）当车辆离开时，首先要寻找到要离开车辆的车牌号，若车是从停车场离开，则在它之后进入的车辆必须先退出为它让路，待该辆车开出大门外，其它车辆再按原次序进入停车场，并将停放在便道上第一位置的车开进停车场，离开的车辆按其在停车场内停留的时间交费。即当元素在栈s1中时，就将在它之后的元素出栈并依序放入栈s0中，此元素出栈，随后将栈s0中的元素放入s0中，最后将队列Q的首元素放入栈s1中。
（5）若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，从停车场离去，则输出汽车应交的费用，否则停车便道直接离去，此时排在它之前的汽车要先开走让路，然后依次排到队尾。 . 百度文库 - 让每个人平等地提升自我 3 （7）测试数据，当输入数据为2,5 ('A',1,5), ('A',2,10), ('D',1,15),
输出结果为： 二．概要设计 该程序主要分六个模块：定义栈和队列的结构体，实现队列和栈的初始化以及栈，压车元素进栈，取车元素出栈，车元素入列，队头元素出列和取出队列中车元素操作。 typedef struct {int car_num; int time; }car_info 操作结果：定义车节点 void Initstack(sqstack *s) 操作结果： 构造一个长度为n的空栈 void push(sqstack *s,car_info e) 初始条件：栈S已经存在 操作结果：若栈不满则压一个车元素进栈,是把数据拷贝进 car_info pop(sqstack *s) 初始条件：栈S已经存在 操作结果：从栈S中取出元素e，若e不在栈顶，将栈顶元素一个一个取出放入栈S中 void EnQueue(LinkQueue *Q,car_info *a ) 初始条件：存在队列Q 操作结果：将元素查入队列 QueuePtr DeQueue(LinkQueue *Q) 初始条件：存在队列Q 百度文库 - 让每个人平等地提升自我 4 操作结果：从队列中取出某个要离开的元素 void arrive(sqstack *s,LinkQueue *p,car_info a,int n) 操作结果：此函数用来表示进入车辆 { push(s,a) 操作结果：车进栈 EnQueue(p,&a)停车场已满，停通道 Void leave(sqstack *tcc,sqstack*dcc,LinkQueue *p,car_info a,float pay) 操作结果：用来出车 主程序模块： void main(){ 初始化 while(sum) { Initstack(&tcc); Initstack(&dcc); InitQueue(&p); switch(sign) { case 'a': case 'A':arrive(&tcc,&p,a,n);break; case 'D': case 'd':leave(&tcc,&dcc,&p,a,pay);break; case 'e': case 'E':exit(OVERFLOW);break; } }
三．详细设计 #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 1 栈类型 typedef int status ; #include<> #include<> #include<> #include<>
typedef struct 百度文库 - 让每个人平等地提升自我 5 {int car_num; int time; }car_info; typedef struct { car_info *base; car_info *top; status stacksize; }sqstack; void Initstack(sqstack *s) { s->base=(car_info *)malloc(STACK_INIT_SIZE*sizeof(car_info)); if(!s->base) exit(OVERFLOW); s->top=s->base; s->stacksize=0; } 其中部分操作的算法 void push(sqstack *s,car_info e) { *s->top++=e; s->stacksize++; } car_info pop(sqstack *s) {car_info e; if(s->top==s->base) {printf("停车场内没有该车辆!\n"); exit(0) ;} e=*--s->top; s->stacksize--; return e; } typedef struct Qnode { int car_num; int time; struct Qnode *next; }QNode,*QueuePtr; typedef struct { 百度文库 - 让每个人平等地提升自我 6 QueuePtr front; QueuePtr rear; int lenth; }LinkQueue; status InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q->front)exit(OVERFLOW); Q->front->next=NULL; Q->lenth=0; return OK; }
void EnQueue(LinkQueue *Q,car_info *a ) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->car_num=a->car_num; p->time=a->time; p->next=NULL; Q->rear->next=p; Q->rear=p; Q->lenth++;
} QueuePtr DeQueue(LinkQueue *Q) { QueuePtr p,e,s={0}; if(Q->front==Q->rear) {printf("便道上没有车辆!\n"); return s;} p=Q->front->next; e=p; Q->front->next=p->next; Q->lenth--; if(Q->rear==p)Q->front=Q->rear; -6.2f义栈和队列的结构体，实现队列和栈的初始化以及栈，压车元素进栈，取车元素出栈，车元素入列，队头元素出列和取出队列中车元素操作 2.时间复杂度均为O（n）
五．测试结果 百度文库 - 让每个人平等地提升自我 7 输入数据为 2 5 操作一：当车位未满时： ('A',1,5)进入停车场的1号车道 ('A',2,10)进入停车场的2号车道 ('D',1,15)车牌为1的车离开停车场
操作二：当车位满时 ('A',1,5)进入停车场的1号车道 ('A',2,10)进入停车场的2号车道 ('A',3,20) 停车场满进入1号便道 ('D',2,35)离开，车牌为3车进入2号车道，输出2号车应缴的费用 输入 ('E',0,0 )退出
