链式前向星封装版

类 - 链式前向星(封装)

by 橙之夏

Code

struct forstar
{
    vector<int> _h, _e, _ne, _w;
    int idx = 0;
    forstar(int n) // 初始化，n为容量
    {
        _h.resize(n + 1, -1), _e.resize(n + 1), _ne.resize(n + 1), _w.resize(n + 1);
    }
    void add(int a, int b, int c = 0)
    {
        _e[idx] = b, _w[idx] = c, _ne[idx] = _h[a], _h[a] = idx++;
    }
    int h(int idx) // 返回h[idx]
    {
        return _h[idx];
    }
    int to(int idx) // 返回e[idx]
    {
        return _e[idx];
    }
    int operator[](int idx) // 返回w[idx]
    {
        assert(~idx);
        return _w[idx];
    }
    void next(int &u) // next
    {
        u = _ne[u];
    }
};

接口以及成员函数

• forstar(int n)
  初始化一组链式前向星，n为容量(最大边的数量)

• void add(int a, int b, int c = 0)
  添加一条边，a为起点，b为终点，c为边权(可选)

• int h(int idx)
  返回h[idx]，即返回idx的链表头

• int to(int idx)
  返回e[idx]，即返回idx的终点

• int operator[](int idx)
  返回w[idx]，即返回idx的边权

• void next(int &u)
  让u指向下一个点

example:

signed main()
{
    forstar star(100); //初始化一个可以容纳100条边的链式前向星
    star.add(1,2); //从1向2添加一条有向边，默认边权为0
    star.add(2,3); //从2向3添加一条有向边，默认边权为0
    star.add(1,3,5); //从1向3添加一条边，边权为5
    star.add(1,4); //从1向4添加一条有向边，默认边权为0
    int i = star.h(1); // 定义 i 为节点1的链表头
    while(~i) // 如果i非空
    {
        cout << star.to(i) << " " << star[i] << endl;
        // 输出 i 指向的点以及边权
        star.next(i); //向后移动i指针
    }
}

VS Code 配置文件

将以下内容复制到你的配置文件中，即可使用该代码段

触发词: forstar

"链式前向星(封装版)": {
  "prefix": "forstar",
  "body": [
    "struct forstar",
    "{",
    "    vector<int> _h, _e, _ne, _w;",
    "    int idx = 0;",
    "    forstar(int n) // 初始化，n为容量",
    "    {",
    "        _h.resize(n + 1, -1), _e.resize(n + 1), _ne.resize(n + 1), _w.resize(n + 1);",
    "    }",
    "    void add(int a, int b, int c = 0)",
    "    {",
    "        _e[idx] = b, _w[idx] = c, _ne[idx] = _h[a], _h[a] = idx++;",
    "    }",
    "    int h(int idx) // 返回h[idx]",
    "    {",
    "        return _h[idx];",
    "    }",
    "    int to(int idx) // 返回e[idx]",
    "    {",
    "        return _e[idx];",
    "    }",
    "    int operator[](int idx) // 返回w[idx]",
    "    {",
    "        assert(~idx);",
    "        return _w[idx];",
    "    }",
    "    void next(int &u) // next",
    "    {",
    "        u = _ne[u];",
    "    }",
    "};"
  ],
  "description": "链式前向星(封装版)"
}