C语言，邻接矩阵，邻接表，十字链表，邻接多重表及其基本操作的实现

待我称王封你为后i 2023-05-29 03:43 17阅读 0赞

###        最近复习考研遇到了图的问题，发现自己对这一块的数据结构不怎么熟悉，于是自己全部手写了一遍。我写的可能和一些官方标准不太一样(毕竟教材上也没有非常明确的官方标准)，但基本思路是一样的，自己测试的一些数据也没有问题，如果谁发现了问题欢迎指出。 ###

###        图一共有四个基本存储结构，分别是邻接矩阵，邻接表，十字链表，邻接多重表。它们各有各自的特点，我将这四个存储结构全部实现了一遍，并针对每个结构都实现了以下11个基本功能： ###

1.  初始化
2.  插入顶点
3.  删除顶点
4.  插入边(弧)
5.  删除边(弧)
6.  判断a，b两点是否联通
7.  列出所有与顶点a邻接的边
8.  返回顶点a的第一个邻接点的顶点号
9.  假设顶点b是顶点a的一个邻接点，返回除b之外顶点a的下一个邻接点的顶点号
10. 获取边(a,b)或弧<a,b>的权值
11. 设置边(a,b)或弧<a,b>的权值

# 邻接矩阵（有向） #

struct AdjacencyMatrix//邻接矩阵
    {
    	int inf = 0x3f3f3f3f;//设一个无穷大用来表示不连通的弧的权值
    	int V_num;//顶点数量
    	int V_max;//顶点最大ID
    	bool V[105];//V[i]表示顶点i是否存在
    	int MA[105][105];//图矩阵
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		memset(V, false, sizeof(V));
    		memset(MA, 0x3f, sizeof(MA));
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a])
    		{
    			V[a] = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a])
    			return;
    		for (int i = 0; i <= V_max; i++)//同时将该顶点的弧删除，即权值设为无穷大
    		{
    			MA[i][a] = inf;
    			MA[a][i] = inf;
    		}
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i])
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a] = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入弧
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		MA[a][b] = weight;
    	}
    	void remove_edge(int a, int b)//删除弧
    	{
    		MA[a][b] = inf;
    	}
    	bool adjacent(int a, int b)//判断a,b是否连通
    	{
    		if (MA[a][b] < inf)
    			return true;
    		else
    			return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的弧
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a,i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点，没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点，没有则返回-1
    	{
    		for (int i = b+1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取a到b的弧的权值
    	{
    		return MA[a][b];
    	}
    	void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
    	{
    		MA[a][b] = v;
    	}
    };

# 邻接表（有向） #

struct AdjacencyArcNode//邻接表的弧结点
    {
    	int weight;//该弧的权重
    	int destination;//该弧的弧头
    	struct AdjacencyArcNode* next;//指向下一条邻接弧
    };
    
    struct AdjacencyVNode//邻接表的顶点表
    {
    	bool exist;//表示顶点是否存在
    	struct AdjacencyArcNode* first;//弧表头指针
    	void delete_edge(int a)//删除该顶点对应的边表中到点a的弧
    	{
    		struct AdjacencyArcNode* last;
    		struct AdjacencyArcNode* p = first;
    		if (p->destination == a)
    		{
    			first = p->next;
    			free(p);
    		}
    		last = p;
    		p = p->next;
    		while (p->destination!=a)
    		{
    			last = p;
    			p = p->next;
    			if (p == NULL)
    				return;
    		}
    		last->next = p->next;
    		free(p);
    	}
    	void clear(struct AdjacencyArcNode* p)//清空该顶点的弧表
    	{
    		if (p->next != NULL)
    			clear(p->next);
    		free(p);
    	}
    	void append_edge(int a,int v)//给该顶点添加一条弧
    	{
    		struct AdjacencyArcNode* n = (AdjacencyArcNode*)malloc(sizeof(AdjacencyArcNode));
    		struct AdjacencyArcNode* p = first;
    		n->destination = a;
    		n->next = NULL;
    		n->weight = v;
    		if (p == NULL)
    		{
    			first = n;
    			return;
    		}
    		while (p->next != NULL)
    			p = p->next;
    		p->next = n;
    	}
    };
    
    struct AdjacencyList
    {
    	int V_num;//顶点数量
    	int V_max;//顶点最大ID
    	AdjacencyVNode V[105];//顶点表
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		for (int i = 0; i < 105; i++)
    		{
    			V[i].exist = false;
    			V[i].first = NULL;
    		}
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a].exist)
    		{
    			V[a].exist = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a].exist)
    			return;
    		AdjacencyArcNode* p, *p1, *p2;
    		p = V[a].first;
    		while (p!=NULL)//删除别的顶点中包含该顶点的弧
    		{
    			V[p->destination].delete_edge(a);
    			p = p->next;
    		}
    		V[a].clear(V[a].first);//删除该顶点自己的弧
    		V[a].exist = false;
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i].exist)
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a].exist = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入弧
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		V[a].append_edge(b, weight);
    	}
    	void remove_edge(int a, int b)//删除弧
    	{
    		V[a].delete_edge(b);
    	}
    	bool adjacent(int a, int b)//判断a,b是否联通
    	{
    		AdjacencyArcNode* p = V[a].first;
    		while (p!=NULL)
    		{
    			if (p->destination == b)
    				return true;
    			p = p->next;
    		}
    		return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的弧
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点，没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点，没有则返回-1
    	{
    		for (int i = b + 1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取a到b的弧的权值
    	{
    		AdjacencyArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->destination == b)
    				return p->weight;
    			p = p->next;
    		}
    		return -1;
    	}
    	void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
    	{
    		AdjacencyArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->destination == b)
    			{
    				p->weight = v;
    				break;
    			}
    			p = p->next;
    		}
    	}
    };

