1 problem description
Nowadays, with the improvement of living standards, everyone likes to visit a scenic spot during the holidays. In the scenic spots, tourists often hear about the shortest path and distance from one scenic spot to another. Such tourists who don't like to visit according to the guide map often need a scenic spot management system to select their favorite scenic spots, Then plan a shortest path and shortest distance to visit, so as to save time and improve tourism efficiency.

2 design of data structure
Establish a scenic spot tourism information management system to realize the following functions:

1. Create distribution map of scenic spots
   The distribution map of scenic spots is recorded through an adjacency matrix (essentially a two-dimensional array, m[i][j] represents the weight from I to j, and zero represents no direct path)

2. Output the distribution map of scenic spots (adjacency matrix)
   Output the distribution map of scenic spots by scanning the adjacency matrix

3. Output tour guide route map: depth first strategy
   Firstly, through traversing the scenic spots and an entrance scenic spot c given by the user, a tour guide route map is established, which is represented by a directed graph. Traversal adopts the depth first strategy (recursion), which is also the psychology of normal tourists

4. Judge whether there is a circuit in the tour guide route map: topological sorting (find scenic spots with a penetration greater than 1)
   In order to optimize the tour guide route map, you can judge whether there is a loop in the map through topological sorting. If there is a loop, print out the scenic spots in the loop for manual optimization

5. Find the shortest path and shortest distance between two scenic spots: floyd algorithm
   In the tour guide route map, it also provides information services for some tourists who are unwilling to follow the route, such as the shortest path and shortest distance from one scenic spot to another. In this circuit diagram, the shortest path and shortest distance between any scenic spots will be output

6. Output road construction plan: prime algorithm
   In the construction of scenic spots, road construction is one of the important contents. Road construction should first ensure that it can connect all scenic spots, but it should spend the least cost. This problem can be solved by finding the minimum spanning tree and finding the minimum spanning tree by prime algorithm
   Functions added through modification:

7. Save the file name specified by the scenic spot distribution map installation (which can be named by the scenic spot name) to the default directory file
   Here I encountered the problem of path format, which can be solved by querying data

8. Read the scenic spot distribution map of the specified file name from the default directory file
   This reduces the need to create the distribution map of scenic spots every time, and it is also convenient to import the system from the existing distribution map of scenic spots. There is no need to manually create a new one, which is more convenient and humanized in practical application

9. Add a scenic spot road for the current scenic spot
   At the beginning, the path of scenic spots was not cleared, so that after adding scenic spot roads, the distribution map of scenic spots with fewer scenic spots was imported again. When adding scenic spot roads, it was found that the previous roads still exist. Therefore, the road scenic spots should be cleared before adding scenic spot roads

3 algorithm design (core code)

