数据结构校园导游程序

2016-12-11 22:20:13 qq_33406883 阅读数 19510

校园导游系统   数据结构课程设计

郑州师范学院老校区校园导游系统

尴尬的最短路算法

Floyd and Dijkstra

尴尬的数据结构......


记录一下代码:

多有参考.....

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

#define MaxSize 100     
#define VISITED 1       
#define NOTVISITED 0    
#define Infinite 1073741823  
#define MaxViewNum 50     /*景点个数最大50*/
#define MaxRoad 1000      /*定义路径为无穷大*/
#define N 16              /*目前景点个数*/

typedef struct
{
    char name[30];          /*景点名称*/
    char number[10];        /*景点代号*/
    char introduce[200];    /*景点介绍*/	
}Elemtype;                  /*景点信息*/
 
typedef struct
{
    int num;              /*景点编号*/
    Elemtype date;        /*景点信息*/
}View;                    /*定义景点*/

typedef struct
{
    View view[MaxViewNum];         /*存放顶点的一维数组,数组第零单元没有用上*/
    int length[MaxViewNum][MaxViewNum];  /*存放路径长度*/
    int m,n;
}MGraph;

MGraph MGr;              /*全局变量,定义MGr为MGraph类型*/
int shortest[MaxViewNum][MaxViewNum];     /*定义全局变量存贮最小路径*/
int path[MaxViewNum][MaxViewNum];         /*定义存贮路径*/

void init()
{
    int i,j;
    MGr.view[1].num=1;
    strcpy(MGr.view[1].date.name,"学校正门");
    strcpy(MGr.view[1].date.number,"001");
    strcpy(MGr.view[1].date.introduce,"坐落于英才街,对面为国基生活园区,市井繁华,交通便利。");
	
    MGr.view[2].num=2;
    strcpy(MGr.view[2].date.name,"行政楼");
    strcpy(MGr.view[2].date.number,"002");
    strcpy(MGr.view[2].date.introduce,"学校领导,办公主楼。");
	
    MGr.view[3].num=3;
    strcpy(MGr.view[3].date.name,"教学区");
    strcpy(MGr.view[3].date.number,"003");
    strcpy(MGr.view[3].date.introduce,"1-5号教学楼,包含信息学院以及化学,物理学院等。");
	
    MGr.view[4].num=4;
    strcpy(MGr.view[4].date.name,"天鹅湖");
    strcpy(MGr.view[4].date.number,"004");
    strcpy(MGr.view[4].date.introduce,"郑州师范学院老校区的一大景点,黑白天鹅,戏水相融。");
	
    MGr.view[5].num=5;
    strcpy(MGr.view[5].date.name,"图书馆");
    strcpy(MGr.view[5].date.number,"005");
    strcpy(MGr.view[5].date.introduce,"历史悠久,文化积淀。供同学安静学习的环境。");
	
    MGr.view[6].num=6;
    strcpy(MGr.view[6].date.name,"艺术之地");
    strcpy(MGr.view[6].date.number,"006");
    strcpy(MGr.view[6].date.introduce,"美术学院和音乐与舞蹈学院,通往艺术的殿堂。");
	
    MGr.view[7].num=7;
    strcpy(MGr.view[7].date.name,"运动场");
    strcpy(MGr.view[7].date.number,"007");
    strcpy(MGr.view[7].date.introduce,"绿茵地、活动中心。篮球场、足球场、网球场依次,丰富课余生活。");
	
    MGr.view[8].num=8;
    strcpy(MGr.view[8].date.name,"餐厅");
    strcpy(MGr.view[8].date.number,"008");
    strcpy(MGr.view[8].date.introduce,"餐厅,有民族餐厅的免费的开水房,老校区同学们吃饭的地方。饭菜是否可口就......");
	
    MGr.view[9].num=9;
    strcpy(MGr.view[9].date.name,"校医院");
    strcpy(MGr.view[9].date.number,"009");
    strcpy(MGr.view[9].date.introduce,"校医院,同学们看病拿药的地方,提供便利。");
	
    MGr.view[10].num=10;
    strcpy(MGr.view[10].date.name,"老校区西门");
    strcpy(MGr.view[10].date.number,"010");
    strcpy(MGr.view[10].date.introduce,"西门出去正对文化路,对面就是河南牧业经济学院。");
	
    MGr.view[11].num=11;
    strcpy(MGr.view[11].date.name,"特殊教育学院");
    strcpy(MGr.view[11].date.number,"011");
    strcpy(MGr.view[11].date.introduce,"特殊教育学院,其中聋哑人居多,为每一个学生提供合适平等的教学场所。");
	
    MGr.view[12].num=12;
    strcpy(MGr.view[12].date.name,"学生公寓");
    strcpy(MGr.view[12].date.number,"012");
    strcpy(MGr.view[12].date.introduce,"学生宿舍区,其中8号楼为女生宿舍,9号楼为男生宿舍。");
	
    MGr.view[13].num=13;
    strcpy(MGr.view[13].date.name,"郑州市自然博物馆");
    strcpy(MGr.view[13].date.number,"013");
    strcpy(MGr.view[13].date.introduce,"郑州市自然博物馆,坐落于郑州师范学院老校区西北角,历史悠久。");
	
    MGr.view[14].num=14;
    strcpy(MGr.view[14].date.name,"初教院教学楼");
    strcpy(MGr.view[14].date.number,"014");
    strcpy(MGr.view[14].date.introduce,"初教院,初等教育学院的学生日常上课的地方。");
	
    MGr.view[15].num=15;
    strcpy(MGr.view[15].date.name,"中州北门");
    strcpy(MGr.view[15].date.number,"015");
    strcpy(MGr.view[15].date.introduce,"相邻的中州大学的北门,出门为开元路,右转直走即可到郑州师范学院新校区。");
	
    MGr.view[16].num=16;
    strcpy(MGr.view[16].date.name,"中州大学教学区");
    strcpy(MGr.view[16].date.number,"016");
    strcpy(MGr.view[16].date.introduce,"该地区为中州大学教学区域。");
	
    for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
        {
			MGr.length[i][j]=MaxRoad;
        }
    }
    for(i=1;i<=N;i++)
    {
		shortest[i][j]=0;
    }
    MGr.length[1][2]=MGr.length[2][1]=50;
    MGr.length[2][3]=MGr.length[3][2]=50;
    MGr.length[3][4]=MGr.length[4][3]=60;
    MGr.length[3][5]=MGr.length[5][3]=100;
    MGr.length[5][6]=MGr.length[6][5]=100;
    MGr.length[6][7]=MGr.length[7][6]=220;
	MGr.length[6][9]=MGr.length[9][6]=80;
    MGr.length[7][8]=MGr.length[8][7]=250;
    MGr.length[8][9]=MGr.length[9][8]=100;
	MGr.length[8][10]=MGr.length[10][8]=150;
    MGr.length[9][11]=MGr.length[11][9]=50;
    MGr.length[10][11]=MGr.length[11][10]=60;
    MGr.length[11][12]=MGr.length[12][11]=40;
    MGr.length[12][13]=MGr.length[13][12]=50;
	MGr.length[13][14]=MGr.length[14][13]=20;
    MGr.length[11][14]=MGr.length[14][11]=80;
	MGr.length[16][14]=MGr.length[14][16]=500;
	MGr.length[13][15]=MGr.length[15][13]=450;
	MGr.length[2][16]=MGr.length[16][2]=150;
    MGr.length[1][1]=MGr.length[2][2]=MGr.length[3][3]=MGr.length[4][4]=0;
    MGr.length[5][5]=MGr.length[6][6]=MGr.length[7][7]=MGr.length[8][8]=0;
    MGr.length[9][9]=MGr.length[10][10]=MGr.length[11][11]=MGr.length[12][12]=0;
    MGr.length[13][13]=MGr.length[14][14]=MGr.length[15][15]=MGr.length[16][16]=0;
}

