[已解决]求一段程序

haoduoduoyu · 发表于 2018-1-12 10:00:47

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

中国铁路站点分布图（3人）
输入文件是stations.xls，该文件保存有某次列车途经的所有车站名（地名）及与始发站的距离。
1）首先将该文件保存为便于处理的文本文件。
2）对该文件处理的结果是输出有铁路直接连接的两个地名及其距离，如果有冲突，保留最小值，例如：
T1 A B 150km
K33 A B 147km
此时A与B间距离有两个，则保留最小的147
3）最终输出rwmap.txt，该文件中每行均是如下格式
A B L
其中A、B是地名，L是两个城市间铁路的距离。
4）在输出文件基础上，实现图的基本操作。
5）在4）的基础上，计算从某个城市到其它城市的最短路径。
6）输出文件可以作为图的基础数据文件供其他组同学使用，也可以自己使用。

冥思苦想一整天毫无思路拜托众大佬了

问题是这样的之前有大佬回复过我，给了思路但是实在能力有限做不出来，这是我们的课程设计，做不出来要重修求大佬！！！

最佳答案

月排行榜 / 总排行榜

8306最硬

2018-1-12 19:02:24

本帖最后由 8306最硬于 2018-1-13 00:47 编辑

看不太懂题目，但是直觉告诉我这是数据结构的题目。
你可以做一张无向图，地点为顶点，距离为权值，如果你学过数据结构的话。
然后最核心的是最短距离的计算吧，我以前课程设计也是地图，可以用那个费啥啥的算法，我贴一段出来。

void ShowShortPath(Map &G,int p1,int p2){
/* G--图，p1，p2--要计算距离的地点 */
int v,u,w,i;
int D[G.vexnum][G.vexnum],p[G.vexnum][G.vexnum][G.vexnum];
/* D为邻接矩阵副本,P为最优路径 */
for(v=0;v<G.vexnum;v++){
for(w=0;w<G.vexnum;w++){
D[v][w]=G.adj[v][w].ArcVal;
for(u=0;u<G.vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY){
p[v][w][v]=1;p[v][w][w]=1;
}//end if
}// end for
}// end for
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]){
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}//end if
for (i=0; i<G.vexnum;i++)
if (p[p1][p2][i]){
printf("%s-->",G.vexs[i]);
}//end if
printf("\b\b\b 路径长度:%dm\n\n",D[p1][p2]);

复制代码

希望帮助到你，至于excel和txt的接口操作什么的，百度就一抓一大把了。
但是！！但是如果你没有学过数据结构
我猜那就只能到此为止了

跳转到最佳答案楼层

Dr丶温 · 发表于 2018-1-12 11:49:28

虽然看不懂是啥，但是感觉是好厉害的东东。。。

z402375830 · 发表于 2018-1-12 12:36:27

兄台，我虽然还没有学到这里，但是可以给你提供一些思路（本人只学过C，在学C++）。

1. 可以设置一个原始为0的地点，例如北京，那么你A地点和 B地点就有了一个统一的公里数。（也就是距离北京多少公里）；
2. 手动封装函数，函数内为各大铁路线，或者地理详细信息等。

haoduoduoyu · 发表于 2018-1-12 13:28:11

z402375830 发表于 2018-1-12 12:36
兄台，我虽然还没有学到这里，但是可以给你提供一些思路（本人只学过C，在学C++）。

1. 可以设置一个 ...

老哥我也有思路就是不会代码啊

haoduoduoyu · 发表于 2018-1-12 13:29:33

Dr丶温发表于 2018-1-12 11:49
虽然看不懂是啥，但是感觉是好厉害的东东。。。

我们整个班都不会，只学过一个星期的java现在告诉我们要搞出这个程序，一堆专业术语，搞不成就重修

Dr丶温 · 发表于 2018-1-12 16:43:39

兄弟，保重。。。

8306最硬 · 发表于 2018-1-12 19:02:24

本帖最后由 8306最硬于 2018-1-13 00:47 编辑