//Depth first search tour guide route
int visited[M]={0};
int np=0;//Number of scenic spots found
int p[M];//Indicates the penetration value of each scenic spot
void DFS(int c){
    //c is the number of scenic spots
    np++;//Each recursive call will be added once to judge whether it has reached the last scenic spot
    p[c]++;
    if(np==S.count){
        //To the last scenic spot
        cout<<S.mat.Pname[c]<<endl;
        returnMainFace();
    }else{
       cout<<S.mat.Pname[c]<<"-->";
    }
     visited[c]=1;
     for(int i=0;i<S.count;i++){
        if(S.mat.m[c][i]>0&&visited[i]==0){
             DFS(i);
             if(S.count>np){
                 cout<<S.mat.Pname[c]<<"-->";
                 p[c]++;
             }
         }
     }
     if(np==S.count)
         returnMainFace();
}
void guide_line()//Tour guide route
{
     checked();
     cout<<"\n*Please enter the attraction number of the starting attraction:";
     int c;
     cin>>c;
     c--;
     for(int i=0;i<S.count;i++){
         visited[i]=0;
         p[i]=0;//Set the initial value of penetration to 0
     }
     np=0;
     cout<<"*The formed tour guide route map (adopting the depth first strategy) is as follows:\n\n\t";
     DFS(c);
}
//Floyd algorithm, A[M][M] represents the shortest distance, path[M][M] represents the auxiliary array, and remember the precursor
void Floyd(int A[M][M],int path[M][M]){
     int i,j,k;
     for(i=0;i<S.count;i++){
         for(j=0;j<S.count;j++){
            if(S.mat.m[i][j]==0&&i!=j){
                 //If there is no edge between two points, the weight is infinite
                 A[i][j]=INF;//INF=999666333
             }else if(i==j){
                 A[i][j]=0;
             }else{
                 //S.mat.m[i][j] indicates the length of the road between two scenic spots
                A[i][j]=S.mat.m[i][j];
             }
             //Assign values to all paths [i] [J]
             if(i!=j&&S.mat.m[i][j]<INF){
                 path[i][j]=i;
             }else{
                 //(i==j&&S.mat.m[i][j]=INF
                 path[i][j]=-1;
             }
         }
     }
        //Pay attention to placing k on the outermost layer and let A[i][j] test pass through each k
         for(k=0;k<S.count;k++){
             for(i=0;i<S.count;i++){
                for(j=0;j<S.count;j++){
                    if(A[i][j]>A[i][k]+A[k][j]){//If the weight of I - > J is greater than that of I - > k - > J
                        A[i][j]=A[i][k]+A[k][j];
                        path[i][j]=path[k][j];//path[k][j]=k precursor? K is the next scenic spot
                     }
                 }
             }
         }
}
void min_distance()//Shortest path, distance
{
     checked();
     int A[M][M],path[M][M];
     Floyd(A,path);//A is the length of the shortest path from one scenic spot to another
     while(true){
         Num_Name();//Scenic spot name corresponding to the number
         int i,j,k,s;
         int apath[M],d;//apath[M] is an array of record paths
         bool flag=true;
         while(flag){
             cout<<"\t-Attraction 1:";
             cin>>i;
             i--;
            if(i<0||i>S.count-1){
                 cout<<"*Please enter a valid attraction number:\n";
             }else{
                 flag=false;
             }
         }
         flag=true;
         while(flag){
             cout<<"\t-Attraction 2:";
             cin>>j;
             j--;
            if(j<0||j>S.count-1){
                 cout<<"*Please enter a valid attraction number:\n";
             }else{
                 flag=false;
             }
         }
        if(A[i][j]<INF&&i!=j){
             k=path[i][j];//k is the next scenic spot
             d=0;//The path has d+2 scenic spots, which is the subscript of the array apath
             //Store the point of the path to be output in the stack apath
             apath[d]=j;//Last attraction
            while(k!=-1&&k!=i){
                 d++;
                 apath[d]=k;
                 //Continue to judge whether there are scenic spots
                 k=path[i][k];
             }
             d++;
             apath[d]=i;//Add the first point
             cout<<"\n*from "<<S.mat.Pname[i]<<" reach"<<S.mat.Pname[j]<<" The shortest path is:";
             cout<<S.mat.Pname[apath[d]];//The last of the apath[M] array is the first starting point, which is equivalent to the stack
             for(s=d-1;s>=0;s--){//Print out the remaining scenic spots (the remaining elements of the apath[M] array)
                 cout<<"-->"<<S.mat.Pname[apath[s]];
             }
             cout<<" ，The shortest distance is:"<<A[i][j]<<endl;//Floyd algorithm has calculated the shortest path and stored it in A[i][j] (replaced the INF value with the shortest path)
         }else if(i==j){
             cout<<"\n*The scenic spot input is illegal. The two entered scenic spots cannot be the same!\n";
         }else{
             cout<<"\n*There is no path between the two attractions\n";
         }
         cout<<"\n Continue to query the shortest path and shortest distance( Y/N)";
         Y_N();
     }
     returnMainFace();
}
//Road construction plan, minimum spanning tree (prime algorithm)
void build_road()
{
     checked();
     cout<<"\n*Road construction plan( prime Algorithm) is planned as follows:\n";
     //Ai[M] represents the weight of the edge to be selected, one row of the adjacency matrix, closest[M]: point number array, which records the number of the starting point of a road
     intAi[M],min,closest[M],i,j,k,sum=0,num=0;//num indicates which way
     int A[M][M];
     //Weighted value
     for(i=0;i<S.count;i++){
         for(j=0;j<S.count;j++){
            if(S.mat.m[i][j]==0&&i!=j){
                 A[i][j]=INF;
             }else if(i==j){
                 A[i][j]=0;
             }else{
                A[i][j]=S.mat.m[i][j];
             }
         }
     }
     for(i=0;i<S.count;i++){
         Ai[i]=A[0][i];//Take the first line and save four Ai[i], which is the weight from one scenic spot to all scenic spots
         closest[i]=0;//0
     }
     for(i=1;i<S.count;i++){
         min=INF;
         //Select the minimum value from Ai[j] and store it in min
         for(j=0;j<S.count;j++){
            if(Ai[j]!=0&&Ai[j]<min){
                 min=Ai[j];
                 k=j;//The column j:k=j that records the minimum value is selected for the following sign
             }
         }
         if(min<INF){
             cout<<"\t-The first "<<++num<<" Road: from"<<S.mat.Pname[closest[k]]<<" reach"<<S.mat.Pname[k]<<" , The length of the road is:"<<min<<endl;
             sum+=min;//sum cumulative road length, that is, the selected weight
         }
         Ai[k]=0;//The flag is the weight of the selected edge to avoid repeated selection
         //Example: compare the weights of a to c and b to c, take the minimum and store it in Ai[j]
         for(j=0;j<S.count;j++){
            if(A[k][j]!=0&&A[k][j]<Ai[j]){
                 Ai[j]=A[k][j];
                 closest[j]=k;//The point number array records the number of the starting point of the next road
             }
         }
     }
     cout<<"*The total length of the road to be built is:"<<sum<<endl;
     returnMainFace();
}

4 operation and test
The test results are correct by creating different scenic spot distribution maps. The following is an example to demonstrate the process of running the test:

Create a distribution map of scenic spots:

5 Summary and experience
By taking the course design of data structure seriously, seriously thinking about how to use algorithms and codes to solve problems in real life, and carefully referring to excellent references and excellent works, we have gained a lot. At the beginning, I had no clue in the face of real-life problems and didn't know how to start to solve real-life problems. Later, through references and similar works of others, I found that the original data structure algorithm was used in this way. Therefore, I solved the doubts in the data structure class: how to use the data structure in our work code. Generally speaking, there are a lot of things to gain. As long as we take every link of learning seriously, we will gain something.

Through the teacher's guidance, the system has been greatly optimized, and I have learned a lot. Many practical problems have not been considered thoroughly. The teacher can point out and ask me to modify. It is precisely because of the modification that I learned more knowledge and made me understand that doing curriculum design is not just doing curriculum design, But also through this curriculum design to consider practical problems and constantly optimize.