void introduce()
{
    int m;
    printf("请输入查询景点编号:\n");
    scanf("%d",&m); fflush(stdin);
    switch(m)
    {
	case 1:
		printf("景点编号:%s\t",MGr.view[1].date.number);
		printf("景点名称:%s\n",MGr.view[1].date.name);
		printf("景点简介:%s\n",MGr.view[1].date.introduce);
		break;
	case 2:
		printf("景点编号:%s\t",MGr.view[2].date.number);
		printf("景点名称:%s\n",MGr.view[2].date.name);
		printf("景点简介:%s\n",MGr.view[2].date.introduce);
		break;
	case 3:
		printf("景点编号:%s\t",MGr.view[3].date.number);
		printf("景点名称:%s\n",MGr.view[3].date.name);
		printf("景点简介:%s\n",MGr.view[3].date.introduce);
		break;
	case 4:
		printf("景点编号:%s\t",MGr.view[4].date.number);
		printf("景点名称:%s\n",MGr.view[4].date.name);
		printf("景点简介:%s\n",MGr.view[4].date.introduce);
		break;
	case 5:
		printf("景点编号:%s\t",MGr.view[5].date.number);
		printf("景点名称:%s\n",MGr.view[5].date.name);
		printf("景点简介:%s\n",MGr.view[5].date.introduce);
		break;
	case 6:
		printf("景点编号:%s\t",MGr.view[6].date.number);
		printf("景点名称:%s\n",MGr.view[6].date.name);
		printf("景点简介:%s\n",MGr.view[6].date.introduce);
		break;
	case 7:
		printf("景点编号:%s\t",MGr.view[7].date.number);
		printf("景点名称:%s\n",MGr.view[7].date.name);
		printf("景点简介:%s\n",MGr.view[7].date.introduce);
		break;
	case 8:
		printf("景点编号:%s\t",MGr.view[8].date.number);
		printf("景点名称:%s\n",MGr.view[8].date.name);
		printf("景点简介:%s\n",MGr.view[8].date.introduce);
		break;
	case 9:
		printf("景点编号:%s\t",MGr.view[9].date.number);
		printf("景点名称:%s\n",MGr.view[9].date.name);
		printf("景点简介:%s\n",MGr.view[9].date.introduce);
		break;
	case 10:
		printf("景点编号:%s\t",MGr.view[10].date.number);
		printf("景点名称:%s\n",MGr.view[10].date.name);
		printf("景点简介:%s\n",MGr.view[10].date.introduce);
		break;
	case 11:
		printf("景点编号:%s\t",MGr.view[11].date.number);
		printf("景点名称:%s\n",MGr.view[11].date.name);
		printf("景点简介:%s\n",MGr.view[11].date.introduce);
		break;
	case 12:
		printf("景点编号:%s\t",MGr.view[12].date.number);
		printf("景点名称:%s\n",MGr.view[12].date.name);
		printf("景点简介:%s\n",MGr.view[12].date.introduce);
		break;
	case 13:
		printf("景点编号:%s\t",MGr.view[13].date.number);
		printf("景点名称:%s\n",MGr.view[13].date.name);
		printf("景点简介:%s\n",MGr.view[13].date.introduce);
		break;
	case 14:
		printf("景点编号:%s\t",MGr.view[14].date.number);
		printf("景点名称:%s\n",MGr.view[14].date.name);
		printf("景点简介:%s\n",MGr.view[14].date.introduce);
		break;
	case 15:
		printf("景点编号:%s\t",MGr.view[15].date.number);
		printf("景点名称:%s\n",MGr.view[15].date.name);
		printf("景点简介:%s\n",MGr.view[15].date.introduce);
		break;
	case 16:
		printf("景点编号:%s\t",MGr.view[16].date.number);
		printf("景点名称:%s\n",MGr.view[16].date.name);
		printf("景点简介:%s\n",MGr.view[16].date.introduce);
		break;
	default:
		printf("输入序号错误。\n");
		break;
    }
    printf("\n");
}

void floyd()                 /*佛洛依德算法*/
{
    int i,j,k;
    for(i=1;i<=N;i++)
    {
		for(j=1;j<=N;j++)
		{
			shortest[i][j]=MGr.length[i][j];
			path[i][j]=0;
		}
    }   /*初始化数组*/
    for(k=1;k<=N;k++)
    {
		for(i=1;i<=N;i++)
		{
			for(j=1;j<=N;j++)
			{
				if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
				{
					shortest[i][j]=shortest[i][k]+shortest[k][j];
					path[i][j]=k;
					path[j][i]=k;   /*记录经过的路径*/
				}//end_if
			}			
		}//end_for
    }
}

void display(int i,int j)
{         /*打印两个景点的路径及最短路径*/
    int a,b;
    a=i;
    b=j;
    printf("您要查询的两景点间最短路径是: \n\n");
    fflush(stdin);
	if(i<j)
	{
		printf("%d",b);
		while(path[i][j]!=0)
		{
			printf("<--%d",path[i][j]);
			if(i<j)
				j=path[i][j];
			else
				i=path[j][i];
		}
		printf("<-%d\n\n",a);
		printf("%d->%d的最短路径是: %d 米。\n\n",a,b,shortest[a][b]);
	}
	else
	{
		printf("%d",a);
		while(path[i][j]!=0)
		{      /*把i到j的路径上所有经过的景点按顺序打印出来*/
			printf("-->%d",path[i][j]);
			if(i<j)
				j=path[i][j];
			else
				i=path[j][i];
		}
		printf("->%d\n\n",b);
		printf("%d->%d的最短路径是: %d 米。\n\n",a,b,shortest[a][b]);
	}
}/*display*/

int shortdistance()
{    /*要查找的两景点的最短路径*/
    int i,j;
    printf("请输入要查询的两个景点的数字编号(1->16)中间用空格间隔开。\n");
    scanf("%d %d",&i,&j);
    if(i>N||i<0||j>N||j<0)
    {
		printf("输入信息错误!\n\n");
		printf("请输入要查询的两个景点的数字编号(1->16)中间用空格间隔开。\n");
		scanf("%d %d",&i,&j);
    }
    else
    {
		floyd();
		display(i,j);
    }
    return 1;
    fflush(stdin);
}/*shortestdistance*/

int A[MaxSize+1][MaxSize+1];   /*迪杰斯特拉算法*/
int D[MaxSize+1];
int S[MaxSize+1],P[MaxSize+1];
int source,sink;
int step = 1;
int top = -1;                    
int Stack[MaxSize+1];   
         
void input()                  
{
	int i;
	printf("\n请输入起始节点:");
	scanf("%d",&source);
	printf("\n请输入结束节点:");
	scanf("%d",&sink);
	
	for ( i = 1; i <= N; i++ )
	{
		S[i] = NOTVISITED;                     
		D[i] = MGr.length[source][i];      
		P[i] = source;      
	}
	S[source] = VISITED;          
	D[source] = 0;
}
void Push(int value)
{
	if ( top >= MaxSize )
	{
		printf("没有路径存在!\n\n");
		exit(1);
	}
	else
		Stack[++top] = value;
}
int Pop()
{
	if ( top < 0 )
	{
		printf("没有路径存在!\n\n");
		exit(1);
	}
	return Stack[top--];
}
int minD()
{
	int i,t=0;
	long int minimum = Infinite;
	for ( i=1;i<=N;i++ )
		if ( (S[i] == NOTVISITED) && D[i] < minimum )
		{
			minimum = D[i];
			t = i;
		}
		return t;
}

void output_path()
{
	int node = sink;
	
	if ( (sink == source) || (D[sink] == Infinite) )
	{
		printf("\n节点%d与节点%d之间没有路径存在!\n\n",source,sink);
		return;
	}
	printf("\n");
	
	while ( node != source )
	{
		Push(node);
		node  = P[node];
	} 
	printf("V%d到V%d的最短路径为:\n",source,sink);
	printf("  V%d",source);
	while( node != sink)
	{
		node = Pop();
		printf(" --%ld-->",MGr.length[ P[node] ][node]);
		printf("V%d",node);
	}
	printf("\n");
	printf("\n %d->%d的最短路径是: %ld\n",source,sink,D[sink]);
	printf("\n");
}

void distance()
{
	int t,I;
	input();
	for ( step =2;step <=N; step++ )
	{
		
		t = minD();
		S[t] = VISITED;
		
		for ( I=1; I <= N; I++ )
			if ( (S[I] == NOTVISITED) && (D[t]+MGr.length[t][I] <= D[I]) )
			{
				D[I] = D[t] + MGr.length[t][I];
				P[I] = t;
			}
	}
	output_path();
}


