请选择 进入手机版 | 继续访问电脑版
    查看: 640|回复: 1

    8.2 图的存储表示—十字链表

    [复制链接]

    2

    主题

    2

    帖子

    6

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    6
    基情
    4
    发表于 2016-9-9 23:28:14 | 显示全部楼层 |阅读模式
    十字链表(Orthogonal List)是有向图的一种存储方法,它实际上是邻接表与逆邻接表的结合,即把每一条边的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头顶点的链表中。在十字链表表示中,顶点表和边表的结点结构分别如图8.13 的(a)和(b)所示。

    8.2 图的存储表示—十字链表

    8.2 图的存储表示—十字链表

    在弧结点中有五个域:其中尾域(tailvex)和头(headvex)分别指示弧尾和弧头这两个顶点在图中的位置,链域hlink 指向弧头相同的下一条弧,链域tlink 指向弧尾相同的下一条弧,info 域指向该弧的相关信息。弧头相同的弧在同一链表上,弧尾相同的弧也在同一链表上。它们的头结点即为顶点结点,它由三个域组成:其中vertex 域存储和顶点相关的信息,如顶点的名称等;firstin 和firstout 为两个链域,分别指向以该顶点为弧头或弧尾的第一个弧结点。例如,图8.14(a)中所示图的十字链表如图8.14(b)所示。若将有向图的邻接矩阵看成是稀疏矩阵的话,则十字链表也可以看成是邻接矩阵的链表存储结构,在图的十字链表中,弧结点所在的链表非循环链表,结点之间相对位置自然形成,不一定按顶点序号有序,表头结点即顶点结点,它们之间而是顺序存储。有向图的十字链表存储表示的形式描述如下:
    #define MAX_VERTEX_NUM 20
    typedef struct ArcBox {
    int tailvex,headvex; /*该弧的尾和头顶点的位置*/
    struct ArcBox * hlink, tlink; /分别为弧头相同和弧尾相财的弧的链域*/
    InfoType info; /*该弧相关信息的指针*/
    }ArcBox;
    typedef struct VexNode {
    VertexType vertex:
    ArcBox fisrin, firstout; /*分别指向该顶点第一条入弧和出弧*/
    }VexNode;
    typedef struct {
    VexNode xlist[MAX_VERTEX_NUM]; /*表头向量*/
    int vexnum,arcnum; /*有向图的顶点数和弧数*/
    }OLGraph;

    8.2 图的存储表示—十字链表

    8.2 图的存储表示—十字链表

    下面给出建立一个有向图的十字链表存储的算法。通过该算法,只要输入n 个顶点的信息和e 条弧的信息,便可建立该有向图的十字链表,其算法内容如下。
    void CreateDG(LOGraph **G)
    /*采用十字链表表示,构造有向图G(G.kind=DG)*/
    { scanf (&(*G->brcnum),&(*G->arcnum),&IncInfo); /*IncInfo 为0 则各弧不含其实信息*/
    for (i=0;i<*G->vexnum;++i) /*构造表头向量*/
    { scanf(&(G->xlist.vertex)); /*输入顶点值*/
    *G->xlist.firstin=NulL;*G->xlist.firstout =NULL; /*初始化指针*/
    }
    for(k=0;k<G.arcnum;++k) /*输入各弧并构造十字链表*/
    { scanf(&v1,&v2); /*输入一条弧的始点和终点*/
    i=LocateVex(*G,v1); j=LocateVex(*G,v2); /*确定v1 和v2 在G 中位置*/
    p=(ArcBox*) malloc (sizeof(ArcBox)); /*假定有足够空间*/
    *p={ i,j,*G->xlist[j].fistin,*G->xlist.firstout,NULL} /*对弧结点赋值*/
    /*{tailvex,headvex,hlink,tlink,info}*/
    *G->xlist[j].fisrtin=*G->xlist.firstout=p; /*完成在入弧和出弧链头的插入*/
    if (IncInfo) Input( p->info); /*若弧含有相关信息,则输入*/
    }
    }/*CreateDG*/
    算法8.3

    在十字链表中既容易找到以为尾的弧,也容易找到以vi 为头的弧,因而容易求得顶点的出度和入度(或需要,可在建立十字链表的同时求出)。同时,由算法8.3 可知,建立十字链表的时间复杂度和建立邻接表是相同的。在某些有向图的应用中,十字链表是很有用的工具。
    回复

    使用道具 举报

    0

    主题

    2

    帖子

    2

    积分

    新手上路

    Rank: 1

    积分
    2
    基情
    0
    发表于 2017-7-12 16:40:20 | 显示全部楼层
    做个记号,下次好找!












    现实竞争如此激烈,如何在同行中胜出?
    帮您抓住无限商机——海量投放广告,让有需求的客户主动找到您!

    联系QQ:188662616   微信号:188662616


    一直被同行模仿,从来没有被超越!

    智友网络推广是一家专业从事网络营销推广和软件开发销售的专业技术团队,真正的网络营销业内人士;8年来,我们一直从事网络推广,从未间断过,因为专业,才值得依赖;我们有一支高素质的团队,为客户和合作伙伴提供一个最好支持和机会的平台。对于发展期的我们,创新和独特是我们的优势,我们期待更多的合作伙伴认识我们、了解我们,与我们共同发展;
    【联系我们】

    联系QQ:188662616 微信号:188662616

    离石专业代发帖子,新津网络推广,阳泉论坛发帖,竹溪产品推广,红古区外链代发,叶城软文代发,綦江网络营销,宜昌县网络推广策划方案|桂东手工代发外链|拜泉博客论坛推广|荔浦代发帖子包收录|唐海如何进行网络推广|澄海广告公司|丘县代发论文广告|中江网络推广知识|丰都店铺推广|磬石营销外包 。
    回复 支持 反对

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|小黑屋|网站地图|DZ商业模板|VR福利资源|嵌入式Linux论坛 ( 粤ICP备15085165号-2

    GMT+8, 2017-8-23 18:13 , Processed in 0.249601 second(s), 11 queries , File On.

    Powered by 深嵌论坛 X3.3

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表