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

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

    [复制链接]

    883

    主题

    941

    帖子

    3575

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3575
    基情
    1843
    发表于 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 可知,建立十字链表的时间复杂度和建立邻接表是相同的。在某些有向图的应用中,十字链表是很有用的工具。


    上一篇:8.2 图的存储表示—邻接表
    下一篇:8.2 图的存储表示—邻接多重表
    回复

    使用道具 举报

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

    本版积分规则

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

    GMT+8, 2017-5-27 14:19 , Processed in 0.696406 second(s), 50 queries .

    Powered by 深嵌论坛 X3.2

    © 2001-2013 Comsenz Inc.

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