Data structure course design North

Version 3:12.13 modified

Recently, Mr. Zhang (in fact, I'm not sure who did it, but I feel that Mr. Zhang has this level) gave me an interesting question. Many younger brothers and sisters came to ask me. In order to facilitate everyone in the province to ask me several times, I'll share my personal ideas with you.

First topic:

This course is designed as an independent comprehensive course with a credit of 2.0 (Internet of things Engineering). It mainly involves C language, data structure and other course knowledge, covering the main professional course knowledge of this major.

Background: Danzhou campus is a picturesque campus. It not only has a strong humanistic learning atmosphere, but also has beautiful scenery. Suppose your parents or friends come to Danzhou campus for tourism, but their time is limited. How can you be a good tour guide if you want to complete the main teaching, office and tourism points of Danzhou campus in the shortest time? The map of Danzhou campus is given, and the main teaching buildings, office locations, scenic spots and their distances are marked.

Problem Description: the shortest path problem of graph refers to finding the shortest path from a specified point v to each other vertex. The length of the shortest path and the location of the path are given. In addition to solving the shortest path, it can also modify the graph, such as the addition and deletion of vertices and edges, the modification of weights on edges, etc.

The main elements include:

1. Apex: teaching point, office point and scenic spot.
2. Number of sides: the number of roads between locations.
3. Side length (weight): distance.

Functional requirements:

1. Output vertex information: names of teaching, office and scenic spots

2. Edge information: output the distance between any two positions (if there is a direct path)

3. Modify: modify the distance between two positions and re output the distance between each two positions.

4. Delete: deletes any edge.

5. Insert: inserts any edge.

6. Find the shortest path: give any two points, output the path length and path location between the two points, and output the shortest path between any point and other points.

I'll just go straight to the point and say according to the requirements of the topic:

Topic requirements 1-5 are very basic questions. If I write near the end of the term, I must choose the adjacency matrix, so as to achieve the fastest speed and highest efficiency.

The first two don't say. There's nothing to say. It's too simple.

Modify: it should be noted that this can only be modified if it exists, then read in the modification target, read in the modified content, and directly modify the corresponding content of the array.

Delete: note how to delete. For the shortest path problem, the distance that can never be reached is equivalent to deletion, so it is recommended to assign a large number directly.

Insert: as above, it is a direct assignment.

Seeking the shortest path: in fact, there are two requirements, one is the output distance and the other is the output path. Here, two algorithms are recommended, one is Floyd and the other is Dijkstra. Because this paragraph is learning algorithms, I'll write them down and practice.

User interface design: it is recommended to use a while loop to poll the contents that users may enter.

Like this:

while(1)//The dead cycle keeps running all the time
	{
		printf("\r\n Please enter the command serial number to start the task\r\n");
		scanf("%d",command); //Read in command
		if(command == 0)//For each, first enter the command sequence number, start the command, and then enter the start place and end place
		else if(command == 1)//Execution of a command
            
         else if(command == 2)//A command
             
		else if(command == 3)//A command
            
		else if(command == 4)//A command
            
		else if(command == 5)//A command
            
	}

Each operation is similar to modify, delete and insert.

void An operation()//Operation function
{
	//Read in input parameters
    //assignment
    //end
}

The establishment of the graph is very simple. The picture should be a one-way graph.

Since the array is used, it is OK to assign values directly

int Two dimensional array[][]=
{
    [East Gate][Academic Building]=distance
    //Assign a value directly to the map
}

Shortest path algorithm:

I'll give you two approximate codes directly. See how to write them for yourself. There are many online tutorials..

No more details.

void fold()//Freudian algorithm
{
	int k=0,i=0,j=0;
     for(k=0;k< N;k++)
        for(i=0;i< N;i++)
			for(j=0;j< N;j++)
				if(edge[i][j]>edge[i][k]+edge[k][j])
					 edge[i][j]=edge[i][k]+edge[k][j];
}

/*
Compared with finding the shortest path, add a path array to record the shortest path
 First set path[i]=-1, then find the shortest point p each time, and then set path[j]=p
 Use path[j]=i to represent the shortest path from i to j
*/

void Dijkstra(int number,int target)//Dijkstra algorithm / / I can't remember it clearly by handwriting. Maybe so
{
    int i,j,k;
    int min;
    int tmp;
    int flag[MAX];      // flag[i]=1 indicates that the shortest path from "vertex vs" to "vertex i" has been successfully obtained.

    // initialization
    for (i = 0; i < G.vexnum; i++)
    {
        flag[i] = 0;              // The shortest path of vertex i has not been obtained.
        prev[i] = 0;              // The leading vertex of vertex i is 0.
        dist[i] = G.matrix[vs][i];// The shortest path of vertex i is the weight from vertex vs to vertex i.
    }

    // Initializes vertex vs itself
    flag[vs] = 1;
    dist[vs] = 0;

    // Traverse G.vexnum-1 times; Find the shortest path of one vertex at a time.
    for (i = 1; i < G.vexnum; i++)
    {
        // Find the current minimum path;
        // That is, among the vertices that do not obtain the shortest path, find the vertex (k) closest to vs.
        min = INF;
        for (j = 0; j < G.vexnum; j++)
        {
            if (flag[j]==0 && dist[j]<min)
            {
                min = dist[j];
                k = j;
            }
        }
        // Mark "vertex k" as having obtained the shortest path
        flag[k] = 1;

        // Fix the current shortest path and precursor vertices
        // That is, when the "shortest path of vertex k" has been, the "shortest path and precursor vertex of vertex without the shortest path" are updated.
        for (j = 0; j < G.vexnum; j++)
        {
            tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // Prevent overflow
            if (flag[j] == 0 && (tmp  < dist[j]) )
            {
                dist[j] = tmp;
                prev[j] = k;
            }
        }
	}
        //Path recording method / / reverse reading is required
	for(int j=1; j<=n; j++)
    {
        if(!visited[j] && dis[p]+mapp[p][j]<dis[j])
        {
            dis[j]=dis[p]+mapp[p][j];
            path[j]=p;
        }
	}
	
}