看不太懂题目，但是直觉告诉我这是数据结构的题目。
你可以做一张无向图，地点为顶点，距离为权值，如果你学过数据结构的话。
然后最核心的是最短距离的计算吧，我以前课程设计也是地图，可以用那个费啥啥的算法，我贴一段出来。

void ShowShortPath(Map &G,int p1,int p2){
/* G--图，p1，p2--要计算距离的地点 */
int v,u,w,i;
int D[G.vexnum][G.vexnum],p[G.vexnum][G.vexnum][G.vexnum];
/* D为邻接矩阵副本,P为最优路径 */
for(v=0;v<G.vexnum;v++){
for(w=0;w<G.vexnum;w++){
D[v][w]=G.adj[v][w].ArcVal;
for(u=0;u<G.vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY){
p[v][w][v]=1;p[v][w][w]=1;
}//end if
}// end for
}// end for
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]){
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}//end if
for (i=0; i<G.vexnum;i++)
if (p[p1][p2][i]){
printf("%s-->",G.vexs[i]);
}//end if
printf("\b\b\b 路径长度:%dm\n\n",D[p1][p2]);

复制代码

希望帮助到你，至于excel和txt的接口操作什么的，百度就一抓一大把了。
但是！！但是如果你没有学过数据结构
我猜那就只能到此为止了

print官方旗舰店 · 发表于 2018-1-12 21:58:56

看不懂怎么办

newyutao · 发表于 2018-1-12 23:03:46

haoduoduoyu · 发表于 2018-1-13 00:39:44

8306最硬发表于 2018-1-12 19:02
看不太懂题目，但是直觉告诉我这是数据结构的题目。
你可以做一张无向图，地点为顶点，距离为权值，如果你 ...

谢谢老哥！！！

不过你猜的不错，老哥高见

haoduoduoyu · 发表于 2018-1-14 15:47:20

8306最硬发表于 2018-1-12 19:02
看不太懂题目，但是直觉告诉我这是数据结构的题目。
你可以做一张无向图，地点为顶点，距离为权值，如果你 ...

#include<iostream>
#include<string>
#include<conio.h>
using namespace std;
#include'Map.h'
//邻接矩阵的类型定义
#define MAX 10000000
#define MAX_VERTEX_NUM 20
typedef struct
{
string vexs[MAX_VERTEX_NUM];//用一维数组存储顶点信息
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二维数组充当矩阵，来存储顶点边的信息
int vexnum,edgenum;//顶点数和边数
}MGraph;
/*构造有向网的邻接矩阵*/
void ShowShortPath(Map &G,int p1,int p2){
/* G--图，p1，p2--要计算距离的地点 */
int v,u,w,i;
int D[G.vexnum][G.vexnum],p[G.vexnum][G.vexnum][G.vexnum];
/* D为邻接矩阵副本,P为最优路径 */
for(v=0;v<G.vexnum;v++){
for(w=0;w<G.vexnum;w++){
D[v][w]=G.adj[v][w].ArcVal;
for(u=0;u<G.vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY){
p[v][w][v]=1;p[v][w][w]=1;
}//end if
}// end for
}// end for
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]){
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}//end if
for (i=0; i<G.vexnum;i++)
if (p[p1][p2][i]){
printf("%s-->",G.vexs[i]);
}//end if
printf("\b\b\b 路径长度:%dm\n\n",D[p1][p2]);
int main(void)
{
int data;
FILE *fp=fopen("stations.txt","r");
if(!fp)
{
printf("can't open file\n");
return -1;
}
while(!feof(fp))
{
fscanf(fp,"%c",&data);
printf("%c",data);
}
printf("\n");
fclose(fp);
return 0;
}

复制代码

大神我这调用了这个stations文件结果各种报错实在是不知道怎样定义类怎样纠错了您帮帮我吧

haoduoduoyu · 发表于 2018-1-14 15:50:52

