C面向对象编程--抽象数据类型（2）

接上一篇：C面向对象编程--抽象数据类型(1) ，本篇主要实现Set

实现--Set

main.c 可以成功编译，但是在编译和执行程序之前，我们必须实现抽象数据类型和内存管理，如果一个对象不储存任何信息，并且每一个对象都至少属于一个set，那么我们可以用一个唯一的较小的正整数值来表示对象和每一个set，而这些正整数值可以使用一个数组heap[ ]中的索引来表示。

如果一个对象是set的成员，对应的数组元素包含代表set的整数值。

Sets和对象具有相同的展示，new( )不会在意type的类型描述，它将返回heap[ ]中值为0的元素，代码如下:

#if ! defined MANY || MANY < 1
#define	MANY	10
#endif

static int heap [MANY];

void * new (const void * type, ...)
{	int * p;							/* & heap[1..] */

	for (p = heap + 1; p < heap + MANY; ++ p)
		if (! * p)
			break;
	assert(p < heap + MANY);
	* p = MANY;
	return p;
}

  使用0来标记heap[ ]中的有效元素，结果，我们不能返回指向heap[0]的指针----假如是set，其成员可以获得0索引。new()可能越界，可以使用assert（）来避免。elete()必须小心null指针，一个heap[]元素通过被设置为0从而被回收：

void delete (void * _item)
{	int * item = _item;

	if (item)
	{	assert(item > heap && item < heap + MANY);
		* item = 0;
	}
}

    注：我们必须使用统一的方式来处理通用指针，于是我们使用在变量名前加下划线前缀的方法，只是用来初始化我们期待的类型并且名字接近的局部变量。

 一个set有所包含的的对象表示：每一个元素指向set，假如一个元素包含MANY，就可以添加到set，否则，说明set中已经包含。

void * add (void * _set, const void * _element)
{	int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);

	if (* element == MANY)
		* (int *) element = set - heap;
	else
		assert(* element == set - heap);

	return (void *) element;
}

 

其他的函数就简单了，find( ) 仅仅用来判断set中是否包含有下划线前缀的变量名元素：

void * find (const void * _set, const void * _element)
{	const int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);
	assert(* element);

	return * element == set - heap ? (void *) element : 0;
}

 

   contains( )将find( ) 得到的结果转换为一个真值：

int contains (const void * _set, const void * _element)
{
	return find(_set, _element) != 0;
}

   drop( ) 依赖find( )函数来检查要删除的元素是否在set中，若是，则通过将相应的对象元素的值标记为MANY：

void * drop (void * _set, const void * _element)
{	int * element = find(_set, _element);

	if (element)
		* element = MANY;
	return element;
}

      接着提供了一个判断两个对象是否相等的函数differ( )：

int differ (const void * a, const void * b)
{
	return a != b;
}

 

 完整的Set.c源代码如下：

#include <assert.h>
#include <stdio.h>

#include "new.h"
#include "Set.h"
#include "Object.h"

const void * Set;
const void * Object;

#if ! defined MANY || MANY < 1
#define	MANY	10
#endif

static int heap [MANY];

void * new (const void * type, ...)
{	int * p;							/* & heap[1..] */

	for (p = heap + 1; p < heap + MANY; ++ p)
		if (! * p)
			break;
	assert(p < heap + MANY);
	* p = MANY;
	return p;
}

void delete (void * _item)
{	int * item = _item;

	if (item)
	{	assert(item > heap && item < heap + MANY);
		* item = 0;
	}
}

void * add (void * _set, const void * _element)
{	int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);

	if (* element == MANY)
		* (int *) element = set - heap;
	else
		assert(* element == set - heap);

	return (void *) element;
}

void * find (const void * _set, const void * _element)
{	const int * set = _set;
	const int * element = _element;

	assert(set > heap && set < heap + MANY);
	assert(* set == MANY);
	assert(element > heap && element < heap + MANY);
	assert(* element);

	return * element == set - heap ? (void *) element : 0;
}

int contains (const void * _set, const void * _element)
{
	return find(_set, _element) != 0;
}

void * drop (void * _set, const void * _element)
{	int * element = find(_set, _element);

	if (element)
		* element = MANY;
	return element;
}

int differ (const void * a, const void * b)
{
	return a != b;
}