数据结构课程设计停车场管理

1、课程设计任务书及成绩评定课题名称停车场管理、题目的目的和要求： 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。、设计进度及完成情况日 期内 容12.29-12.30熟悉设计任务，查阅有关文献资料，确定所采用的数据结构，初步制定解决问题的方法，

2、完成课程设计说明书内容1-3部分12.311.4选择合适的存储结构,明确解决问题的算法，上机编写并调试源程序1.41.5整体调试程序并记录调试中的问题，完成课程设计说明书第4-6部分。1.81.9演示设计成果，考核成绩。整理课程设计报告。、主要参考文献及资料1 严蔚敏，吴伟民主编. 数据结构（c语言版）.清华大学出版社. 2002 2 殷人昆等著. 数据结构（c+版）. 清华大学出版社. 20013 金远平著. 数据结构（c+描述）. 清华大学出版社. 2005 4 许卓群等著. 数据结构与算法. 高等教育出版社. 20045 frank m.carrano 等著. 数据结构与+高级教程.清华

3、大学出版社. 20046 严蔚敏、吴伟民. 数据结构习题集（c语言版）.清华大学出版社. 2002学科部主任_（签字）、成绩评定：设计成绩： （教师填写）指导老师： （签字）二九 年 一 月 五 日目 录第一章 概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1第二章 系统分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2第三章 概要设计.

4、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3第四章 详细设计与源程序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6第五章 调试过程中的问题及系统测试情况. . . . . . . . . . . . . . . . . . 11第六章 结束语. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5、. . . . . .12参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13第一章 概述一、本课程设计意义 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、

6、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、本课程设计任务及目的停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。停车场内已停了n辆汽车，后来的汽车只能在门外的便道上等候，一旦有车开走，排在通道上的第一辆车即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场。为停车场编写按上述要求进行管理的模拟程序。第二章 系统分析一、问题描述设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车

7、辆到达时间的先后顺序，依次由北向南排列（大门在南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停了n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，排在便道上的第一辆车即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场，每辆停放在停车场的车在它离开停车场时必须按它停留在停车场内的时间长短交纳停车费。试为停车场编写按上述要求进行管理的模拟程序。二、基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车到达或离去信息，汽车牌照号码以

8、及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。三、测试数据 设n=2，输入数据（a，1，5），（a，2，15），（d，1，15），（a，3，20），（a，4，25），（a，5，30），（d，2，35），（d，4，40），（e，0，0）。其中：a表示到达（arrival）；d表示离去（departure）；e表示输出（end）。四、实现思路需要另设一个栈，临时停放为离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和

9、进入停车场的时刻。第三章 概要设计一、栈的抽象数据类型 adt stack数据对象：d=aiaicharset,i=1,2,，n,n=0数据关系：r1=ai-1,aiai-1,aid,i=2,n基本操作：initstack(&s)操作结果：构造一个空栈s。destroystack(&s)初始条件：栈s已经存在。操作结果：操作结果：销毁栈s。claerstack(&s)初始条件：栈s已经存在。操作结果：将s清空为空栈。stacklength(&s)初始条件：栈s已经存在。操作结果：返回栈s的长度。stackempty(&s)初始条件：栈s已经存在。操作结果：若s为空栈，则返回ture，否则返回f