8306最硬发表于 2018-1-12 19:02
看不太懂题目，但是直觉告诉我这是数据结构的题目。
你可以做一张无向图，地点为顶点，距离为权值，如果你 ...

这个是stations这个文件

8306最硬 · 发表于 2018-1-14 18:28:37

本帖最后由 8306最硬于 2018-1-14 19:20 编辑

haoduoduoyu 发表于 2018-1-14 15:50
这个是stations这个文件

嗯.. 我攀不上大神啊，只是恰巧课程设计也是做图

我看了错误大多是变量名没对上而已，比如
INFINITY-->MAX
邻接矩阵adj
权值ArcVal
ShowShortPath函数也少了个括号}

其他不好说，好像图的定义也没定义全..
文件只是打印数据没存起来吗，我看的有点云里雾里
这样我发我的课程设计给你琢磨琢磨吧？代码很初级效果也很水，但是弄出来及格还是没问题的

（BTW我用的是c-free）

8306最硬 · 发表于 2018-1-14 18:34:13

本帖最后由 8306最硬于 2018-1-14 18:44 编辑

/****** Graph.h *******/
#include <stdio.h>
#include <string.h>
#define MAX_VEXTEX_NUM 9
#define INFINITY 65535
typedef struct ArcCell{
/* 边的结构体 */
char *vex1,*vex2; //对应顶点
int ArcVal; //权值
char *info;
}ArcCell,AdjMatrix[MAX_VEXTEX_NUM][MAX_VEXTEX_NUM];
typedef struct Map{
/* 图的结构体 */
char *vexs[MAX_VEXTEX_NUM];
int vexnum,arcnum;
AdjMatrix adj; //邻接矩阵
}Map;
/* 定位顶点 */
int LocateVex(Map &G,char *vp){
int k;
for (k=0 ; k<MAX_VEXTEX_NUM ; k++)
if (!strcmp(G.vexs[k],vp)) return(k) ;
return (-1);
}
/* 创建图 */
int CreateMap(Map &G){
G.arcnum = 0;
G.vexnum = 0;
G.adj[G.vexnum][G.vexnum].ArcVal = INFINITY;
return 0;
}
/* 添加顶点 */
int AddVertex(Map &G , char *vp){
/* if (LocateVex(G , vp)!=-1){
printf("Vertex has existed !\n");
return(-1) ;
}*/
G.vexs[G.vexnum] = vp;
G.adj[G.vexnum][G.vexnum].ArcVal = INFINITY;
for (int j=0,k=G.vexnum; j<G.vexnum; j++){
G.adj[j][k].ArcVal = INFINITY;
G.adj[k][j].ArcVal = INFINITY;
/* 初始化顶点各边设为INFINITY */
}
G.vexnum++;
return 0;
}
/* 添加边 */
int AddArc(Map &G , char *vex1, char *vex2, int ArcVal)
{
int i = LocateVex(G , vex1), j = LocateVex(G , vex2);
if (i==-1||j==-1){
printf("Arc’s Vertex do not existed !\n") ;
return(-1) ;
}
G.adj[i][j].ArcVal=ArcVal ;
G.adj[j][i].ArcVal=ArcVal ;
G.adj[i][j].vex1=vex1 ;
G.adj[i][j].vex2=vex2 ;
G.adj[j][i].vex1=vex1 ;
G.adj[j][i].vex2=vex2 ;
/* G.adj[i][j].info=info;
G.adj[j][i].info=info; */
/* 对称矩阵赋值两次 */
G.arcnum++;
return 0;
}

复制代码

这里主要的函数是
边和图的初始化
CreateMap创建图
AddVertex添加顶点(地点)
AddArc添加边，主要包括权值(地点间的距离)
之后怎么做呢，很简单。
只要把你的数据读取出来，把地点和距离添加进图里面，图就算写好了，最短距离的计算建立在你写好图的基础上。

8306最硬 · 发表于 2018-1-14 18:35:24

本帖最后由 8306最硬于 2018-1-14 18:48 编辑

