在任何编程语言中，数据类型作为一个整体，ANSI-C包含的类型为：int、double、char……，程序员很少满意语言本身提供的数据类型，一个简单的办法就是构造类似：array、struct或union的聚合体。

那么，什么是数据类型呢？我们可以这样定义：一种数据类型是一些值的集合——通常char类型共有不同的值，int有更多，double也包含更多的值，但是它通常和数学意义上的实数不同。

相应地，我们可以定义数据类型：包含一些值的集合，在值上面添加一些操作。通常，这些值都是计算机可以表示，同时对其的操作或多或少反应了可行的硬件指令。ANCI-C中的int类型在这方面表现得不是很好：在不同的机器上有不同的值，并且算术右移等操作也可能不同。

例如，通常我们定义一个线性结构的数据结构如下：

typedefstructnode{structnode*next;//...information...}node;

并且我们定义如下的操作：

node*head(node*elt,constnode*tail);二、抽象数据类型：

当我们没有向用户展现具体实现，称为抽象数据类型，比如，我们可以从一个队列中移除一个元素，同事也可以按照一定的顺序向其中添加一个元素。

抽象数据类型给程序员提供了最大的灵活性，因为定义中不包含具体的实现，我们可以很自由地选择任何简单高效的实现。

抽象数据类型满足好的编程原则：信息隐藏与分治策略

代表数据项的信息只展现给需要知道的人：对程序员但不对用户。

通过抽象数据类型，我们可以方便地隔离程序的制定与实现：以自己的方式将一个大的任务拆成小的模块

我们怎样构建一个抽象数据类型呢？一个集合set包含如下操作：add,find,drop……，它们将提供集合一个元素并且会返回添加的元素。find操作被用作告诉我们是否某一个元素在集合内。

这样看来，set是一个抽象数据类型，声明我们对set的操作，从一个Set.h头文件开始：

#ifndefSET_H#defineSET_Hexternconstvoid*Set;void*add(void*set,constvoid*element);void*find(constvoid*set,constvoid*element);void*drop(void*set,constvoid*element);intcontains(constvoid*set,constvoid*element);unsignedcount(constvoid*set);#endif

Set将在某种程度上展示我们在sets上的操作，add()向set中添加一个元素，返回是否已经存在于set或是添加成功，find()在set中寻找一个元素，返回位置或是空指针。drop()定位一个元素并从set中移除，返回移除元素。contains()将find()的结果转换为一个具体的值。

通用指针void*贯穿始终，一方面，通过它可以隐藏set的一些细节，另一方面，它允许我们虚拟的传递任何的类型给add()以及其他的函数。

如何获取一个set集合？Set是一个指针，并不是通过typedef定义的类型，结果，我们不能把Set类型定义为局部变量或是全局变量。相反，我们只能通过使用指针指向sets与其中的元素，在new.h中定义如下代码：

#ifndefNEW_H#defineNEW_Hvoid*new(constvoid*type,...);voiddelete(void*item);#endif五、Object

假如我们打算收集set中的任何感兴趣的数据，需要另一种数据类型Object，在Object.h中描述如下：

#ifndefOBJECT_H#defineOBJECT_Hexternconstvoid*Object;/*new(Object);*/intdiffer(constvoid*a,constvoid*b);#endif六、应用

通过上述头文件，可以写出如下的应用main.c:

#includestdio.h#include"new.h"#include"Object.h"#include"Set.h"intmain(){void*s=new(Set);void*a=add(s,new(Object));void*b=add(s,new(Object));void*c=new(Object);if(contains(s,a)contains(s,b))puts("ok");if(contains(s,c))puts("contains?");if(differ(a,add(s,a)))puts("differ?");if(contains(s,drop(s,a)))puts("drop?");delete(drop(s,b));delete(drop(s,c));return0;}七、实现

下面将逐一实现本文所有头文件中声明的函数：

实现--Set

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

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

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

#if!definedMANY

MANY1#defineMANY10#endifstaticintheap[MANY];void*new(constvoid*type,...){int*p;/*heap[1..]*/for(p=heap+1;pheap+MANY;++p)if(!*p)break;assert(pheap+MANY);*p=MANY;returnp;}

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

voiddelete(void*_item){int*item=_item;if(item){assert(itemheapitemheap+MANY);*item=0;}}

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

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

void*add(void*_set,constvoid*_element){int*set=_set;constint*element=_element;assert(setheapsetheap+MANY);assert(*set==MANY);assert(elementheapelementheap+MANY);if(*element==MANY)*(int*)element=set-heap;elseassert(*element==set-heap);return(void*)element;}

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

void*find(constvoid*_set,constvoid*_element){constint*set=_set;constint*element=_element;assert(setheapsetheap+MANY);assert(*set==MANY);assert(elementheapelementheap+MANY);assert(*element);return*element==set-heap?(void*)element:0;}

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

intcontains(constvoid*_set,constvoid*_element){returnfind(_set,_element)!=0;}

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

void*drop(void*_set,constvoid*_element){int*element=find(_set,_element);if(element)*element=MANY;returnelement;}

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

intdiffer(constvoid*a,constvoid*b){returna!=b;}

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

#includeassert.h#includestdio.h#include"new.h"#include"Set.h"#include"Object.h"constvoid*Set;constvoid*Object;#if!definedMANY

MANY1#defineMANY10#endifstaticintheap[MANY];void*new(constvoid*type,...){int*p;/*heap[1..]*/for(p=heap+1;pheap+MANY;++p)if(!*p)break;assert(pheap+MANY);*p=MANY;returnp;}voiddelete(void*_item){int*item=_item;if(item){assert(itemheapitemheap+MANY);*item=0;}}void*add(void*_set,constvoid*_element){int*set=_set;constint*element=_element;assert(setheapsetheap+MANY);assert(*set==MANY);assert(elementheapelementheap+MANY);if(*element==MANY)*(int*)element=set-heap;elseassert(*element==set-heap);return(void*)element;}void*find(constvoid*_set,constvoid*_element){constint*set=_set;constint*element=_element;assert(setheapsetheap+MANY);assert(*set==MANY);assert(elementheapelementheap+MANY);assert(*element);return*element==set-heap?(void*)element:0;}intcontains(constvoid*_set,constvoid*_element){returnfind(_set,_element)!=0;}void*drop(void*_set,constvoid*_element){int*element=find(_set,_element);if(element)*element=MANY;returnelement;}intdiffer(constvoid*a,constvoid*b){returna!=b;}代码排版比较混乱，点击“阅读原文”进入我的博客查看

赞赏

人赞赏