第7章-图-十字链表-表示有向图/D-G/(开放测试权限)

相较于二叉树,更为复杂的数据形式,创建起来,层层嵌套,难理解,难使用,但是现代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);

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注


皖ICP备2021003932号
召唤伊斯特瓦尔