算法 7.1.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 7.1
void CreateUDG(ALGraph &G) 
{
      // 采用邻接表存储表示，构造无向图G（G.kind=UDG）。
      cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0表明各弧不含其它信息
      for (i=0; i<G.vexnum; ++i) {              // 构造表头向量
        cin >> G.vertices[i].data;              // 输入顶点值
        G.vertices[i].firstarc = NULL;          // 初始化链表头指针为"空"
       }//for
      for (k=0; k<G.arcnum; ++k) {              // 输入各边并构造邻接表
        cin >> v1 >> v2;                        // 输入一条弧的始点和终点
        i = LocateVex(G, v1);  j = LocateVex(G, v2); 
                                                // 确定v1和v2在G中位置，即顶点的序号
        pi = new ArcNode;                      
        pi -> adjvex = j;                       // 对弧结点赋邻接点"位置"信息
        pi -> nextarc = G.vertices[i].firstarc;  G.vertices[i].firstarc = pi; 
                                                // 插入链表G.vertices[i]                
        pj = new ArcNode;                       
        pj -> adjvex = i;                       // 对弧结点赋邻接点"位置"信息
        pj -> nextarc = G.vertices[j].firstarc;  G.vertices[j].firstarc = pj;  
                                                // 插入链表G.vertices[j]                
        if (IncInfo)                            // 若弧含有相关信息，则输入
          { cin>> pj->info;  pi->info=pj->info; }
      }//for
} // CreateUDG