数据结构课程设计之校园导航

问题描述

为本校设计一个校园导航程序，具体要求如下： ① 校园地图存储于格式自定义的文本文件中，包括地点编号、名称、简介；道路名称、长度、
种类（车行、骑行、步行）等信息，至少包含 15 个地点、25 条道路。
② 能根据编号（或名称）查询任意地点、道路的相关信息。 ③ 能根据指定的出发、目的地点、导航方式（车行、骑行、步行），计算出最短路径。 ④ 能为用户提供从指定地点出发游览完其他所有地点的路线信息。

涉及算法及知识：

图的创建、遍历、最短路径、文本文件读 API。

源代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MaxName 15
#define MaxRoad 25
#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/

typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */

1、导入地点文件内容

typedef struct{
    int no;					//序号
    char name[8];			//名称
    char infor[40];			//地点信息
}place,Place[MaxName];

void InPlace(place a[MaxName]){
    FILE *fp1,*fp2;
    int i;
    fp1=fopen("地点.txt","r");
    fp2=fopen("地点信息.txt","r");
    if(fp1==NULL || fp2==NULL){			//判断文件是否打得开
        printf("不能打开文件！！");
        exit(0);
    }
    for(i=0;i<MaxName;i++){				//获取需要的信息
        fscanf(fp1,"%d%s",&a[i].no,a[i].name);
        fscanf(fp2,"%d%s",&a[i].no,a[i].infor);
    }

	//关闭文件
    fclose(fp1);
    fclose(fp2);
}

2、导入道路信息的内容

typedef struct{
    int last;				//道路一端的序号
	int next;				//道路另一端的序号
    char roadname[10];		//道路名称
    char roadinfor[40];		//内容
	int type;				//交通方式：车行、骑行、步行
    int len;				//长度
}road,Road[MaxRoad];

void InRoad(road a[MaxRoad]){
    FILE *fp1,*fp2;
    int i;
    fp1=fopen("道路.txt","r");			//判断文件是否打得开
	fp2=fopen("道路信息.txt","r");
    if(fp1==NULL || fp2==NULL){
        printf("不能打开文件！！");
        exit(0);
    }
    for(i=0;i<MaxRoad;i++){				//获取需要的信息
        fscanf(fp1,"%d%s%d%s",&a[i].type,a[i].roadname,&a[i].len,a[i].roadinfor);
		fscanf(fp2,"%d%s%d%s",&a[i].last,a[i].roadname,&a[i].next,a[i].roadinfor);
    }

	//关闭文件
    fclose(fp1);
	fclose(fp2);
}

查找地点信息与道路信息

void Lookplace(){
    place a[MaxName];
    int i,b;
    InPlace(a);						//导入地点信息
    for(i=0;i<MaxName;i++){
        printf("%d  %s\n",i,a[i].name);
    }
	printf("请输入查询地点的序号：");
    scanf("%d",&b);
    if(b<MaxName && b>=0){			//判断查询序号是否正确
        printf("\n%s：%s\n",a[b].name,a[b].infor);
    }
    else printf("\n查询出错，请确认序号查询范围内\n");
}

void Lookroad(){
    road a[MaxRoad];
    int i;
	char b;
    InRoad(a);
    for(i=0;i<MaxRoad;i++){
        printf("%d  %s\n",i,a[i].roadname);
    }
	printf("请输入查询地点的序号：");
    scanf("%d",&b);
    if(b<MaxRoad && b>=0){
        printf("\n%s：%s\n",a[b].roadname,a[b].roadinfor);
    }
    else printf("\n查询出错，请确认序号查询范围内\n");
}

创建有向图的邻接矩阵

 typedef struct{
    char vex[MaxName];			//顶点表
    int arc[MaxName][MaxName];	//邻接矩阵
	int n,e;					//边数，顶点数
 }graph;

