[已解决]求一段程序

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！

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