相较于二叉树,图更为复杂的数据形式,创建起来,层层嵌套,难理解,难使用,但是现代Network基础,没办法,必学
本质是多链表集合,即,以图的每个端点为头节点,以矢量边为节点,建立链式存储结构,借助矢量特性,链接各链表,实现图型数据结构
建立十字链表结构:
typedef struct ArcBox { int trailvex, 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;
看着,嵌套的很麻烦,但是,实际上,仔细品味,你品,你仔细品!🤣,还是很有意思的,至少指针结构用的妙啊!
Status CreateDG(OLGraph& G) { int IncInfo; cout << "输入顶点,弧,信息位:"; cin >> G.vexnum >> G.arcnum >> IncInfo; for (int i = 0; i < G.vexnum; i++) { cout << "输入顶点" << i + 1 << "数据值:"; cin >> G.xlist[i].data; G.xlist[i].firstin = NULL; G.xlist[i].firstout = NULL; } for (int k = 0; k < G.arcnum; k++) { int v1, v2; cout << "键入关联顶点" << k + 1 << ":"; cin >> v1 >> v2; int m = v1 - 1, n = v2 - 1; ArcBox* p; p = (ArcBox*)malloc(sizeof(ArcBox)); *p = { m,n,G.xlist[n].firstin,G.xlist[m].firstout,NULL }; G.xlist[n].firstin = G.xlist[m].firstout = p; if (IncInfo) { //p->info[0] = '0'; //p->info[1] = '\0'; } else { //p->info[0] = '1'; //p->info[1] = '\0'; } } return OK; }
利用指针结构的巧妙定位和赋值功能,既能够实现指针域的连接,在链表结构中,最为有深远意义🤣
测试内容值:
额,我个人是建议采用“引用”架构实现顶点数值的校验,因为,比较容易实现集成和拓展化、程序化等😀
printf("%d\n", e);