数据结构课程设计报告(含源码)

1、. . . . 科技学院课程设计报告院（系）:电气与信息工程学院专业班级: 计科普0902 学生: 邓小祥 学 号: 2009441656 设计地点（单位）_计算机基础自主学习中心I306_设计题目:_停车场管理系统设计_ 完成日期： 2011年 1月 14日指导教师评语: _ _ 成绩（五级记分制）:_ _ 指导教师（签字）:_ _ 19 / 24科技学院课程设计任务书设计题目：停车场管理系统的设计学生课程名称数据结构课程设计专业班级计科2009-01、02地 点计算机基础自主学习中心起止时间2011.01.4-2011.01.14设计容与要求问题描述：设停车场是一个可停放n辆汽车的狭长通道

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

3、达”或“离去”信息、汽车牌照以与到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场或便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。设计参数设n=2，输入数据为：（A,1,5）,（A,2,10）,（D,1,15）,（A,3,20）,（A,4,25）,（A5,30）,（D,2,35）,（D,4,40）,（E,0,0）。其中：A表示到达（arrival）；D表示离去（departure）；E表示输出结束（end）。参考资料1严蔚敏 吴伟民 著， 数据结构（C语言版）

4、，清华大学，2007.42Richard F.Gilberg Behrouz A.Forouzan, Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13. 春葆 著，数据结构教程，清华大学，2005.1说明.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。.若填写容较多可另纸附后。3.一题多名学生共用的，在设计容、参数、要求等方面应有所区别。教研室主任：向毅 指导教师：向毅、奎、熊茜 2010年 12 月 20日摘要随着现在数据处理的多样性、复杂性，数据

5、结构的应用也随之运用的更加的广泛，运用数据结构处理问题也更加的方便快捷。此次停车场管理系统的设计是利用两个堆栈来分别模拟停车场以与停车场车辆为其它车辆让路时退出停车的临时停放地点。通道上车辆的停放则用一个队列来实现，此时，通道上车辆的离开或者进入停车场只需改变此队列上的结点。对于要对停车场的车辆根据其停放时间收取相应的停车费用，可以记录下车辆进入以与离开停车场的时间，再用时间差乘以相应的单价并且打印出最后的费用就可以实现。关键词：数据结构、堆栈、对列、计时收费目录摘要I1.设计容与要求11.1 设计容11.2 设计要求12.概要设计12.1 设计思想12.2 主要模块22.3 程序结构23.系

6、统分析与设计33.1 系统数据结构设计33.1.1 堆栈33.1.2 队列33.2系统算法设计和流程43.2.1系统算法设计43.2.2系统流程图54.系统测试65.致8参考文献9附录101.设计容与要求1.1 设计容设计一个停车场，停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端），若停车场已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门

7、外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。1.2 设计要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照以与到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场或便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。2.概要设计2.1 设计思想此停车场管理系统是在一个狭长

8、的通道上的，而且只有一个大门可以供车辆进出，并且要实现停车场某辆车要离开时，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再依原来的次序进场的功能，就可以设计两个堆栈，其中一个堆栈用来模拟停车场，另一个堆栈用来模拟临时停车场，该临时停车场用来存放当有车辆离开时，原来停车场为其让路的车辆。至于当停车场已满时，需要停放车辆的通道可以用一个队列来实现。当停车场开走一辆车时，通道上便有一辆车进入停车场，此时只需要将对列元素弹到堆栈中就可以了，使通道上第一辆车进入停车场这个堆栈，并且使通道上原来的第二辆车成为通道上的第一辆车。2.2 主要模块首先定义用来模拟停车场的堆栈以与用

9、来模拟通道的队列为全局变量，然后编写主函数，在此主函数中实现对其它各个模块的调用。在主函数中首先调用Menu()函数，出现欢迎用户使用的主界面，然后提示用户进入此停车场管理系统后，再出现一个供用户选择的界面，在用户的选择过程中，程序又分别调用车辆的进入、车辆的离开、停车场停放车辆的信息以与退出程序这四个函数模块。其中，在车辆的离开那个模块函数中又调用了打印离开车辆信息的函数，在停车场停放车辆信息的那个模块函数中，又分别调用了显示停车场上车辆信息的函数以与显示便道上车辆信息的函数。最后，从调用的这四个函数中回到主函数结束整个程序的运行。2.3 程序结构导航菜单汽车进入汽车离开车库信息信息处理退出

