详细解释相邻链表的构造 [表头插入法和表尾插入法
最编程
2024-06-11 12:49:20
...
这里要讲的邻接链表的构建是在练习ACM中的从常见的存储方式,方便图的存储与构建,并非是数据结构书中的那么复杂,但思想都是相同的。
大家都知道,临界链表的构建有两种,一种是头插法,一种是尾插法。尾插法会更容易理解。所以先讲下较难理解头插法。
头插法
头插法是用结构体数组来实现的。
具体的思路是:在建立邻接表时,记录的不是点而是边,对于每一个点所对应的邻接表都是以栈的形式存储的,也就是说先添加的边在遍历时后取出,除此以外,所有的边用一个结构体数组存储起来,每条边对应的索引就是其编号,在建立邻接表时,表中存放的实质是边的编号,在遍历时先获得编号,在放回结构体数组中获得相应的边的数据。
举例讲解
举例就仅仅讲解一下有向图的无权邻接链表的头插法,至于无向图或者是否有权和这个类似我就不再一一详解。
首先先看下面的一个树,假设每条路的方向都是向下的。
则头插法以后可以得到其头插法的存储形式
我们将其head,e.to,e.next
打印出来,就可以看出来他们之间的存储关系以及变量代表的含义。
- 如果想要找1节点所指向的节点。
- 先找到head[1]的值为编号3,然后查看e[3].to就是他的第一个节点也就是4节点,next的代表下一个的编号也就是2。
- 然后查e[2].to就是他的第二个节点也就是3,同样找到2,当找到-1时表示已经查找完了。
- 查找完以后查看一下上面的存储形式是不是和那个一样,接着自己试试找一下2的节点。
如果不太理解就看代码部分吧
无权值有向图的邻接链表
#include<iostream>
#include<string.h>
#define Size 1000
using namespace std;
struct Edge//边的结构体
{
int to;//边所连接的点
int next;//在栈中的底下一条边的编号
}e[Size << 1];//Size是边的最大数目,当图为无向图时,对一条边的两个端点建立邻接表时,
//均会记录该边,因此,同一条边会被记录两次
int cnt = 0;//用来确定当前边的编号
int head[Size << 1];//Size是点的最大数目,该数组用来存放每一个点在建立邻接表时,栈顶的边的编号
int n, m;
void addEdge(int u, int v)//在u点的邻接表中加入一条边,也就是在栈顶加入一条边
{
e[++ cnt].to = v;
e[cnt].next = head[u];//在u顶点的邻接表这个栈的顶部加入一条边(头插法)
head[u] = cnt;//top为加入边的编号,加入后要更新head,使得head记录邻接表栈顶边的编号
}
/*void bfs()//遍历邻接表
{
for(int i = 1; i <= n; i++)//遍历所有点
{
for(int j = head[i]; j != -1; j = e[j].next)//j=head[i]:获取当前点邻接表的栈顶的边的编号
{ //j=e[j].next:获取栈中底下一条边的编号,j==-1表示遍历完
//操作
}
}
} */
void init()
{
int u, v;
cin >> n >> m;
//初始化
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i ++)
{
e[i].to = 0;
e[i].next = 0;
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v;
addEdge(u,v);
}
}
无权值无向图的邻接链表
#include<iostream>
#include<string.h>
#define Size 1000
using namespace std;
struct Edge//边的结构体
{
int to;//边所连接的点
int next;//在栈中的底下一条边的编号
}e[Size << 1];//Size是边的最大数目,当图为无向图时,对一条边的两个端点建立邻接表时,
//均会记录该边,因此,同一条边会被记录两次
int cnt = 0;//用来确定当前边的编号
int head[Size << 1];//Size是点的最大数目,该数组用来存放每一个点在建立邻接表时,栈顶的边的编号
int n, m;
void addEdge(int u, int v)//在u点的邻接表中加入一条边,也就是在栈顶加入一条边
{
e[++ cnt].to = v;
e[cnt].next = head[u];//在u顶点的邻接表这个栈的顶部加入一条边(头插法)
head[u] = cnt;//top为加入边的编号,加入后要更新head,使得head记录邻接表栈顶边的编号
}
/*void bfs()//遍历邻接表
{
for(int i = 1; i <= n; i++)//遍历所有点
{
for(int j = head[i]; j != -1; j = e[j].next)//j=head[i]:获取当前点邻接表的栈顶的边的编号
{ //j=e[j].next:获取栈中底下一条边的编号,j==-1表示遍历完
//操作
}
}
} */
void init()
{
int u, v;
cin >> n >> m;
//初始化
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i ++)
{
e[i].to = 0;
e[i].next = 0;
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v;
addEdge(u,v);
addEdge(v,u);
}
}
带权值有向图的邻接链表
#include<iostream>
#include<string.h>
#define Size 1000
using namespace std;
struct Edge//边的结构体
{
int to;//边所连接的点
int w;
int next;//在栈中的底下一条边的编号
}e[Size << 1];//Size是边的最大数目,当图为无向图时,对一条边的两个端点建立邻接表时,
//均会记录该边,因此,同一条边会被记录两次
int cnt = 0;//用来确定当前边的编号
int head[Size << 1];//Size是点的最大数目,该数组用来存放每一个点在建立邻接表时,栈顶的边的编号
int n, m;
void addEdge(int u, int v, int w)//在u点的邻接表中加入一条边,也就是在栈顶加入一条边
{
e[++ cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];//在u顶点的邻接表这个栈的顶部加入一条边(头插法)
head[u] = cnt;//top为加入边的编号,加入后要更新head,使得head记录邻接表栈顶边的编号
}
/*void bfs()//遍历邻接表
{
for(int i = 1; i <= n; i++)//遍历所有点
{
for(int j = head[i]; j != -1; j = e[j].next)//j=head[i]:获取当前点邻接表的栈顶的边的编号
{ //j=e[j].next:获取栈中底下一条边的编号,j==-1表示遍历完
//操作
}
}
} */
void init()
{
int u, v, w;
cin >> n >> m;
//初始化
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i ++)
{
e[i].to = 0;
e[i].next = 0;
e[i].w = 0;
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v >> w;
addEdge(u, v, w);
}
}
带权值无向图的邻接链表
#include<iostream>
#include<string.h>
#define Size 1000
using namespace std;
struct Edge//边的结构体
{
int to;//边所连接的点
int w;
int next;//在栈中的底下一条边的编号
}e[Size << 1];//Size是边的最大数目,当图为无向图时,对一条边的两个端点建立邻接表时,
//均会记录该边,因此,同一条边会被记录两次
int cnt = 0;//用来确定当前边的编号
int head[Size << 1];//Size是点的最大数目,该数组用来存放每一个点在建立邻接表时,栈顶的边的编号
int n, m;
void addEdge(int u, int v, int w)//在u点的邻接表中加入一条边,也就是在栈顶加入一条边
{
e[++ cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];//在u顶点的邻接表这个栈的顶部加入一条边(头插法)
head[u] = cnt;//top为加入边的编号,加入后要更新head,使得head记录邻接表栈顶边的编号
}
/*void bfs()//遍历邻接表
{
for(int i = 1; i <= n; i++)//遍历所有点
{
for(int j = head[i]; j != -1; j = e[j].next)//j=head[i]:获取当前点邻接表的栈顶的边的编号
{ //j=e[j].next:获取栈中底下一条边的编号,j==-1表示遍历完
//操作
}
}
} */
void init()
{
int u, v, w;
cin >> n >> m;
//初始化
memset(head, -1, sizeof(head));
for(int i = 1; i <= n; i ++)
{
e[i].to = 0;
e[i].next = 0;
e[i].w = 0;
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v >> w;
addEdge(u, v, w);
addEdge(v, u, w);
}
}
最后说一点在添加节点过程中,可以有以下两种形式
//形式1
void addEdge(int u, int v, int w)
{
e[++ cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
//形式2
void addEdge(int u, int v, int w)
{
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt ++;
}
其中区别并不大,只是形式1的情况,head的下标就是从1开始,对应的e的下表也是从1开始的,而形式2的情况,他们的下表都是从0开始的。
尾插法
尾插法的思想很简单就是找到一个u到v的点,就把v给push_back到u后面,尾插法需要用到STL中的容器,动态数组vector。
无权值无向图的邻接链表
#include<iostream>
#include<cstdio>
#include<vector>
#define Size 1000
using namespace std;
vector<int> linked[Size];
int n, m; //n代表节点个数,m代表边的条数
void init()
{
cin >> n >> m;
int u, v; //u 边的起点,v边的终点
for(int i = 1; i <= n; i ++) //初始化
{
linked[i].clear();
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v;
linked[u].push_back(v);
linked[v].push_back(u);
}
}
无权值有向图的邻接链表
#include<iostream>
#include<cstdio>
#include<vector>
#define Size 1000
using namespace std;
vector<int> linked[Size];
int n, m; //n代表节点个数,m代表边的条数
void init()
{
cin >> n >> m;
int u, v; //u 边的起点,v边的终点
for(int i = 1; i <= n; i ++) //初始化
{
linked[i].clear();
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v;
linked[u].push_back(v);
}
}
有权值无向图的邻接链表
#include<iostream>
#include<vector>
#define Size 1000
using namespace std;
struct Edge
{
int v,w;
};
Edge temp;
int n, m;
vector<Edge> linked[Size];
void init()
{
cin >> n >> m;
int u, v, w;
for(int i = 1; i <= n; i ++)
{
linked[i].clear();
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v >> w;
temp.v = v;
temp.w = w;
linked[u].push_back(temp);
temp.v = u;
linked[v].push_back(temp);
}
}
有权值有向图的邻接链表
#include<iostream>
#include<vector>
#define Size 1000
using namespace std;
struct Edge
{
int v,w;
};
Edge temp;
int n, m;
vector<Edge> linked[Size];
void init()
{
cin >> n >> m;
int u, v, w;
for(int i = 1; i <= n; i ++)
{
linked[i].clear();
}
for(int i = 1; i <= m; i ++)
{
cin >> u >> v >> w;
temp.v = v;
temp.w = w;
linked[u].push_back(temp);
}
}
推荐阅读
-
链表学习:链表表头插入法和表尾插入法以及 HashMap 中的链表节点插入法
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
数据结构:逆转单向链表的表头插入法(附原理解释和代码实现)
-
详细解释相邻链表的构造 [表头插入法和表尾插入法
-
单链表的表头插入法和表尾插入法详解与实现 (C) [简单易懂]