【数据结构】邻接表的3种常用表示方式——C++描述

指针表示法

struct ArcNode  //定义边表结点
{
    int adjvex； //邻接点域
    ArcNode* next;
};

struct VertexNode   //定义顶点表结点
{
    int vertex;
    ArcNode* firstedge;
};

//头插法
void add(int from,int to)
{
    s = new ArcNode;
    s->adjvex = to;
    s->next = adjlist[i].firstedge;
    adjlist[from].firstedge = s;
}

vector表示法

vector<int> v[MAXN];

void add(int x,int y)
{
    v[x].push_back(y);
}

数组表示法

int head[MAXN]; //初始化为-1
int h = 0;
struct Edge
{
    int to;
    int next;
};

Edge e[MAXN<<1]；

void add(int x,int y)
{
    e[h].to = y;
    e[h].next = head[x];
    head[x] = h++;
}

三种方法的简单比较

1. 指针结构清晰，占用空间小，但是指针操作容易出错。
2. vector简单明了，但仅限于顶点编号为1~N的情况，而且储存的信息量少，此外，如果数据量比较大，vector的操作会比较费时间。
3. 数组表示法，实际上是模拟指针来实现的，既摆脱了令人头晕的指针，又有占用空间小、速度快的优势，强烈推荐！