Data structure adjacency multiple table (C language implementation)

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

I'm learning data structure recently , Yesterday I realized the adjacency multiple table , There was a little problem before writing , Originally wanted to find a big man to write the program reference , But there was no satisfactory , So I can only write by myself . Little brother wrote this program, the whole process only refers to the textbook on the adjacency multiple table some simple text description , As for the code section , It's all written by my little brother alone , There is no reference , The writing is redundant , So if some big guy thinks that my brother's writing is too clumsy , Please keep your mouth on your mind , First time I posted an article on the Internet .

Compared with adjacency list, adjacency multiple table saves space greatly （ Half ）, In adjacency multiple table, when defining the structure of adjacent vertices, it does not represent a vertex , It's a side by node_1 To node_2 One side of , And there are two pointer fields, one of which belongs to node_1 A pointer field belongs to node_2, They two don't interfere with , It's like two adjacent highways , Put on a road node_1 Motorcade , Put on another road node_2 Motorcade （ First of all, you should create a sense of adjacency to multiple tables ）, Therefore, an edge node can be used by two vertices
This is the structure that defines the edge nodes

This is the structure that defines the vertex nodes , among vex Record top points ,edge Record edges ,head The information of each vertex is recorded in the structure , And the pointer field of the linked list

This is a picture on the Internet adjacent to multiple tables , You can understand

Then I'll talk about the key points and difficulties of this program ！！！！！
Look at the example above , Let's find any side , Just v2 To v5 This side , That is to say （4,1） This side , What we need to do now is mount the side to v2 Nodes and v5 Under the node , Let's be simple , Let's mount this side in v5 Next ( Mount on the with node_1 Under vertex nodes with the same value ), First of all, judge v5 Whether there are mount nodes under , Judge nothing , Then mount the node directly in v5 Vertex node of next in , This is the success of the mount .
Then mount it on v2 Next （ Mount on the with node_2 Under vertex nodes with the same value ）, equally , First judge v2 Is there a mount node , There is a judgment , use 1（node_2） And v2 The first node of （0,1） Compare （ First of all, determine the attached edge node's node_1 and node_2 Which vertex to mount v2）. Found the mount of node_2 And the ones to be mounted node_2 identical , And then compare what you want to mount node_1（4） Larger than the one that has been mounted node_1（0）, Get into node_2_pointer, And again （2,1） Comparison found mounted node_2 And the ones to be mounted node_2 identical , And then compare what you want to mount node_1（4） Larger than the one that has been mounted node_1（2）, Get into node_2_pointer, Find out node_2_pointer by NULL Will （4,1） Edge node , Mount this pointer field . Those who have doubts about the above operation can take a look at the contents in brackets below .
（------------------------------------------------------------------------------------------------------------------
Because it is to be inserted with node_2 Under the same vertex node , So we need to use what we want to mount node_2 Make the following judgments ：
Case one ： To mount the edge node of node_2 And the ones that have been mounted node_1 identical , And it's better to mount node_1 And the ones that have been mounted node_2, If small , Then the edge node is inserted into the first （next）, Otherwise , The node pointer enters the mounted node node_1_pointer（ Why not enter node_2_pointer Well ？ Because the above has been compared to mount node_2 With the ones that have been mounted node_1 The value of is the same , So to enter node_1_pointer Pointer to the domain ）, And then continue with the same operation （ Compare -> Judge the size -> Insert a node or enter a pointer field ）.
The second case ： To mount the edge node node_2 With the ones that have been mounted node_2 identical , And it's better to mount node_1 And the ones that have been mounted node_1, If small , Then the edge node is inserted into the first （next）, Otherwise , The node pointer enters the mounted node node_2_pointer, Why enter the pointer field , The reason as above . And then continue with the same operation .
）--------------------------------------------------------------------------------------------------------------------