10、系统图2.1模块调用结构图3.系统分析与设计3.1 系统数据结构设计本停车场管理系统是利用堆栈和队列来进行实现的，分别利用堆栈和队列的基本操作。3.1.1 堆栈利用堆栈的性质就可以模拟出停车场的部车道，车辆必须满足先进后出的规律，里面的车辆出入必须先移出后进的车辆。堆栈的基本操作如下：creatStack() 建立堆栈pushStack (STACK* stack, void* dataInPtr) 压入元素进栈popStack (STACK* stack, void* dataInPtr) 弹出栈元素fullStack (STACK* stack) 判断栈满emptyStack (STACK

11、* stack) 判断栈空destoryStack (STACK* stack) 销毁堆栈3.1.2 队列利用队列的性质可以模拟出停车场外部的便道，当停车场部的车满后将车辆停在便道上。便道着满足队列的性质先进先出，当部有空位就将便道上第一辆车停如。队列的基本操作如下：createQueue () 建立队列enqueue (QUEUE* queue, void* itemPtr) 元素进对dequeue (QUEUE* queue) 元素出队fullQueue (QUEUE* queue) 判断队满emptyQueue (QUEUE* queue) 判断队空destroyQueue(QUEUE*

12、 queue) 销毁队列3.2系统算法设计和流程3.2.1系统算法设计分别利用一个堆栈和一个队列来模拟停车厂部车道和外部便道，当有车停入时则将车的信息压入栈中，当部车道满了后则将车先停到便道中等候车位。当车辆要出去时则利用一个临时的堆栈来进行数据的缓存，先将车的信息压入临时堆栈，当目标车出栈后则将临时栈的元素转入停车场栈中，并将便道的上的车的第一辆转入部车道。通过堆栈、队列对信息的查询也只需要对结构元素一一遍历即可，这样就可以实现对停车场信息的处理。系统主要2个部分：停车 取车都是对堆栈和队列的操作。汽车进入时则压入堆栈或队列中，离开时则弹出。定义汽车的属性结构体，并用结构体来描述和存储汽车的

13、信息。typedef structint number;车牌号int time; 进入时间char size; 汽车型号 CAR;汽车的入库时对堆栈和队列的压入操作，将汽车信息结构体链到堆栈队列中CAR* car; 定义一汽车的信息pushStack(stack,car); 压栈与进入车库中enqueue(queue, car); 进对与停放在便道上汽车离开时将堆栈或队列中的目标汽车信息删掉并对信息处理分析打印出要的信息车库中车的离开处理：carout=(CAR*)popStack(stack)pushStack(changestack,carout) 将汽车信息转入临时栈中保存pushSta

14、ck(stack,changecar) 处理后汽车信息从新存入车库栈中便道上车辆的离开：changecar=(CAR*)dequeue(queue)enqueue(changequeue,changecar) 将汽车信息转入临时队中保存enqueue(queue,changecar) 处理后汽车信息从新存入便道队中通过部车库栈和便到队列来存储汽车信息，然后通过其得基本操作来得到汽车的进入和离开，并得到预期的结果。3.2.2系统流程图开始初始化栈parklot和队列road进入主菜单车进入车离开退出目标车前车辆进临时栈目标车计费便道车信息车场内信息判便道是否有车车场是否为空列表显示元素进栈par

15、klot便道车进车场元素进队列road判断栈是否为满结束退出列表显示是否否是否是图3.5 程序流程图4.系统测试进入系统，先调用void beginsystem(STACK*stack,QUEUE*queue)函数进行初始化堆栈和队列，读取已保存的信息。然后调用menu()函数调出导航菜单提供功能导航，如图4.1图4.1通过导航菜单分别对不同的功能进行实现，而调用相关的函数。车辆进入时则调用停车函数void car_park(STACK*stack,QUEUE* queue)，可以将车辆信息显示并将车入库。图4.2同样的车库信息、汽车离开、退出系统也通过调用各自的函数来实现的，分别为void