//判断序号v是否存在于顶点表内
int locatevex(graph g,int v)
{
    int i;
    for(i=0;i<g.n;i++)
		if(g.vex[i]==v)
			return i;
    return -1;
}

 //创建邻接矩阵
 void creategraph(graph *g){
     int i,j,k,c,v1,v2;
	 place a[MaxName];
	 road b[MaxRoad];
	 InPlace(a);
	 InRoad(b);

	 g->n=MaxName;
	 g->e=MaxRoad;

	 //将序号存入顶点表内
     for(i=0;i<g->n;i++){
		g->vex[i]=a[i].no;
	 }
	 //初始化
     for(i=0;i<g->n;i++)
         for(j=0;j<g->n;j++)
             g->arc[i][j]=INFINITY;
	 //将道路长度存入邻接矩阵中
     for(k=0;k<g->e;k++)
     {
		v1=b[k].last;
		v2=b[k].next;
        i=locatevex(*g,v1);
		j=locatevex(*g,v2);
		for(c=0;c<g->e;c++)
			if(b[c].last==i && b[c].next==j || b[c].next==i && b[c].last==j){
				g->arc[i][j]=b[c].len;
				g->arc[j][i]=b[c].len;
		 }
     }
 }

DFS

int DFSvisited[MaxName];/* 访问标志数组*/
/*从第i个顶点出发递归地深度优先遍历图G*/
void DFS(graph g,int i)
{
    int j;
	place a[MaxName];
	InPlace(a);
	printf("===》%d.%s",g.vex[i],a[i].name);
    DFSvisited[i]=1;
    for(j=0;j<g.n;j++)
    {
        if((g.arc[i][j]>0)&&(DFSvisited[j]==0))
            DFS(g,j); //对i的尚未访问的邻接顶点j递归调用DFS 
    }
}

void DFStravel(graph g){
	int i;
	place a[MaxName];

    InPlace(a);
    for(i=0;i<MaxName;i++){
        printf("%d  %s\n",a[i].no,a[i].name);
    }
	printf("请输入起始地点的编号：");
	scanf("%d",&i);
	DFS(g,i);
	printf("\n");
}

最短路径之Floyd算法

int Floyd(graph *g)
{
    Vertex k,z,x,i,j;
	int D[MaxName][MaxName],path[MaxName][MaxName];
	place a[MaxName];
	InPlace(a);

	for(i=0;i<MaxName;i++){
        printf("%d  %s\n",a[i].no,a[i].name);
    }
	printf("请输入起始地点的编号：");
	scanf("%d",&z);
	printf("请输入结束地点的编号：");
	scanf("%d",&x);
    /* 初始化 */
    for ( i=0; i<g->n; i++ )
        for( j=0; j<g->n; j++ ) {
            D[i][j] = g->arc[i][j];
            path[i][j] = -1;
        }

	for( k=0; k<g->n; k++ )
        for( i=0; i<g->n; i++ )
            for( j=0; j<g->n; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
					g->arc[i][j]=D[i][j];
					
                    if ( i==j && D[i][j]<0 ) 
                        return 0; /* 不能正确解决，返回错误标记 */
                    path[i][j] = k;
                }
	printf("\n\n\n最短路程为：%d\n\n\n",g->arc[z][x]);
    return 1; /* 算法执行完毕，返回正确标记 */
}

void main（）

void main(){
	int i,z;
	graph g;
	creategraph(&g);
	printf("*******欢迎来到Ashios2的课程设计*******\n");
	printf("      1、根据编号查询地点的相关信息\n");
	printf("      2、根据编号查询道路的相关信息\n");
	//导航方式我并没有去实现，可以使用road里的type去实现
	printf("      3、指定的出发、目的地点、导航方式（车行、骑行、步行），计算出最短路径\n");
	printf("      4、从指定地点出发游览完其他所有地点的路线信息\n");
	printf("      0、退出系统\n");
	for(;;){
		printf("请输入你要的选项：");
		scanf("%d",&z);
		switch(z)
		{
		case 1:Lookplace();break;
		case 2:Lookroad();break;
		case 3:Floyd(&g);break;
		case 4:DFStravel(g);break;
		case 0:exit(0);
		}
	}
}

文本文件

道路.txt

地点.txt道路信息.txt

地点信息.txt

结尾

这是我第一次写博客，内容是这学期的数据结构课设。本来不打算发的，但是后来想想，还是发上来让大家看看，发的目的是为了让大家指正出我的一些不足及错误，以更好的改进代码水平，如果哪里做的不好的地方，还希望大家指出。
如果是初学数据结构的同学的话，推荐中国大学MOOC里浙江大学陈越教授和何钦铭教授，因为我就是看得他们的课程，个人感觉收获很多。

重点

本博客的所有内容只限于学习交流。