void map()
{
        printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
	printf("┃┏━━━━━━━━┓┏━━━━━┓                      ┏━━━━━━━┓  ┃\n");
	printf("┃┃13.自然博物馆   ┃┃14.初教院 ┃                ━━━┫15.中州北门   ┣━┃\n");
	printf("┃┗━━━━━━━━┛┗━━━━━┛                      ┗━━━━━━━┛  ┃\n");
	printf("┃                                                                            ┃\n");
	printf("┃                  ┏━━━━━┓                                           ┃\n");
	printf("┃                  ┃ 12.      ┃  ┏━━━━┓                              ┃\n");
	printf("┃                  ┃ 学生公寓 ┃  ┃8.餐厅  ┃                              ┃\n");
	printf("┃                  ┗━━━━━┛  ┗━━━━┛                              ┃\n");
	printf("┃┏━━━━━━━━━━━━━━┓  ┏━━━━┓                            ┃\n");
	printf("┃┃     11. 特教院             ┃ ┃9.校医院┃       ┏━━━━━━┓   ┃\n");
	printf("┃┗━━━━━━━━━━━━━━┛ ┗━━━━┛          ┃  16.       ┃   ┃\n");
	printf("┃┏━━━━┓                                   ┃    中州    ┃   ┃\n");
	printf("┃┃10.西门 ┃                                      ┃   教学区   ┃   ┃\n");
	printf("┃┗━━━━┛                                       ┃            ┃   ┃\n");
	printf("┃ ┏━━━━━━━━━┓           ┏━━━━━━┓       ┗━━━━━━┛   ┃\n");
	printf("┃ ┃                  ┃           ┃6.美术学院  ┃                          ┃\n");
	printf("┃ ┃                  ┃           ┃与音乐学院  ┃                          ┃\n");
	printf("┃ ┃    7. 运         ┃           ┗━━━━━━┛                          ┃\n");
	printf("┃ ┃                  ┃                                                     ┃\n");
	printf("┃ ┃       动         ┃           ┏━━━━┓                              ┃\n");
	printf("┃ ┃                  ┃           ┃ 4.     ┃                              ┃\n");
	printf("┃ ┃       场         ┃           ┃ 天鹅湖 ┃                              ┃\n");
	printf("┃ ┃                  ┃           ┗━━━━┛   ┏━━━━━━┓           ┃\n");
	printf("┃ ┃                  ┃                          ┃     图     ┃           ┃\n");
	printf("┃ ┃                  ┃          ┏━━━━━┓  ┃ 5.  书     ┃           ┃\n");
	printf("┃ ┃                  ┃          ┃四五号楼  ┃  ┃     馆     ┃           ┃\n");
	printf("┃ ┗━━━━━━━━━┛          ┃━━━━━┃  ┗━━━━━━┛           ┃\n");
	printf("┃                                 ┃二三号楼  ┃                             ┃\n");
	printf("┃                                 ┃━━━━━┃                             ┃\n");
	printf("┃                                 ┃3.一号楼  ┃                             ┃\n");
	printf("┃                                 ┗━━━━━┛                             ┃\n");
	printf("┃                                                                            ┃\n");
	printf("┃                                                                            ┃\n");
	printf("┃         ┏━━━━━━━━━┓                   ┏━━━━━┓            ┃\n");
	printf("┃         ┃   2. 行 政 楼    ┃     ━━━━━━━┫1.学校正门┣━━━━━━┃\n");
	printf("┃         ┗━━━━━━━━━┛                   ┗━━━━━┛            ┃\n");
	printf("┃                                                                            ┃\n");
	printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
    printf("\n");
    fflush(stdin);
}/*map*/

int main()
{
    char k;
    init();
	printf("**********************************************************************\n");
	printf("*                                                                    *\n");
	printf("*                                                                    *\n");
	printf("*           欢迎使用郑州师范学院老校区导游系统 !                     *\n");
	printf("*                                                                    *\n");
	printf("*                                                                    *\n");
	printf("**********************************************************************\n");
    printf("\n");
    while(1)
    {   
		printf("1.景点信息查询请按“1”键;\n");
		printf("2.景点最短路径查询(佛洛依德算法)请按“2”键;\n");
		printf("3.景点最短路径查询(迪杰斯特拉算法)请按“3”键;\n");
		printf("4.校内景点地图查询请按“4”键;\n");	    
		printf("5.退出系统请按“5”键;\n");
		printf("请选择: \n");
		scanf("%c",&k);
		
		switch(k)
		{
		case '1':printf("景点介绍查询(请输入1-16)。\n");
			introduce();break;
		case '2':printf("景点最短路径查询(佛洛依德算法)。");
			shortdistance();break;
		case '3':printf("景点最短路径(迪杰斯特拉算法)查询。");
			distance();break;
		case '4':printf("景点地图。\n");
			map();break;
		case '5':printf("谢谢使用!\n");exit(0);
		}
    }
    system("pause");
	return 0;
}


2019-01-19 19:37:40 DEAR_CXN 阅读数 2281

问题描述

设计一个校园导游程序,为来访的客人提供各种信息查询服务。

(1)设计学校的校园平面图,所含景点不少于10个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息;

(2)提供基本信息的修改功能;

(3)为来访客人提供图中任意景点相关信息的查询;

(4)为来访客人提供景点的问路查询,即已知一个景点,查询到某景点之间的一条最短路径及长度。

算法思想

用直接赋值的方法给予各个景点信息,若两景点之间可达,则对路径长度赋值,对于自己到自己的路径,赋值为0,其他均赋成最大值。查看所有景点时,就遍历结构体数组,然后全部输出;查询景点,根据输入的景点代号,遍历数组然后利用字符串比较方法找到所查询的景点,输出景点的具体信息;修改景点信息的第一步为查找到该景点,然后将该景点的所有信息清空,重新输入即可;问路求最短路径及长度即是采用弗洛伊德算法,获得具体的最短路径时,从后往前追溯走过的结点,并且用一个数组记录下它的位置,然后再遍历数组输出所经过的每个点的信息。

算法设计

1、菜单显示void menu()——供用户选择的功能菜单。

2、输出所有景点信息void Allprint(AMGragh G)——输出景点名称、代号和简介。

3、建图void CreateUDG(AMGragh &G)——用直接赋值的方法给予各个景点信息,若两景点之间可达,则对路径长度赋值,对于自己到自己的路径,赋值为0,其他均赋成最大值。

4、修改信息void Change(AMGragh &G)——修改景点信息的第一步为查找到该景点,然后将该景点的所有信息清空,重新输入即可。

5、查询景点void Query(AMGragh G)——查询景点,根据输入的景点代号,遍历数组然后利用字符串比较方法找到所查询的景点,输出景点的具体信息。

6、弗洛伊德算法void Floyd(AMGragh G)——获得最短路径及长度。

7、获得具体路径void Path(AMGragh G,int a,int b)——从后往前追溯走过的结点,并且用一个数组记录下它的位置,然后再遍历数组输出所经过的每个点的信息。

8、问路void Ask(AMGragh G)——调用函数输出具体路径及长度。

9、主函数int main()——先调用建图函数,然后用while循环实现不断地对功能进行选择。

代码实现