10、alse。gettop(s,&e)初始条件：栈s已经存在。操作结果：若栈s不空，则以e返回栈顶元素。push(&s,e)初始条件：栈s已经存在。操作结果：在栈s的栈顶插入新的栈顶元素e。pop(&s,&e)初始条件：栈s已经存在。操作结果：删除s的栈顶元素，并以e返回其值。stacktraverse(s,visit()初始条件：栈s已经存在。操作结果：从栈底到栈顶依次对s中的每个元素调用函数visit( )。adt stack二、链式队列的抽象数据类型typedef struct qnode qelemtype data; struct qnode next;qnode,queueptr;ty

11、pedef structqueueptr front; 队头指针queueptr rear; 队尾指针adt queue数据对象：d=aiaielemset,i=1,2,n,n=0数据关系：r1=ai-1,aiai-1,aid,i=2,n 约定中端为队列头，后端为队列尾。基本操作：initqueue(&q)操作结果：构造一个空队列q。destroyqueue(&q)初始条件：队列q已经存在。操作结果：队列q被销毁，不再存在。clearqueue(&q)初始条件：队列q已经存在。操作结果：将q清为空队列。queueempty(q)初始条件：队列q已经存在。操作结果：若q为空队列，则返回true，

12、否则false。queuelength(q)初始条件：队列q已经存在。操作结果：返回q的元素个数，即队列的长度。gethead(q,&e)初始条件：q为非空队列。操作结果：用e返回的e队头元素。enqueue(&q,e)初始条件：队列q已经存在。操作结果：插入元素e为q的新的队尾元素。dequeue(&q,&e)初始条件：q为非空队列。操作结果：删除q的队头元素，并用e返回其值。queuetraverse(q,visit()初始条件：q已经存在且非空。操作结果：从队头到队尾，依次对q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。adt queue三、模块划分1、主程

13、序模块main()初始化while(重复条件) 接受命令； switch(调用条件)case调用条件a 到达处理；break；case调用条件d 离开处理；break；case调用条件e 退出处理； 2、2个栈模块-实现栈抽象数据类型3、队列模块-实现队列抽象数据类型 四、模块调用关系主程序模块栈模块1队列模块栈模块2 图3-1 模块调用关系栈模块1-模拟停车场栈模块2-模拟倒车场队列模块-模拟车道第四章 详细设计与源程序一、详细设计以栈模拟停车场,以队列模拟停车场外的便道,按照从终端读入的输入数据序列进行模拟管理。另设一个栈，临时停放为离去的汽车让路而从停车场退出来的汽车。栈以顺序存储结构实

14、现，队列以链表存储结构实现。停车场栈park模拟停车场。临时栈aux-park模拟倒车场。便道队列road模拟停车场外便道。程序运行后，先设定停车时间单位和计费单位，再设定停车场容量（测试数据设定停车场容量n=2）。继续输入车辆数据：车辆属性（到达a或离开d）、车牌号、时间（到达时间或离开时间）。程序根据输入数据中的“车辆属性”进入该属性程序模块。输出车辆停放位置或离开时的收据。然后循环，继续输入车辆数据。当输入车辆数据为e时，程序自动退出。二、源程序可执行程序文件名：停车问题.exe停车场问题管理程序代码如下：#include/定义输入输出函数#include/数据流输入输出#include

15、/字符串处理#include/定义数学函数 #include /定义杂项函数及内存分配函数 #define size 2 /停车场位置数/模拟停车场的堆栈的性质typedef struct zanlind int number; /汽车车号 int ar_time; /汽车到达时间 zaninode;typedef struct zaninode *base; /停车场的堆栈底 zaninode *top; /停车场的堆栈顶 int stacksize_curren;stackhead;/堆栈的基本操作；void initstack(stackhead &l) /构造一个空栈 l.base=(

16、zaninode*)malloc(size*sizeof(zanlind);if(!l.base)exit(0); /存储分配失败 l.top=l.base; l.stacksize_curren=0;void push(stackhead &l,zaninode e) /把元素e压入l栈成为新的栈顶元素 *l.top+=e; l.stacksize_curren+;void pop(stackhead &l,zaninode &e) /把元素e弹出l栈 if(l.top=l.base) coutnext=null; q.length=0;void enqueue(linkqueue &q,i

17、nt number,int ar_time) /把元素插入队列成为新的队尾元素（属性为number，ar_time） queueptr p; p=(queueptr)malloc(sizeof(duilie); if(!p) exit(0); p-number=number; p-ar_time=ar_time; p-next=null; q.rear-next=p; q.rear=p; q.length+;void popqueue(linkqueue &q,queueptr &w) /把元素插入队列（属性为number，ar_time） queueptr p; if(q.front=q.r

18、ear) cout停车场的便道为空 ! !next; w=p; q.front-next=p-next; q.length-; if(q.rear=p) q.front=q.rear;void jinru(stackhead &st,linkqueue &q) /对进入停车场的汽车的处理； int number,time_a; coutnumber; couttime_a; if(st.stacksize_curren2) zaninode e; e.number=number; e.ar_time=time_a; push(st,e); cout 该车已进入停车场在: st.stacksiz

19、e_curren 号车道endlendl; else enqueue(q,number,time_a);/插入元素time_a为q的新的队尾元素 cout停车场已满，该车先停在便道的第q.length个位置上endl; void likai(stackhead &st,stackhead &sl,linkqueue &q) /对离开的汽车的处理 /st堆栈为停车场，sl堆栈为倒车场 int number,time_d,flag=1,money,arrivaltime; /q为便道队列 coutnumber; couttime_d; zaninode e,q_to_s; queueptr w;

20、while(flag) /找到要开出的车，并弹出停车场栈 pop(st,e); push(sl,e); if(e.number=number) flag=0; money=(time_d-e.ar_time)*2; arrivaltime=e.ar_time; pop(sl,e); /把临时堆栈的第一辆车（要离开的）去掉； while(sl.stacksize_curren) /把倒车场的车倒回停车场 pop(sl,e); push(st,e); if(st.stacksize_currennumber; push(st,q_to_s); cout车牌为q_to_s.number的车已从通道进

21、入停车场,所在的停车位为:st.stacksize_currenendlendl; cout 收 据endl; cout = 车牌号: numberendl; cout=endl; cout|进车场时刻 | 出车场时刻 | 停留时间 | 应付（元）|endl; cout=endl; cout| arrivaltime | time_d | time_d-arrivaltime | money |endl;cout-endlendl;int main()/主函数int m=100;char flag; /进入或离开的标识；stackhead sting,slinshi; /停车场和临时倒车场堆栈

22、的定义；linkqueue line; /队列的定义；initstack(sting); /构造停车场堆栈stinginitstack(slinshi); /构造倒车场堆栈slinshiinitqueue(line); /构造便道队列linewhile(m) coutn * 停车场管理程序 *endl; cout=endl; cout* *endl; cout* a - 汽车 进 车场 d - 汽车 出 车场 *endl; cout* *endl; cout* e - 退出 程序 *endl; cout=endl; coutflag; switch(flag) case a: jinru(st

23、ing,line);break; /汽车进车场 case d: likai(sting,slinshi,line);break; /汽车出车场 case e: exit(0); m-;return 0; 第五章 调试过程中的问题及系统测试情况一、出现的问题1、编程过程中忽略头文件的作用，导致漏掉了一个头文件,以致产生下列错误提示。错误提示：error c2065: malloc : undeclared identifier error c2065: exit : undeclared identifier 执行 cl.exe 时出错.在代码中加上#definestdlib.h，解决此问题。2、没有良好的编程习惯，没有合适的缩进及换行，给程序的调试带来了比较多的困难。3、编程过程中比较粗心，一些程序结束的分号和成对出现的大括号忘记写。第六章 结束语 通过这次数据结构课程设计，我认识到从课本上学到的知识是远远不够的。本次设计使我深入的了解了栈与队列的建立、插入、删除和在实际问题下灵活运用它们，另一方面使我对栈和队列的抽象数据类型有了进一步的认识。虽然经过努力终于把该系统完成，可是该系统还是不完善，程序