数据结构—课程设计（城市导航系统）
程序员文章站
2024-03-01 18:36:46
...
- Copyright (c) 2017, 烟台大学计算机学院
- *All rights reserved.
- *作 者：张行
- *完成日期：2017年12月22日
- *文件名称：hang.c
- *文件标识：无
- *内容摘要：该代码用于获取满足后缀要求的第一个文件
- *其他说明：无
-
*当前版本：V1.0
main.cpp
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "type.h"
#include <malloc.h>
int CreatGrath(MatGrath &G); //创造图
int DFS(MatGrath &G,int m);
void ShortestPath(MatGrath &G,int v,int w); //Dijkstra算法求最短路径
void Ppath(MatGrath &G,int path[],int w,int v); //前向递归查找路径上的顶点
int Ppath1(MatGrath &G,int path[][MAXV],int v,int w);//前向递归查找路径上的顶点
int ShortestMoney(MatGrath &G,int v,int w); //用floyd算法求最少费用
int menu(void);
int delet(MatGrath &G,int y,int x);
int search(MatGrath &G); //查找某一个城市的信息
int addbian(MatGrath &G); //增加城市的边信息
int adddian(MatGrath &G); //增加城市的信息
int modify(MatGrath &G); //修改城市信息
int display(MatGrath &G);//输出所有城市信息
int danyuan(MatGrath &G,int d); //求两点之间的最短路径
int Ppath2(MatGrath &G,int path[],int i,int v);
int main()
{
int a; //case语句的选择
int v,w; //用于求最好费用以及最短路程
int b; //选择两种最短
int c; //选择增加点还是增加边
int d; //定义单源的源点
int m; //用于DFS算法
int x,y; //代表删除点的两边城市的编号
MatGrath G;
system("color 1A"); /*修改控制台的颜色信息,改为绿字红底的模式*/
CreatGrath(G);
printf(" ■■■■■■■■■■■■■■■■■■■■ \n");
printf(" ■ ■ \n");
printf(" ■ ■■■■■■■■■■■■■■■■ ■ \n");
printf(" ■ ■欢迎来到烟台大学自制导航系统■ ■ \n");
printf(" ■ ■■■■■■■■■■■■■■■■ ■ \n");
printf(" ■ 作者：张行 ■ \n");
printf(" ■■■■■■■■■■■■■■■■■■■■ \n");
printf("\n");
printf(" 编号 城市名称\n");
printf(" 1 烟台市\n");
printf(" 2 青岛市\n");
printf(" 3 潍坊市\n");
printf(" 4 威海市\n");
printf(" 5 东营市\n");
printf(" 6 滨州市\n");
printf(" 7 德州市\n");
printf(" 8 聊城市\n");
printf(" 9 菏泽市\n");
printf(" 10 泰安市\n");
while(a!=9)
{
a=menu();
switch(a)
{
case 1:
printf("1-路径最短,2-费用最少，请选择");
scanf("%d",&b);
scanf("%d",&v);
scanf("%d",&w);
if(b==1)
{
ShortestPath(G,v,w);
}
if(b==2)
{
ShortestMoney(G,v,w);
}
break;
case 2:
search(G);
break;
case 3:
modify(G);
break;
case 4:
printf("1-增加边，2-增加点");
scanf("%d",&c);
if(c==1)
addbian(G);
else
adddian(G);
break;
case 5:
display(G);
break;
case 6:
scanf("%d",&d);
danyuan(G,d);
break;
case 7:
scanf("%d",&m);
DFS(G,m);
break;
case 8:
scanf("%d",&y);
scanf("%d",&x);
delet(G,y,x);
break;
case 9:
printf("欢迎使用，再见！\n");
exit(0);
break;
default:
break;
}
}
return 0;
}
#include"type.h"
#include <string.h>
/***********************
功能：创建图结构
输入：给图中的点赋予该点的编号，名称以及简介
输出：无
***********************/
int CreatGrath(MatGrath &G)//进行图的创建
{
int i,j;
G.vexnum=10; //说明图的顶点的数目
G.arcnum=14; //说明图的边的数目
for(i=1;i<=G.vexnum;i++)
{
G.vexs[i].no=i;
}
strcpy(G.vexs[1].sight,"烟台市");
strcpy(G.vexs[1].introduction,"山东省沿海城市，位于山东半岛中部");
strcpy(G.vexs[2].sight,"青岛市");
strcpy(G.vexs[2].introduction,"山东省沿海城市，位于山东半岛南部，有崂山风景区等众多景点");
strcpy(G.vexs[3].sight,"潍坊市");
strcpy(G.vexs[3].introduction,"景色优美，气候宜人，经济发达");
strcpy(G.vexs[4].sight,"威海市");
strcpy(G.vexs[4].introduction,"山东省辖地级市,位于山东半岛东端,北,东,南三面濒临 黄海");
strcpy(G.vexs[5].sight,"东营市");
strcpy(G.vexs[5].introduction,"山东省辖地级市,位于山东省东北部,黄河入海口的三角洲地带");
strcpy(G.vexs[6].sight,"滨州市");
strcpy(G.vexs[6].introduction,"山东省辖地级市,位于山东省北部、鲁北平原、黄河三角洲腹地");
strcpy(G.vexs[7].sight,"德州市");
strcpy(G.vexs[7].introduction,"山东省辖地级市,位于山东省西北部,北以新河为界,");
strcpy(G.vexs[8].sight,"聊城市");
strcpy(G.vexs[8].introduction,"山东省辖地级市，位于山东省西部，西部靠漳卫河与河 ");
strcpy(G.vexs[9].sight,"菏泽市");
strcpy(G.vexs[9].introduction,"位于山东西南部,鲁苏豫皖交界地带,东与济宁市相邻");
strcpy(G.vexs[10].sight,"泰安市");
strcpy(G.vexs[10].introduction,"位于山东省中部,是鲁中地区中心城，国家历史文化名城");
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
{
G.arc[i][j].length=INF;
G.arc[i][j].money=INF;
}
}
G.arc[1][3].length=G.arc[3][1].length=500;
G.arc[1][4].length=G.arc[4][1].length=200;
G.arc[3][5].length=G.arc[5][3].length=100;
G.arc[10][3].length=G.arc[3][10].length=800;
G.arc[6][4].length=G.arc[4][6].length=200;
G.arc[5][2].length=G.arc[2][5].length=200;
G.arc[2][4].length=G.arc[4][2].length=800;
G.arc[5][7].length=G.arc[7][5].length=500;
G.arc[2][4].length=G.arc[4][2].length=400;
G.arc[4][7].length=G.arc[7][4].length=600;
G.arc[6][8].length=G.arc[8][6].length=500;
G.arc[8][7].length=G.arc[7][8].length=300;
G.arc[6][9].length=G.arc[9][6].length=500;
G.arc[10][3].length=G.arc[3][10].length=600;
G.arc[1][3].money=G.arc[3][1].money=100;
G.arc[1][4].money=G.arc[4][1].money=250;
G.arc[3][5].money=G.arc[5][3].money=360;
G.arc[10][3].money=G.arc[3][10].money=5000;
G.arc[6][4].money=G.arc[4][6].money=200;
G.arc[5][2].money=G.arc[2][5].money=100;
G.arc[2][4].money=G.arc[4][2].money=450;
G.arc[5][7].money=G.arc[7][5].money=600;
G.arc[6][4].money=G.arc[4][6].money=120;
G.arc[4][7].money=G.arc[7][4].money=300;
G.arc[6][8].money=G.arc[8][6].money=460;
G.arc[8][7].money=G.arc[7][8].money=100;
G.arc[6][9].money=G.arc[9][6].money=640;
G.arc[10][3].money=G.arc[3][10].money=230;
return 1;
}
#include<stdio.h>
#include"type.h"
#include <string.h>
/***********************
功能：查找某一个城市的信息
输入：城市的编号
输出：城市的编号，名称以及简介
***********************/
int search(MatGrath &G)
{ int a;
int flag=1;
printf("请输入您要查询的城市编号\n");
scanf("%d",&a);
while(flag)
{
if(a<=0||a>G.vexnum)
{
printf("编号不存在，请重新输入\n");
scanf("%d",&a);
}
else
{ flag=0;
printf("编号 景点名称 简介 \n");
printf(" %-4d %-16s%-58s\n",G.vexs[a].no,G.vexs[a].sight,G.vexs[a].introduction);
;
}
}
return 0;
}
/***********************
功能：连接任意两个点
输入：两个点的编号
输出：无
***********************/
int addbian(MatGrath &G)
{ int b,c,d;
int i,j;
printf("请输入你要增加的边的两个点\n");
scanf("%d %d",&b,&c);
printf("请输入你要增加的边的权值\n");
scanf("%d",&d);
for (i=1; i<=G.vexnum;i++)
for (j=1;j<=G.vexnum;j++)
{
if((G.arc[i][j].length==INF)&&(i==b)&&(j==c))
{
G.arc[i][j].length=G.arc[j][i].length=d;
}
}
}
/***********************
功能：增加一个点
输入：与其他点的边的权值
输出：无
***********************/
int adddian(MatGrath &G)
{
int a;
int b;
int c;
int d;
char e[10]; //地点名
char f[100]; //地点介绍
int flag;
printf("请输入该城市的编号\n");
scanf("%d",&a);
G.vexs[a].no=a;
while(flag)
{
if(a>=0&&a<=G.vexnum)
{
printf("编号已经存在，请重新输入\n");
scanf("%d",&a);
G.vexs[a].no=a;
}
else
flag=0;
}
printf("请输入你要连接的点权值和所需费用\n");
scanf("%d",&b);
scanf("%d",&c);
scanf("%d",&d);
G.arc[a][b].money=G.arc[a][b].money=c;
G.arc[a][b].length=G.arc[b][a].length=d;
scanf("%s",G.vexs[a].sight);
scanf("%s",G.vexs[a].introduction);
G.vexnum++;
}
/***********************
功能：修改城市信息
输入：要修改的城市编号，以及修改后的城市信息
输出：无
***********************/
int modify(MatGrath &G)
{ int a;
int flag=1;
printf("请输入你要修改的城市的编号\n");
scanf("%d",&a);
while(flag)
{
if(a<=0||a>G.vexnum)
{
printf("编号不存在，请重新输入\n");
scanf("%d",&a);
}
else
flag=0;
}
printf("请输入你要修改的信息\n");
scanf("%s",G.vexs[a].sight);
scanf("%s",G.vexs[a].introduction);
}
/***********************
功能：输出所有的城市信息
输入：无
输出：输出所有的城市信息
***********************/
int display(MatGrath &G)
{
int i;
printf("城市编号 城市名称 城市介绍\n");
for (i=1; i<=G.vexnum;i++)
{
printf("% -9d % -10s %-15s\n",G.vexs[i].no,G.vexs[i].sight,G.vexs[i].introduction);
}
return 0;
}
/***********************
功能：用深度遍历输出城市信息
输入：无
输出：输出所有的城市信息
***********************/
bool visited[MAXV];
int DFS(MatGrath &G,int m)//深度优先搜索
{
int i;
printf("%d %s %s\n",G.vexs[m].no,G.vexs[m].sight,G.vexs[m].introduction);
visited[m]=true;
for(i=1;i<=G.vexnum;i++)
{
if(G.arc[m][i].length!=INF&&visited[i]==false)
{
DFS(G,i);
}
}
return 0;
}
/***********************
功能：删除某一个边
输入：边两边的城市编号
输出：无
***********************/
int delet(MatGrath &G,int y,int x)
{
G.arc[x][y].length=G.arc[y][x].length=INF;
return 0;
}
type.h
#include<stdio.h>
#define NO 30
#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示∞
typedef struct
{
int length;//边的长度，既两个地点之的长
int money;
}ArcCell; //定义边的类型
typedef struct
{ int no; //顶点的编号
char sight[10]; //地点
char introduction[100]; //地点的介绍
}VertexType; //定义顶点的类型
typedef struct
{
int vexnum; //顶点数
int arcnum; //边数
VertexType vexs[NO]; //在图结构体中调用点的结构体
ArcCell arc[NO][NO]; //在图结构体中调用边的结构体
}MatGrath;
menu.cpp
#include<stdio.h>
/***********************
功能：输出所有的功能目录
输入：选择的功能编号
输出：返回一个值给main函数
***********************/
int menu()
{ int c;
int flag;
do
{
flag=1;
printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n");
printf(" ┃ 1.选择出发点和目的地 ┃\n");
printf(" ┃ 2.查看景点信息 ┃\n");
printf(" ┃ 3.修改城市信息 ┃\n");
printf(" ┃ 4.增加景点信息 ┃\n");
printf(" ┃ 5.输出所有城市信息 ┃\n");
printf(" ┃ 6.输出单源路径 ┃\n");
printf(" ┃ 7.DFS遍历输出 ┃\n");
printf(" ┃ 8.删除节点 ┃\n");
printf(" ┃ 9.退出系统 ┃\n");
printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n");
printf(" 请输入您的选择\n");
scanf("%d",&c);
if(c==1||c==2||c==3||c==4||c==5||c==6||c==7||c==8||c==9)
flag=0;
}while(flag);
return c;
}
short.cpp
#include"type.h"
/***********************
功能：用floyd算法求给出的两点之间的最短路径
输入：出发地，目的地
输出：地点的最短路程以及路径
***********************/
//Dijkstra算法
void Ppath(MatGrath &G,int path[],int w,int v) //前向递归查找路径上的顶点
{
int k;
k=path[w];
if (k==v) return; //找到了起点则返回
Ppath(G,path,k,v); //找顶点k的前一个顶点
printf("%s->",G.vexs[k].sight); //输出顶点k
}
int ShortestPath(MatGrath &G,int v,int w)//求两点之间的最短路径
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for (i=0; i<G.vexnum; i++)
{
dist[i]=G.arc[v][i].length; //距离初始化
s[i]=0; //s[]置空
if (G.arc[v][i].length<INF) //路径初始化
path[i]=v; //v到i有边
else
path[i]=-1; //v到i没有边，置顶点i的前一个顶点为-1
}
s[v]=1;
path[v]=0; //源点编号v放入s中
for (i=0; i<G.vexnum; i++) //循环直到所有顶点的最短路径都求出
{
mindis=INF; //mindis置最小长度初值
for (j=0; j<G.vexnum; j++) //选取不在s中且具有最小距离的顶点u
if (s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1; //顶点u加入s中
for (j=0; j<G.vexnum; j++) //修改不在s中的顶点的距离
if (s[j]==0)
if (G.arc[u][j].length<INF && dist[u]+G.arc[u][j].length<dist[j])
{
dist[j]=dist[u]+G.arc[u][j].length;
path[j]=u;
}
}
if (s[w]==1)
{
printf(" 从%s到%s的最短路径长度为:%d米\t路径为:",G.vexs[v].sight,G.vexs[w].sight,dist[w]);
printf("%s->",G.vexs[v].sight); //输出路径上的起点
Ppath(G,path,w,v); //输出路径上的中间点
printf("%s\n",G.vexs[w].sight); //输出路径上的终点
}
if(s[w]==0)
printf("从%d到%d不存在路径\n",v,w);
}
/***********************
功能：用floyd算法求给出的两点之间的最好费用
输入：出发地，目的地
输出：地点的最少费用以及路径
***********************/
//Floyd算法
int Ppath1(MatGrath &G,int path[][MAXV],int v,int w) //前向递归查找路径上的顶点
{
int k;
k=path[v][w];
if (k==-1) return 0; //找到了起点则返回
Ppath1(G,path,v,k); //找顶点i的前一个顶点k
printf("%s->",G.vexs[k].sight);
Ppath1(G,path,k,w); //找顶点k的前一个顶点j
}
void ShortestMoney(MatGrath &G,int v,int w)//求花费最少的路径
{
int A[MAXV][MAXV],path[MAXV][MAXV];
int i,j,k;
for (i=0; i<G.vexnum; i++)
for (j=0; j<G.vexnum; j++)
{
A[i][j]=G.arc[i][j].money;
path[i][j]=-1; //i到j没有边
}
for (k=0; k<G.vexnum; k++)
{
for (i=0; i<G.vexnum; i++)
for (j=0; j<G.vexnum; j++)
if (A[i][j]>A[i][k]+A[k][j])
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
if (A[v][w]==INF)
{
if (v!=w)
printf("从%d到%d没有路径\n",v,w);
}
else
{
printf(" 从%s到%s路径费用:%d元人民币 路径:",G.vexs[v].sight,G.vexs[w].sight,A[v][w]);
printf("%s->",G.vexs[v].sight); //输出路径上的起点
Ppath1(G,path,v,w); //输出路径上的中间点
printf("%s\n",G.vexs[w].sight); //输出路径上的终点
}
}
/***********************
功能：用Dijkstra算法求给出的一点到其余个点的最短路径
输入：源点
输出：地点的最短路程以及路径
***********************/
//Dijkstra算法求单源路径
int Ppath2(MatGrath &G,int path[],int i,int v) //前向递归查找路径上的顶点
{
int k;
k=path[i];
if (k==v)
return k; //找到了起点则返回
Ppath2(G,path,k,v); //找顶点k的前一个顶点
printf("%s->",G.vexs[k].sight);//输出顶点k
}
int danyuan(MatGrath &G,int v)//求两点之间的最短路径
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for (i=1; i<=G.vexnum; i++)
{
dist[i]=G.arc[v][i].length; //距离初始化
s[i]=0; //s[]置空
if (G.arc[v][i].length<INF) //路径初始化
path[i]=v;
else
path[i]=-1;
}
s[v]=1;
path[v]=0; //源点编号v放入s中
for (i=1; i<=G.vexnum; i++) //循环直到所有顶点的最短路径都求出
{
mindis=INF; //mindis置最小长度初值
for (j=1; j<=G.vexnum; j++) //选取不在s中且具有最小距离的顶点u
if (s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1; //顶点u加入s中
for (j=1; j<=G.vexnum; j++) //修改不在s中的顶点的距离
if (s[j]==0)
if (G.arc[u][j].length<INF && dist[u]+G.arc[u][j].length<dist[j])
{
dist[j]=dist[u]+G.arc[u][j].length;
path[j]=u;
}
}
for(i=1; i<=G.vexnum; i++)
if (s[i]==1&&v!=i)
{
printf(" 从%s到%s的最短路径长度为:%d米\t路径为:",G.vexs[v].sight,G.vexs[i].sight,dist[i]);
printf("%s->",G.vexs[v].sight); //输出路径上的起点
Ppath2(G,path,i,v); //输出路径上的中间点
printf("%s\n",G.vexs[i].sight); //输出路径上的终点
}
}