喜欢天晴 2017-12-25 08:11 采纳率: 72.7%
浏览 1081
已结题

十字链表存储图的代码写好了(代码如下),寻找两节点间的简单路径不会写。大佬帮我写一下C++代码,谢了

 #include <iostream>  
#include <cstdio>  
#include <stdlib.h>  
#include <cstring>  
using namespace std;
#define MAX_VERTEX_NUM 20  
#define OVERFLOW -2  
#define OK 1  
typedef int Status;
typedef char VertexType[MAX_VERTEX_NUM];
typedef char InfoType;
//弧(边)的结构体  
typedef struct ArcBox
{
    int tailvex, headvex;                        //该弧的尾和头顶点的位置  
    struct ArcBox *hlink, *tlink;               //分别为弧头相同和弧尾相同的弧的链域  
    InfoType *info;                             //该弧的相关信息的指针  
}ArcBox;

//顶点的结构体  
typedef struct VexNode
{
    VertexType data;
    ArcBox *firstin, *firstout;  //分别指向该顶点的第一条入弧和出弧  
}VexNode;

//有向图的结构体  
typedef struct
{
    VexNode xlist[MAX_VERTEX_NUM];      //表头向量  
    int vexnum, arcnum;                 //有向图的当前顶点数和弧数  
}OLGraph;

int LocateVex(OLGraph &G, VertexType u)
{
    for (int i = 0; i < G.vexnum; ++i)
        if (strcmp(G.xlist[i].data, u) == 0)
            return i;
    return -1;
}

//构造有向图G;  
Status CreateDG(OLGraph &G)
{

    int i, j, k;
    printf("请输入有向图的顶点数以及弧数:\n");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("请输入%d个顶点的值,之间有空格隔开:\n", G.vexnum);
    for (i = 0; i<G.vexnum; ++i) //构造表头向量  
    {
        getchar();
        scanf("%s", G.xlist[i].data);  //输入顶点值  
        G.xlist[i].firstin = NULL;
        G.xlist[i].firstout = NULL;
    }

    VertexType v1, v2;
    ArcBox *p;
    printf("请依次输入%d条弧各自依附的两个顶点(输入格式:v1 v2)\n", G.arcnum);
    for (k = 0; k < G.arcnum; ++k)  //输入各弧并构造十字链表  
    {
        getchar();
        scanf("%s%s", v1, v2);
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        p = (ArcBox *)malloc(sizeof(ArcBox));
        if (!p)
            exit(OVERFLOW);
        p->tailvex = i;
        p->headvex = j;
        p->hlink = G.xlist[j].firstin;
        p->tlink = G.xlist[i].firstout;
        p->info = NULL;
        G.xlist[j].firstin = G.xlist[i].firstout = p;  //完成在入弧和出弧链头的插入  
    }
    getchar();
    return OK;
}

void DisplayArc(OLGraph &G)
{
    ArcBox *p;
    for (int i = 0; i < G.vexnum; ++i)
    {
        p = G.xlist[i].firstout;
        while (p)
        {
            printf("<%s,%s> ", G.xlist[p->tailvex].data, G.xlist[p->headvex].data);
            p = p->tlink;
        }
    }
    printf("\n");
}


//顶点的度:入度+出度  
int VexDegree(OLGraph &G, VertexType v)
{

    int k = LocateVex(G, v);
    if (k<0)
        exit(OVERFLOW);
    int id = 0, od = 0;  //入度,出度  

    ArcBox *pin = G.xlist[k].firstin;
    ArcBox *pout = G.xlist[k].firstout;
    while (pin)  //求入度  
    {
        ++id;
        pin = pin->hlink;
    }

    while (pout)  //求出度  
    {
        ++od;
        pout = pout->tlink;
    }

    return id + od; //顶点的度  
}

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-12-25 16:19
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)