C语⾔泛型编程--抽象数据类型
⼀、数据类型：
在任何编程语⾔中，数据类型作为⼀个整体，ANSI-C包含的类型为：int、double、char……，程序员很少满意语⾔本⾝提供的数据类型，⼀个简单的办法就是构造类似：array、struct 或union。
那么，什么是数据类型呢？我们可以这样定义：⼀种数据类型是⼀些值的集合——通常char类型共有256不同的值，int有更多，double也包含更多的值，但是它通常和数学意义上的实数不同。
相应地，我们可以定义数据类型：包含⼀些值的集合，在值上⾯添加⼀些操作。通常，这些值都是计算机可以表⽰，同时对其的操作或多或少反应了可⾏的硬件指令。ANCI-C中的int类型在这⽅⾯表现得不是很好：在不同的机器上有不同的值，并且算术右移等操作也可能不同。
例如，通常我们定义⼀个线性结构的数据结构如下：
并且我们定义如下的操作：
⼆、抽象数据类型：
当我们没有向⽤户展现具体实现，称为抽象数据类型，⽐如，我们可以从⼀个队列中移除⼀个元素，同事也可以按照⼀定的顺序向其中添加⼀个元素。
抽象数据类型给程序员提供了最⼤的灵活性，因为定义中不包含具体的实现，我们可以很⾃由地选择任何简单⾼效的实现。
抽象数据类型满⾜好的编程原则：信息隐藏与分治策略
代表数据项的信息只展现给需要知道的⼈：对程序员但不对⽤户。
通过抽象数据类型，我们可以⽅便地隔离程序的制定与实现：以⾃⼰的⽅式将⼀个⼤的任务拆成⼩的模块
三、例⼦--Set
我们怎样构建⼀个抽象数据类型呢？⼀个集合set包含如下操作：add, find, drop……，它们将提供集合⼀个元素并且会返回添加的元素。find操作被⽤作告诉我们是否某⼀个元素在集合内。
这样看来，set是⼀个抽象数据类型，声明我们对set的操作，从⼀个Set.h头⽂件开始：
Set将在某种程度上展⽰我们在sets上的操作，add( )向set中添加⼀个元素，返回是否已经存在于set或是添加成功，find( )在set中寻⼀个元素，返回位置或是空指针。drop( )定位⼀个元素并从set中移除，返回移除元素。contains( )将find( )的结果转换为⼀个具体的值。
通⽤指针void*贯穿始终，⼀⽅⾯，通过它可以隐藏set的⼀些细节，另⼀⽅⾯，它允许我们虚拟的传递任何的类型给add( )以及其他的函数。
四、内存管理
如何获取⼀个set集合？Set是⼀个指针，并不是通过typedef定义的类型，结果，我们不能把Set类型定义为局部变量或是全局变量。相反，我们只能通过使⽤指针指向sets与其中的元素，在new.h中定义如下代码：
c编程网
五、Object
假如我们打算收集set中的任何感兴趣的数据，需要另⼀种数据类型Object，在Object.h中描述如下：
六、应⽤
通过上述头⽂件，可以写出如下的应⽤main.c :
#include <stdio.h>
七、实现
下⾯将逐⼀实现本⽂所有头⽂件中声明的函数：
实现--Set
main.c 可以成功编译，但是在编译和执⾏程序之前，我们必须实现抽象数据类型和内存管理，如果⼀个对象不储存任何信息，并且每⼀个对象都⾄少属于⼀个set，那么我们可以⽤⼀个唯⼀的较⼩的正整数值来表⽰对象和每⼀个set，⽽这些正整数值可以使⽤⼀个数组heap[ ]中的索引来表⽰。
如果⼀个对象是set的成员，对应的数组元素包含代表set的整数值。
Sets和对象具有相同的展⽰，new( )不会在意type的类型描述，它将返回heap[ ]中值为0的元素，代码如下:
使⽤0来标记heap[ ]中的有效元素，结果，我们不能返回指向heap[0]的指针----假如是set，其成员可以获得0索引。new()可能越界，可以使⽤assert（）来避免。elete()必须⼩⼼null指针，⼀个heap[]元素通过被设置为0从⽽被回收：
注：我们必须使⽤统⼀的⽅式来处理通⽤指针，于是我们使⽤在变量名前加下划线前缀的⽅法，只是⽤来初始化我们期待的类型并且名字接近的局部变量。
⼀个set有所包含的的对象表⽰：每⼀个元素指向set，假如⼀个元素包含MANY，就可以添加到set，否则，说明set中已经包含。
其他的函数就简单了，find( ) 仅仅⽤来判断set中是否包含有下划线前缀的变量名元素：
contains( )将find( ) 得到的结果转换为⼀个真值：
drop( ) 依赖find( )函数来检查要删除的元素是否在set中，若是，则通过将相应的对象元素的值标记为MANY：
接着提供了⼀个判断两个对象是否相等的函数differ( )：
完整的Set.c源代码如下：
#include <assert.h>

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。