数据结构之邻接表存储图 发表于 2019-05-06 | 更新于 2019-05-20 | 分类于 数据结构 | 阅读次数: 用邻接表存图适合稀疏图,不会浪费太多空间。写的时候一定要思路清晰,点和边的结构体存储要明确他们都包含什么内容。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <bits/stdc++.h>using namespace std;typedef struct Arcnode{ int vertex,data; //这条边的终点 以及权值 struct Arcnode *nextArc; //与这条边同起点的下一条边}Arcnode;typedef struct vernode{ int data; //顶点数据 Arcnode *nextArc; // 以该点为起点的边}vernode;typedef struct { vernode vertex[1001]; int vernum,arcnum;}Graph;int locate(Graph G, int x){ for(int i = 1 ; i <= G.vernum; ++i) { if(G.vertex[i].data == x) { return i; } }}void create(Graph &G){ int a,b,w; cin >> G.vernum >> G.arcnum; for(int i = 1; i <= G.vernum ; ++i) { cin >> G.vertex[i].data; G.vertex[i].nextArc = NULL; } for(int i = 1; i <= G.arcnum; ++i) { cin >> a >> b >> w; int A = locate(G,a); int B = locate(G,b); Arcnode *p,*p1; p = new Arcnode; //!!!这一步总是忘记 p -> vertex = B; p -> nextArc = G.vertex[A].nextArc; p -> data = w; G.vertex[A].nextArc = p; p = new Arcnode; p -> vertex = A; p -> nextArc = G.vertex[B].nextArc; p -> data = w; G.vertex[B].nextArc = p; }}int main(){ Graph G; create(G); Arcnode *p; for(int i = 1; i <= G.vernum; ++i){ p = G.vertex[i].nextArc; while(p != NULL) { cout << p -> data << ' ' << p -> vertex << '\n'; p = p -> nextArc; } cout << '\n'; }} 打赏