Biegral Blog

       我们已经很熟悉链表了， 到目前为止， 我们接触到的链表中的结点类型都是相同的。 但是， 在实际中， 很多场景都要用链表来管理不同类型的对象/结点， 这样的链表叫异质链表， 它非常常见， 也很实用。 异质链表的实现有很多方式， 下面， 我们来介绍最简单的实现方式， 作为异质链表的入门吧。

       先思考一下， 如果将这些不同类型的对象用链表进行直接链接， 显然不太好操作（不能用for循环来搞）， 换个思路吧， 我们可以抽象出这些对象的共同点， 将这些共同点构造成结点， 然后把这些结点串起来。 并且需要保证， 通过这些结点， 可以访问到对应的对象， 且看简要的示意代码：

#include <iostream>
using namespace std;

// 整数类
struct Integer
{
	int a;
};

// 点类
struct Point
{
	int x;
	int y;
};

// 矩形类
struct Rectangle
{
	Point point;
	int width;
	int height;
};

// 对象的id值
typedef enum
{
	ErrorId = -1,
	IntegerId = 1,
	PointId = 2,
	RectangeId = 3,
}ObjectID;

// 抽象对象的共同点， 构造成新的结点， 便于链接
typedef struct node
{
	node *next;
	void *pBasic;
	ObjectID id;
}Node;



// 注意: A模块要和B模块商量好
int main()
{

	/* A模块 */

	// 定义三个对象并初始化
	Integer i = {1};
	Point po = {2, 3};
	Rectangle rect = {4, 5, 6, 7};	


	// 定义三个抽象出来的结点
	Node node1;
	node1.id = IntegerId;
	node1.pBasic = &i;

	Node node2;
	node2.id = PointId;
	node2.pBasic = &po;
	
	Node node3;
	node3.id = RectangeId;
	node3.pBasic = &rect;


	// 将三个结点链接起来， 便于用manager管理链表
	Node manager;
	Node *p = &manager;
	p->id = ErrorId;
	p->next = NULL;
	p->pBasic = NULL;

	p->next = &node1;
	node1.next = &node2;
	node2.next = &node3;
	node3.next = NULL;
	
	Integer *pI = NULL;
	Point *pPo = NULL;
	Rectangle *pRect = NULL;



	/* B模块 */

	// 遍历链表
	while(NULL != p->next)
	{
		// 由于结点中指向对象的指针是void*形式的， 所以有必要根据id对void*进行还原(基于A,B模块商量的结果)
		switch(p->next->id) 
		{
			case IntegerId:
			{
				pI = (Integer*)(p->next->pBasic);
				cout << pI->a << endl;
				break;
			}
			case PointId:
			{
				pPo = (Point *)(p->next->pBasic);
				cout << pPo->x << endl;
				cout << pPo->y << endl;
				break;
			}
			case RectangeId:
			{
				pRect = (Rectangle *)(p->next->pBasic);
				cout << pRect->point.x << endl;
				cout << pRect->point.y << endl;
				cout << pRect->width << endl;
				cout << pRect->height << endl;
				break;
			}
			default:
			{
				break;
			}
		}

		p = p->next;
	}

	return 0;
}

       上面的实现方法非常简单易懂，有兴趣的童鞋可以画画图， 看看是怎么回事， 鉴于比较简单， 我就没有附图了。 在后续博文中， 会继续介绍异质链表的其他实现方法，让我们拭目以待