#include<stdio.h>//实验四
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define Max 11
#define MX 999999
int D[Max][Max];
int path[Max][Max];
typedef struct Ver{//顶点信息
    char num[5];
    char name[51];
    char instruct[101];
}Ver;
typedef struct{//邻接矩阵
    Ver vex[Max];//顶点表
    int arcs[Max][Max];
    int vnum,arcnum;
}AMGragh;
void menu(){
    cout<<"************中工欢迎您************"<<endl;
    cout<<"        1、查看所有景点           "<<endl;
    cout<<"        2、景点查询               "<<endl;
    cout<<"        3、问路                   "<<endl;
    cout<<"        4、修改景点基本信息       "<<endl;
    cout<<"        5、退出                   "<<endl;
    cout<<"**********************************"<<endl;
    cout<<"请选择..."<<endl;
}
void Allprint(AMGragh G){//输出所有景点信息
    cout<<"---------------校园景点总览---------------"<<endl;
    cout<<"景点名称   "<<"  "<<"代号"<<"     "<<"    简介"<<endl;
    for(int i=0;i<G.vnum;i++){
        cout<<G.vex[i].name<<"    "<<G.vex[i].num<<"   "<<G.vex[i].instruct<<endl;
    }
    cout<<endl;
}
void CreateUDG(AMGragh &G){//建图
    G.vnum=10;
    strcpy(G.vex[0].num,"01");
    strcpy(G.vex[1].num,"02");
    strcpy(G.vex[2].num,"03");
    strcpy(G.vex[3].num,"04");
    strcpy(G.vex[4].num,"05");
    strcpy(G.vex[5].num,"06");
    strcpy(G.vex[6].num,"07");
    strcpy(G.vex[7].num,"08");
    strcpy(G.vex[8].num,"09");
    strcpy(G.vex[9].num,"10");
    strcpy(G.vex[0].name,"北苑美食城");
    strcpy(G.vex[1].name,"北大坑    ");
    strcpy(G.vex[2].name,"体育馆    ");
    strcpy(G.vex[3].name,"图书馆    ");
    strcpy(G.vex[4].name,"弘德广场  ");
    strcpy(G.vex[5].name,"紫薇广场  ");
    strcpy(G.vex[6].name,"湿地公园  ");
    strcpy(G.vex[7].name,"海豚湾    ");
    strcpy(G.vex[8].name,"绮湖      ");
    strcpy(G.vex[9].name,"绮园      ");
    strcpy(G.vex[0].instruct,"北苑美食城里面有各种各样的美食,可以让你大饱口福");
    strcpy(G.vex[1].instruct,"北大坑是北苑的一个运动场地,也是一个篮球场");
    strcpy(G.vex[2].instruct,"体育馆设施齐全,建筑优美,在此可以尽情享受运动的快乐!");
    strcpy(G.vex[3].instruct,"图书馆环境安适,藏书丰富,让人感受阅读的美好");
    strcpy(G.vex[4].instruct,"弘德广场与学校西门相邻,也是升国旗的地方");
    strcpy(G.vex[5].instruct,"紫薇广场上会举办一些文艺晚会和校园招聘会,更是轮滑爱好者的乐园");
    strcpy(G.vex[6].instruct,"湿地公园有小石桥和美丽的树木,让人心旷神怡");
    strcpy(G.vex[7].instruct,"海豚湾的标志是一对白色的大海豚,坐落在水中央,夏天水中开有漂亮的莲花");
    strcpy(G.vex[8].instruct,"绮湖的水清澈见底,还能看到活泼的小鱼");
    strcpy(G.vex[9].instruct,"绮园里往届校友栽的树,生机勃勃,代表着他们对母校的爱");
    G.arcs[1][2]=G.arcs[2][1]=2;
    G.arcs[1][9]=G.arcs[9][1]=19;
    G.arcs[2][3]=G.arcs[3][2]=3;
    G.arcs[2][4]=G.arcs[4][2]=5;
    G.arcs[3][4]=G.arcs[4][3]=2;
    G.arcs[4][5]=G.arcs[5][4]=3;
    G.arcs[4][7]=G.arcs[7][4]=29;
    G.arcs[4][10]=G.arcs[10][4]=33;
    G.arcs[5][6]=G.arcs[6][5]=6;
    G.arcs[6][7]=G.arcs[7][6]=7;
    G.arcs[7][8]=G.arcs[8][7]=8;
    G.arcs[8][9]=G.arcs[9][8]=1;
    G.arcs[9][10]=G.arcs[10][9]=2;
    for(int i=1;i<=10;i++)//初始化路径长度
        for(int j=1;j<=10;j++){
            if(G.arcs[i][j]==0&&i!=j)
                G.arcs[i][j]=MX;
        }
    G.arcnum=13;
}
void Change(AMGragh &G){//修改信息
    Allprint(G);
    cout<<"请输入要修改信息的代号:";
    char c[5];
    cin>>c;
    for(int i=0;i<G.vnum;i++){
        if(strcmp(c,G.vex[i].num)==0)//字符串比较的方法进行查找
        {
            memset(G.vex[i].name,0,sizeof(G.vex[i].name));
            memset(G.vex[i].num,0,sizeof(G.vex[i].num));
            memset(G.vex[i].instruct,0,sizeof(G.vex[i].instruct));
            char num1[5];
            char name1[51];
            char instruct1[101];
            cout<<"请输入修改后的景点信息:"<<endl;
            cout<<"景点名称:";
            scanf("%s",name1);
            cout<<"代号:";
            scanf("%s",num1);
            cout<<"简介:";
            scanf("%s",instruct1);
            strcpy(G.vex[i].name,name1);
            strcpy(G.vex[i].num,num1);
            strcpy(G.vex[i].instruct,instruct1);
            cout<<"修改成功!"<<endl;
            break;
        }
    }
}
void Query(AMGragh G){//查询景点
    cout<<"请输入查询景点的代号:";
    char c[5];
    cin>>c;
    int i;
    for(i=0;i<G.vnum;i++)
        if(strcmp(c,G.vex[i].num)==0)
        {
            cout<<"景点名称:"<<G.vex[i].name<<"   ";
            cout<<"代号:"<<G.vex[i].num<<"   ";
            cout<<"简介:"<<G.vex[i].instruct<<endl;
            break;
        }
    if(i==G.vnum)
        cout<<"该代号不存在!"<<endl;
}
void Floyd(AMGragh G){//弗洛伊德算法,获得最短路径
    int i,j,k;
    for(i=1;i<=G.vnum;++i)
        for(j=1;j<=G.vnum;j++){
            D[i][j]=G.arcs[i][j];
            if(D[i][j]<MX&&i!=j)
                path[i][j]=i;
            else
                path[i][j]=-1;
        }
    for(k=1;k<=G.vnum;k++)
        for(i=1;i<=G.vnum;++i)
            for(j=1;j<=G.vnum;j++)
                if(D[i][k]+D[k][j]<D[i][j]){
                    D[i][j]=D[i][k]+D[k][j];
                    path[i][j]=path[k][j];
                }
}
void Path(AMGragh G,int a,int b){//获得具体路径
   int p[Max];
   p[0]=b;
   int i=1;
   while(a!=b){
    b=path[a][b];
    p[i]=b;
    ++i;
   }
   cout<<"路径:"<<G.vex[a-1].name;
   i=i-2;
   while(i>=0){
    cout<<"--->"<<G.vex[p[i]-1].name;
    --i;
   }
}
void Ask(AMGragh G){//问路
    Allprint(G);
    cout<<"请输入起点和目的地(1~10,即第几个景点,中间用空格隔开):";
    int a,b;
    cin>>a>>b;
    Floyd(G);
    cout<<endl<<endl<<"从"<<G.vex[a-1].name<<"到"<<G.vex[b-1].name<<":"<<endl<<endl<<"最短路径长度:"<<D[a][b]*10<<"米"<<endl;
    Path(G,a,b);
    cout<<endl;
}
int main(){
    AMGragh G;
    memset(G.arcs,0,sizeof(G.arcs));
    CreateUDG(G);
    int m;
    while(m!=5){
        menu();
        cin>>m;
        switch(m){
        case 1:
            Allprint(G);
            break;
        case 2:
            Query(G);
            break;
        case 3:
            Ask(G);
            break;
        case 4:
            Change(G);
            break;
        case 5:
            cout<<"感谢您的使用!"<<endl;
            return 0;
        default:
            cout<<"没有该选项!"<<endl;
        }
        system("pause");
        system("cls");
    }
    return 0;
}

 

