概念及介绍

首先邻接表一种图的存储结构，他是用来存储图的，接下来我将带大家手撕邻接表

依照上图，给大家解释一些名词：1的箭头指向下一个数值的时候，我们把箭头叫有向边或者叫节点，下一个数值，列如1->2的这个2我们叫他编号

1、存储方式

我们用结构体来存储

首先vertex是编号，也就是存储当前的编号，例如1->2,我们存储的2

next是节点，当我们存好了2的时候，假如要存储下一个的时候，我们要拉出来一个节点，为存储下一个编号做好准备，例如当前1->2(存好了)，再来出来一个节点，为下一个做好准备1->？

注意：不要多想，如果想到1->2,为什么不是2->3,就不要去想为什么是1拉开一个节点存储3？看看下面的添加代码会解开你的疑惑

typedef struct Node {
    int vertex;       
    //存储的是当前这条边指向的目标节点编号
    // 例如1->2，存储的是2
    // 例如：1指向2存的就是2，再来1指向3，存储的就是3
    struct Node* next;
    //指向同一个起始节点的下一条出边的节点。
    // 例如：1->2,1->3.1->4
    // ->就是节点
    // 起始节点1
    // 下一条出边：就是当前2存储了，下次要存3这个编号的节点
    // 例如；1—>2(现在存好了)，假设下一个要存1—>3,虽然没有存到3，但是已经拉出来了这个->节点为存3做出了准备
} Node;

2、添边

先申请一个结构体空间，申请失败就打印出问题

最后添边操作就是模拟（蓝色是申请新的结构体空间）

void add(int x, int y)
{
	Node* newNode = (Node*)malloc(sizeof(Node));//申请一个结构体空间
	if (newNode == NULL)
	{
		//如果申请失败就退出，并且打印出哪里的问题
		printf("malloc fail!");
		return;
	}
	//添边操作
	newNode->vertex = y;
	newNode->next = graph[x];
	graph[x] = newNode;
}

3、实现排序

排序就是先把链表转换成数组，然后数组转换成链表，直接把代码给你们看，我用的是y总的快排模板去排序的，也可以用冒泡等排序，自己喜欢

//快排模板
void quick_sort(int a[], int l, int r)
{
	if (l >= r)return;
	int key = a[l], i = l - 1, j = r + 1;
	while (i < j)
	{
		do {
			i++;
		} while (a[i] < key);
		do {
			j--;
		} while (a[j] > key);
		if (i < j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	quick_sort(a, l, j);
	quick_sort(a, j + 1, r);
}
//邻接表排序
void aListsort(int x)
{
	if (graph[x] == NULL)return;

	//链表转换为数组
	int a[N], idx = 0;
	Node* curr = graph[x];
	while (curr != NULL)
	{
		a[idx++] = curr->vertex;
		curr = curr->next;
	}

	//邻接表排序快排
	quick_sort(a, 0, idx - 1);

	//数组转换为链表
	curr = graph[x];
	for (int i = 0;i < idx;i++)
	{
		curr->vertex = a[i];
		curr = curr->next;
	}
}

4、打印显示结果查看

直接给看代码

//显示结果
void print(int x)
{
	if (graph[x] == NULL)return;
	Node* curr = graph[x];
	printf("%d: ", x);
	while (curr != NULL)
	{
		printf("%d->", curr->vertex);
		curr = curr->next;
	}
	printf("NULL\n");
}

展示所有代码

.h文件写的

#pragma once
#include <stdio.h>
#include <stdlib.h>

#define N 100005

typedef struct Node {
    int vertex;       
    //存储的是当前这条边指向的目标节点编号
    // 例如1->2，存储的是2
    // 例如：1指向2存的就是2，再来1指向3，存储的就是3
    struct Node* next;
    //指向同一个起始节点的下一条出边的节点。
    // 例如：1->2,1->3.1->4
    // ->就是节点
    // 起始节点1
    // 下一条出边：就是当前2存储了，下次要存3这个编号的节点
    // 例如；1—>2(现在存好了)，假设下一个要存1—>3,虽然没有存到3，但是已经拉出来了这个->节点为存3做出了准备
} Node;

extern Node* graph[N];

void add(int x, int y);
void aListsort(int x);
void print(int x);

.c文件

#include "aList.h"

Node* graph[N];

//添边
void add(int x, int y)
{
	Node* newNode = (Node*)malloc(sizeof(Node));//申请一个结构体空间
	if (newNode == NULL)
	{
		//如果申请失败就退出，并且打印出哪里的问题
		printf("malloc fail!");
		return;
	}
	//添边操作
	newNode->vertex = y;
	newNode->next = graph[x];
	graph[x] = newNode;
}

//快排模板
void quick_sort(int a[], int l, int r)
{
	if (l >= r)return;
	int key = a[l], i = l - 1, j = r + 1;
	while (i < j)
	{
		do {
			i++;
		} while (a[i] < key);
		do {
			j--;
		} while (a[j] > key);
		if (i < j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	quick_sort(a, l, j);
	quick_sort(a, j + 1, r);
}
//邻接表排序
void aListsort(int x)
{
	if (graph[x] == NULL)return;

	//链表转换为数组
	int a[N], idx = 0;
	Node* curr = graph[x];
	while (curr != NULL)
	{
		a[idx++] = curr->vertex;
		curr = curr->next;
	}

	//邻接表排序快排
	quick_sort(a, 0, idx - 1);

	//数组转换为链表
	curr = graph[x];
	for (int i = 0;i < idx;i++)
	{
		curr->vertex = a[i];
		curr = curr->next;
	}
}

//显示结果
void print(int x)
{
	if (graph[x] == NULL)return;
	Node* curr = graph[x];
	printf("%d: ", x);
	while (curr != NULL)
	{
		printf("%d->", curr->vertex);
		curr = curr->next;
	}
	printf("NULL\n");
}

最后测试.c

#include "aList.h"

Node* graph[N];
void test()
{
	int n, m;
	scanf_s("%d%d", &n, &m);
	//初始化
	for (int i = 1;i <= n;i++)
	{
		graph[i] = NULL;
	}
	while (m--)
	{
		int x, y;
		scanf_s("%d%d", &x, &y);
		add(x, y);
	}
	for (int i = 1;i <= n;i++)
	{
		aListsort(i);
	}
	for (int i = 1;i <= n;i++)
	{
		print(i);
	}
}
int main()
{
	test();
	return 0;
}

最后给大家的数据自己写完就测试一下对不对吧！

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8