当前位置：首页 > 其他 > 手搓邻接表类代码注释与详解：从零开始理解图数据结构（适合新手小白）

手搓邻接表类代码注释与详解：从零开始理解图数据结构（适合新手小白）

3周前 (06-27)

一、简介和特点

邻接表是一种用于存储图（Graph）的数据结构，特别适合稀疏图（边数较少的图）。它通过链表的方式为每个节点维护其相邻节点的信息，既能高效节省空间，又能灵活支持图的动态操作。本文将基于您手写的C++邻接表类，通过代码注释与步骤解析，帮助新手小白理解其核心实现逻辑。

二、优点

1. 空间效率：相较于邻接矩阵（二维数组），邻接表在稀疏图中仅需存储实际存在的边，避免大量无效空间的浪费。

2. 动态扩展：支持节点和边的随时添加，无需提前确定图规模。

3. 操作灵活：通过链表快速定位节点的出边，便于实现深度/广度优先遍历等算法。

三、实现步骤

1. 定义边和节点的结构体：

edge：每条边包含指向下一节点的索引（nextnum）、边权值（data）和指向下一条边的指针（next）。

listnode：每个节点包含节点数据（data）和指向第一条边的指针（first）。

2. 构建图类（graph）：

使用节点数组（g）存储所有节点，节点数（n）记录当前节点数量。

提供两种构造函数：指定节点数初始化或默认初始化为1001个节点。

3. 添加边（addedge(head, tail, data)）：

从节点head指向节点tail，边权值为data。

若head节点无出边，直接创建第一条边；否则遍历链表找到末尾，添加新边。

4. 添加节点（addnode(k, data)）：

在索引k处创建新节点，存储数据data，并更新节点数。

5. 打印图结构（print()）：

遍历所有节点，输出节点数据及其所有出边的目标节点和权值。

四、代码和注释

#include <iostream>
using namespace std;

// 边结构体：存储指向下一节点的索引、边权值、指向下一条边的指针
struct edge {
    int nextnum;      // 下一节点的索引
    int data;         // 边权值（可根据需求修改类型）
    edge* next = nullptr;  // 指向下一条边的指针
};

// 节点结构体：存储节点数据、指向第一条边的指针
struct listnode {
    int data;          // 节点数据
    edge* first = nullptr;   // 指向第一条出边
};

// 图类：维护节点数组和节点数
class graph {
    listnode* g;        // 节点数组
    int n = 0;          // 当前节点数量

public:
    // 构造函数1：指定节点数初始化数组
    graph(int num) {
        g = new listnode[num];
    }

    // 构造函数2：默认初始化1001个节点
    graph() {
        g = new listnode[1001];
    }

    // 添加边方法
    void addedge(int head, int tail, int data) {
        // 获取head节点的第一条边
        edge* tmp = g[head].first;
        if (!tmp) {          // 若head无出边，创建第一条边
            g[head].first = new edge;
            g[head].first->data = data;
            g[head].first->nextnum = tail;
        } else {             // 若已有出边，遍历到末尾添加新边
            while (tmp->next) 
                tmp = tmp->next;
            tmp->next = new edge;
            tmp->next->data = data;
            tmp->next->nextnum = tail;
        }
    }

    // 添加节点方法
    void addnode(int k, int data) {
        g[k].data = data;       // 设置节点数据
        n++;                    // 更新节点数量
    }

    // 打印图结构方法
    void print() {
        for (int i = 0; i < n; i++) {  // 遍历所有节点
            cout << g[i].data << "->";   // 输出节点数据
            edge* tmp = g[i].first;     // 获取当前节点的第一条边
            while (tmp) {               // 遍历所有出边
                cout << tmp->nextnum << "(" << tmp->data << ") -> ";
                tmp = tmp->next;
            }
            cout << "null" << endl;      // 末尾标记
        }
    }
};