#include<bits/stdc++.h>
#include<stdlib.h>
#include<windows.h>
#include<string>
#include<string.h>
#define MaxVertexNum 100
#define Never 100000
using namespace std;
typedef struct info
{
int num;//序号
char name[100];//名字
char features[200]; //简介
}VertexType;
//图的存储结构：
typedef int EdgeType;
typedef struct mp{
EdgeType Edge[MaxVertexNum][MaxVertexNum];
int vn, en;//点数，边数
VertexType Vexs[MaxVertexNum] = {
{0,"体检中心","体检用的地方"},{1,"操场","体育课,社团锻炼的地方"},
{2,"校门北口","挨着小吃街,叫北街"},{3,"银杏景观","秋天的拍照聚集地"},
{4,"餐厅","beautiful"},{5,"校门东口","啥也没有"},
{6,"图书馆","高调奢华,考试前爆满"},{7,"花园景观","有花有草"},
{8,"校门南口","正门"},{9,"信息学部","很厉害的样子"},
{10,"邯郸音乐厅","好活动,大活动都在那"},{11,"网计学院","别问,问就是nb"}
};
}MGraph;
MGraph SchoolMap;
int now=12;
int Distance[MaxVertexNum][MaxVertexNum]; //记录最短的路径
int Path[MaxVertexNum][MaxVertexNum]; // 记录路径
int Length[MaxVertexNum][MaxVertexNum];
void initLoading();
void Login(); //登录
void Admin(); //管理
void Visitor();//游客
void Inite( MGraph &G );//创建无向图
void GetVex(MGraph &G);
void InsertPath(MGraph &G);//加路径
void InsertVertex( MGraph &G);//添加点
void DeleteVertex( MGraph &G);//删除节点
void DeletePath( MGraph &G);//删除路
void search_All_The_Shotest(MGraph &G);
void search_Shotest(MGraph &G);
void showAll(MGraph &G);
void Modify(MGraph &G);
void Floyd(MGraph &G);
int main()
{
Floyd(SchoolMap);
initLoading();
}
void InsertVertex( MGraph &G)//加点
{
char newname[100];
char information[100];
getchar();
printf("\t请输入新节点点的信息:\n");
printf("新节点的名字和简介空格分隔\n");
scanf("%s%s",newname,information);
G.Vexs[now].num=now;
strcpy(G.Vexs[now].name,newname);
strcpy(G.Vexs[now].features,information);
printf("%s",G.Vexs[now].name);
printf("%s",G.Vexs[now].features);
G.vn++;
now++;
}
void Visitor()
{
Floyd(SchoolMap);
printf("\n\t\t****************************************");
printf("\n\t\t* *");
printf("\n\t\t* 1.查询景点信息 *");
printf("\n\t\t* *");
printf("\n\t\t* 2.查找某点到其他地方的最短路径 *");
printf("\n\t\t* *");
printf("\n\t\t* 3.查找两点的最短路径 4.退出 *");
printf("\n\t\t* *");
printf("\n\t\t****************************************");
int choice=0;
showAll(SchoolMap);
while(1)
{
printf("\n\t\t输入功能选项>>>>>>>>>>>>:");
scanf("%d",&choice);
switch(choice)
{
case 1:GetVex(SchoolMap);break;
case 2:search_All_The_Shotest(SchoolMap);break;
case 4:exit(0);break;
case 3:search_Shotest(SchoolMap);break;
default:printf("重新输入:\n");
}
}
}
void GetVex(MGraph &G)
{
char The_name[100];
printf("请输入要查询的地方的名称:>>>:");
scanf("%s",The_name);
getchar();
int i,yes=0;
printf("\t序号\t\t名称\t\t\t简****************介\n\n");
for(i=0;i<G.vn;++i)
{
if(strcmp(The_name,G.Vexs[i].name)==0)
yes=1,printf("\t%d\t\t%s\t\t\t%s\n\n\n",i,G.Vexs[i].name,G.Vexs[i].features);
}
if(yes==0)
printf("failed! 结束\n");
else
printf("success! 结束\n");
}
void Admin()
{
printf("\t\t***用户登录***\n\n");
FILE *fp=fopen("pwd.config","r");
if(fp == NULL)
printf("因为文件损坏,不存在管理员用户"),Visitor(),exit(0);
int len=0;
int first=1;
char buf[1024];
char fusername[1024];
char fpassword[1024];
while( fgets( buf, 1024, fp) != NULL )
{
len = strlen(buf);
buf[len-1] = '\0'; /*去掉换行符*/
if(buf[0]=='\0')break;
// printf("%s %d \n",buf,len - 1);
if(first==1)printf("\t\t本地用户名读取成功\n\n"),first=2,strcpy(fusername,buf);
else printf("\t\t密码读取成功\n\n"),strcpy(fpassword,buf);
}
int count=3;
char username[1000];
char password[1000];
while(count--)
{
printf("请输入用户名&密码:\n\n");
printf("............用户名:>>>>>:");
gets(username);
printf("............密 码:>>>>>:");
gets(password);
if(strcmp(fusername,username)==0&&strcmp(fpassword,password)==0)
{
printf("登录成功,3秒钟后跳转"),Sleep(3000);break;
}
}
if(count==0)printf("输入错误超过三次,自动切换为游客模式"),Visitor(),exit(0);
showAll(SchoolMap);
printf("\n\t\t****************************************");
printf("\n\t\t* 1.增加景点信息 2.删除景点信息 *");
printf("\n\t\t* *");
printf("\n\t\t* 3.更改景点信息 4.查询景点信息 *");
printf("\n\t\t* *");
printf("\n\t\t* 5.增加道路 6.删除道路 *");
printf("\n\t\t* *");
printf("\n\t\t* 7.某点到其他点的最短路径 *");
printf("\n\t\t* *");
printf("\n\t\t* 8.浏览景点信息 9.退出 *");
printf("\n\t\t* 0.某点到某点的最短 *");
printf("\n\t\t****************************************\n\n");
int choice=0;
while(1)
{
Floyd(SchoolMap);
printf("\n\t\t选择功能:>>>>>>>>>>>>:");
scanf("%d",&choice);
switch(choice)
{
case 1:InsertVertex(SchoolMap);break;
case 2:DeleteVertex(SchoolMap);break;
case 3:Modify(SchoolMap);break;
case 4:GetVex(SchoolMap);break;
case 5:InsertPath(SchoolMap);break;
case 6:DeletePath(SchoolMap);break;
case 7:search_All_The_Shotest(SchoolMap);break;
case 8:showAll(SchoolMap);break;
case 9:exit(0);break;
case 0:search_Shotest(SchoolMap);break;
default:;
}
}
}
void InsertPath(MGraph &G)//加边
{
showAll(SchoolMap);
int N=0;
printf("请输入要添加的边数目>>>:");
scanf("%d",&N);
int x,y,len;
while(N--)
{
printf("请输入要加入路径的两个编号,以空格分隔,如：2 3 100\n");
scanf("%d %d %d",&x,&y,&len);
if(x<G.vn&&y<G.vn)
{
Length[x][y]=Length[y][x]=len;
G.en++;
printf("success\n");
} else{
printf("添加失败,输入了不存在的序号\n");
}
}
printf("添加路径结束\n");
system("pause");
}
void DeletePath( MGraph &G)
{
showAll(SchoolMap);
int N=0;
printf("请输入要删除的边数目>>>:");
scanf("%d",&N);
int x,y,len;
while(N--)
{
printf("请输入要删除路径的两个编号,以空格分隔,如：2 3 100\n");
scanf("%d %d %d",&x,&y,&len);
if(x<G.vn&&y<G.vn)
{
Length[x][y]=Length[y][x]=Never;
G.en++;
printf("success\n");
} else{
printf("删除失败,输入了不存在的序号\n");
}
}
printf("删除路径结束\n");
system("pause");
system("cls");
}
void Modify(MGraph &G){//修改景点信息
showAll(SchoolMap);
char newName[100];
char newinfo[100];
showAll(SchoolMap);
int N=0;
printf("\t输入要修改的节点数目>>:");scanf("%d",&N);getchar();
while(N--)
{
printf("\t请输入要修改的序号和简介,以空格分隔>>>>");
int number;
scanf("%d%s",&number,newinfo);
getchar();
if(G.vn>number)
{
strcpy(G.Vexs[number].features,newinfo);
printf("\t修改完毕\n\n");
}else
{
printf("\t不存在\n\n");
}
}
printf("\n\n\t修改节点信息结束按任意键回到初始界面\n");
system("pause");
//system("cls");
}
void DeleteVertex( MGraph &G)
{
int N=0;
printf("\t请输入要删除的点的数目>>>:");
scanf("%d",&N);
int x,i,j;
int count=0;
printf("\t请输入要删除的点的编号,回车符结束,如：2\n\n");
scanf("%d",&x);
count=0;
if(x<G.vn)
{
for(i=x;i<G.vn-1;++i)
{
for(j=0;j<G.vn;++j)
{
if(Length[x][j]<Never)count++;
Length[j][i]=Length[i][j]=Length[i+1][j];
}
}
for(i=0;i<G.vn;++i)
{
for(j=x;j<G.vn-1;++j)
{
Length[i][j]=Length[j][i]=Length[i][j+1];
printf("123");
}
}
for(i=x;i<G.vn-1;++i)
{
G.Vexs[i].num = G.Vexs[i+1].num;
strcpy(G.Vexs[i].name, G.Vexs[i+1].name);
strcpy(G.Vexs[i].features, G.Vexs[i+1].features);
}
G.en-=count;
G.vn-=1;
printf("success\n");
}else{
printf("添加失败,输入了不存在的序号\n");
}
printf("删除结束,按任意键回到初始界面\n");
system("pause");
//system("cls");
}
void initLoading()//初始话加载
{
int i=0;
printf("加载中");
for(i=0;i<10;++i)
printf("******"),Sleep(120);
system("cls");
printf("\n\n\n");
printf("\t Welcome,Welcome,Welcome,Welcome!...................作者:一个刚刚学数据结构的web菜汪:何止\n\n");
printf("\t へ ／|\n");
printf("\t / ＼ ∠Z/\n");
printf("\t / Z │ ／ ／\n");
printf("\t / Z ＿,＜ ／ /\\ヽ\n");
printf("\t │ ヽ\ / /〉\n");
printf("\t Y \\ / / /\n");
printf("\t ィ● 、 ● \\〈/\n");
printf("\t () へ () ＼〈\n");
printf("\t \>--___--ィ│／\n");
printf("\t /へ/ ／ |＼＼\n");
printf("\t /ヽ_/ (_／ │／\n");
printf("\t 7 \\ \\ \n");
printf("\t (>>―-￣￣`-―＿) \n");
printf("\n");
Inite(SchoolMap);//初始话
printf("\n\n\n\t...加载完毕............................ 画了一下午求多给两分叭!\n\n\n");
printf("\t即将进入登录阶段\t");
system("pause");
printf("\t");
system("cls");
Login();
}
void Login()
{
int choic = -1;
printf("\t选择登录方式:1.管理员登录\t\t2.游客登录\n");
printf("\n");
printf("\t 0.退出\n\n\n\n");
while(1)
{
printf("\t>>>>>>>>>>>>:");
scanf("%d",&choic);
getchar();
// printf("你输入了%d\n",choic);
switch(choic)
{
case 1:Admin();break;
case 2:Visitor();break;
case 0:exit(0);break;
default:break;
}
}
}
void showAll(MGraph &G)
{
int i=0;
int count=0;
printf("now=%d VN=%d\n",now,G.vn);
printf("\t序号\t\t名称\t\t\t简****************介\n\n");
for(i=0;i<G.vn;++i)
{
Sleep(110);
printf("\t%d\t\t%s\t\t\t\t%s\n\n",count++,G.Vexs[i].name,G.Vexs[i].features);
}
printf("\n\t*****End!******\n");
}
void Inite(MGraph &G)
{
G.vn = 12; //顶点数
G.en = 20; //边数
int i,j;
for (i = 0; i < MaxVertexNum; i++)//全部设置**正无穷**
{
for (j = 0; j < MaxVertexNum; j++)
{
G.Edge[i][j] = Never;
}
}
Length[0][1] = Length[0][1]=200;
Length[0][4] = Length[4][0]=350;
Length[1][2] = Length[2][1]=500;
Length[1][3] = Length[3][1]=500;
Length[1][4] = Length[4][1]=480;
Length[1][5] = Length[5][1]=400;
Length[2][7] = Length[7][2]=400;
Length[3][6] = Length[6][3]=100;
Length[3][7] = Length[7][3]=400;
Length[4][5] = Length[5][4]=280;
Length[4][8] = Length[8][4]=200;
Length[5][6] = Length[6][4]=100;
Length[5][9] = Length[9][5]=300;
Length[6][7] = Length[7][6]=500;
Length[6][9] = Length[9][6]=200;
Length[7][9] = Length[9][7]=100;
Length[8][10] = Length[10][8]=300;
Length[8][11] = Length[8][11]=100;
Length[9][10] = Length[10][9] = 100;
Length[10][11] = Length[11][10]=100;
//建立边的关系
int temp;
for (i = 0; i < G.vn; i++)
{
for (j = 0; j < G.vn; j++)
{
if(Length[i][j]!=0 || Length[j][i]!=0)
{
if(Length[i][j] != 0)
{
temp = Length[i][j];
}
else
{
temp = Length[j][i];
}
G.Edge[i][j] = temp;
G.Edge[j][i] = temp;
}
}
}
// //查看这个无向图
// for(i=0;i<G.vn;i++)
// {
// for(j=0;j<G.vn;j++)
// {
// printf("%d\t",G.Edge[i][j]);
// }
// printf("\n");
// }
}
void Floyd(MGraph &G)
{
int i,j,k;
for(i = 0; i < G.vn; i++)
{
for(j = 0; j < G.vn;j++)
{
Distance[i][j] = G.Edge[i][j];
Path[i][j] = j;
}
}
//Floyd算法
for(k = 0; k < G.vn; k++)
{
for(i = 0; i < G.vn; i++)
{
for(j = 0; j < G.vn; j++)
{
if(Distance[i][j] > Distance[i][k] + Distance[k][j])
{
Distance[i][j] = Distance[i][k] + Distance[k][j];
Path[i][j] = Path[i][k];
}
}
}
}
}
int Locate(MGraph *G,char Name[])//查找地点编号
{
int i;
for ( i= 0; i < G->vn; i++)
{
if( strcmp(G->Vexs[i].name,Name)==0 )//若含有该地点,则返回其编号
{
return i+1;
}
}
return -1; //若不存在该地地点,返回-1
}
//查询某一地点到其他所有地点的的最短路径
void search_All_The_Shotest(MGraph &G)
{
int start = -2;
char Name[100];
while(start == -2)
{
printf("请输入查询地点名称>>>:");
getchar();
gets(Name);
if(strlen(Name)>0)
{
start = Locate(&G,Name)-1;
printf("%s %s %d\n\n",Name,G.Vexs[start].name,start);
}
if(start==-2)
{
printf("不存在此地\n");
}
}
int i,j,k;
for(i = 0; i < G.vn; i++)
{
for(j = 0; j < G.vn;j++)
{
Distance[i][j] = G.Edge[i][j];
Path[i][j] = j;
}
}
//Floyd算法
for(k = 0; k < G.vn; k++)
{
for(i = 0; i < G.vn; i++)
{
for(j = 0; j < G.vn; j++)
{
if(Distance[i][j] > Distance[i][k] + Distance[k][j])
{
Distance[i][j] = Distance[i][k] + Distance[k][j];
Path[i][j] = Path[i][k];
}
}
}
}
//输出
for(j = 0; j < G.vn; j++)
{
if(j != start && G.Vexs[j].num != -1)
{
printf("从%s到%s的距离是：%d,",G.Vexs[start].name,G.Vexs[j].name,Distance[start][j]);
k = Path[start][j];
cout << "路径为：" << G.Vexs[start].name;
while(k != j)
{
printf(" ->%s ",G.Vexs[k].name);
k = Path[k][j];
}
printf(" ->%s \n\n",G.Vexs[j].name );
}
}
printf("操作完毕.....按任意键返回\n");
system("pause");
}
void search_Shotest(MGraph &G)
{
int start,end,k;
int flag=0;
printf("\t请输入起点和终点,空格分隔\n\t>>>:");
scanf("%d%d",&start,&end);
if(start<60&&end<60&&Distance[start][end]>0)
{
if(end!=start&&strlen(G.Vexs[end].name)>0&&end>=0&&start>=0)
{
printf("从%s到%s的距离是：%d,",G.Vexs[start].name,G.Vexs[end].name,Distance[start][end]);
k = Path[start][end];
cout << "路径为：" << G.Vexs[start].name;
while( k != end)
{
printf(" ->%s ",G.Vexs[k].name);
k = Path[k][end];
}
printf(" ->%s \n\n",G.Vexs[end].name );
}else
{
printf("不存在路径,不能到达\n\n");
}
system("pause");
} else
{
printf("不存在路径,不能到达\n\n");
}
}
root
flag{1amh3zhi}
京公网安备 11010502036488号