数据结构上机实习报告.docx

2 CUG 线性部分 非线性部分数据结构上机实习报告 学校：中国地质大学（武汉）专业：数学与应用数学班级：姓名：完成时间：2017.12.14第一部分停车场模拟1.1问题描述我们要模拟一个停车场的管理系统。问题中有一个停车场，由于其可以停泊的车辆数量有限，为满足需求，我们有一个辅助的变道，一旦有车要停泊，我们便判断停车场的停车位是否已满，如果满了的话，就将其停泊在便道上。实际的要求是不但有进，亦有出。这就涉及到两个问题：其一是我们要对从停车场驶出的车进行收费，这就涉及到其在停车场停留的时间计算。通常情况下，我们会在总的入口（也就是出口）处设立收费站，有一辆车出现，我们首先会判断这辆车要入还是要出，如果是要入，我们就把当前时刻与该车对应起来。 如果该车是出来的（为简化问题，我们假设便道的车不许驶出，故驶出的车定是从停车场出来的），那么它必然已有一个时刻与之对应，我们只要用当前时刻减去该已有时刻，就是该车在停车场停留时间了。其二是从停车场要出来车，就要后进入停车场的车给其暂时让位，为了使得该车驶离后其余车仍保持原来的顺序，我们需要一个辅助的堆栈。事实上，该堆栈最满停车的数量为停车场停车位的数量减去一，我们在实际操作中让其与停车场堆栈的大小相同，这样就不用在定义一个堆栈结构了。事实上，对于每从停车场驶出一辆车，就会有一个停车位空出，这时就要便道上的一辆车驶入停车场（如果便道上有车的话），我们对其开始计时。那么，给他对应的时刻是多少呢？事实上，驶出停车场的车会过收费站（程序输入端），会有一个当前时刻，我们只要将该时刻与要从便道驶入停车场的车从新对应就行了。这就说明对每辆车开始收费的时刻并不一定是到“达的时刻”，而是要看该车是入停车场还是入便道，对于入便道的车，们还要修改其时刻，应为对于如便道的车，其“到达时刻”是没有实际意义的。1.2基本要求1以栈模拟停车场，以队列模拟车场外的便道。 2：按照从终端读入的输入数据序列进行模拟管理。3：每一组输入数据包括三个数据项；汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。4：栈以顺序结构实现，队列以链表结构实现。1.3数据结构 /车结构体typedef struct carint tag; /设置标志位，如果车辆到达tag=1,如果车辆tag=-1 long int carID; /车牌号float time; /到达或离开的时刻，DataType;/停车场堆栈，定义其大小即停车位个数为4typedef structDataType stackmaxsizestack; /我们会将maxsizestack固定为4int top;SeqStack;/便道队列节点typedef struct qnodeDataType data;struct qnode *next;LQNode;/便道队列typedef structLQNode *front; LQNode *rear;int count;LQueue;1.4测试数据 我们为了竟可能对所建模型进行测试，共设计了四组测试数据： 1.3.1第一组测试数据：Test3=1,10001,10, 1,10002,20,1,10003,30从终端输入的数据为：1 10004 40说明：test3表示已经有三辆车从终端（大门口）近去了，它们的车牌号依次为：10001,10002,10003.到达时刻以此为 10,20,30.现在有一辆车10004从大门口进入，我们要该系统对其做出反应。1.3.2 第二组测试数据Test3= 1,10001,10, 1,10002,20, 1,10003,30终端输入数据为：-1 10002 40说明：test3表示已经有三辆车从终端（大门口）近去了，它们的车牌号依次为：10001,10002,10003.到达时刻以此为 10,20,30.这与第一组测试数据相同，不同之处在于：现有一辆车牌号为10002的车要离开，我们要该系统对其做出反应。 1.3.3 第三组测试数据Test3= 1,10001,10, 1,10002,20, 1,10003,30从终端输入的数据为：-1 10004 40数明：test3表示已经有三辆车从终端（大门口）近去了，它们的车牌号依次为：10001,10002,10003.到达时刻以此为 10,20,30.这与第一，二组测试数据相同，不同之处在于：现有一辆车牌号为10004的车显示的是离开，我们要该系统对其作出反应。 1.3.4 第四组测试数据 Test4= 1,10001,10, 1,10002,20, 1,10003,30, 1,10004,40 从终端输入数据为 1 10005 50 说明：test4表示已经有四辆车从大门口进入（终端读入），现在有一辆车牌为10005的车要从大门口进入，需要该系统做出反应。1.4模块划分 1：PARK.h文件,定义堆栈的数据结构，初始化，判断堆栈是否为空，入栈，出栈操作。队列的数据结构，包括队列的定义，初始化，入队列，出队列操作。 2：StackDelete.h文件：创建停车场内的任意一辆车的出堆栈函数void StackDelete(SeqStack *S,long int carID,float *tt)，参数分别为该堆栈的指针和该车辆的车牌号carID,输出值为该车辆进入停车场时的时间。 3：PARK.cpp文件，包括主函数。1.6源程序/*PARK .h文件*/#includemalloc.htypedef struct carint tag; /设置标志位，如果车辆到达tag=1,如果车辆离开tag=-1 long int carID; /车牌号float time; /到达或离开的时刻DataType;#define maxsizestack 4 typedef structDataType stackmaxsizestack;int top;SeqStack;/*初始化函数StackInitiate(SeqStack *S)*/void StackInitiate(SeqStack *S)S-top=0;/*判空函数StackNotEmpty(SeqStack S)*/int StackNotEmpty(SeqStack S)if(S.top=maxsizestack)return 0;else return 1;/*入堆栈StackPush(SeqStack *S,DateType x)*/int StackPush(SeqStack *S,DataType x)if(S-top=maxsizestack)printf(堆栈以满，无法插入n);return 0;elseS-stackS-top=x;S-top+;return 1;/*出堆栈函数StackPop(SeqStack *S,DateType *d)*/int StackPop(SeqStack *S,DataType *d)if(S-toptop-;*d=S-stackS-top;return 1;/*LQueue*/typedef struct qnodeDataType data;struct qnode *next;LQNode;typedef structLQNode *front; LQNode *rear;int count;LQueue;/*初始化QueueInitiate(LQueue *Q)*/void QueueInitiate(LQueue *Q)Q-front=NULL; Q-rear=NULL;Q-count=0;/*队列判空QueueNotEmpty(LQueue Q)*/int QueueNotEmpty(LQueue Q)if(Q.front=NULL) return 0;else return 1;/*入队列QueueAppend(LQueue *Q,DataType x)*/void QueueAppend(LQueue *Q,DataType x)LQNode *p;p=(LQNode*)malloc(sizeof(LQNode);p-data=x;p-next=NULL;if(Q-rear!=NULL)Q-rear-next=p;Q-rear=p;if(Q-front=NULL)Q-front=p;Q-count+;/*出队列QueueDelete(LQueue *Q,DataType *d)*/int QueueDelete(LQueue *Q,DataType *d)LQNode *p;if(Q-front=NULL)printf(队列为空);return 0;else*d=Q-front-data;p=Q-front;Q-front=Q-front-next;if(Q-front=NULL)Q-rear=NULL;free(p);Q-count-; return 1;/* StackDelete.h文件*/*创建停车场内的任意一辆车的出堆栈函数，参数分别为该堆栈的指针和该车辆的车牌号carID,输出值为该车辆进入停车场时的时间*/void StackDelete(SeqStack *S,long int carID,float *tt)int n=S-top; /记下未出堆栈S时堆栈内元素的个数SeqStack T; /创建辅助堆栈DataType x;StackInitiate(&T); / 初始化辅助堆栈Twhile(StackNotEmpty(*S)StackPop(S,&x);if(x.carID!=carID)StackPush(&T,x); /*依次将堆栈S中的元素出堆栈，若该元素不是要找的元素，将其压入堆栈T中*/else *tt=x.time;break;/*若该元素是要找的元素，返回该元素的time改时间是其入堆栈S时的时间*/while(StackNotEmpty(T)StackPop(&T,&x); StackPush(S,x);/*将T中的元素还给S*/if(S-top=n)*tt=0; /如果此时栈顶指针的位置没有变换，说明S中没有该车牌号的车辆/* PARK. CPP文件*/#include#includePARK.h#includemalloc.h/typedef Car DataType; /将抽象数据具体化#define maxsizestack 4 /停车场的容量为4#include” StackDelete.h”#define e 1 /停车场单位时间的收费为e=1/为第一组，第二组，第三组测试数据编的主函数void main()SeqStack S1;float t; /定义停车场堆栈S1，停车场辅助堆栈S2；float *tt=&t;LQueue Q; /定义变道队列Q DataType ca1,ca2; /定义数据StackInitiate(&S1); /初始化S1；QueueInitiate(&Q); /初始化Q；DataType test3=1,10001,10,1,10002,20, 1,10003,30; /*定义测试数据*/for(int i=0;i3;i+)StackPush(&S1,testi); /*测试数据入堆栈*/scanf(%d%ld%f,&ca1.tag,&ca1.carID,&ca1.time); /输入车辆ca1的信息/*对到达的车辆的处理*/if(ca1.tag=1)if(StackNotFull(S1)printf(该车停于停车场S1的第%d个停车位n,S1.top);StackPush(&S1,ca1);else printf(该车停于便到的第%d个位置n,Q.count);QueueAppend(&Q,ca1);elseStackDelete(&S1,ca1.carID,tt); /调用StackDelete函数，将车辆ca1出停车场，并将其进入停车场是的时刻赋给t if(t)t=ca1.time-t; /如果该车辆是从停车场内开出的，将停留时间重新赋给t if(QueueNotEmpty(Q)QueueDelete(&Q,&ca2);ca2.time=ca1.time;StackPush(&S1,ca2); /*如果此时变车道上有车辆的话记作ca2将其辆驶入停车场，将其time改ca1离开时的time,即从ca1离开时对ca2开始计时*/else t=0; /若该车辆不是从停车场开出的，显然其停留时间为printf(该车停留的时间t=%f,应收取的费用为money=%fn,t,t*e);/为第四组数据编的主函数 void main()SeqStack S1;float t; /定义停车场堆栈S1，停车场辅助堆栈S2；float *tt=&t;LQueue Q; /定义变道队列Q DataType ca1,ca2; /定义数据StackInitiate(&S1); /初始化S1；QueueInitiate(&Q); /初始化Q；DataType test4=1,10001,10,1,10002,20, 1,10003,30,1,10004,40,; /*定义测试数据*/for(int i=0;inumofVerts=0; /顶点个数G-numofEdges=0; /边个数for(i=0;iai.source=i;G-ai.adj=NULL;/插入顶点void InsertVertex(AdjlGraph *G,int i,DataType vertex)if(i=0&iai.data=vertex ;G-numofVerts+;else printf(顶点越界);/ 插入边void InsertEdge(AdjlGraph *G, int v1,int v2,int cost)Edge *p;if(v1=G-numofVerts|v2=G-numofVerts)return;p=(Edge*)malloc(sizeof(Edge);p-dest=v2;p-cost=cost;p-next=G-av1.adj;G-av1.adj=p;G-numofEdges+; /*AdjMGraphCreate.h文件*/*创建图*/ typedef structint row; /弧尾int col; /弧头int cost; /边权重RowCol; /变信息结构体void CreatGraph(AdjlGraph *G,DataType v,int n, RowCol d,int e)int i,k;AdjInitiate(G);for(i=0;in;i+)InsertVertex(G,i,vi); /插入顶点for(k=0;knumofVerts;int *s=(int *)malloc(sizeof(int)*n); /申请一个长度为顶点个数的标志数组s,若si=0表示顶戴你在集合T中，若si=1，则顶点在S集合中int minDis,i,j,u;/初始化for(i=0;iav0.adj;while(p1!=NULL)distancep1-dest=p1-cost;pathp1-dest=v0;p1=p1-next;/标记顶点v0已经从T中加入到S中，v0到本身的最短路径为0sv0=1;distancev0=0;/在当前未找到最短路的顶点集中选取具有最短路的顶点u，for(i=1;in;i+)minDis=MaxWeight;for(j=0;jn;j+)if(sj=0&distancejau.adj;while(p1!=NULL)if(sp1-dest=0&p1-cost+minDisdest)distancep1-dest=p1-cost+minDis;pathp1-dest=u;p1=p1-next; /*work2.cpp文件*/为第一个测试数据编的主函数#include#includetypedef int DataType;#define MaxWeight 100#define MaxVert 20#includeAdjMGraph.h#includeAdjMGraphCreate.h#include Djikstra.hvoid main()AdjlGraph g;int a=1,2,3,4,5,6;RowCol d=0,1,20,0,2,4,0,3,34,1,0,20,1,3,8,1,5,25,2,0,4,2,4,14, 3,0,34,3,1,8,3,4,12,3,5,10,4,2,14,4,3,12,4,5,30,5,1,25,5,3,10,5,4,30;int i,n=6,e=18;int distance6,path6;CreatGraph(&g,a,n,d,e);Dijkstra(&g,0,distance,path);printf(从顶点%d到各顶点的最短距离为:n,g.a0.data);for(i=0;in;i+)printf(到顶点%d的最短距离为%dn,g.ai.data,distancei);p