`

有向图的十字链表存储

c数据结构有向图的十字链表存储 
阅读更多 
 /* c7-3.h 有向图的十字链表存储表示 */
 #define MAX_VERTEX_NUM 20
 typedef struct ArcBox
 {
   int tailvex,headvex; /* 该弧的尾和头顶点的位置 */
   struct ArcBox *hlink,*tlink; /* 分别为弧头相同和弧尾相同的弧的链域 */
   InfoType *info; /* 该弧相关信息的指针(可无) */
 }ArcBox; /* 弧结点 */
 typedef struct
 {
   VertexType data;
   ArcBox *firstin,*firstout; /* 分别指向该顶点第一条入弧和出弧 */
 }VexNode; /* 顶点结点 */
 typedef struct
 {
   VexNode xlist[MAX_VERTEX_NUM]; /* 表头向量(数组) */
   int vexnum,arcnum; /* 有向图的当前顶点数和弧数 */
 }OLGraph;

 

 /* bo7-3.c 有向图的十字链表存储(存储结构由c7-3.h定义)的基本函数(15个) */
 int LocateVex(OLGraph G,VertexType u)
 { /* 返回顶点u在有向图G中的位置(序号),如不存在则返回-1 */
   int i;
   for(i=0;i<G.vexnum;++i) /* 用循环查找该结点 */
     if(!strcmp(G.xlist[i].data,u))
       return i;
   return -1;
 }

 Status CreateDG(OLGraph *G)
 { /* 采用十字链表存储表示,构造有向图G。算法7.3 */
   int i,j,k;
   int IncInfo;
   char str[MAX_Info];
   ArcBox *p;
   VertexType v1,v2;
   printf("请输入有向图的顶点数,弧数,弧是否含其它信息(是:1，否:0): ");
   scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_VERTEX_NAME);
   for(i=0;i<(*G).vexnum;++i)
   { /* 构造表头向量 */
     scanf("%s",&(*G).xlist[i].data); /* 输入顶点值 */
     (*G).xlist[i].firstin=NULL; /* 初始化指针 */
     (*G).xlist[i].firstout=NULL;
   }
   printf("请输入%d条弧的弧尾和弧头(空格为间隔):\n",(*G).arcnum);
   for(k=0;k<(*G).arcnum;++k)
   { /* 输入各弧并构造十字链表 */
     scanf("%s%s",&v1,&v2);
     i=LocateVex(*G,v1); /* 确定v1和v2在G中的位置 */
     j=LocateVex(*G,v2);
     p=(ArcBox *)malloc(sizeof(ArcBox)); /* 产生弧结点(假定有足够空间) */
     p->tailvex=i; /* 对弧结点赋值 */
     p->headvex=j;
     p->hlink=(*G).xlist[j].firstin; /* 完成在入弧和出弧链表表头的插入 */
     p->tlink=(*G).xlist[i].firstout;
     (*G).xlist[j].firstin=(*G).xlist[i].firstout=p;
     if(IncInfo)
     { /* 若弧含有相关信息，则输入 */
       printf("请输入该弧的相关信息(<%d个字符): ",MAX_Info);
       scanf("%s",str);
       p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
       strcpy(p->info,str);
     }
     else /* 弧不含有相关信息 */
       p->info=NULL;
   }
   return OK;
 }

 void DestroyGraph(OLGraph *G)
 { /* 初始条件: 有向图G存在 */
   /* 操作结果: 销毁有向图G */
   int j;
   ArcBox *p,*q;
   for(j=0;j<(*G).vexnum;j++) /* 对所有顶点 */
   {
     p=(*G).xlist[j].firstout; /* 仅处理出弧 */
     while(p)
     {
       q=p;
       p=p->tlink;
       if(q->info)
         free(q->info);
       free(q);
     }
   }
   (*G).arcnum=0;
   (*G).vexnum=0;
 }

 VertexType* GetVex(OLGraph G,int v)
 { /* 初始条件:有向图G存在,v是G中某个顶点的序号。操作结果:返回v的值 */
   if(v>=G.vexnum||v<0)
     exit(ERROR);
   return &G.xlist[v].data;
 }

 Status PutVex(OLGraph *G,VertexType v,VertexType value)
 { /* 初始条件: 有向图G存在,v是G中某个顶点 */
   /* 操作结果: 对v赋新值value */
   int i;
   i=LocateVex(*G,v);
   if(i<0) /* v不是G的顶点 */
     return ERROR;
   strcpy((*G).xlist[i].data,value);
   return OK;
 }

 int FirstAdjVex(OLGraph G,VertexType v)
 { /* 初始条件: 有向图G存在,v是G中某个顶点 */
   /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
   int i;
   ArcBox *p;
   i=LocateVex(G,v);
   p=G.xlist[i].firstout; /* p指向顶点v的第1个出弧 */
   if(p)
     return p->headvex;
   else
     return -1;
 }

 int NextAdjVex(OLGraph G,VertexType v,VertexType w)
 { /* 初始条件: 有向图G存在,v是G中某个顶点,w是v的邻接顶点 */
   /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
   /*           若w是v的最后一个邻接顶点,则返回-1 */
   int i,j;
   ArcBox *p;
   i=LocateVex(G,v); /* i是顶点v的序号 */
   j=LocateVex(G,w); /* j是顶点w的序号 */
   p=G.xlist[i].firstout; /* p指向顶点v的第1个出弧 */
   while(p&&p->headvex!=j)
     p=p->tlink;
   if(p) /* w不是v的最后一个邻接顶点 */
     p=p->tlink; /* p指向相对于w的下一个邻接顶点 */
   if(p) /* 有下一个邻接顶点 */
     return p->headvex;
   else
     return -1;
 }

 void InsertVex(OLGraph *G,VertexType v)
 { /* 初始条件: 有向图G存在,v和有向图G中顶点有相同特征 */
   /* 操作结果: 在有向图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
   strcpy((*G). xlist[(*G). vexnum].data,v);
   (*G). xlist[(*G). vexnum].firstin=(*G). xlist[(*G). vexnum].firstout=NULL;
   (*G). vexnum++;
 }

 Status DeleteVex(OLGraph *G,VertexType v)
 { /* 初始条件: 有向图G存在,v是G中某个顶点 */
   /* 操作结果: 删除G中顶点v及其相关的弧 */
   int j,k;
   ArcBox *p,*q;
   k=LocateVex(*G,v); /* k是顶点v的序号 */
   if(k<0) /* v不是图G的顶点 */
     return ERROR;
   /* 以下删除顶点v的出弧 */
   for(j=0;j<(*G). vexnum;j++) /* 顶点v的出弧是其它顶点的入弧 */
   {
     if(j==k)
       continue;
     p=(*G). xlist[j].firstin; /* 在其它顶点的入弧链表中删除顶点v的出弧 */
     while(p)
       if(p->tailvex==k&&p==(*G). xlist[j].firstin) /* 待删结点为首结点 */
       {
         (*G). xlist[j].firstin=p->hlink;
         break;
       }
       else if(p->tailvex!=k) /* 没找到待删结点 */
       {
         q=p;
         p=p->hlink;
       }
       else /* 找到待删结点且不是首结点 */
       {
         q->hlink=p->hlink;
         break;
       }
   }
   p=(*G). xlist[k].firstout; /* 删除与顶点v有关的出弧 */
   while(p)
   {
     q=p->tlink; /* q指向p的下一个出弧 */
     if(p->info) /* 释放p */
       free(p->info);
     free(p);
     (*G). arcnum--;
     p=q;
   }
   /* 以下删除顶点v的入弧 */
   for(j=0;j<(*G). vexnum;j++) /* 顶点v的入弧是其它顶点的出弧 */
   {
     if(j==k)
       continue;
     p=(*G). xlist[j].firstout; /* 在其它顶点的出弧链表中删除顶点v的入弧 */
     while(p)
       if(p->headvex==k&&p==(*G). xlist[j].firstout) /* 待删结点为首结点 */
       {
         (*G). xlist[j].firstout=p->tlink;
         break;
       }
       else if(p->headvex!=k) /* 没找到待删结点 */
       {
         q=p;
         p=p->tlink;
       }
       else /* 找到待删结点且不是首结点 */
       {
         q->tlink=p->tlink;
         break;
       }
   }
   p=(*G). xlist[k].firstin; /* 删除与顶点v有关的入弧 */
   while(p)
   {
     q=p->hlink; /* q指向p的下一个入弧 */
     if(p->info) /* 释放p */
       free(p->info);
     free(p);
     (*G). arcnum--;
     p=q;
   }
   for(j=k+1;j<(*G). vexnum;j++) /* 序号>k的顶点依次向前移 */
     (*G). xlist[j-1]=(*G). xlist[j];
   (*G). vexnum--; /* 顶点数减1 */
   for(j=0;j<(*G). vexnum;j++) /* 结点序号>k的要减1 */
   {
     p=(*G). xlist[j].firstout; /* 处理出弧 */
     while(p)
     {
       if(p->tailvex>k)
         p->tailvex--; /* 序号-1 */
       if(p->headvex>k)
         p->headvex--; /* 序号-1 */
       p=p->tlink;
     }
   }
   return OK;
 }

 Status InsertArc(OLGraph *G,VertexType v,VertexType w)
 { /* 初始条件: 有向图G存在,v和w是G中两个顶点 */
   /* 操作结果: 在G中增添弧<v,w> */
   int i,j;
   int IncInfo;
   char str[MAX_Info];
   ArcBox *p;
   i=LocateVex(*G,v); /* 弧尾的序号 */
   j=LocateVex(*G,w); /* 弧头的序号 */
   if(i<0||j<0)
     return ERROR;
   p=(ArcBox *)malloc(sizeof(ArcBox)); /* 生成新结点 */
   p->tailvex=i; /* 给新结点赋值 */
   p->headvex=j;
   p->hlink=(*G). xlist[j].firstin; /* 插在入弧和出弧的链头 */
   p->tlink=(*G). xlist[i].firstout;
   (*G). xlist[j].firstin=(*G). xlist[i].firstout=p;
   (*G). arcnum++; /* 弧数加1 */
   printf("要插入的弧是否含有其它信息(是: 1,否: 0): ");
   scanf("%d",&IncInfo);
   if(IncInfo)
   {
     printf("请输入该弧的相关信息(<%d个字符): ",MAX_Info);
     scanf("%s",str);
     p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
     strcpy(p->info,str);
   }
   else
     p->info=NULL;
   return OK;
 }

 Status DeleteArc(OLGraph *G,VertexType v,VertexType w)
 { /* 初始条件: 有向图G存在,v和w是G中两个顶点 */
   /* 操作结果: 在G中删除弧<v,w> */
   int i,j;
   ArcBox *p1,*p2;
   i=LocateVex(*G,v); /* 弧尾的序号 */
   j=LocateVex(*G,w); /* 弧头的序号 */
   if(i<0||j<0||i==j)
     return ERROR;
   p2=(*G). xlist[i].firstout; /* 将弧结点从出弧链表中删去 */
   if(p2&&p2->headvex==j) /* 第1个结点为待删除结点 */
     (*G). xlist[i].firstout=p2->tlink;
   else
   {
     while(p2&&p2->headvex!=j) /* 向后找 */
     {
       p1=p2;
       p2=p2->tlink;
     }
     if(p2) /* 没到表尾 */
       p1->tlink=p2->tlink;
   }
   p2=(*G). xlist[j].firstin; /* 将弧结点从入弧链表中删去 */
   if(p2&&p2->tailvex==i)
     (*G). xlist[j].firstin=p2->hlink;
   else
   {
     while(p2&&p2->tailvex!=i)
     {
       p1=p2;
       p2=p2->hlink;
     }
     if(p2) /* 没到表尾 */
       p1->hlink=p2->hlink;
   }
   if(p2->info) /* 释放弧结点 */
     free(p2->info);
   free(p2);
   (*G). arcnum--; /* 弧数减1 */
   return OK;
 }

 Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组 */
 Status(*VisitFunc)(VertexType); /* 函数变量 */
 void DFS(OLGraph G,int i) /* DFSTraverse()调用 */
 {
   ArcBox *p;
   visited[i]=TRUE; /* 访问标志数组置1(已被访问) */
   VisitFunc(G.xlist[i].data); /* 遍历第i个顶点 */
   p=G.xlist[i].firstout; /* p指向第i个顶点的出度 */
   while(p&&visited[p->headvex]) /* p没到表尾且该弧的头顶点已被访问 */
     p=p->tlink; /* 查找下一个结点 */
   if(p&&!visited[p->headvex]) /* 该弧的头顶点未被访问 */
     DFS(G,p->headvex); /* 递归调用DFS() */
 }

 void DFSTraverse(OLGraph G,Status(*Visit)(VertexType))
 { /* 初始条件: 有向图G存在,v是G中某个顶点,Visit是顶点的应用函数 */
   /* 操作结果: 从第1个顶点起,按深度优先递归遍历有向图G,并对每个顶点调用 */
   /*           函数Visit一次且仅一次。一旦Visit()失败,则操作失败 */
   int i;
   for(i=0;i<G.vexnum;i++)
     visited[i]=FALSE; /* 访问标志数组置初值(未被访问) */
   VisitFunc=Visit;
   for(i=0;i<G.vexnum;i++) /* 由序号0开始,继续查找未被访问过的顶点 */
     if(!visited[i])
       DFS(G,i);
   printf("\n");
 }

 typedef int QElemType;
 #include"c3-3.h"
 #include"bo3-3.c"
 void BFSTraverse(OLGraph G,Status(*Visit)(VertexType))
 { /* 初始条件: 有向图G存在,Visit是顶点的应用函数。算法7.6 */
   /* 操作结果: 从第1个顶点起,按广度优先非递归遍历有向图G,并对每个顶点调用 */
   /*           函数Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
   /*           使用辅助队列Q和访问标志数组visited */
   int v,u,w;
   VertexType u1,w1;
   SqQueue Q;
   for(v=0;v<G.vexnum;v++)
     visited[v]=FALSE;
   InitQueue(&Q);
   for(v=0;v<G.vexnum;v++)
     if(!visited[v])
     {
       visited[v]=TRUE;
       Visit(G.xlist[v].data);
       EnQueue(&Q,v);
       while(!QueueEmpty(Q))
       {
         DeQueue(&Q,&u);
         strcpy(u1,*GetVex(G,u));
         for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
           if(!visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
           {
             visited[w]=TRUE;
             Visit(G.xlist[w].data);
             EnQueue(&Q,w);
           }
       }
     }
   printf("\n");
 }

 void Display(OLGraph G)
 { /* 输出有向图G */
   int i;
   ArcBox *p;
   printf("共%d个顶点,%d条弧:\n",G.vexnum,G.arcnum);
   for(i=0;i<G.vexnum;i++)
   {
     printf("顶点%s: 入度: ",G.xlist[i].data);
     p=G.xlist[i].firstin;
     while(p)
     {
       printf("%s ",G.xlist[p->tailvex].data);
       p=p->hlink;
     }
     printf("出度: ");
     p=G.xlist[i].firstout;
     while(p)
     {
       printf("%s ",G.xlist[p->headvex].data);
       if(p->info) /* 该弧有相关信息 */
         printf("弧信息: %s ",p->info);
       p=p->tlink;
     }
     printf("\n");
   }
 }

 

 /* algo7-3.c 实现算法7.10、7.11的程序 */
 #include"c1.h"
 #define MAX_NAME 2 /* 顶点字符串的最大长度+1 */
 typedef int InfoType;
 typedef char VertexType[MAX_NAME]; /* 字符串类型 */
 #include"c7-2.h"
 #include"bo7-2.c"

 int count; /* 全局量count对访问计数 */
 int low[MAX_VERTEX_NUM];

 void DFSArticul(ALGraph G,int v0)
 { /* 从第v0个顶点出发深度优先遍历图G，查找并输出关节点。算法7.11 */
   int min,w;
   ArcNode *p;
   visited[v0]=min=++count; /* v0是第count个访问的顶点 */
   for(p=G.vertices[v0].firstarc;p;p=p->nextarc) /* 对v0的每个邻接顶点检查 */
   {
     w=p->adjvex; /* w为v0的邻接顶点 */
     if(visited[w]==0) /* w未曾访问，是v0的孩子 */
     {
       DFSArticul(G,w); /* 返回前求得low[w] */
       if(low[w]<min)
         min=low[w];
       if(low[w]>=visited[v0])
         printf("%d %s\n",v0,G.vertices[v0].data); /* 关节点 */
     }
     else if(visited[w]<min)
       min=visited[w]; /* w已访问，w是v0在生成树上的祖先 */
   }
   low[v0]=min;
 }

 void FindArticul(ALGraph G)
 { /* 连通图G以邻接表作存储结构，查找并输出G上全部关节点。算法7.10 */
   /* 全局量count对访问计数。 */
   int i,v;
   ArcNode *p;
   count=1;
   low[0]=visited[0]=1; /* 设定邻接表上0号顶点为生成树的根 */
   for(i=1;i<G.vexnum;++i)
     visited[i]=0; /* 其余顶点尚未访问 */
   p=G.vertices[0].firstarc;
   v=p->adjvex;
   DFSArticul(G,v); /* 从第v顶点出发深度优先查找关节点 */
   if(count<G.vexnum) /* 生成树的根有至少两棵子树 */
   {
     printf("%d %s\n",0,G.vertices[0].data); /* 根是关节点，输出 */
     while(p->nextarc)
     {
       p=p->nextarc;
       v=p->adjvex;
       if(visited[v]==0)
         DFSArticul(G,v);
     }
   }
 }

 void main()
 {
   int i;
   ALGraph g;
   printf("请选择无向图\n");
   CreateGraph(&g);
   printf("输出关节点：\n");
   FindArticul(g);
   printf(" i G.vertices[i].data visited[i] low[i]\n");
   for(i=0;i<g.vexnum;++i)
     printf("%2d %9s %14d %8d\n",i,g.vertices[i].data,visited[i],low[i]);
 }

 

 /* main7-3.c 检验bo7-3.c的主程序 */
 #include"c1.h"
 typedef char InfoType;
 #define MAX_Info 80 /* 信息字符串最大长度+1 */
 #define MAX_VERTEX_NAME 3  /* 顶点字符串最大长度+1 */
 typedef char  VertexType[MAX_VERTEX_NAME];
 #include"c7-3.h"
 #include"bo7-3.c"
 Status visit(VertexType v)
 {
   printf("%s ",v);
   return OK;
 }

 void main()
 {
   int j,k,n;
   OLGraph g;
   VertexType v1,v2;
   CreateDG(&g);
   Display(g);
   printf("修改顶点的值，请输入原值 新值: ");
   scanf("%s%s",v1,v2);
   PutVex(&g,v1,v2);
   printf("插入新顶点，请输入顶点的值: ");
   scanf("%s",v1);
   InsertVex(&g,v1);
   printf("插入与新顶点有关的弧，请输入弧数: ");
   scanf("%d",&n);
   for(k=0;k<n;k++)
   {
     printf("请输入另一顶点的值 另一顶点的方向(0:弧头 1:弧尾): ");
     scanf("%s%d",v2,&j);
     if(j)
       InsertArc(&g,v2,v1);
     else
       InsertArc(&g,v1,v2);
   }
   Display(g);
   printf("删除一条弧，请输入待删除弧的弧尾 弧头：");
   scanf("%s%s",v1,v2);
   DeleteArc(&g,v1,v2);
   Display(g);
   printf("删除顶点及相关的弧，请输入顶点的值: ");
   scanf("%s",v1);
   DeleteVex(&g,v1);
   Display(g);
   printf("深度优先搜索的结果:\n");
   DFSTraverse(g,visit);
   printf("广度优先搜索的结果:\n");
   BFSTraverse(g,visit);
   DestroyGraph(&g);
 }

 

分享到：
| 图的邻接表存储
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    有向图的十字链表

    十字链表是表示有向图的一种高效方式，尤其适用于频繁进行增删操作的情况。 十字链表，又称为邻接多重表，是由两个双向链表组成的结构。第一个链表按照顶点顺序排列，每个顶点对应一个链表结点，称为顶点链表。第二...

    数据结构6.5图的存储之三：十字链表

    而十字链表则是一种更为高效的图存储方法，它结合了邻接表和逆邻接表的优点，尤其适用于有向图的存储。 #### 二、十字链表的概念 十字链表是邻接表的一种变体，它不仅存储了每个顶点的所有出边信息，还同时记录了...

    十字链表数据结构 十字链表数据结构

    十字链表数据结构是一种在计算机科学中用于存储和操作二维数据的高级数据结构。它以节点为基础，每个节点包含四个指针，分别指向上下左右四个方向的相邻元素，从而形成一个类似于十字交叉的链接模式。这种数据结构...

    图的十字链表代码(C语言)

    其中，十字链表是一种高效的存储有向图的方式，特别适合处理边的数量远大于顶点数量的情况。 ### 十字链表的特点与优势 十字链表结合了邻接矩阵和邻接表的优点，不仅节省了空间，还提高了查找效率。每个顶点都有两...

    6.2.3 十字链表、邻接多重表1

    但是，十字链表只能用于存储有向图。 邻接多重表 邻接多重表是一种常用的无向图存储方法。它将每个顶点和边结点分开存储，边结点中存储了边的两个顶点的信息，以及next指针指向下一个边结点。邻接多重表的空间...

    数据结构_图的拓扑排序

    题目：图的存储结构及拓扑排序  从键盘或文件读入有向图的顶点信息和弧信息（输入格式自拟）；  建立有向图的十字链表存储结构；  利用拓扑排序方法判断该图是否为有向无环图。

    6.2_3_十字链表、邻接多重表1

    本节将介绍三种常见的图存储结构：邻接矩阵、邻接表、以及十字链表，重点是它们在存储有向图和无向图时的特点和优缺点。 首先，邻接矩阵是最直观的图存储方法。对于无向图，邻接矩阵是一个二维对称矩阵，其中的每个...

    szlb.zip_图十字链表

    图十字链表是一种高效的数据结构，用于存储图的邻接关系，特别适合处理大规模的图数据。在传统的二维数组或邻接矩阵表示法中，存储空间可能会成为问题，特别是当图的顶点数量非常大时。十字链表的出现正是为了解决这...

    十字链表的C++实现

    十字链表是一种特殊的图数据结构，它用于存储稀疏图，即边的数量远小于顶点数量的图。这种数据结构可以高效地进行邻接顶点的查找和操作。在这个问题中，我们有四个文件，它们共同实现了十字链表的数据结构及其相关...

    C 语言实现数据结构(栈, 双向链表, 十字链表, 平衡树, 图, 哈希表).zip

    本压缩包文件包含了一系列用C语言实现的数据结构，包括栈、双向链表、十字链表、平衡树、图以及哈希表。接下来，我们将深入探讨这些数据结构及其C语言实现的关键点。 1. **栈**：栈是一种后进先出（LIFO）的数据...

    数据结构--图的存储结构及操作--思维导图.pdf

    定义：十字链表是一种用链表存储有向图中的边信息的方法。每个弧对应一个链表结点，链表结点中存储着弧尾、弧头和相关信息。 实现：十字链表可以用一个链表数组实现，每个链表元素对应一个弧。 优缺点： * 优点：...

    C语言实现数据结构(栈,双向链表,十字链表,平衡树,图,哈希表).zip

    本资源“C语言实现数据结构(栈,双向链表,十字链表,平衡树,图,哈希表)”提供了一系列C语言编写的关于经典数据结构的实现代码，对于学习和理解这些数据结构的底层工作原理非常有帮助。 1. **栈（Stack）**：栈是一种...

    有向图的强连通分量的求解

    通过对有向图的强连通分量求解算法的学习，我们不仅可以了解深度优先遍历的基本原理，还能掌握如何利用十字链表来高效地处理图数据。这种方法不仅适用于理论研究，也在实际应用中有广泛的应用场景，比如社交网络分析...

    图的存储结构（下）十字链表和邻接多重表，边集数组 数组和链表.pdf

    十字链表是一种有向图的存储结构，它可以解决邻接表的出度问题。在十字链表中，每个顶点表后面接的是其出边表，每个出边表节点中含有头节点指针域（headlink）和尾节点指针域（taillink）。headlink指向的是下一个出...

    图的遍历，存储和求解实现

    - **十字链表法**：这是一种针对有向图的高效存储方法，它使用两个链表来分别存储入度和出度，每个节点包含两个指针，一个指向入边的链表，另一个指向出边的链表。这种结构便于快速查找邻接节点，但实现复杂度较高...

    数据结构中图的存储，排序，代码

    十字链表是针对有向图的邻接表的变体，它包含两个指针字段，分别表示指向该节点的边（firstin）和从该节点出发的边（firstout），同时还有一个尾指针（tailvex）用于跟踪链表的末尾。这种结构使得查找进入和离开...

    6.2图存储和基本操作.zip

    十字链表法是邻接表法的一种优化，尤其适合有向图。它使用两个链表，分别表示入边和出边，每个节点有两个指针，分别指向其入边和出边的链表。这种结构方便了对边的插入和删除操作。 ```cpp struct Node { int data...

    根据有向图的广优先搜索遍历算法PPT学习教案.pptx

    在图的存储结构中，链接矩阵适用于稠密图，而链接表或十字链表更适合稀疏图。在链接表中，顶点的入度表示指向该顶点的边数，出度表示由该顶点出发的边数。 在算法复杂度方面，链接表建立图的时间复杂度为`O(n+e)`，...

    aaa.rar_无向图 环_无向图所有环_无向图最小环_最小生成树_树所有操作

    对任意给定的图（顶点数不小于20，边数不少于30，图的类型可以是有向图、无向图、有向网、无向网），能够输入图的顶点和边（或弧）的信息，并存储到相应存储结构（邻接矩阵、邻接表、十字链表、邻接多重表，任选其中...

    graph.zip_随机图

    十字链表是一种高效存储有向图的结构，它由两个链表组成，分别表示每个顶点的入边和出边。这样的设计有利于快速查询和修改边，尤其是在处理大量边的图时，效率比传统的邻接矩阵和邻接表更高。 具体实现上，我们可以...

Magicbox
Global site tag (gtag.js) - Google Analytics