# 十字链表（有向） #

struct OrthogonalArcNode//十字链表的弧结点
    {
    	int weight;//该弧的权重
    	int tailvex;//该弧的尾部
    	int headvex;//该弧的头部
    	struct OrthogonalArcNode* tailnext;//下一个尾部与该弧尾部相同的弧
    	struct OrthogonalArcNode* headnext;//下一个头部与该弧头部相同的弧
    };
    
    struct OrthogonalVNode//十字链表的顶点结点
    {
    	bool exist;//该顶点是否存在
    	struct OrthogonalArcNode* tailfirst;//以该点为尾的弧
    	struct OrthogonalArcNode* headfirst;//以该点为头的弧
    	void delete_edge_to(int a)//删除从该点到a点的弧
    	{
    		struct OrthogonalArcNode* last;
    		struct OrthogonalArcNode* p = tailfirst;
    		if (p->headvex == a)
    		{
    			tailfirst = p->tailnext;
    			return;
    		}
    		last = p;
    		p = p->tailnext;
    		while (p->headvex != a)
    		{
    			last = p;
    			p = p->tailnext;
    			if (p == NULL)
    				return;
    		}
    		last->tailnext = p->tailnext;
    	}
    	void delete_edge_from(int a)//删除从a点到该点的弧
    	{
    		struct OrthogonalArcNode* last;
    		struct OrthogonalArcNode* p = headfirst;
    		if (p->tailvex == a)
    		{
    			headfirst = p->headnext;
    			return;
    		}
    		last = p;
    		p = p->headnext;
    		while (p->tailvex != a)
    		{
    			last = p;
    			p = p->headnext;
    			if (p == NULL)
    				return;
    		}
    		last->headnext = p->headnext;
    	}
    	void append_to(OrthogonalArcNode* a)//增加从该点到a点的弧
    	{
    		OrthogonalArcNode* p = tailfirst;
    		if (p == NULL)
    		{
    			tailfirst = a;
    			return;
    		}
    		while (p->tailnext!=NULL)
    			p = p->tailnext;
    		p->tailnext = a;
    		return;
    	}
    	void append_from(OrthogonalArcNode* a)//增加从a点到该点的弧
    	{
    		OrthogonalArcNode* p = headfirst;
    		if (p == NULL)
    		{
    			headfirst = a;
    			return;
    		}
    		while (p->headnext != NULL)
    			p = p->headnext;
    		p->headnext = a;
    		return;
    	}
    };
    
    struct OrthogonalList//十字链表
    {
    	int V_num;//顶点数目
    	int V_max;//顶点最大ID
    	OrthogonalVNode V[105];//顶点表
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		for (int i = 0; i < 105; i++)
    		{
    			V[i].exist = false;
    			V[i].headfirst = NULL;
    			V[i].tailfirst = NULL;
    		}
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a].exist)
    		{
    			V[a].exist = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a].exist)
    			return;
    		OrthogonalArcNode* p;
    		p = V[a].tailfirst;
    		while (p != NULL)//删除以该点为弧尾的弧
    		{
    			V[p->headvex].delete_edge_from(a);
    			V[a].delete_edge_to(p->headvex);
    			p = p->tailnext;
    		}
    		p = V[a].headfirst;
    		while (p != NULL)//删除以该点为弧头的弧
    		{
    			V[p->tailvex].delete_edge_to(a);
    			V[a].delete_edge_from(p->tailvex);
    			p = p->headnext;
    		}
    		V[a].exist = false;
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i].exist)
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a].exist = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入弧
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		OrthogonalArcNode* p = (OrthogonalArcNode*)malloc(sizeof(OrthogonalArcNode));
    		p->tailvex = a;
    		p->headvex = b;
    		p->weight = weight;
    		p->headnext = NULL;
    		p->tailnext = NULL;
    		V[a].append_to(p);
    		V[b].append_from(p);
    	}
    	void remove_edge(int a, int b)//删除弧
    	{
    		V[a].delete_edge_to(b);
    		V[b].delete_edge_from(a);
    	}
    	bool adjacent(int a, int b)//判断a,b是否联通
    	{
    		OrthogonalArcNode* p = V[a].tailfirst;
    		while (p != NULL)
    		{
    			if (p->headvex == b)
    				return true;
    			p = p->tailnext;
    		}
    		return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的弧
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点，没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点，没有则返回-1
    	{
    		for (int i = b + 1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取a到b的弧的权值
    	{
    		OrthogonalArcNode* p = V[a].tailfirst;
    		while (p != NULL)
    		{
    			if (p->headvex == b)
    				return p->weight;
    			p = p->tailnext;
    		}
    		return -1;
    	}
    	void set_edge_value(int a, int b, int v)//设定a到b的弧的权值
    	{
    		OrthogonalArcNode* p = V[a].tailfirst;
    		while (p != NULL)
    		{
    			if (p->headvex == b)
    			{
    				p->weight = v;
    				break;
    			}
    			p = p->tailnext;
    		}
    	}
    };

# 邻接多重表（无向） #

struct AdjacencyMultilistArcNode//邻接多重表的边结点
    {
    	bool mark;//标志域
    	int weight;//该边的权重
    	int Avex;//该边依附的一个顶点A
    	int Bvex;//该边依附的另一个顶点B
    	struct AdjacencyMultilistArcNode* Anext;//指向下一条依附于顶点A的边
    	struct AdjacencyMultilistArcNode* Bnext;//指向下一条依附于顶点B的边
    };
    
    struct AdjacencyMultilistVNode//邻接多重表的顶点结点
    {
    	int id;//该顶点的编号
    	bool exist;//该顶点是否存在
    	struct AdjacencyMultilistArcNode* first;//该顶点的边表
    	void delete_edge(int a)//从该顶点的边表中删除与a相连的边
    	{
    		bool lastvex;//Avex:true Bvex:false
    		struct AdjacencyMultilistArcNode* last;
    		struct AdjacencyMultilistArcNode* p = first;
    		if (p->Avex == id)
    		{
    			if (p->Bvex == a)
    			{
    				first = p->Anext;
    				return;
    			}
    			lastvex = true;
    			last = p;
    			p = p->Anext;
    		}
    		else
    		{
    			if (p->Avex == a)
    			{
    				first = p->Bnext;
    				return;
    			}
    			lastvex = false;
    			last = p;
    			p = p->Bnext;
    		}
    		while (p != NULL)
    		{
    			if (p->Bvex != a && p->Avex == id)
    			{
    				last = p;
    				lastvex = true;
    				p = p->Anext;
    			}
    			else if (p->Avex != a && p->Bvex == id)
    			{
    				last = p;
    				lastvex = false;
    				p = p->Bnext;
    			}
    			else if (p->Avex == a && p->Bvex == id)
    			{
    				if (lastvex)
    					last->Anext = p->Bnext;
    				else
    					last->Bnext = p->Bnext;
    				return;
    			}
    			else if (p->Bvex == a && p->Avex == id)
    			{
    				if (lastvex)
    					last->Anext = p->Anext;
    				else
    					last->Bnext = p->Anext;
    				return;
    			}
    		}
    	}
    	void append(AdjacencyMultilistArcNode* a)//添加该点与点a的一条边
    	{
    		struct AdjacencyMultilistArcNode* p = first;
    		if (p == NULL)
    		{
    			first = a;
    			return;
    		}
    		while (p!=NULL)
    		{
    			if (p->Avex == id)
    			{
    				if (p->Anext == NULL)
    				{
    					p->Anext = a;
    					return;
    				}
    				p = p->Anext;
    			}
    			else
    			{
    				if (p->Bnext == NULL)
    				{
    					p->Bnext = a;
    					return;
    				}
    				p = p->Bnext;
    			}
    		}
    	}
    };
    
    struct AdjacencyMultilist//邻接多重表
    {
    	int V_num;//顶点数目
    	int V_max;//顶点最大ID
    	AdjacencyMultilistVNode V[105];//顶点表
    	void init()//初始化
    	{
    		V_num = 0;
    		V_max = 0;
    		for (int i = 0; i < 105; i++)
    		{
    			V[i].exist = false;
    			V[i].first = NULL;
    			V[i].id = i;
    		}
    	}
    	void insert_vertex(int a)//插入顶点
    	{
    		if (a > V_max)
    			V_max = a;
    		if (!V[a].exist)
    		{
    			V[a].exist = true;
    			V_num++;
    		}
    	}
    	void delete_vertex(int a)//删除顶点
    	{
    		if (!V[a].exist)
    			return;
    		AdjacencyMultilistArcNode* p;
    		p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == a)
    			{
    				V[a].delete_edge(p->Bvex);
    				V[p->Bvex].delete_edge(a);
    				p = p->Anext;
    			}
    			else
    			{
    				V[a].delete_edge(p->Avex);
    				V[p->Avex].delete_edge(a);
    				p = p->Bnext;
    			}
    		}
    		V[a].exist = false;
    		if (a == V_max)
    		{
    			for (int i = V_max - 1; i >= 0; i--)
    				if (V[i].exist)
    				{
    					V_max = i;
    					break;
    				}
    			if (V_max == a)
    				V_max = 0;
    		}
    		V[a].exist = false;
    		V_num--;
    	}
    	void add_edge(int a, int b, int weight)//插入一条边
    	{
    		insert_vertex(a);
    		insert_vertex(b);
    		AdjacencyMultilistArcNode* p = (AdjacencyMultilistArcNode*)malloc(sizeof(AdjacencyMultilistArcNode));
    		p->Avex = a;
    		p->Bvex = b;
    		p->weight = weight;
    		p->Anext = NULL;
    		p->Bnext = NULL;
    		V[a].append(p);
    		V[b].append(p);
    	}
    	void remove_edge(int a, int b)//删除一条边
    	{
    		V[a].delete_edge(b);
    		V[b].delete_edge(a);
    	}
    	bool adjacent(int a, int b)//判断a,b是否联通
    	{
    		if (a == b)
    			return false;
    		AdjacencyMultilistArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == b || p->Bvex == b)
    				return true;
    			if (p->Avex == a)
    				p = p->Anext;
    			else
    				p = p->Bnext;
    		}
    		return false;
    	}
    	void neighbors(int a)//列出所有与a邻接的边
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				printf("%d---%d\n", a, i);
    	}
    	int first_neighbor(int a)//返回顶点a的第一个邻接点，没有则返回-1
    	{
    		for (int i = 0; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int next_neighbor(int a, int b)//返回顶点a的在b之后的下一个邻接点，没有则返回-1
    	{
    		for (int i = b + 1; i <= V_max; i++)
    			if (adjacent(a, i))
    				return i;
    		return -1;
    	}
    	int get_edge_value(int a, int b)//获取边(a,b)的权值
    	{
    		AdjacencyMultilistArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == b || p->Bvex == b)
    				return p->weight;
    			if (p->Avex == a)
    				p = p->Anext;
    			else
    				p = p->Bnext;
    		}
    		return -1;
    	}
    	void set_edge_value(int a, int b, int v)//设定边(a,b)的权值
    	{
    		AdjacencyMultilistArcNode* p = V[a].first;
    		while (p != NULL)
    		{
    			if (p->Avex == b || p->Bvex == b)
    			{
    				p->weight = v;
    				break;
    			}
    			if (p->Avex == a)
    				p = p->Anext;
    			else
    				p = p->Bnext;
    		}
    	}
    };