in general , There are three cases of insertion ,
Case one ： No mount on the vertex head , Or judge that the adjacent node of the first edge node that has been mounted is larger than the adjacent node of the edge node to be mounted , Then the edge node is inserted into the vertex node next
The second case ： Determine that it needs to be inserted in the middle of the mount list of vertex nodes
The third case ： The adjacent nodes of the edge nodes to be mounted are larger than those of all the mounted edge nodes
（ Because it's too complicated , So language is very difficult to describe , You should look the same ^ _ ^）
Now please take a look at the code

#include<stdio.h>
// Adjacency multiple tables 
#define MAX 20


struct Enode
{
   
   
	int node_1;
	int node_2;
	struct Enode* node_1_pointer;
	struct Enode* node_2_pointer;
};

struct AMLGraph
{
   
   
	int edge;
	int vex;
	struct
	{
   
   
		char head_ele;
		struct Enode* next;
	}head[MAX];
};

void show(struct AMLGraph* map);
void creat(struct AMLGraph* map);
void insert(struct AMLGraph* map, char node_1, char node_2);


void creat(struct AMLGraph* map)
{
   
   
	char node_1;
	char node_2;
	printf(" To build several nodes , A few sides ：");
	scanf("%d%d", &map->vex, &map->edge);
	getchar();
	for (int i = 0; i < map->vex; i++)
	{
   
   
		map->head[i].next = NULL;
		map->head[i].head_ele = i + 'A';
	}
	printf(" Please input side :\n");
	for (int i = 0; i < map->edge; i++)
	{
   
   
		scanf("%c%c", &node_1, &node_2);
		getchar();
		insert(map, node_1, node_2);
	}


}
void insert(struct AMLGraph* map, char node_1, char node_2)
{
   
   
	struct Enode* now;
	struct Enode* q;
	struct Enode* before;
	struct Enode* p = malloc(sizeof(struct Enode));
	p->node_1 = node_1 - 'A';
	p->node_2 = node_2 - 'A';
	p->node_1_pointer = NULL;
	p->node_2_pointer = NULL;
	// Mount this node in node_1 and node_2 In the linked list 
	// Insert and node_1 The same list 
	now = map->head[node_1 - 'A'].next;
	before = now;
	while (now)
	{
   
   
		// Determine whether the node should be inserted in the chain header 
		if (node_1-'A' == map->head[node_1 - 'A'].next->node_1 )
		{
   
   
			if (node_2-'A' < map->head[node_1 - 'A'].next->node_2)
			{
   
   
				p->node_1_pointer = map->head[node_1 - 'A'].next;
				map->head[node_1 - 'A'].next = p;
				break;
			}
		}
		else
		{
   
   
			if (node_2 - 'A' < map->head[node_1 - 'A'].next->node_1)
			{
   
   
				p->node_1_pointer = map->head[node_1 - 'A'].next;
				map->head[node_1 - 'A'].next = p;
				break;
			}
		}
		
		//node_1 and now->node_1 equal 
		if (node_1 - 'A' == now->node_1)
		{
   
   
			if (node_2 - 'A' > now->node_2)
			{
   
   
				before = now;
				now = now->node_1_pointer;
			}
			else if (node_2 - 'A' < now->node_2)
			{
   
   
				if (before->node_1 == node_1 - 'A')
				{
   
   
					q = before->node_1_pointer;
					before->node_1_pointer = p;
					p->node_1_pointer = q;
				}
				else
				{
   
   
					q = before->node_2_pointer;
					before->node_2_pointer = p;
					p->node_1_pointer = q;
				}
				break;
			}
		}
		else//node_1 and now->node_2 equal 
		{
   
   
			if (node_2 - 'A' > now->node_1)
			{
   
   
				before = now;
				now = now->node_2_pointer;
			}
			else if (node_2 - 'A' < now->node_1)
			{
   
   
				if (before->node_2 == node_1 - 'A')
				{
   
   
					q = before->node_2_pointer;
					before->node_2_pointer = p;
					p->node_1_pointer = q;
				}
				else
				{
   
   
					q = before->node_1_pointer;
					before->node_1_pointer = p;
					p->node_1_pointer = q;
				}
				break;
			}
		}

	}

	if (!now)// There are two situations map->head[node_1 - 'A'].next Empty or to be inserted at the end of the list 
	{
   
   
		if (!before)
		{
   
   
			map->head[node_1 - 'A'].next = p;
		}
		else if (before->node_1 == node_1 - 'A')
		{
   
   
			before->node_1_pointer = p;
		}
		else if (before->node_2 == node_1 - 'A')
		{
   
   
			before->node_2_pointer = p;
		}
	}
	//--------------------------------------------------------------------------------------
	// Insert and node_2 The same list 
	now = map->head[node_2 - 'A'].next;
	before = now;
	while (now)
	{
   
   
		// Determine whether the node should be inserted in the chain header 
		if (node_2 - 'A' == map->head[node_2 - 'A'].next->node_1)
		{
   
   
			if (node_1 - 'A' < map->head[node_2 - 'A'].next->node_2)
			{
   
   
				p->node_2_pointer = map->head[node_2 - 'A'].next;
				map->head[node_2 - 'A'].next = p;
				break;
			}
		}
		else
		{
   
   
			if (node_1 - 'A' < map->head[node_2 - 'A'].next->node_1)
			{
   
   
				p->node_2_pointer = map->head[node_2 - 'A'].next;
				map->head[node_2 - 'A'].next = p;
				break;
			}
		}

		//node_2 and now->node_2 equal 
		if (node_2 - 'A' == now->node_2)
		{
   
   
			if (node_1 - 'A' > now->node_1)		
			{
   
   
				before = now;
				now = now->node_2_pointer;
			}
			else if (node_1 - 'A' < now->node_1)
			{
   
   
				
				if (before->node_1 == node_2 - 'A')
				{
   
   
					q = before->node_1_pointer;
					before->node_1_pointer = p;
					p->node_2_pointer = q;
				}
				else
				{
   
   
					q = before->node_2_pointer;
					before->node_2_pointer = p;
					p->node_2_pointer = q;
				}
				break;
			}
		}
		else//node_2 and now->node_1 equal 
		{
   
   
			if (node_1 - 'A' > now->node_2)
			{
   
   
				before = now;
				now = now->node_1_pointer;
			}
			else if (node_1 - 'A' < now->node_2)
			{
   
   
				if (before->node_1 == node_2-'A')
				{
   
   
					q = before->node_1_pointer;
					before->node_1_pointer = p;
					p->node_2_pointer = q;
				}
				else
				{
   
   
					q = before->node_2_pointer;
					before->node_2_pointer = p;
					p->node_2_pointer = q;
				}
				break;
			}
		}
	}
	if (!now)// There are two situations map->head[node_2 - 'A'].next Empty or to be inserted at the end of the list 
	{
   
   
		if (!before)
		{
   
   
			map->head[node_2 - 'A'].next = p;
		}
		else if (before->node_1 == node_2 - 'A')
		{
   
   
			before->node_1_pointer = p;
		}
		else if (before->node_2 == node_2 - 'A')
		{
   
   
			before->node_2_pointer = p;
		}
	}
}

void show(struct AMLGraph* map)
{
   
   
    int head_ele;
	struct Enode* p;
	for (int i = 0; i < map->vex; i++)
	{
   
   
		p = map->head[i].next;
		head_ele = map->head[i].head_ele - 'A';
		printf(" And %c The connected nodes are ：", head_ele+'A');
		while (p)
		{
   
   

			printf("%c ",( head_ele == p->node_1 ? (p->node_2 + 'A') :( p->node_1 + 'A')));//head_ele If it is equal to p->node_1 Just output another value 
			p = (head_ele == p->node_1 ?( p->node_1_pointer) : (p->node_2_pointer));//head_ele If it is equal to p->node_1 To get into p->node_1_pointer
		}
		printf("\n");
	}

}



int main()
{
   
   

	struct AMLGraph map;
	creat(&map);
	show(&map);
}

Look at two below vs2019 Run the results next

I also found a more complex diagram in the book to verify , The result is correct

If you don't understand, you can leave a message below , Make progress together ^ _ ^（ by the way , If a friend runs the program and finds bug Leave a comment below , I can modify ）