邻接表
邻接表由第一数列的表头和每个表头对应连接的链表构成。每一个表头都是一个单链表表头。表头作为出发点，其链表内元素就是出发点可直接到达的目标点(也可以附加边权)。
图邻接表存储优势：
1、支持有向图无向图
2、支持带边权和不带边权
3、支持自环和重边
4、适合处理稀疏图
图邻接表存储缺陷：
相当于边表空间复杂度为o(n+m)m为边数。使用非常广泛的图的存储结构缺点很少QAQ。
测试数据：
34 412341 452 461 372 35
测试输出;
1-<7>->3-<5>->42-<5>->3-<6>->43-<5>->2-<7>->14-<6>->2-<5>->1<>内为边权
代码：
#include<iostream>#include<string>using namespace std;#define MAX_VERTEX_NUM 20#define ERROR -1typedef enum {DG, DN, UDG, UDN } GraphKind; //有向图、有向网、无向图、无向网typedef int Status;typedef string VertexType;// 图结点 typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置 ArcNode* nextarc; // 指向下一条弧的指针 int dis; // 边权}ArcNode, * ArcList;// 表头 typedef struct Vnode {VertexType data; // 顶点信息 ArcList firstarc; // 指向第一条依附该顶点弧的指针 }VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum; // 图的顶点树和弧数 int kind; // 图的种类 }ALGraph;Status InitFistarc(ArcList& A){A = (ArcList)malloc(sizeof(ArcNode));if (A == NULL)return ERROR;A->nextarc = NULL;return 1;}int Locate(VertexType ver, ALGraph G){for (int i = 0; i < G.vexnum; i++) {if (ver == G.vertices[i].data)return i;}return ERROR;}//头插法//图Status ArcInsert(ALGraph& G, int u, int v){ArcNode* newnode = (ArcNode*)malloc(sizeof(ArcNode));if (newnode == NULL)return ERROR;newnode->adjvex = v + 1;//因为Locate的到的下标从0开始newnode->nextarc = G.vertices[u].firstarc->nextarc;G.vertices[u].firstarc->nextarc = newnode;}//网Status ArcInsert(ALGraph& G, int u, int v, int w){ArcNode* newnode = (ArcNode*)malloc(sizeof(ArcNode));if (newnode == NULL)return ERROR;newnode->adjvex = v + 1;//因为Locate的到的下标从0开始newnode->dis = w;newnode->nextarc = G.vertices[u].firstarc->nextarc;G.vertices[u].firstarc->nextarc = newnode;}Status CreateDG(ALGraph& G)//有向图{cout << "请输入图的顶点数和弧数：\n";cin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {cout << "请输入第" << i + 1 << "个顶点的信息：\n";cin >> G.vertices[i].data;InitFistarc(G.vertices[i].firstarc);}//边信息VertexType u, v;for (int k = 0; k < G.arcnum; k++){cout << "请输入第" << k + 1 << "条边的信息（u,v）:\n";cin >> u >> v;int i = Locate(u, G), j = Locate(v, G);if (i == -1 || j == -1)return ERROR;//G.vertices[i].firstarc.if (!ArcInsert(G, i, j))return 0;}return 1;}Status CreateUDG(ALGraph& G)//无向图{cout << "请输入图的顶点数和弧数：\n";cin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {cout << "请输入第" << i + 1 << "个顶点的信息：\n";cin >> G.vertices[i].data;InitFistarc(G.vertices[i].firstarc);}//边信息VertexType u, v;for (int k = 0; k < G.arcnum; k++){cout << "请输入第" << k + 1 << "条边的信息（u,v）:\n";cin >> u >> v;int i = Locate(u, G), j = Locate(v, G);if (i == -1 || j == -1)return ERROR;//G.vertices[i].firstarc.if (!ArcInsert(G, i, j) || !ArcInsert(G, j, i))return 0;}return 1;}Status CreateDN(ALGraph& G)//有向网{cout << "请输入图的顶点数和弧数：\n";cin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {cout << "请输入第" << i + 1 << "个顶点的信息：\n";cin >> G.vertices[i].data;InitFistarc(G.vertices[i].firstarc);}//边信息VertexType u, v;for (int k = 0; k < G.arcnum; k++){cout << "请输入第" << k + 1 << "条边的信息（u,v）:\n";cin >> u >> v;int i = Locate(u, G), j = Locate(v, G);if (i == -1)return ERROR;//G.vertices[i].firstarc.int w;cout << "请输入权值信息（w）：\n";cin >> w;if (!ArcInsert(G, i, j, w))return 0;}return 1;}Status CreateUDN(ALGraph& G)//无向网{cout << "请输入图的顶点数和弧数：\n";cin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {cout << "请输入第" << i + 1 << "个顶点的信息：\n";cin >> G.vertices[i].data;InitFistarc(G.vertices[i].firstarc);//cout << InitFistarc(G.vertices[i].firstarc) << endl;}//边信息VertexType u, v;for (int k = 0; k < G.arcnum; k++){cout << "请输入第" << k + 1 << "条边的信息（u,v）:\n";cin >> u >> v;int i = Locate(u, G), j = Locate(v, G);if (i == -1 || j == -1)return ERROR;//G.vertices[i].firstarc.int w;cout << "请输入权值信息（w）：\n";cin >> w;if (!ArcInsert(G, i, j, w) || !ArcInsert(G, j, i, w))return 0;}return 1;}Status CreateGraph(ALGraph& G){cin >> G.kind;switch (G.kind){case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateUDN(G);default: return ERROR;}}//CreateGraphvoid TraveGraph(ALGraph G){for (int i = 0; i < G.vexnum ; i++) {cout << G.vertices[i].data;ArcNode* p = G.vertices[i].firstarc->nextarc;while (p != NULL) {if (G.kind == 1 || G.kind == 3) {cout << "-<" << p->dis << '>';}cout << "->" << p->adjvex;p = p->nextarc;}cout << endl;}cout << "<>内为边权" << endl;}int main(){ALGraph G;cout << "请输入要创建的图的类型（有向图 0、有向网 1、无向图 2、无向网 3）：\n";CreateGraph(G);TraveGraph(G);return 0;}
如果觉得《【数据结构/C语言版】邻接表存储》对你有帮助，请点赞、收藏，并留下你的观点哦！
