ZBLOG

//建立邻接表存储方式的有向网 void CreateALGraph(ALGraph &G) { /* 1.输入图中顶点总数与边的总数 2.输入图中顶点信息 3.输入边的信息,建立边结点,插入到相对应数组元素后的边表中(注:有向网中每条边需要插入两个边结点)。*/ int i,j,k; char v1,v2; ArcNode *p, *q; int w; cin>>G.vexnum>>G.arcnum; for(i=0; i>G.vexs[i]...

这段代码是用来创建邻接表存储方式的有向网的。下面是完整的代码实现:

// 定义邻接表结点
typedef struct ArcNode {
    int adjvex;          // 该边所指向的顶点位置
    struct ArcNode *nextarc;   // 指向下一条边的指针
    int weight;          // 权值,如果不需要权值可以省略
} ArcNode;

// 定义顶点结构体
typedef struct VexNode {
    char data;           // 顶点信息
    ArcNode *firstarc;   // 指向第一条依附该顶点的边的指针
} VexNode, AdjList[MAXVEX];

// 定义有向图结构体
typedef struct {
    AdjList vertices;      // 邻接表数组
    int vexnum, arcnum;    // 图中顶点数和弧(边)数目
} ALGraph;

void CreateALGraph(ALGraph &G) {
    int i, j, k;
    char v1, v2;
    ArcNode *p, *q;
    int w;

    cin >> G.vexnum >> G.arcnum;
    
    // 输入图中顶点信息,建立顶点数组
    for (i = 0; i < G.vexnum; i++) {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;
    }

     // 输入边信息,建立边结点,并插入到相应顶点后的边表中
    for (k = 0; k < G.arcnum; k++) {
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);   // 找到顶点v1在顶点数组的位置
        j = LocateVex(G, v2);   // 找到顶点v2在顶点数组的位置

        p = new ArcNode;
        p->adjvex = j;
        p->weight = w;

        if (G.vertices[i].firstarc == NULL) {   // 若该顶点没有边,则直接插入
            G.vertices[i].firstarc = p;
        } else {
            q = G.vertices[i].firstarc;
            while (q->nextarc != NULL) {   // 找到最后一条边的位置
                q = q->nextarc;
            }
            q->nextarc = p;   // 插入到最后一条边之后
        }
    }
}

这段代码实现了输入有向网的顶点总数和边总数,以及每个顶点的信息。然后根据输入的边信息建立对应的邻接表结构。注意,在有向网中,每条边都需要插入两个相应的边结点,一个在起始顶点对应的边表中,另一个在终止顶点对应的边表中。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=9986

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?