2017-08-07 19:43:37 zw159357 阅读数 8434
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
#include <conio.h>
#define INF 32767
int visited[100],password;  //password为后台管理的登录密码
FILE *fp;
char na[100];
char str1[100],str3[100];
int N,M;
int a[100][100];
using namespace std;
typedef struct
{
    int num;
    char name[100];
    char introduction[100];
} VertexType;
typedef struct
{
    int edges[100][100];
    int n,e;
    VertexType vex[100];
} MGraph;
typedef struct ANode
{
    int adjvex;
    struct ANode *nextarc;
} ArcNode;
typedef struct Vnode
{
    ArcNode *firstarc;
} VNode;
typedef VNode AdjList[100];
typedef struct
{
    AdjList adjlist;
    int n,e;
} ALGraph;
MGraph g;
//将文本文件打开并输出文件中的内容
void ReadData1(MGraph &g)
{
    M=N;
    FILE *fp;
    int i = 0,j;
    if ((fp=fopen("path.txt", "r"))==NULL)
    {
        printf("error open!");
        exit(0);
    }
    for(i=0; i<M; i++)
    {
        for(j=0; j<M; j++)
        {
            fscanf(fp,"%d",&g.edges[i][j]);
        }
    }
    fclose(fp);
}
void WriteData1(MGraph &g)
{
    FILE *fp;
    int i = 0,j;
    if ((fp=fopen("path.txt", "w"))==NULL)
    {
        printf("error open!");
        exit(0);
    }
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
        {
            printf("%d ",g.edges[i][j]);
            fprintf(fp,"%d ",g.edges[i][j]);
        }
        fprintf(fp,"\n");
        printf("\n");
    }
    fclose(fp);
}
void ReadData(MGraph &g)
{
    FILE *fp;
    int i = 0;
    if ((fp=fopen("data.txt", "r"))==NULL)
    {
        printf("error open!");
        exit(0);
    }
    while(fscanf(fp,"%d %s %s",&g.vex[i].num,g.vex[i].name,g.vex[i].introduction)!= EOF)
    {
        i++;
    }
    N = i;
    fclose(fp);
    return;
}
void WriteData(MGraph &g)
{
    FILE *fp;
    int i=0;
    if ((fp=fopen("data.txt", "w"))==NULL)
    {
        printf("error open!");
        exit(0);
    }
    for(i=0; i<N; i++)
        fprintf(fp,"%d %s %s\n",g.vex[i].num,g.vex[i].name,g.vex[i].introduction);
    fclose(fp);
}
//将邻接矩阵改为邻接表
void MatToList(MGraph g,ALGraph *&G)
{
    int i,j;
    ArcNode *p;
    G=(ALGraph *)malloc(sizeof(ALGraph));
    for(i=0; i<g.n; i++)
        G->adjlist[i].firstarc=NULL;
    for(i=0; i<g.n; i++)
        for(j=g.n-1; j>=0; j--)
        {
            if(g.edges[i][j]!=INF)
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));
                p->adjvex=j;
                p->nextarc=G->adjlist[i].firstarc;
                G->adjlist[i].firstarc=p;
            }
        }
    G->n=g.n;
    G->e=g.e;
}
//查找相应景点的介绍
void FindIntroduction(MGraph &g)
{
    int x,d;
    while(1)
    {
        printf("请输入要查询的景点的编号:");
        scanf("%d",&x);
        ReadData(g);
        printf("景点的名称:%s\n",g.vex[x].name);
        printf("景点的简介:");
        printf("%s\n",g.vex[x].introduction);
        printf("是否要继续查询(0.继续  1.不继续):");
        scanf("%d",&d);
        while(1)
        {
            if(d==0||d==1)
                break;
            else
            {
                printf("输入的数据不合理,请重新输入:");
                scanf("%d",&d);
            }
        }
        if(d==0)
            continue;
        else
            break;
    }
}
//输出两个顶点间的最短路径
void Dispath(MGraph &g,int A[][100],int path[][100])
{
    int i,j,k,s,u,v;
    printf("请输入你所在位置的编号:");
    scanf("%d",&u);
    printf("请输入你要去位置的编号:");
    scanf("%d",&v);
    int apath[100],d;
    for(i=0; i<g.n; i++)
    {
        for(j=0; j<g.n; j++)
        {
            if(A[i][j]!=INF&&i!=j&&u==i&&v==j)
            {
                printf("  从%s到%s的最短路径为:",g.vex[i].name,g.vex[j].name);
                k=path[i][j];
                d=0;
                apath[d]=j;
                while(k!=-1&&k!=i)
                {
                    d++;
                    apath[d]=k;
                    k=path[i][k];
                }
                d++;
                apath[d]=i;
                printf("%s",g.vex[apath[d]].name);
                for(s=d-1; s>=0; s--)
                    printf("->%s",g.vex[apath[s]].name);
                printf("\n");
                printf("  路径长度为:%d",A[i][j]);
                printf("\n");
            }
        }
    }
}
//查找两顶点间的最短路径
void FindMinPath(MGraph &g)
{
    int A[100][100],path[100][100];
    int i,j,k;
    for(i=0; i<g.n; i++)
    {
        for(j=0; j<g.n; j++)
        {
            A[i][j]=g.edges[i][j];
            if(i!=j&&g.edges[i][j]<INF)
                path[i][j]=i;
            else
                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(A[i][j]>A[k][j]+A[i][k])
                {
                    A[i][j]=A[k][j]+A[i][k];
                    path[i][j]=path[k][j];
                }
            }
        }
    }
    Dispath(g,A,path);
}
//查找两顶点间的所有路径
void FindaPath(MGraph &g,ALGraph *G,int u,int v,int path[],int d)
{
    int w,i;
    ArcNode *p;
    visited[u]=1;
    d++;
    path[d]=u;
    if(u==v&&d>=1)
    {
        printf(" ");
        for(i=0; i<d; i++)
            printf("%s->",g.vex[path[i]].name);
        printf("%s",g.vex[path[d]].name);
        printf("\n");
    }
    p=G->adjlist[u].firstarc;
    while(p!=NULL)
    {
        w=p->adjvex;
        if(visited[w]==0)
            FindaPath(g,G,w,v,path,d);
        p=p->nextarc;
    }
    visited[u]=0;
}
//删除景点简介信息
void delete_str(char str1[], char str2[],int len,char str3[])
{
    int num=0,k=0,i=0,j=0;   //num用来记录子串的个数 k用来记录子串的位置
    char *p=str2;             //使用p还原str到初始位置
    while(str1[i]!='\0')
    {
        if(str1[i]!=str2[j])
        {
            str3[k++]=str1[i++];  //当str1中的字符与str的首字符不相同时
        }
        else
        {
            char *temp=str2;
            for(; (str1[i]==str2[j])&&str2[j]!='\0'; j++)
            {
                i++;
            }
            if(j==len)
            {
                num++;           //出现重复子串,num加一
            }
            else
            {
                //主字符串中存在和子串前几个字符相同的一段字符
                //退出循环并将这段字符写进新的字符数组中
                for(int m=0; m<j; m++)
                {
                    str3[k++]=temp[m];
                }
            }
            str2=p;
            j=0;
        }
    }
}
//密码输入函数
int inputpassword()
{
    char a[10];
    int pass=0;
    int i;
    while(1)
    {
        for(i=0; i<6; i++)
        {
            a[i]=getch();
            putchar('*');
            if(a[i]>='0'&&a[i]<='9')
                pass=pass*10+a[i]-'0';
            else if(a[i]=='\b')         //当遇到退格键不做处理
            {
                printf("\b \b");
                i--;
            }
            else
            {
                pass=0;
                break;   //退出for循环后,再次接受
            }
        }
        fflush(stdin);  //清除键盘缓存区中已经有的输入
        printf("\n");
        if(pass==0)    //此条件成立可能由两种情况引起:输入了非数字字符被直接重置为0,或6位全0后正常退出for循环
        {
            printf("密码要求全为数字,且不能全0!\n");
            printf("请重新输入密码: ");
        }
        else
            break;
    }
    return pass;
}
//在图中增加一个顶点
void add_point(MGraph &g)
{
    int i,d;
    N++;
    g.vex[N-1].num=N-1;
    printf("%d\n",N);
    printf("请输入要增加景点的名称:");
    scanf("%s",g.vex[N-1].name);
    printf("%s\n",g.vex[N-1].name);
    printf("请输入该景点与其它景点间的路径长度:");
    for(i=0; i<N; i++)
    {
        scanf("%d",&d);
        g.edges[i][N-1]=g.edges[N-1][i]=d;
    }
    printf("请输入要增加顶点的简介:");
    scanf("%s",g.vex[N-1].introduction);
    printf("增加成功!\n");
}
//在图中增加一条路径
void add_path(MGraph &g)
{
    int i,j,length,k;
    do
    {
        printf("请输入要增加路径的起始点的编号:");
        scanf("%d",&i);
        printf("请输入要增加路径的终点的编号:");
        scanf("%d",&j);
        if(i>=0&&i<=N-1&&j>=0&&j<=N-1&&j>=0)
        {
            if(g.edges[i][j]!=INF&&g.edges[j][i]!=INF)
            {
                printf("该两点之间已存在路径,是否进行修改(0.修改 1.不修改):");
                scanf("%d",&k);
                if(k==0)
                {
                    printf("请输入要修改的路径的长度:");
                    scanf("%d",&length);
                    g.edges[j][i]=g.edges[i][j]=length;
                    printf("修改成功!");
                }
                else
                    g.edges[j][i]=g.edges[i][j];
            }
            else
            {
                printf("请输入要增加的路径的长度:");
                scanf("%d",&length);
                g.edges[j][i]=g.edges[i][j]=length;
                printf("添加成功!\n");
            }
            break;
        }
        else
        {
            printf("输入的顶点在原图中不存在!\n");
            continue;
        }
    }
    while(1);
}
//删除图中的一个顶点
void delete_point(MGraph &g)
{
    int i,j,m;
    printf("%d\n",N);
    printf("请输入要删除景点的编号:");
    scanf("%d",&m);
    do
    {
        if(m>=0&&m<=N-1)
            break;
        else
        {
            printf("请输入要删除景点的编号:");
            scanf("%d",&m);
        }
    }
    while(1);
    for(i=0; i<M; i++)
    {
        for(j=0; j<M; j++)
        {
            if(g.edges[m][j]!=INF&&g.edges[i][m]!=INF)
                g.edges[m][j]=g.edges[i][m]=INF;
        }
    }
    g.vex[m].num=INF;
    strcpy(g.vex[m].name,"F");
    printf("删除成功!\n");
}
//删除图中的一条路径
void delete_path(MGraph &g)
{
    int i,j;
    do
    {
        printf("请输入要删除路径的起始点的编号:");
        scanf("%d",&i);
        printf("请输入要删除路径的终点的编号:");
        scanf("%d",&j);
        if(g.edges[i][j]==INF)
            printf("这两点间不存在路径!\n");
        else
        {
            g.edges[i][j]=g.edges[j][i]=INF;
            break;
        }
    }
    while(1);
    printf("删除成功!\n");
}
//整个程序的驱动
void function()
{
    ALGraph *G;
    int i,j,u,v,path[100],x,k,l,d,y;
    int ch,pass;
    char str2[500],nam[100];
    g.n=10;
    g.e=18;
    ReadData(g);
    ReadData1(g);
    MatToList(g,G);
    for(i=0; i<G->n; i++)
        visited[i]=0;
    system("color F0");
    printf("\t\t     *******************************\n");
    printf("\t\t     *       1.用户                *\n");
    printf("\t\t     *       2.管理人员            *\n");
    printf("\t\t     *******************************\n");
    printf("请选择相应的编号进行下一步操作:");
    scanf("%d",&k);
    do
    {
        if(k==1||k==2)
            break;
        else
        {
            printf("输入数据不合理,请重新输入:");
            scanf("%d",&k);
        }
    }
    while(1);
    if(k==1)
    {
        system("title 校园景点介绍及路径查询系统");
        system("color F0");
        printf("\n\n\n\n\n\n\n\n\n\n\n\n");
        printf("\t\t\t欢迎进入校园景点介绍及路径查询系统!\n\n\n\n\n\n\n\n\n\n\n\n\n");
        printf("正在进入,请稍后...\n");
        printf("===============================================================================\r");
        for(j=0; j<80; j++)
        {
            Sleep(50);
            printf(">");
        }
        system("cls");
        do
        {
            printf("\t\t     *******************************\n");
            printf("\t\t     *       1.景点简介            *\n");
            printf("\t\t     *       2.两景点间最短路径    *\n");
            printf("\t\t     *       3.两景点间所有路径    *\n");
            printf("\t\t     *       4.退出系统            *\n");
            printf("\t\t     *******************************\n");
            printf("请输入要进行的操作的编号:");
            scanf("%d",&x);
            do
            {
                if(x>=1&&x<=4)
                    break;
                else
                {
                    printf("输入数据不合理,请重新输入:");
                    scanf("%d",&x);
                }
            }
            while(1);
            if(x>=1&&x<=3)
            {
                printf("\t\t     *******************************\n");
                if(N%2!=0)
                {
                    for(i=0; i<N-1; i+=2)
                    {
                         printf("\t\t          %d.%s  \t%d.%s  \n",g.vex[i].num,g.vex[i].name,g.vex[i+1].num,g.vex[i+1].name);
                    }
                     printf("\t\t          %d.%s       \n",g.vex[i].num,g.vex[i+1].name);

                }
                else
                {
                    for(i=0; i<N; i+=2)
                    {
                         printf("\t\t          %d.%s  \t%d.%s  \n",g.vex[i].num,g.vex[i].name,g.vex[i+1].num,g.vex[i+1].name);
                    }
                }

                printf("\t\t     *******************************\n");
                printf("%d",11);
            }

            switch(x)
            {
            case 1:
                ReadData(g);
                FindIntroduction(g);
                system("cls");
                break;
            case 2:
                ReadData(g);
                do
                {
                    FindMinPath(g);
                    printf("是否继续进行该操作(0.继续 1.不继续):");
                    scanf("%d",&y);
                    if(y==1)
                        break;
                    else
                        continue;
                }
                while(1);
                system("pause");
                system("cls");
                break;
            case 3:
                ReadData(g);
                do
                {
                    printf("请输入起点位置的编号:");
                    scanf("%d",&u);
                    printf("请输入终点位置的编号:");
                    scanf("%d",&v);
                    printf("从%s到%s的所有路径为:\n",g.vex[u].name,g.vex[v].name);
                    FindaPath(g,G,u,v,path,-1);
                    printf("是否继续进行该操作(0.继续 1.不继续):");
                    scanf("%d",&y);
                    if(y==1)
                        break;
                    else
                        continue;
                }
                while(1);
                system("pause");
                system("cls");
                break;
            case 4:
                printf("确认退出吗?(0.退出 1.不退出):");
                scanf("%d",&ch);
                while(1)
                {
                    if(ch==0||ch==1)
                        break;
                    else
                    {
                        printf("输入的数据不合理,请重新输入:");
                        scanf("%d",&ch);
                    }
                }
                if(ch==0)
                {
                    x=0;
                    printf("谢谢使用本系统,欢迎下次光临!");
                }
                else
                {
                    continue;
                }
            }
        }
        while(x!=0);
    }
    else
    {
        printf("请输入管理代号:");
        scanf("%s",na);
        printf("请输入管理登录密码:");
        password=inputpassword();
        FILE *fp1;
        if((fp1=fopen("password.txt","r"))==NULL)
        {
            printf("Cannot open the file!");
            exit(0);
        }
        fscanf(fp1,"%s %d",nam,&pass);
        fclose(fp1);
        int t=3;
        do
        {
            if(password!=pass)
            {
                t--;
                if(t==0)
                {
                    printf("你已经输错三次密码,系统将于10秒后关闭!");
                    Sleep(10000);
                    break;
                }
                printf("输入的密码错误!你还有%d次机会,请重新输入:",t);
                password=inputpassword();
            }
            else
                break;
        }
        while(t!=0);
        system("cls");
        if(password==pass&&strcmp(nam,na)==0)
        {
            do
            {
                printf("\t\t     *******************************\n");
                printf("\t\t     *     1.增加景点简介信息      *\n");
                printf("\t\t     *     2.删除景点简介信息      *\n");
                printf("\t\t     *     3.更新景点简介信息      *\n");
                printf("\t\t     *     4.增加景点              *\n");
                printf("\t\t     *     5.增加路径              *\n");
                printf("\t\t     *     6.删除景点              *\n");
                printf("\t\t     *     7.删除路径              *\n");
                printf("\t\t     *     8.退出系统              *\n");
                printf("\t\t     *******************************\n");
                printf("请选择要进行的操作:");
                scanf("%d",&l);
                printf("\t\t     *******************************\n");
                if(N%2!=0)
                {
                    for(i=0; i<N-1; i+=2)
                    {
                         printf("\t\t          %d.%s  \t%d.%s  \n",g.vex[i].num,g.vex[i].name,g.vex[i+1].num,g.vex[i+1].name);
                    }
                     printf("\t\t          %d.%s       \n",g.vex[i].num,g.vex[i].name);

                }
                else
                {
                    for(i=0; i<N; i+=2)
                    {
                         printf("\t\t          %d.%s  \t%d.%s  \n",g.vex[i].num,g.vex[i].name,g.vex[i+1].num,g.vex[i+1].name);
                    }
                }
                printf("\t\t     *******************************\n");
                if(l==1)
                {
                    do
                    {
                        printf("请输入要要增加信息的景点的编号:");
                        scanf("%d",&d);
                        ReadData(g);
                        printf("%s\n",g.vex[d].introduction);
                        printf("请输入要增加的信息:");
                        scanf("%s",str2);
                        strcat(g.vex[d].introduction,str2);
                        printf("增加成功!\n");
                        WriteData(g);
                        printf("是否继续进行该操作(0.继续 1.不继续):");
                        scanf("%d",&y);
                        if(y==1)
                            break;
                        else
                            continue;
                    }
                    while(1);
                    system("cls");
                }
                if(l==2)
                {
                    do
                    {
                        printf("请输入要删除信息的景点的编号:");
                        scanf("%d",&d);
                        ReadData(g);
                        strcpy(str1,g.vex[d].introduction);
                        printf("%s\n",str1);
                        printf("请输入要删除的信息:");
                        scanf("%s",str2);
                        printf("%d\n",N);
                        delete_str(str1,str2,strlen(str2),str3);
                        printf("%s\n",str3);
                        strcpy(g.vex[d].introduction,str3);
                        printf("%s\n",g.vex[d].introduction);
                        WriteData(g);
                        printf("删除成功!\n");
                        printf("是否继续进行该操作(0.继续 1.不继续):");
                        scanf("%d",&y);
                        if(y==1)
                            break;
                        else
                            continue;
                    }
                    while(1);
                    system("cls");
                }
                if(l==3)
                {
                    do
                    {
                        printf("请输入要更新信息的景点的编号:");
                        scanf("%d",&d);
                        ReadData(g);
                        printf("请输入要更新的信息:");
                        scanf("%s",str2);
                        strcpy(g.vex[d].introduction,str2);
                        WriteData(g);
                        printf("是否继续进行该操作(0.继续 1.不继续):");
                        scanf("%d",&y);
                        if(y==1)
                            break;
                        else
                            continue;
                    }
                    while(1);
                    system("cls");
                }
                if(l==4)
                {
                    ReadData(g);
                    ReadData1(g);
                    for(i=0; i<N; i++)
                    {
                        for(j=0; j<N; j++)
                        {
                            printf("%d ",g.edges[i][j]);
                        }
                        printf("\n");
                    }
                    add_point(g);
                    WriteData1(g);
                    WriteData(g);
                }
                if(l==5)
                {
                    ReadData1(g);
                    for(i=0; i<M; i++)
                    {
                        for(j=0; j<M; j++)
                        {
                            printf("%d ",g.edges[i][j]);
                        }
                        printf("\n");
                    }
                    add_path(g);
                    WriteData1(g);
                }
                if(l==6)
                {
                    ReadData(g);
                    ReadData1(g);
                    for(i=0; i<M; i++)
                    {
                        for(j=0; j<M; j++)
                        {
                            printf("%d ",g.edges[i][j]);
                        }
                        printf("\n");
                    }
                    delete_point(g);
                    WriteData1(g);
                    WriteData(g);
                }
                if(l==7)
                {
                    ReadData1(g);
                    for(i=0; i<M; i++)
                    {
                        for(j=0; j<M; j++)
                        {
                            printf("%d ",g.edges[i][j]);
                        }
                        printf("\n");
                    }
                    delete_path(g);
                    WriteData1(g);
                }
                if(l==8)
                {
                    printf("确认退出吗?(0.退出 1.不退出):");
                    scanf("%d",&ch);
                    while(1)
                    {
                        if(ch==0||ch==1)
                            break;
                        else
                        {
                            printf("输入的数据不合理,请重新输入:");
                            scanf("%d",&ch);
                        }
                    }
                    if(ch==0)
                    {
                        x=0;
                        printf("正在退出....");
                        Sleep(5000);
                        break;
                    }
                    else
                    {
                        continue;
                    }
                }
            }
            while(1);
        }
    }
}
int main()
{
    function();
    return 0;
}

