数据结构实习报告Word格式文档下载.docx
- 文档编号:8571642
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:24
- 大小:64.11KB
数据结构实习报告Word格式文档下载.docx
《数据结构实习报告Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构实习报告Word格式文档下载.docx(24页珍藏版)》请在冰点文库上搜索。
1.3数据结构
//车结构体
typedefstructcar
{
inttag;
//设置标志位,如果车辆到达tag==1,如果车辆tag==-1
longintcarID;
//车牌号
floattime;
//到达或离开的时刻,
}DataType;
//停车场堆栈,定义其大小即停车位个数为4
typedefstruct
DataTypestack[maxsizestack];
//我们会将maxsizestack固定为4
inttop;
}SeqStack;
//便道队列节点
typedefstructqnode
DataTypedata;
structqnode*next;
}LQNode;
//便道队列
LQNode*front;
LQNode*rear;
intcount;
}LQueue;
1.4测试数据
我们为了竟可能对所建模型进行测试,共设计了四组测试数据:
1.3.1第一组测试数据:
Test[3]={
{1,10001,10},
{1,10002,20},
{1,10003,30}
}
从终端输入的数据为:
11000440
说明:
test[3]表示已经有三辆车从终端(大门口)近去了,它们的车牌号依次为:
10001,10002,10003.到达时刻以此为10,20,30.现在有一辆车10004从大门口进入,我们要该系统对其做出反应。
1.3.2第二组测试数据
{1,10001,10},
{1,10003,30}
终端输入数据为:
-11000240
10001,10002,10003.到达时刻以此为10,20,30.这与第一组测试数据相同,不同之处在于:
现有一辆车牌号为10002的车要离开,我们要该系统对其做出反应。
1.3.3第三组测试数据
-11000440
数明:
10001,10002,10003.到达时刻以此为10,20,30.这与第一,二组测试数据相同,不同之处在于:
现有一辆车牌号为10004的车显示的是离开,我们要该系统对其作出反应。
1.3.4第四组测试数据
Test[4]={
{1,10003,30},
{1,10004,40}
}
从终端输入数据为11000550
说明:
test[4]表示已经有四辆车从大门口进入(终端读入),现在有一辆车牌为10005的车要从大门口进入,需要该系统做出反应。
1.4模块划分
1:
PARK.h文件,定义堆栈的数据结构,初始化,判断堆栈是否为空,入栈,出栈操作。
队列的数据结构,包括队列的定义,初始化,入队列,出队列操作。
2:
StackDelete.h文件:
创建停车场内的任意一辆车的出堆栈函数voidStackDelete(SeqStack*S,longintcarID,float*tt),参数分别为该堆栈的指针和该车辆的车牌号carID,输出值为该车辆进入停车场时的时间。
3:
PARK.cpp文件,包括主函数。
1.6源程序
/**********************************************PARK.h文件*****************************************/
#include"
malloc.h"
//设置标志位,如果车辆到达tag==1,如果车辆离开tag==-1
//到达或离开的时刻
#definemaxsizestack4
/*****************初始化函数StackInitiate(SeqStack*S)**/
voidStackInitiate(SeqStack*S)
S->
top=0;
/****************判空函数StackNotEmpty(SeqStackS)******/
intStackNotEmpty(SeqStackS)
if(S.top<
=0)return(0);
elsereturn1;
/****************判满函数StackNotFull(SeqStackS)*******/
intStackNotFull(SeqStackS)
if(S.top>
=maxsizestack)return0;
/******入堆栈StackPush(SeqStack*S,DateTypex)**********/
intStackPush(SeqStack*S,DataTypex)
if(S->
top>
=maxsizestack)
{
printf("
堆栈以满,无法插入\n"
);
return0;
else
S->
stack[S->
top]=x;
top++;
return1;
/********出堆栈函数StackPop(SeqStack*S,DateType*d)*/
intStackPop(SeqStack*S,DataType*d)
top<
=0)
堆栈以空无数据元素可出!
\n"
top--;
*d=S->
top];
/*********************LQueue**************************/
/***************初始化QueueInitiate(LQueue*Q)*******/
voidQueueInitiate(LQueue*Q)
Q->
front=NULL;
rear=NULL;
count=0;
/**************队列判空QueueNotEmpty(LQueueQ)******/
intQueueNotEmpty(LQueueQ)
if(Q.front==NULL)return0;
/******入队列QueueAppend(LQueue*Q,DataTypex)******/
voidQueueAppend(LQueue*Q,DataTypex)
LQNode*p;
p=(LQNode*)malloc(sizeof(LQNode));
p->
data=x;
next=NULL;
if(Q->
rear!
=NULL)Q->
rear->
next=p;
rear=p;
front==NULL)Q->
front=p;
count++;
/******出队列QueueDelete(LQueue*Q,DataType*d)******/
intQueueDelete(LQueue*Q,DataType*d)
front=NULL){
队列为空"
*d=Q->
front->
data;
p=Q->
front;
Q->
front=Q->
next;
if(Q->
free(p);
count--;
return1;
/*****************************************StackDelete.h文件*****************************************/
/*创建停车场内的任意一辆车的出堆栈函数,参数分别为该堆栈的
指针和该车辆的车牌号carID,输出值为该车辆进入停车场时的时间*/
voidStackDelete(SeqStack*S,longintcarID,float*tt)
intn=S->
top;
//记下未出堆栈S时堆栈内元素的个数
SeqStackT;
//创建辅助堆栈
DataTypex;
StackInitiate(&
T);
//初始化辅助堆栈T
while(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,&
StackPush(S,x);
/*将T中的元素还给S*/
top==n)*tt=0;
//如果此时栈顶指针的位置没有变换,说明S中没有该车牌号的车辆
/**********************************************PARK.CPP文件***************************************/
#include<
stdio.h>
PARK.h"
//typedefCarDataType;
//将抽象数据具体化
#definemaxsizestack4//停车场的容量为4
#include”StackDelete.h”
#definee1//停车场单位时间的收费为e=1
//为第一组,第二组,第三组测试数据编的主函数
voidmain()
SeqStackS1;
floatt;
//定义停车场堆栈S1,停车场辅助堆栈S2;
float*tt=&
t;
LQueueQ;
//定义变道队列Q
DataTypeca1,ca2;
//定义数据
S1);
//初始化S1;
QueueInitiate(&
Q);
//初始化Q;
DataTypetest[3]={
{1,10001,10},
{1,10002,20},
};
/*定义测试数据*/
for(inti=0;
i<
3;
i++)
StackPush(&
S1,test[i]);
}/*测试数据入堆栈*/
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);
该车停于便到的第%d个位置\n"
Q.count);
QueueAppend(&
Q,ca1);
StackDelete(&
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开始计时*/
elset=0;
//若该车辆不是从停车场开出的,显然其停留时间为
该车停留的时间t=%f,应收取的费用为money=%f\n"
t,t*e);
//为第四组数据编的主函数
voidmain()
//定义数据
//初始化S1;
//初始化Q;
DataTypetest[4]={
{1,10004,40},
4;
1.6测试情况
第一组数据的测试结果:
第二组数据的测试结果:
第三组数据的测试结果:
第四组数据的测试结果:
第二部分
求最短路径
2.1问题描述
在给定的图中,求出以任意顶点为源点,到其他顶点的最短路径。
2.2基本要求
1:
以邻接表作为存储结构。
用Dijkstra算法求最短路径。
按长度非递减次序打印输出最短路径长度以及所对应的路径。
2.3测试数据
2.3.1
无向图1
2.3.2
有向图2
2.4模块划分
AdijMGraph.h文件中:
其中包括邻接表存储结构下的图的数据结构的定义,包括顶点结构体的定义,便结构体的定义,邻接表的定义。
初始化函数,在图中插入顶点函数,在图中插入边的函数。
2:
AdjMGraphCreate.h文件:
包括RowCal结构体的定义,以及图的建立函数voidCreatGraph(AdjlGraph*G,DataTypev[],intn,RowCold[],inte)
Djikstra.h文件,最短路径的voidDijkstra(AdjlGraph*G,intv0,intdistance[],intpath[])函数。
4:
work2.cpp文件对测试数据编写的测试主函数。
2.5数据结构
//边节点
typedefstructNode
intcost;
//边权重
intdest;
structNode*next;
}Edge;
//图顶点结构
typedefstruct
DataTypedata;
intsource;
Edge*adj;
}AdjLHeight;
//邻接表结构下的图
AdjLHeighta[MaxVert];
intnumofVerts;
//顶点数
intnumofEdges;
//边数
}AdjlGraph;
//快速创建图所定义的结构
introw;
//弧尾
intcol;
//弧头
}RowCol;
2.6源程序
/*****************************************AdjMGraph.h文件******************************************/
/*数据结构的定义*/
//theheavyofEdge
/*边节点*/
//
//thenumberofvert
//thenumberofedge
//初始化图
voidAdjInitiate(AdjlGraph*G)
inti;
G->
numofVerts=0;
//顶点个数
numofEdges=0;
//边个数
for(i=0;
MaxVert;
G->
a[i].source=i;
a[i].adj=NULL;
//插入顶点
voidInsertVertex(AdjlGraph*G,inti,DataTypevertex)
if(i>
=0&
&
MaxVert)
a[i].data=vertex;
numofVerts++;
elseprintf("
顶点越界"
//插入边
voidInsertEdge(AdjlGraph*G,intv1,intv2,intcost)
Edge*p;
if(v1<
0||v1>
=G->
numofVerts||v2<
0||v2>
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实习 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)