第一种:
#include <iostream> #include <fstream> #include <string> #include <sstream> #include <stdio.h> using namespace std; const int numNodes = 10; typedef struct node//这个点j就是表示一个点i的邻接点,adj表示这个点j的位置,next指向点i的下一个邻接点,i--->j { int adj;// struct node *next; int w; }node,*pnode; node Nodes[numNodes]; void CreatNode(int s,int t,int w)//s--->t { /*pnode pn = &Nodes[s]; while(pn->next!=NULL)//找到最后一个邻接点 pn = pn->next; pn->next = (pnode)malloc(sizeof(node)); pn->next->adj = t; pn->next->next = NULL; pn->next->w = w;*/
//以上做法是在连接表的最后添加结点,没有必要,可以像方法二一样做,每次都是把新结点放在头结点的后面
}
void del(pnode p) { if(p == NULL) return; pnode next = p->next; if(next!=NULL) del(next); free(p); } int main() { int n,m; while (scanf("%d%d",&n,&m)!=EOF) { for (int i=1;i<=n;++i) Nodes[i].next = NULL; cout<<endl; if(n==0 && m ==0) break; for (int i=0;i<m;++i) { int s,t,w; scanf("%d%d%d",&s,&t,&w); CreatNode(s,t,w); CreatNode(t,s,w); } for (int i=1;i<=n;++i)//数组Nodes的元素作为头结点,不放入值,真正的结点是 Nodes[i].next { cout<<i<<"-->"; pnode p = Nodes[i].next; while (p!=NULL) { cout<<p->adj<<" "<<p->w<<";"; p = p->next; } cout<<endl; } for (int i=1;i<=n;++i) { del(Nodes[i].next); } } return 0; }
数组内的元素是空元素,不代表任何结点
第二种方法:
typedef struct Arc { int adj;//边所指向的点的id struct Arc * nextArc; int w; }Arc; typedef struct Node { Arc *firstArc; }Node,AdjList[numNodes]; typedef struct Graph { AdjList vertices; }Graph; Graph g; void CreatNode(int s,int t,int w) { Arc *arc = (Arc *)malloc(sizeof(Arc)); arc->adj = t; arc->w = w; arc->nextArc = g.vertices[s].firstArc; g.vertices[s].firstArc = arc; } void del(Arc *p) { if(p==NULL) return; if(p!=NULL) del(p->nextArc); free(p); } int main() { int n,m; while (scanf("%d%d",&n,&m)!=EOF) { for (int i=1;i<=n;++i) g.vertices[i].firstArc = NULL; cout<<endl; if(n==0 && m ==0) break; for (int i=0;i<m;++i) { int s,t,w; scanf("%d%d%d",&s,&t,&w); CreatNode(s,t,w); CreatNode(t,s,w); } for (int i=1;i<=n;++i)// { cout<<i<<"-->"; Arc * p = g.vertices[i].firstArc; while (p!=NULL) { cout<<p->adj<<" "<<p->w<<";"; p = p->nextArc; } cout<<endl; } for (int i=1;i<=n;++i) { del(g.vertices[i].firstArc); } } return 0; }
第三种:
typedef struct { int to; int w; int next; }Edge; Edge e[MAX]; int pre[MAX]; //初始化 memset(pre,-1,sizeof(pre)); //输入 scanf("%d %d %d",&from,&to,&w1); e[i].to = to; e[i].w = w1; e[i].next = pre[from]; pre[from] = i; i++;
上面这段代码中,边的结构体Edge由三个元素组成:弧头结点序号,边权值,下一条边的序号。e[i]指的是第i条边。pre[i]记录的是从当前输入的情况来看,序号为i的弧尾结点发出的第一条边的序号是pre[i]。
这样,在操作某个结点发出的边时,可以像这么做:
/*now为弧尾结点序号,i为now所发出的边序号,adj为弧头结点序号,w为now-->adj这条边的权值*/ for(i = pre[now]; i != -1; i = edge[i].next) { int adj = edge[i].to; int w = edge[i].w; //do something... }
其实,对于哈希表这类的存储结构(链表法解决冲突),与图的邻接表类似,也可以用类似的表示方法:
typedef struct { char e[11]; //value char f[11]; //key int next; //下一个结果(hash冲突) }Entry; Entry entry[M]; int hashIndex[M]; //哈希值为M的结果集的第一个在entry中的序号。 //输入:对key进行hash, sscanf(str,"%s %s",entry[i].e,entry[i].f); int hash = ELFHash(entry[i].f); entry[i].next = hashIndex[hash]; hashIndex[hash] = i; i++; //使用: for(int k = hashIndex[hash]; k; k = entry[k].next) { //do something.. }
转自:http://yzmduncan.iteye.com/blog/883903
方法四:
typedef pair<int,int> IntegerPair;
// Adjacency list for a vertex
typedef list<IntegerPair> VertexList;
插入边u->v
pair<int,int> edge(v,w);
vertices_[u].push_front(edge);
和第一种方法类似