数据结构基础第7章图幻灯片.pptVIP

typedef struct Node { int adjvex; // 邻接点的位置 WeightType weight； //权值域，根据需要设立 struct Node *next; // 指向下一条边（弧） } edgenode; // 边结点 //定义图的邻接表结构类型 （没包含顶点信息） typedef edgenode *adjlist[ MaxVertexNum ]; 例如： adjlist GL; 图的邻接表表示法的C语言描述： V0 V1 V2 V3 V4 G2 V0 V1 V2 V3 G1 有向图G1 无向图G2 0 ^ 1 2 3 2 1 ^ 3 ^ 0 ^ 0 1 2 3 4 3 1 ^ 2 4 2 0 ^ 4 3 1 ^ 0 ^ 2 1 ^ 图G1和G2的邻接表 GL[i] adjvex next (1) 初始化函数 void InitAdjoin(adjlist GL) { int i; for ( i = 0 ; i MaxVertexNum; i++ ) GL[i] = NULL; } (2) 建立邻接表函数 void CreateAdjoin( adjlist GL, int n, char *s, int k1, int k2) { // k1=0 代表无向图否则为有向图, // k2 =0 代表无权图否则为带权图。 // s 存放边集。n为顶点数。 istrstream sin(s); char c1,c2,c3; int i, j; weightType w; edgenode *p; //将指向新申请的边结点 sinc1; //读入第一个字符 ‘{’ if ( k2==0 ) // 建立无权图 do { sinc1ic2jc3; p = (edgenode *) malloc(sizeof(edgenode)); p-adjvex=j; p-weight=1; //插入边结点 p-next = GL[i]; GL[i] = p; if (k1==0) { //对无向图，需再插入一个边结点 p = (edgenode *) malloc(sizeof(edgenode)); p-adjvex=i; p-weight=1; p-next = GL[j]; GL[j] = p; } sinc1; //读入‘,’ 或 ‘}’ } while ( c1==‘,’ ); else // 建立有权图 do { sinc1ic2jc3w; p = (edgenode *) malloc(sizeof(edgenode)); p-adjvex=j; p-weight=w; //插入边结点 p-next = GL[i]; GL[i] = p; if (k1==0) { //对无向图，需再插入一个边结点