需要的文件:


path.txt的内容:


0 20 60 150 32767 60 32767 100 300 150 
20 0 50 100 32767 32767 32767 32767 32767 32767 
60 50 0 32767 32767 300 40 32767 32767 32767 
150 100 32767 0 32767 32767 32767 100 32767 32767 
32767 32767 32767 32767 0 50 32767 32767 32767 30 
60 32767 300 32767 32767 0 200 32767 32767 50 
32767 32767 40 32767 32767 200 0 32767 32767 32767
100 32767 100 32767 32767 32767 0 50 32767 32767 
300 32767 32767 32767 32767 32767 32767 50 0 350
50 32767 32767 32767 30 50 32767 32767 350 

password.txt的内容:


pass 123456

data.txt的内容:


0 三元湖 烟大的一道靓丽的风景
1 钟楼 配备有专业设备的实验综合楼
2 八景园 休息和聊天的好去处
3 小树林 各种社团的活动场所,
4 九龙广场 海豚雕塑加上美丽的喷泉很漂亮
5 八餐 美味的饭菜让人回味无穷
6 一餐 豪华的装修,美味的饭菜
7 体育场 锻炼和饭后散步的好去处
8 七餐 全亚洲最大的学生餐厅
9 新图 藏书丰富,安静的环境让人很舒服

 

