本文共 2825 字，大约阅读时间需要 9 分钟。

第一种：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        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<
   
    ";			pnode p = Nodes[i].next;			while (p!=NULL)			{				cout<
    
     adj<<" "<
     
      w<<";";				p = p->next;			}			cout<
     
    
   

数组内的元素是空元素，不代表任何结点

第二种方法：

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<
   
    ";			Arc * p = g.vertices[i].firstArc;			while (p!=NULL)			{				cout<
    
     adj<<" "<
     
      w<<";";				p = p->nextArc;			}			cout<
     
    
   

第三种：

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..}

转自：

方法四：

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);

和第一种方法类似

转载地址：http://qbeti.baihongyu.com/