图的邻接表实现代解析【数据结构】
引言在图论中，图是一种重要的数据结构，用于表示对象之间的关系。邻接表是一种常用的图的存储方式，它通过链表来表示图中顶点之间的连接关系。本文将详细解析一段使用 C++ 实现的图的邻接表代码，资助读者明白实在现原理和使用方法。
代码实现
1. 头文件和宏界说
#include<iostream>
#define N 105
using namespace std;
[*]#include<iostream>：引入标准输入输出流库，用于程序中的输入输出操作。
[*]#define N 105：界说一个宏 N，表示图中顶点的最大数目为 105。
[*]using namespace std;：使用标准定名空间，方便后续使用标准库中的函数和对象。
2. 结构体界说
typedef struct node {
int date;
struct node* next;
}edg;
typedef struct nodea {
char date;
edg* firstedg;
}vhead;
typedef struct {
vhead adj;//存点
int n, m;//点数，边数
}Adj;
[*]edg 结构体：表示图中的边节点，包罗一个整数 date 用于存储边所指向的顶点编号，以及一个指向下一个边节点的指针 next。
[*]vhead 结构体：表示图中的顶点节点，包罗一个字符 date 用于存储顶点的数据，以及一个指向该顶点第一条边的指针 firstedg。
[*]Adj 结构体：表示整个图，包罗一个 vhead 范例的数组 adj 用于存储所有顶点，以及两个整数 n 和 m 分别表示图的顶点数和边数。
3. 图的创建函数 creatTu
void creatTu(Adj* g, int st)//图，是否为双向图
{
edg* p;
if (!st) cout << "无向图\n";
else cout << "有向图\n";
cin >> g->n;
for (int i = 1; i <= g->n; i++){
cin >> g->adj.date;//点
g->adj.firstedg = NULL;
}
cin >>g-> m;
for(int k=0;k<g->m;k++)
{
int i, j;
cin >> i >> j;//建立i->j;
p = (edg*)malloc(sizeof(edg));
p->date = j;
p->next=g->adj.firstedg;
g->adj.firstedg = p;
if (st)
{
p = (edg*)malloc(sizeof(edg));
swap(i, j);
p->date = j;
p->next = g->adj.firstedg;
g->adj.firstedg = p;
}
}
}
[*]该函数担当一个指向 Adj 结构体的指针 g 和一个整数 st，用于判断图是否为双向图。
[*]首先根据 st 的值输出图的范例信息。
[*]然后读取图的顶点数 g->n，并依次读取每个顶点的数据，同时将每个顶点的第一条边指针初始化为 NULL。
[*]接着读取图的边数 g->m，并循环读取每条边的起点 i 和尽头 j。
[*]对于每条边，创建一个新的边节点 p，将其 date 设为 j，并将其插入到起点 i 的邻接表头部。
[*]假如图是双向图（st 为真），则交换 i 和 j，再创建一个新的边节点并插入到 i 的邻接表头部。
4. 图的打印函数 print
void print(Adj* g)
{
edg* p;
for (int i = 1; i <= g->n; i++){
cout << g->adj.date<<" ";
p = g->adj.firstedg;
while (p != NULL){
//cout << "66";
cout << g->adj.date<<" ";
p = p->next;
}
cout << endl;
}
}
[*]该函数担当一个指向 Adj 结构体的指针 g，用于打印图的邻接表。
[*]遍历每个顶点，先输出该顶点的数据，然后遍历该顶点的邻接表，依次输出每个邻接顶点的数据。
5. 主函数 main
int main() {
Adj* T = (Adj*)malloc(sizeof(Adj));
creatTu(T, 0);
print(T);
return 0;
}
input:
3
a b c
4
1 2
1 3
2 3
3 2
运行结果如下：
https://i-blog.csdnimg.cn/direct/99468684c62c4beab7079e8f93a7d74f.png
[*]在主函数中，首先使用 malloc 动态分配一个 Adj 结构体的内存空间，并将其指针赋值给 T。
[*]然后调用 creatTu 函数创建一个无向图（st 为 0）。
[*]最后调用 print 函数打印图的邻接表。
总结
通过这段代码，我们可以看到如何使用邻接表来存储和表示图的结构。邻接表的优点是空间效率高，适合存储稀疏图。同时，我们也应该注意代码中的一些潜伏问题，如拼写错误、数组越界和内存管理等，以确保代码的精确性和健壮性。
希望本文的解析能够资助读者更好地明白图的邻接表实现，同时也为读者在现实应用中使用图数据结构提供一些参考。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]