16、park_imformation(STACK* stack,QUEUE*queue)void car_gone(STACK*stack,QUEUE*queue)void quittosave(STACK*stack,QUEUE*queue)图4.3图4.4操作完成后保存信息并安全的退出系统。图4.55.致感学校为我们配备了专门的实验室，让我们有更好的学习环境，能更专心的学习；感老师辛勤的工作，耐心的为我们讲解，让我们能更好的理解知识、应用知识；感我的同学们，在我编写遇到困难时，是他们给我的讲解，是我克服了困难，把程序编的跟好；感父母，他们给了我精神和物质上的支持，使我向着自己的目标不断努力，不

17、断前进，不断创新。签名：邓小祥日期：2011-1-11参考文献1严蔚敏 吴伟民 著， 数据结构（C语言版），清华大学，2007.42Richard F.Gilberg Behrouz A.Forouzan, Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13春葆 著，数据结构教程，清华大学，2005.14. C程序设计经典教程，美Deitel,H.M.，美Deitel,P.J.著，清华大学，20065. 鑫.VC+深入详解.：电子工业：20076钱能.C+程序设计教程.：清华大学:2009附

18、录Main:#include<stdio.h>#include"StackADT.h"#include"QueueADT.h"#include"Menu.h"#include"car_park.h"#include"car_gone.h"#include"park_imformatiom.h"#include"Beginsystem.h"#include"QuittoSave.h"int main()STACK* parkl

19、ot;QUEUE* road;char z;parklot=creatStack();road=createQueue();beginsystem(parklot,road);while(1)menu();z=getchar();fflush(stdin);if(z='q')quittosave(parklot,road);break;switch(z)case 'p': car_park(parklot,road);break;case 'g': car_gone(parklot,road);break;case 'i': pa