/******* main.c ********/
#include "Graph.h"
#include <stdio.h>
#include <string.h>
char *position[MAX_VEXTEX_NUM] = {
"北门","饭堂","艺设学院","学生宿舍","英东楼","图书馆","教学楼","行政楼","南门"
};
void ShowShortPath(Map &G,int p1,int p2){
int v,u,w,i;
int D[G.vexnum][G.vexnum],p[G.vexnum][G.vexnum][G.vexnum];
/* D为邻接矩阵副本,P为最优路径 */
for(v=0;v<G.vexnum;v++){
for(w=0;w<G.vexnum;w++){
D[v][w]=G.adj[v][w].ArcVal;
for(u=0;u<G.vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY){
p[v][w][v]=1;p[v][w][w]=1;
}//end if
}// end for
}// end for
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]){
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}//end if
if (p1<p2){
/**
* 如果键入号码为顶点顺序则正常输出
* 如果键入号码为顶点逆序则反向输出*/
for (i=0; i<G.vexnum;i++)
if (p[p1][p2][i]){
printf("%s-->",G.vexs[i]);
}//end if
}
else{
for (i=G.vexnum; i>=0; i--)
if (p[p1][p2][i]){
printf("%s-->",G.vexs[i]);
}//end if
}//end else
/* for (int i=0;i<strlen(G.adj[p1][p2].info);i++)
printf("\b");*/
printf("\b\b\b 路径长度:%dm\n\n",D[p1][p2]);
}
int main(){
Map MySchool;
int position_1,position_2;
CreateMap(MySchool);
for (int i = 0; i < MAX_VEXTEX_NUM; i++)
/* 初始化顶点 */
AddVertex(MySchool, position[i]);
AddArc(MySchool, "学生宿舍", "饭堂", 134);
AddArc(MySchool, "北门", "艺设学院", 132);
AddArc(MySchool, "饭堂", "艺设学院", 64);
AddArc(MySchool, "艺设学院", "英东楼", 220);
AddArc(MySchool, "艺设学院", "学生宿舍", 79);
AddArc(MySchool, "艺设学院", "图书馆", 300);
AddArc(MySchool, "英东楼", "图书馆", 93);
AddArc(MySchool, "英东楼", "教学楼", 84);
AddArc(MySchool, "图书馆", "教学楼", 61);
AddArc(MySchool, "行政楼", "南门", 113);
AddArc(MySchool, "教学楼", "行政楼", 63);
AddArc(MySchool, "图书馆", "行政楼", 108);
AddArc(MySchool, "英东楼", "行政楼", 147);
/* 初始化边 */
for (int i=0; i < MySchool.vexnum; i++)
/* 打印各地点 */
printf("/* %d:%s \n",i,position[i]);
while(1){
printf("输入当前地址号码:");
scanf("%d",&position_1);
printf("输入目的地址号码:");
scanf("%d",&position_2);
/* 等待键入地点编码 */
if ( position_1 >= 0 &&
position_2 >= 0 &&
position_1 <= MySchool.vexnum &&
position_2 <= MySchool.vexnum &&
position_1 != position_2 )
/* 判断键入范围 */
ShowShortPath(MySchool,position_1,position_2);
/* 输出最优路径和距离 */
else printf("\n别乱来\n");
}// end while
return 0;
}

复制代码

两个函数
一个是计算最短距离ShowShortPath
一个是main函数，用于输入顶点和边，计算距离，输出结果
程序到这大致就写好了(我的程序)，你的就多了输入文件和输出文件两步咯
但要详细解释还真不好说啊..不管怎样，兄弟加油吧..

haoduoduoyu · 发表于 2018-1-16 00:43:54

8306最硬发表于 2018-1-14 18:35
两个函数
一个是计算最短距离ShowShortPath
一个是main函数，用于输入顶点和边，计算距离，输出结果

很受启发，已经完成了！谢谢兄dei！

账号		自动登录	找回密码
密码			立即注册