数据结构实训报告样本.doc

n

更多企业学院：
《中小企业管理全能版》
183套讲座+89700份资料

《总经理、高层管理》
49套讲座+16388份资料

《中层管理学院》
46套讲座+6020份资料 

《国学智慧、易经》
46套讲座

《人力资源学院》
56套讲座+27123份资料

《各阶段职员培训学院》
77套讲座+ 324份资料

《职员管理企业学院》
67套讲座+ 8720份资料

《工厂生产管理学院》
52套讲座+ 13920份资料

《财务管理学院》
53套讲座+ 17945份资料 

《销售经理学院》
56套讲座+ 14350份资料

《销售人员培训学院》
72套讲座+ 4879份资料

学生实训汇报

实训名称： 数据结构实训

指导老师：

姓名：

学号：

班级：

日期：

一、实训项目项目名称：
全国交通咨询模拟

二、实训目标
1.熟悉图数据结构;
2.掌握图次序存放结构—邻接表;
3.掌握最短路径算法
4.上机调试程序,掌握查错、排错使程序能正确运行。

三．实训要求
1.每个人独立完成实训项目，相互之间能够交流，不能剽窃
2.实训结果包含程序代码和汇报
3.程序代码要有注释和说明

三、试验环境:
1.硬件环境: PC机
2.软件环环境:Windows +Visual C++6

四、算法描述:

建立图数据结构，采取邻接矩阵作为其存放结构。存放以上全国关键城市交通信息。经过软件模拟方法实现：给定出发点和终点，求出它们之间最短路径，并给出最短路径线路。

五、源程序清单:
#include <stdio.h>
#include<string.h>
#define VEX_NUM 26
#define MAXINT 1000000
typedef struct graph
{
char city[VEX_NUM][10];
int arcs[VEX_NUM][VEX_NUM];
}Mgraph;

void CreatGraph(Mgraph *G,int e);
void Dijkstra(Mgraph *Gn, int v0,int path[],int dist[]);
void PutPath(Mgraph *g,int v0,int v1,int p[],int d[]);
int index(char s[],Mgraph *g);

void main()
{
Mgraph *g;
int i;
int e;
int v0,v1;
char sr[10],dt[10];
int dist[VEX_NUM];
int path[VEX_NUM];
g=new Mgraph;
CreatGraph(g,30);
printf("输入出发城市和终点城市\n");
getchar();
gets(sr);
v0=index(sr,g);
gets(dt);
v1=index(dt,g);
Dijkstra(g,v0,path,dist);
PutPath(g,v0,v1,path,dist);
}

void CreatGraph(Mgraph *G,int e)
{
int i,j,k,cost;
printf("输入城市名称\n");
for(i=0;i<VEX_NUM;++i)
scanf("%s",G->city[i]);
for(i=0;i<VEX_NUM;i++)
for(j=0;j<VEX_NUM;j++)
G->arcs[i][j]=MAXINT;
printf("输入城市之间距离\n");
for(k=0;k<e;k++)
{
scanf("%d,%d,%d",&i,&j,&cost);
G->arcs[i][j]=cost;
G->arcs[j][i]=cost;
}
}

void Dijkstra(Mgraph *Gn, int v0,int path[],int dist[])
{
int s[VEX_NUM];
int v;
int w;
int i,j,k;
int min;
for(v=0; v<VEX_NUM; v++)
{
s[v]=0;
dist[v]=Gn->arcs[v0][v];
if(dist[v]<MAXINT)
path[v]=v0;
else path[v]=-1;
}
dist[v0]=0;s[v0]=1;
for(i=1;i<VEX_NUM -1;i++)
{
min=MAXINT;
for(w=0;w<VEX_NUM;w++)
if(!s[w] && dist[w]<min)
{
v=w;
min=dist[w];
}
s[v]=1;
for(j=0;j<VEX_NUM;j++)
if(!s[j] && (min+Gn->arcs[v][j]<dist[j]))
{
dist[j]=min+Gn->arcs[v][j];
path[j]=v;
}
}
}

void PutPath(Mgraph *g,int v0,int v1,int p[],int d[])
{
int k;
int next;
int top=0;
int st[20];
if(d[v1]<MAXINT && v1!=v0)
{
st[top++]=v1;
next=p[v1];
while(next!=v0)
{
st[top++]=next;

next=p[next];
}
}
else
if(v1!=v0)
{
printf("%s->%s:没有路径\n",g->city[v0],g->city[v1]);
return;
}
st[top++]=v0;
while(top)
{
next=st[--top];
if(top!=0)
printf("%s->",g->city[next]);
else
printf("%s\n",g->city[next]);
}
printf("两个城市之间最短距离为：%d\n",d[v1]);
}

int index(char s[],Mgraph *g)
{
int i;
for(i=0;i<VEX_NUM;i++)
if(strcmp(s,g->city[i])==0)
return i;
}
六、运行结果:

七、试验运行情况分析(包含算法、运行结果、运行环境等问题讨论)。