20、rk_imformation(parklot,road);break;default: printf("enter the right order.n");break;printf("any key to continue.n");getchar();fflush(stdin);system("cls");return 0;调用函数：堆栈、队列操作：STACK* creatStack (void)STACK* stack;stack = (STACK*) malloc( sizeof (STACK);if (stack) stack-

21、>count = 0; stack->top = NULL;return stack;bool pushStack (STACK* stack, void* dataInPtr)STACK_NODE* newPtr;newPtr = (STACK_NODE* ) malloc(sizeof( STACK_NODE);if (!newPtr) return false;newPtr->dataPtr = dataInPtr; newPtr->link = stack->top; stack->top = newPtr; (stack->count)+;

22、return true;void* popStack (STACK* stack) void* dataOutPtr; STACK_NODE* temp;if (stack->count = 0) dataOutPtr = NULL;else temp = stack->top; dataOutPtr = stack->top->dataPtr; stack->top = stack->top->link; free (temp); (stack->count)-; return dataOutPtr;bool fullStack (STACK*

23、 stack) STACK_NODE* temp;if (temp = (STACK_NODE*)malloc (sizeof(*(stack->top) && stack->count<2) free (temp); return false;return true;bool emptyStack (STACK* stack) return (stack->count = 0);STACK* destoryStack (STACK* stack) STACK_NODE* temp;if (stack) while (stack->top != N

24、ULL) free (stack->top->dataPtr); temp = stack->top; stack->top = stack->top->link; free (temp); free (stack);return NULL;QUEUE* createQueue (void)QUEUE* queue;queue = (QUEUE*) malloc (sizeof (QUEUE);if (queue) queue->front = NULL; queue->rear = NULL; queue->count = 0; retu

25、rn queue;bool enqueue (QUEUE* queue, void* itemPtr)QUEUE_NODE* newPtr;if (!(newPtr = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE) return false;newPtr->dataPtr = itemPtr; newPtr->next = NULL; if (queue->count = 0) queue->front = newPtr;else queue->rear->next = newPtr; (queue->count)+;q

26、ueue->rear = newPtr;return true;void* dequeue (QUEUE* queue) void* dataOutPtr;QUEUE_NODE* deleteLoc;if (queue->count=0) dataOutPtr = NULL; dataOutPtr = queue->front->dataPtr;deleteLoc = queue->front;if (queue->count = 1) queue->rear = queue->front = NULL;else queue->front

27、= queue->front->next;(queue->count)-;free (deleteLoc);return dataOutPtr;bool fullQueue (QUEUE* queue) QUEUE_NODE* temp;if (temp = (QUEUE_NODE*)malloc(sizeof(*(queue->rear) && queue->count<5) free (temp); return false; return true;bool emptyQueue (QUEUE* queue) return (queue

28、->count = 0);#ifndef _STDBOOL_H_#define _STDBOOL_H_#define _bool_true_false_are_defined 1#ifndef _cplusplus#define false 0#define true 1#define bool _Bool#if _STDC_VERSION_ < 199901L && _GNUC_ < 3typedef int _Bool;#endif#endif /* !_cplusplus */#endif /* !_STDBOOL_H_ */应用函数：void menu

29、(void)printf("tt|-|n");printf("tt|<p> park car <g> get car |n");printf("tt|<i> park imformation<q> quit to out |n");printf("tt|-|n");printf("tt(cost one hour: small car is 1 yuan,middlen tt caris 2 yuan,big car is 3 yuan.)n");

30、printf("ttyou want:");void beginsystem(STACK*stack,QUEUE*queue)CAR* temp;FILE* fp;fp=fopen("DATA.dat","r");if(fp!=NULL)fseek(fp,0,SEEK_SET);while(1)temp=(CAR*)malloc(sizeof(CAR);temp->number=-1;fread(temp,sizeof(CAR),1,fp);if(temp->number=-1)break;else if(!fullSta

31、ck(stack)pushStack(stack,temp);elseenqueue(queue,temp);fclose(fp);fp=fopen("DATA.dat","w");fclose(fp);free(temp);void car_park(STACK*stack,QUEUE* queue)CAR* car;car=(CAR*)malloc(sizeof(CAR);car->place='a'printf("car number:");scanf("%d",&car->

32、;number);fflush(stdin);printf("car's in time:");scanf("%d",&car->time);fflush(stdin);printf("car's size(ssmall/mmiddle/llarge?):");while(1)car->size=getchar();fflush(stdin);if(car->size='s'|car->size='m'|car->size='l')b

33、reak;printf("enter the right car's size(ssmall/mmiddle/llarge?):");if(!fullStack(stack)printf("the car has been paked and count the time for pay.n now the time is %d.n",car->time);pushStack(stack,car);else if(!fullQueue(queue)printf("the parklot is full,your car park

34、in the road.n here you pay for not.n");enqueue(queue, car);elseprintf("there is no more parking lot.n");void car_gone(STACK*stack,QUEUE*queue)STACK* changestack;QUEUE* changequeue;CAR* carout;CAR* changecar;int number;int time;int found=0;int count;changestack=creatStack();changequeue

35、=createQueue();if(!emptyStack(stack) | !emptyQueue(queue)printf("Enter the outcar number:");scanf("%d",&number);fflush(stdin);printf("Enter the outcar time:");scanf("%d",&time);fflush(stdin);while(!emptyStack(stack)carout=(CAR*)popStack(stack);if(carou

36、t->number=number)found=1;break;pushStack(changestack,carout);while(!emptyStack(changestack)changecar=(CAR*)popStack(changestack);pushStack(stack,changecar);if(found=1)switch(carout->size)case 's':printf("this parking cost %d hour(s),you should pay %d yuan for it.n",time-carou

37、t->time,1*(time-carout->time);break;case 'm':printf("this parking cost %d hour(s),you should pay %d yuan for it.n",time-carout->time,2*(time-carout->time);break;case 'l':printf("this parking cost %d hour(s),you should pay %d yuan for it.n",time-carout-

38、>time,3*(time-carout->time);break;default:break;if(!emptyQueue(queue)changecar=(CAR*)dequeue(queue);printf("The car %d in the road have been parking.n",changecar->number);pushStack(stack,changecar);else count=queue->count;while(!emptyQueue(queue)changecar=(CAR*)dequeue(queue);i

39、f(changecar->number=number)printf("Car is not in the parklot,you pay for not.n");elseenqueue(changequeue,changecar);while(!emptyQueue(changequeue)changecar=(CAR*)dequeue(changequeue);enqueue(queue,changecar);if(queue->count=count)printf("can not find this car,or the parklot is e

40、mpty .n please check your car number.n");free(changestack);free(changequeue);void park_imformation(STACK* stack,QUEUE*queue)STACK_NODE* temp1;QUEUE_NODE* temp2;CAR* temp3;if(!emptyStack(stack)if(!fullStack (stack)printf("there is %d cars in the park lot,%d for car to park.n",stack->count,10-stack->count);else if(fullStack (stack)&am