数据结构_十字链表(C语言)[通俗易懂]

数据结构_十字链表(C语言)[通俗易懂]十字链表1.十字链表图文解析十字链表是有向图的一种存储结构在十字链表里我们称每一条有向边为:弧十字链表的存储结构主要包括:弧结点和顶点结点,如下图:由以上结构组成的有向图如下:红线:与邻接表一样,可以采用头插法插入弧结点绿线:指向同一个尾顶点的弧结点黑线:指向该顶点的绿线弧结点链表,例如顶点V2—>弧的链表(每个弧结点的头顶点都为V2)十字链表的构造方法:2.源代码及测试#include<stdio.h>#include<stdlib.h

大家好,又见面了,我是你们的朋友全栈君。

数据结构总目录



十字链表

1. 图文解析

在无向图中,两个顶点之间的连接我们称之为边;
在这里插入图片描述
而在有向图中,两个顶点之间具有方向的连接称之为英文:Arc
如下图中弧(A->B)的权值=10,其中A为该弧的头顶点,B为该弧的尾顶点
在这里插入图片描述
也可以理解为在无向图中每条边都存在两条弧

十字链表的结构和邻接表的结构较为相似,同样采用了顺序表与链表结构的结合,但在十字链表中存在两个链表,分别用于表示相同头顶点和尾顶点的弧链表。

边结点结构图
在这里插入图片描述
顶点结点结构图
在这里插入图片描述

图与十字链表

在这里插入图片描述

1、在十字链表中,如果仅看相同头顶点的弧链表,其结构和邻接表相同,采用头插法插入弧结点在这里插入图片描述
2、对于相同尾结点的弧链表,实际上就是在已插入的弧结点中,对相同尾顶点的弧结点进行链接,其操作也是链表的头插法。
在这里插入图片描述

2. 源代码

#include <stdio.h>
#include <stdlib.h>
#define MaxVex 20

typedef int ArcType;
typedef char VertexType;

// 弧结点结构
typedef struct ArcNode
{ 
   
    ArcType arcData;        // 弧的数据
    int headVertex, tailVertex;   // 弧的头顶点和尾顶点
    struct ArcNode *nextHeadArc, *nextTailArc;  // 指向相同头、尾顶点的弧指针 
}ArcNode, *ArcList;

// 顶点结点结构
typedef struct VertexNode
{ 
   
    VertexType vertexData;      // 顶点的数据
    ArcList headList, tailList; // 相同头、尾顶点的弧链表
}VertexNode, *VertexList;

// 十字链表结构
typedef struct
{ 
   
    VertexList vertexList;
    int numVertexs, numArcs;
}OLGraph;

// 初始化十字链表
void InitOLGraph(OLGraph *G)
{ 
   
    // 初始化顶点
    G->numVertexs = 0;
    G->numArcs = 0;
    G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));
    // 初始化顶点的两个链表头结点(也可不带头结点)
    int i;
    for (i = 0; i < MaxVex; i++)
    { 
   
        // 相同头顶点的弧链表
        G->vertexList[i].headList = (ArcNode *)malloc(sizeof(ArcNode));
        G->vertexList[i].headList->nextHeadArc = NULL;
        G->vertexList[i].headList->nextTailArc = NULL;
        // 相同尾顶点的弧链表
        G->vertexList[i].tailList = (ArcNode *)malloc(sizeof(ArcNode));
        G->vertexList[i].tailList->nextHeadArc = NULL;
        G->vertexList[i].tailList->nextTailArc = NULL;
    }
    printf("已初始化十字链表!\n");
}

// 创建十字链表
void CreateOLGraph(OLGraph *G)
{ 
   
    printf("请输入顶点数和弧数:");
    scanf("%d %d", &G->numVertexs, &G->numArcs);
    // 输入顶点数据
    int i, j, k;
    for (i = 0; i < G->numVertexs; i++)
    { 
   
        fflush(stdin);
        printf("请输入第%d个顶点信息:", i + 1);
        scanf("%c", &G->vertexList[i].vertexData);
    }
    // 输入弧结点数据
    ArcType w;
    for (k = 0; k < G->numArcs; k++)
    { 
   
        printf("请输入弧(Ai, Aj)的头、尾顶点及其权值:");
        scanf("%d %d %d", &i, &j, &w);
        
        // 创建新的弧结点,并设置该弧结点的数据和头尾顶点的下标
        ArcNode *s;
        s = (ArcNode *)malloc(sizeof(ArcNode));
        s->arcData = w;
        s->headVertex = i - 1;
        s->tailVertex = j - 1;
        
        // 头插法插入相同头顶点的弧链表
        s->nextHeadArc = G->vertexList[i - 1].headList->nextHeadArc;
        G->vertexList[i - 1].headList->nextHeadArc = s;

        // 头插法插入相同尾顶点的弧链表
        s->nextTailArc = G->vertexList[j - 1].tailList->nextTailArc;
        G->vertexList[j - 1].tailList->nextTailArc = s;
    }
    printf("已完成十字链表的创建!\n");
}

