Campus tour guide consultation
[Problem Description]
Design a campus tour guide scheme to provide various information inquiry services for visiting guests.
[Basic requirements]
(1) Design the campus planning of your school, including no less than 10 scenic spots. Vertex in the graph represents the scenic spots in the school and stores the names, codes, profiles and other information of the scenic spots. The path is represented by edges, and the path length and other related information are stored.
(2) Provide tourists with information about any scenic spot in the picture.
(3) Provide tourists with directions for any scenic spot in the map, that is, query the shortest simple path between any two scenic spots.
[Implementation Tips]
In general, the roads on campus are two-way, so it can be assumed that campus planning is an undirected network. Both vertices and edges contain relevant information.
Demand analysis
1 Select 10 familiar scenic spots from the plan of north university of china and abstract them into an undirected weighted map (as shown in the figure). The vertex in the picture represents the scenic spot, and the weight on the side represents the distance between the two places.
The purpose of this program is to provide path consultation and scenic spot inquiry for users. Output the corresponding path according to the starting point and ending point specified by the user or output the scenic spot information according to the scenic spot specified by the user.
south
north
Second, the outline design
This paper adopts 1 data structure.
*/
/* Include header file */
# include & ltstdio.h & gt
# include & ltprocess.h & gt
/* Define symbolic constants */
#define INT_MAX 10000
# Definition number 10
/* Define global variables */
int cost[n][n]； /* Value of edge */
int shortest[n][n]； /* The shortest distance between two points */
int path[n][n]； /* Passing scenic spots */
/* Description of custom function prototype */
void introduce()；
int shortest distance()；
void floy ed()；
Void display (int i, int j);
Division of labor between two people
(1) information query of scenic spots
(2) The shortest distance between two scenic spots
(3) The path between two scenic spots
Third, detailed design.
void main()
{/* Main function */
int i，j；
char k；
for(I = 0； I < = n; i++)
for(j = 0； j & lt= n； j++)
cost[I][j]= INT _ MAX；
cost[ 1][3]= cost[3][ 1]= 2；
Cost [2][3]= cost [3] [2] =1;
Cost [2][4]= cost [4] [2] = 2;
cost[3][ 10]= cost[ 10][3]= 4；
cost[ 1][ 10]= cost[ 10][ 1]= 4；
cost[2][ 10]= cost[ 10][2]= 4；
cost[4][ 10]= cost[ 10][4]= 4；
cost[ 1][4]= cost[4][ 1]= 5；
Cost [4][5]= cost [5] [4] = 3;
Cost [4][9]= cost [9] [4] = 4;
Cost [5][9]= cost [9] [5] = 8;
Cost [5][7]= cost [7] [5] = 4;
Cost [5][6]= cost [6] [5] = 2;
Cost [6][7]= cost [7] [6] =1;
Cost [7][8]= cost [8] [7] = 3;
Cost [8][6]= cost [6] [8] = 4;
cost[ 1][ 1]= cost[2][2]= cost[3][3]= cost[4][4]= cost[5][5]= 0；
Cost [6][6]= cost [7][7]= cost [8][8]= cost [9][9]= cost [10] [10] = 0;
while( 1)
{
Printf ("-Welcome to north university of china Tour Guide System! -\ n ")；
Printf(" 1。 For information about scenic spots ... please press I (Introduction) \ n ");
Printf("2。 The shortest path query of scenic spots ... please press s (shortest distance \ n ");
Printf("3。 log down .................................................................................................................................................................
Printf ("list of school attractions: \ n");
Printf(" 1: south gate of the school ");
Printf("2: student apartment ");
Printf(《3: Berlin Garden);
Printf("4: Restaurant ");
Printf("5: Gymnasium \ n ");
Printf("6: Library ");
Printf("7: Key Laboratory ");
Printf("8: Main Building ");
Printf("9: ke yiyuan ");
Printf(" 10: National Defense Student Apartment \ n ");
Printf ("Please select a service:");
scanf("\n%c "，k)；
Switch (k)
{
Case "I":
Printf ("information inquiry into scenic spots:");
Introduction ();
Break;
Case:
Printf ("Enter the shortest path query:");
shortest distance()；
Break;
Case "e":
Exit (0);
Default value:
Printf ("Incorrect input information! \nPlease enter the letters I or S or E, \ n ");
Break;
}
}
}/*main*/
Void introduction ()
{/* Introduction to scenic spots */
int a；
Printf ("Which scenic spot should I check specifically? Please enter the scenic spot number: ");
scanf("%d "，a)；
getchar()；
printf(" \ n ")；
Switch (a)
{
Case 1:
Printf(" 1: south gate of the school \n\n \ nA stone statue of Peng Dehua stands at the main gate of the school, which is magnificent. \ n \ n ")； Break;
Case 2:
Printf("2: the place where student apartments are concentrated. \ n \ n ")； Break;
Case 3:
Printf("3: Berlin Garden \ n \ n \ nA Place for morning reading and exercise. \ n \ n ")； Break;
Case 4:
Printf("4: Dining Room \ n \ nWhere students and teachers eat \ n \ n "); Break;
Case 5:
Printf("5: Gymnasium \ n \ nGymnasium \ n \ nA Places where students go to physical education class and exercise, including track and field, football field and basketball court. \ n \ n ")； Break;
Case 6:
Printf(" 6:Library \ n \ n \ n nThe school information resource center has a large number of study rooms. \ n \ n ")； Break;
Case 7:
Printf("7: Key Laboratory of our school \ n \ nResearch and Research Center \ n \ n "); Break;
Case 8:
Printf("8: Main building \ n \ n \ The main building of the school administration office. \ n \ n ")； Break;
Case 9:
Printf("9: EcoPark \ n \ n \ There is a coffee shop and a screening room. \ n \ n \ n ")； Break;
Case 10:
Printf(" 10: national defense student apartment \n\n \ nNational defense student residence. \ n \ n ")； Break;
Default value:
Printf ("The scenic spot number is entered incorrectly! Please enter1-> Quantity 10! \ n \ n ")； Break;
}
}/* Introduction */
int shortestdistance()
{/* Find the shortest distance between two scenic spots */
int i，j；
Printf ("Please enter the numbers of the two scenic spots to be queried (1-> The number 10 is separated by','): ";
scanf("%d，%d "，I，j)；
If (I>N || I < = 0 || J>N || J<0)
{
Printf ("Incorrect input information! \ n \ n ")；
Printf ("Please enter the numbers of the two scenic spots to be queried (1-> Number the number of 10 with',' interval): \ n ");
scanf("%d，%d "，I，j)；
}
other
{
floy ed()；
Display (i, j);
}
Returns1;
}/* Shortest distance */
Hollow floyed ()
{/* Find the shortest path between two scenic spots by floyed algorithm */
int i，j，k；
for(I = 1； I < = n; i++)
for(j = 1； j & lt= n； j++)
{
Shortest [I][j]= cost [i] [j];
path[I][j]= 0；
}
for(k = 1； k & lt= n； k++)
for(I = 1； I < = n; i++)
for(j = 1； j & lt= n； j++)
if(shortest[I][j]& gt； (shortest[i][k]+shortest[k][j])
{/* Use path[][] to record the precursor scenic spot number of point J on the shortest path from I to J */
Shortest [I][j]= shortest [I][k]+ shortest [k] [j];
Path [I] [j] = k;
path[j][I]= k；
}
}/*floyed*/
Empty display (int i, int j)
{/* Print the path and shortest distance of two scenic spots */
int a，b；
a = I；
b = j；
Printf ("The shortest path between two scenic spots you want to query is: \ n \ n");
If (shortest [i][j]! =INT_MAX)
{
If (I<j)
{
printf("%d "，b)；
while(path[i][j]！ =0)
{/* Print out all the scenic spots on the I-J route in reverse order */
printf(" & lt； -%d ",path [i] [j]);
If (I<j)
j = path[I][j]；
other
I = path[j][I]；
}
printf(" & lt； -%d”，a)；
printf(" \ n \ n ")；
printf("(% d-& gt； %d) The shortest distance is: %d meters \n\n ",a, b, the shortest [a] [b]);
}
other
{
printf("%d "，a)；
while(path[i][j]！ =0)
{/* Print out all the scenic spots on the I-J route in sequence */
printf("-& gt； %d ",path [i] [j]);
If (I<j)
j = path[I][j]；
other
I = path[j][I]；
}
printf("-& gt； %d”，b)；
printf(" \ n \ n ")；
printf("(% d-& gt； %d) The shortest distance is: %5d m \n\n ",a, b, shortest [a] [b]);
}
}
other
Printf ("Input error! This road does not exist! \ n \ n ")；
printf(" \ n ")；
}/* Display */