数据结构之---C++语言实现图的十字链表存储表示
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构之---C++语言实现图的十字链表存储表示,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2768字,纯文字阅读大概需要4分钟。
内容图文
![数据结构之---C++语言实现图的十字链表存储表示](/upload/InfoBanner/zyjiaocheng/1329/2cc61e276d294ebf903a2e09dea6f23b.jpg)
最近一直忙着考研复习,很久都没有更新博客了,今天写一篇数据结构的存储。
//有向图的十字链表存储表示 //杨鑫 #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; //顶点的度 } int main() { int flag = 1; OLGraph G; CreateDG(G); printf("=========================================\n"); printf("该有向图的弧如下:\n"); DisplayArc(G); VertexType v; printf("\n=========================================\n"); while(1) { if(flag == 0) break; printf("请输入任意顶点,将输出该顶点度的值:"); scanf("%s",v); getchar(); printf("顶点 %s 的度为 :%d\n",v,VexDegree(G,v)); printf("结束请输入 0 以回车键结束\n\n"); cin>>flag; } printf("=========================================\n"); return 0; }
结果:
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/u012965373/article/details/47133441
内容总结
以上是互联网集市为您收集整理的数据结构之---C++语言实现图的十字链表存储表示全部内容,希望文章能够帮你解决数据结构之---C++语言实现图的十字链表存储表示所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。