void DisplayOLGraph(OLGraph G)
{ 
   
    int i;
    ArcNode *p;
    for (i = 0; i < G.numVertexs; i++)
    { 
   
        printf("顶点:%c\n", G.vertexList[i].vertexData);
        // 相同头顶点的弧链表
        printf("\t相同头顶点的弧:");
        p = G.vertexList[i].headList;
        while (p->nextHeadArc)
        { 
   
            p = p->nextHeadArc;
            printf("(%c)%d(%c) => ", 
            G.vertexList[p->headVertex].vertexData,
            p->arcData, 
            G.vertexList[p->tailVertex].vertexData);
        }
        printf("NULL\n");
        // 相同尾顶点的弧链表
        printf("\t相同尾顶点的弧:");
        p = G.vertexList[i].tailList;
        while (p->nextTailArc)
        { 
   
            p = p->nextTailArc;
            printf("(%c)%d(%c) => ", 
            G.vertexList[p->headVertex].vertexData,
            p->arcData, 
            G.vertexList[p->tailVertex].vertexData);
        }
         printf("NULL\n");
    }
}

int main()
{ 
   
    OLGraph G;
    InitOLGraph(&G);
    CreateOLGraph(&G);
    DisplayOLGraph(G);
    system("pause");
    return 0;
}

3. 测试结果

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150325.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 第二代微服务

    第二代微服务

  • 锂电池充电器电源芯片_4056充电芯片

    锂电池充电器电源芯片_4056充电芯片锂电池充电管理芯片模块开源:1,单节锂电池,标称3.7V,充满4.2V,也有4.35V7款模块的编号是:36,1,3,41,43,2,422,两节锂电池,标称7.4V,充满8.4V5款模块的编号是:38,39,33,40,53,三节锂电池,标称11.1V(10.8V),充满12.6V6款模块的编号是:34,37,8,6,7,31,4,四节锂电池,标称14.8V,充满16.8V2款模块的编号是:35,3236号模块板:单节锂电池充电0.5A,加输…

  • 为什么电脑压缩文件图标突然变成这样了

    为什么电脑压缩文件图标突然变成这样了

  • vscode怎样新建项目和文件

    vscode怎样新建项目和文件vscode跟其他编辑器不太一样,今天咪咪我就来给大家分享一下vscode新建项目和文件的方法。需要用品:电脑vscode01、首先是新建文件,如果只是单一的文件,可以直接点击欢迎界面的“新建文件”,这样即可得到一个新的文件。02、而如果欢迎界面被你关闭掉了,则可以在文件菜单中来新建一个文件。当然,这两个方法都只是新建单一文件,并不是一个完整的项目哦。03、接着我们开始创建一个项目,首先…

  • 咸鱼ZTMR实例—PS2手柄

    咸鱼ZTMR实例—PS2手柄咸鱼ZTMR实例—PS2手柄主控板:ZTMR开发板PS2手柄PS2手柄是游戏机的遥控手柄。psx系列游戏主机在全球很是畅销。不知什么时候便有人打起PS2手柄的主意,破解了通讯协议,使得手柄可以接在其他器件上遥控使用,比如遥控我们熟悉的机器人。突出的特点是现在这款手柄性价比极高。按键丰富,方便扩展到其它应用中。PS2由手柄与接收器两部分组成,手柄主要负责发送按键信息。都接通电…

  • MATLAB 2018b 安装与简介

    MATLAB 2018b 安装与简介matlab2018b安装教程该版本是mathworks官方开发的新版本的商业数学软件,可以帮助用户不仅仅将自己的创意停留在桌面,还可以对大型数据集运行分析,并扩展到群集和云。另外matlab代码可以与其他语言集成,使您能够在Web、企业和生产系统中部署算法和应用程序。与matlab2018a相比,matlab2018b拥有更多数据分析、机器学习和深度学习选项,并且速度比以往更快。其亮点…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号