2017-09-05 21:40:52 BAKA_51218 阅读数 1431

一、实验目的

二、使用仪器、器材

微机一台

操作系统:WinXP

编程软件:C++

三、实验内容及原理

1.校园导游咨询

【问题描述】

设计一个校园导游程序,为来访的客人提供各种信息查询服务。

【基本要求】

1)设计你的学校的校园平面图,所含景点不少于10个。以图中顶点表示学校各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。

2)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。

3)为来访客人提供图中任意景点相关信息的查询。

【测试数据】

由读者根据实际情况指定。

【实现提示】

一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向网。顶点和边均含有相关信息。

四、实验过程原始数据记录

实验源程序:

1、校园导游咨询

//graph.h

#define MVnum 10

#define NameLen 20

typedef char *VerTexType;//数据类型

typedef int ArcType;//边权类型

#include<iostream>

#include<queue>

#include<stack>

using namespace std;

typedef struct Closedge

{

int adjvex;

ArcType lowcost;

}Closedge;

typedef struct ArcNode

{

int adjvex;

ArcNode *nextarc;

ArcType info;

}ArcNode;

typedef struct VNode

{

VerTexType placename;

int  id;

char *info;

ArcNode *firstarc;

}VNode,AdjList;

typedef struct 

{

AdjList vertices[MVnum];

int vexnum,arcnum;

}ALGraph;

bool visited[MVnum];

int LocateVex(ALGraph G,char *name)

{

for(int i=0;i<G.vexnum;i++)

if(strcmp(name,G.vertices[i].placename)==0)

return i;

return -1;

}

int LocateVex(ALGraph G,int id)

{

for(int i=0;i<G.vexnum;i++)

if(G.vertices[i].id==id)

return i;

return -1;

}

int CreateUDG(ALGraph &G)

{

cout<<"input vexnum & arcnum"<<endl;

cin>>G.vexnum>>G.arcnum;

cout<<"input place information:like(id,placename,info)"<<endl;

for(int i=0;i<G.vexnum;i++)

{

cin>>G.vertices[i].id;

char *temp1=new char[NameLen];

cin>>temp1;G.vertices[i].placename=temp1;

char *temp2=new char[NameLen];

cin>>temp2;G.vertices[i].info=temp2;

G.vertices[i].firstarc=NULL;

}

char *v1,*v2;int i,j;ArcNode *p1,*p2;ArcType w;

cout<<"input road:(place1,place2,length)"<<endl;

for(int k=0;k<G.arcnum;k++)

{

v1=new char[NameLen];v2=new char[NameLen];

cin>>v1>>v2>>w;

i=LocateVex(G,v1);j=LocateVex(G,v2);

p1=new ArcNode;

p1->adjvex=j;p1->info=w;

p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;

//将新结点*p1插入顶点v1的边表头部

p2=new ArcNode;

p2->adjvex=i;p2->info=w;

p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;

}

return 1;

}

void DFS_AL(ALGraph G,VerTexType v1)

{

int v=LocateVex(G,v1);

cout<<v1<<" ";visited[v]=true;

ArcNode *p;int w;

p=G.vertices[v].firstarc;

while(p)

{

w=p->adjvex;

if(!visited[w])

DFS_AL(G,G.vertices[w].placename);

p=p->nextarc;

}

 

}

void DFSTraverse(ALGraph G)

{

for(int i=0;i<MVnum;i++)

visited[i]=false;

for(int i=0;i<G.vexnum;i++)

if(!visited[i])

DFS_AL(G,G.vertices[i].placename);

}

void BFS_AL(ALGraph G,VerTexType v1)

{

int v=LocateVex(G,v1);

cout<<v1<<" ";visited[v]=true;

queue<VerTexType> Q;

Q.push(v1);

VerTexType u1;

ArcNode *w;

int u;

while(!Q.empty())

{

u1=Q.front();

Q.pop();

u=LocateVex(G,u1);

for(w=G.vertices[u].firstarc;w!=NULL;w=w->nextarc)

{

if(!visited[w->adjvex])

{

cout<<G.vertices[w->adjvex].placename<<" ";visited[w->adjvex]=true;

Q.push(G.vertices[w->adjvex].placename);

}

}

}

}

void BFSTraverse(ALGraph G)

{

for(int i=0;i<MVnum;i++)

visited[i]=false;

for(int i=0;i<G.vexnum;i++)

if(!visited[i])

BFS_AL(G,G.vertices[i].placename);

}

int ShortPath_DIJ(ALGraph G,VerTexType v1,VerTexType v2)

{

bool S[MVnum];

int Path[MVnum];

ArcType D[MVnum];

int n=G.vexnum;

ArcNode *p;

int v0,vk,min,v;

v0=LocateVex(G,v1);vk=LocateVex(G,v2);

for(int i=0;i<n;i++)

{

S[i]=false;

Path[i]=-1;

D[i]=INT_MAX;

}

p=G.vertices[v0].firstarc;

while(p)

{

D[p->adjvex]=p->info;

Path[p->adjvex]=v0;

p=p->nextarc;

}

S[v0]=true;D[v0]=0;

/*------------初始化结束,开始主循环---------------*/

for(int i=1;i<G.vexnum;i++)

{

min=INT_MAX;

for(int w=0;w<n;w++)

{

if(!S[w]&&D[w]<min)

{

v=w;min=D[w];

}

}//for

S[v]=true;

p=G.vertices[v].firstarc;

while(p)

{

if(!S[p->adjvex]&&(D[v]+p->info)<D[p->adjvex])

{

D[p->adjvex]=D[v]+p->info;

Path[p->adjvex]=v;

}//if

p=p->nextarc;

}//while

 

}//for

cout<<v2<<"到"<<v1<<"的最短路径为:";

int k=vk;

while(k!=v0)

{

cout<<G.vertices[k].placename<<" ";

k=Path[k];

}

cout<<G.vertices[v0].placename<<endl;

return D[vk];

}

 

void Search(ALGraph G,VerTexType placename)

{

int i=LocateVex(G,placename);

if(i==-1)

{

cout<<"没有该景点"<<endl;

return ;

}

else

{

cout<<G.vertices[i].id<<'\t'<<G.vertices[i].placename<<'\t'<<G.vertices[i].info<<endl;

return ;

}

 

}

void Search(ALGraph G,int id)

{

int i=LocateVex(G,id);

if(i==-1)

{

cout<<"没有该景点"<<endl;

return ;

}

else

{

cout<<G.vertices[i].id<<'\t'<<G.vertices[i].placename<<'\t'<<G.vertices[i].info<<endl;

return ;

}

}

int SearchPlace(ALGraph G)

{

int flag;

cout<<"按(1.景点名;2.景点代码)查询";

cin>>flag;

VerTexType temp=new char[NameLen];

switch(flag)

{

case 1:

cout<<"input placename:";

cin>>temp;

Search(G,temp);

break;

case 2:

int id;

cout<<"input placeid:";cin>>id;

Search(G,id);

break;

default:

cout<<"wrong input!"<<endl;

break;

}

return 1;

}

int Traverse(ALGraph G)

{

int flag;

cout<<"遍历方式:1.深度;2.广度";

cin>>flag;

switch(flag)

{

case 1:DFSTraverse(G);break;

case 2:BFSTraverse(G);break;

default:

cout<<"wrong input!"<<endl;

break;

}

return 0;

}

//源.cpp

#include"graph.h"

int main()

{

ALGraph G;

while(1)

{

cout<<"----------校园导游程序----------"<<endl;

cout<<"--------1.初始化景点信息;------"<<endl;

cout<<"--------2.遍历景点;------------"<<endl;

cout<<"--------3.查询景点信息;--------"<<endl;

cout<<"--------4.查询最短路径;--------"<<endl;

cout<<"--------5.退出程序;------------"<<endl;

int work,flag=1;

cin>>work;

switch(work)

{

case 1:CreateUDG(G);break;

case 2:Traverse(G);cout<<endl;break;

case 3:SearchPlace(G);break;

case 4:

cout<<"input placename1&placename2:";

VerTexType v1,v2;

v1=new char[NameLen];v2=new char[NameLen];

cin>>v1>>v2;

ShortPath_DIJ(G,v2,v1);

break;

case 5:flag=0;break;

}

if(flag==0)

break;

}

cout<<"--------------------------------"<<endl;

return  0;

}

2015-12-30 09:07:31 suzucheese 阅读数 1171

头文件

#define MAXV 100//最大顶点个数
#define INF 32767//INF表示∞
#include<iostream>
#include<stdio.h>
using namespace std;
#include<string>
#include<fstream>
#include<stdio.h>
#include <malloc.h>
typedef int InfoType;
/*定义校园景点信息*/
typedef struct
{
    int no;//校园景点编号
    string name;//校园景点名称
    string introduct;//校园景点介绍
} VertexType;
typedef struct
{
    VertexType vexs[MAXV];      //景点
    int Arc[MAXV][MAXV];       //景点间的路
    int n,e;                    //景点数n和路数e
} ALGraph;
void ReadArc(ALGraph *g);         //图类
void readvernum(ALGraph *g);
void ArrayToMat(int *Arr, int n,ALGraph &g); //数组构造图的邻接矩阵
//void DispMat(MGraph g);//输出邻接矩阵g
void Photo();//打印界面
void ShowName();//显示名称
void StateVisit(ALGraph *G);
void DFS(ALGraph *G,int v);
void PrintName_1();//读取景点名称
void PaintMap_2();//绘制校园地图
void DFSinfo_3(ALGraph *G);//深度遍历校园
void InquireMess_4();;//查询景点介绍
void shortload(ALGraph *g);
void FlPath_5(ALGraph* g);//指导最短路径
void Exit_0();//退出导游系统
void MENU();//主菜单


源文件

#include"1.h"
int visited[MAXV];
int shortest[MAXV][MAXV];//最短路径
int path[MAXV][MAXV];//经过景点
/*打印界面*/
void Photo()
{
    //system("color 47");
    printf("-o-o-o-o-o-o-o-o-o校园景点导游:o-o-o-o-o-o-o-o-o-o-o-o\n");
    printf("|1 for 读取景点名称~~~~~~~~~~~~~~~~~4 for 查询景点介绍|\n");
    printf("|2 for 绘制校园地图~~~~~~~~~~~~~~~~~5 for 指导最短路径|\n");
    printf("|3 for 深度遍历校园~~~~~~~~~~~~~~~~~0 for 退出导游系统|\n");
    printf("-o-o-o-o-o-o-o-o-o-o你的选择是:o-o-o-o-o-o-o-o-o-o-o-o\n");
}
/*文件读取边*/
void ReadArc(ALGraph *g)
{
    FILE *fp;
    int i=0,j=0,k=0;
    for(i=0;i<g->n;i++)
        for(j=0;i<g->n;j++)
            g->Arc[i][j]=INF;
    fp=fopen("arry.txt","r");
    while(fscanf(fp,"%d %d %d",&i,&j,&k)!=EOF)
    {
        g->Arc[i-1][j-1]=k;
    }
    fclose(fp);
}
/*文件读取景点信息*/
void readvernum(ALGraph *g)
{
    FILE *fp;
    int i=0;
    fp=fopen("info.txt","rt");
    while(fscanf(fp,"%d %s %s",&g->vexs[i].no,g->vexs[i].name,g->vexs[i].introduct)!=EOF)
    {
        printf("景点序号:%d 名称:%s\n",g->vexs[i].no,g->vexs[i].name);
        printf("景点信息:%s\n",g->vexs[i].introduct);
        printf("\n");
        i++;
    }
    g->n=i;
    fclose(fp);
}
/*读取景点名称*/
void PrintName_1()
{
    ;
}
/*绘制校园地图*/
void PaintMap_2()
{
    ;
}

/*访问变量置零*/
void StateVisit(ALGraph *G)
{
    int i;
    for(i=0;i<G->n;i++)
    {
        visited[i]=0;
    }
}

/*深度遍历校园*/
void DFSinfo_3(ALGraph *G)
{
    int n;
    StateVisit(G);
    cout<<"请输入起始地点:\n";
    cin>>n;
    DFS(G,n-1);

}
/*DFS*/
void DFS(ALGraph *G,int v)
{
    int j;
    if(!visited[v])
    {
        visited[v]=1; //标记为访问过
        cout<<"景点:"<<G->vexs[v].name<<"\n介绍:"<<G->vexs[v].introduct<<endl;
    }
    for(j=0;j<G->n;j++)
    if ((G->Arc[v][j]!=INF)&&!visited[j])//邻接矩阵的第(v,j)元素不为0
    {                             //且未被访问过则递归
        DFS(G,j);
    }
}
/*查询景点介绍*/
void InquireMess_4()
{
 ;
}
/*最短路径*/
void shortload(ALGraph *g)
{
    int i,j,a,b;
    //PlaceList();
    FlPath_5(g);
    printf("请输入起始景点和终止景点(1-%d):\n",g->n);
    scanf("%d%d",&i,&j);
    a=i;
    b=j;
    i=i-1;
    j=j-1;
    if(i<j)
    {
        printf("%d",b);
        while(path[i][j]!=0)
        {
             printf("<-%d",path[i][j]+1);
            if(i<j)
            j=path[i][j];
            else
            i=path[j][i];
        }
        printf("<-%d",a);
        printf("\n\n");
        printf("%d->%d 距离是:%d米\n\n",a,b,shortest[a-1][b-1]);
    }
    else
    {
        printf("%d",a);
        while(path[i][j]!=0)
        {
            printf("<-%d",path[i][j]+1);
            if(i<j)
            j=path[i][j];
            else
            i=path[j][i];
        }
        printf("<-%d",b);
        printf("\n\n");
        printf("%d->%d 最短距离是:%d米\n\n",a,b,shortest[a-1][b-1]);
    }
}

/*指导最短路径*/
void FlPath_5(ALGraph* g)
{
 int i,j,k;
    for(i=0; i<g->n; i++)
        for(j=0; j<g->n; j++)
            shortest[i][j]=0;
    for(i=0; i<g->n; i++)
        for(j=0; j<g->n; j++)
        {
            shortest[i][j]=g->Arc[i][j];
            path[i][j]=0;
        }
    for(i=0; i<g->n; i++)
        for(j=0; j<g->n; j++)
            for(k=0; k<g->n; k++)
                if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
                {
                    shortest[i][j]=shortest[i][k]+shortest[k][j];
                    path[i][j]=k;
                    path[j][i]=k;
                }

}
/*退出导游系统*/
void Exit_0()
{
    printf("感谢,再见!\n");
    exit(0);
}
/*主菜单*/
void MENU()
{
    int choice;
    ALGraph *g;
    g=(ALGraph *)malloc(sizeof(ALGraph));//创建头结点
    Photo();
    while(1)
    {
        cin>>choice;
        switch(choice)
        {
            case 1:
				{
					ReadArc(g);
					PrintName_1();//读取景点名称
					break;
				}
				
            case 2:
				{
					PaintMap_2();//绘制校园地图
					break;
				}
				
            case 3:
                {
                    ReadArc(g);
                    DFSinfo_3(g);//深度遍历校园
                    break;
                }
            case 4:
				{
					InquireMess_4();
					break;//查询景点介绍
				}
				
            case 5:
                {
                    //ReadArc(g);
                    FlPath_5(g);//指导最短路径
                    break;
                }

            case 0:Exit_0();break;//退出导游系统
            default:cout<<"What you inputed is wrong.\n";break;
        }
        void Photo();
    }
}

主文件

#include "1.h"
int main()
{
    MENU();
    return 0;
}

显示