C语言泛型编程--抽象数据类型
一、数据类型:
在任何编程语言中,数据类型作为一个整体,ANSI-C包含的类型为:int、double、char……,程序员很少满意语言本身提供的数据类型,一个简单的办法就是构造类似:array、struct 或union。
那么,什么是数据类型呢?我们可以这样定义:一种数据类型是一些值的集合——通常char类型共有256不同的值,int有更多,double也包含更多的值,但是它通常和数学意义上的实数不同。
相应地,我们可以定义数据类型:包含一些值的集合,在值上面添加一些操作。通常,这些值都是计算机可以表示,同时对其的操作或多或少反应了可行的硬件指令。ANCI-C中的int类型在这方面表现得不是很好:在不同的机器上有不同的值,并且算术右移等操作也可能不同。
例如,通常我们定义一个线性结构的数据结构如下:
typedef struct node {
struct node *next;
...information...
} node;
并且我们定义如下的操作:
node * head(node * elt, const node * tail);
二、抽象数据类型:
当我们没有向用户展现具体实现,称为抽象数据类型,比如,我们可以从一个队列中移除一个元素,同事也可以按照一定的顺序向其中添加一个元素。
抽象数据类型给程序员提供了最大的灵活性,因为定义中不包含具体的实现,我们可以很自由地选择任何简单高效的实现。
抽象数据类型满足好的编程原则:信息隐藏与分治策略
代表数据项的信息只展现给需要知道的人:对程序员但不对用户。
通过抽象数据类型,我们可以方便地隔离程序的制定与实现:以自己的方式将一个大的任务拆成小的模块
三、例子--Set
我们怎样构建一个抽象数据类型呢?一个集合set包含如下操作:add, find, drop……,它们将提供集合一个元素并且会返回添加的元素。find操作被用作告诉我们是否某一个元素在集合内。
这样看来,set是一个抽象数据类型,声明我们对set的操作,从一个Set.h头文件开始:
#ifndef SET_H
#define SET_H
extern const void * Set;
void * add (void * set, const void * element);
void * find (const void * set, const void * element);
void * drop (void * set, const void * element);
int contains (const void * set, const void * element);
unsigned count (const void * set);
#endif
Set将在某种程度上展示我们在sets上的操作,add( )向set中添加一个元素,返回是否已经存在于set或是添加成功,find( )在set中寻找一个元素,返回位置或是空指针。drop( )定位一个元素并从set中移除,返回移除元素。contains( )将find( )的结果转换为一个具体的值。
通用指针void*贯穿始终,一方面,通过它可以隐藏set的一些细节,另一方面,它允许我们虚拟的传递任何的类型给add( )以及其他的函数。
四、内存管理
如何获取一个set集合?Set是一个指针,并不是通过typedef定义的类型,结果,我们不能把Set类型定义为局部变量或是全局变量。相反,我们只能通过使用指针指向sets与其中的元素,在new.h中定义如下代码:
#ifndef NEW_H
#define NEW_H
void * new (const void * type, ...);
void delete (void * item);
#endif
五、Object
假如我们打算收集set中的任何感兴趣的数据,需要另一种数据类型Object,在Object.h中描述如下:
#ifndef OBJECT_H
#define OBJECT_H
extern const void * Object; /* new(Object); */
int differ (const void * a, const void * b);
#endif
六、应用
通过上述头文件,可以写出如下的应用main.c :
#include <stdio.h> #include "new.h"
#include "Object.h"
#include "Set.h" int main ()
{ 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)); return ;
}
七、实现
下面将逐一实现本文所有头文件中声明的函数:
实现--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 + ; 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 = ;
}
}
注:我们必须使用统一的方式来处理通用指针,于是我们使用在变量名前加下划线前缀的方法,只是用来初始化我们期待的类型并且名字接近的局部变量。
一个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 : ;
}
contains( )将find( ) 得到的结果转换为一个真值:
int contains (const void * _set, const void * _element)
{
return find(_set, _element) != ;
}
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 + ; 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 = ;
}
} 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 : ;
} int contains (const void * _set, const void * _element)
{
return find(_set, _element) != ;
} 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;
}
最新文章
- 格式化input输入内容(金额)
- JS入门学习,编写一个简易月历
- PHP通过ini_set()来设置显示错误信息和执行时间
- Javascript中的json操作
- iphone 如何清空UIWebView的缓存
- HTTP缓存机制[译文]
- WebApi及Fiddler工具
- memcached使用文档
- 局域网内一台电脑的ip地址自己会变,怎样让它不变
- 360加固apk并自动签名
- 【Alpha】咸鱼冲刺日记第一天-黄紫仪
- java8完全解读一
- 创建自己的library类库包并使用webpack4.x打包发布到npm
- Linux内存管理 (20)最新更新和展望
- 离线安装Cloudera Manager 5和CDH5(最新版5.9.3) 完全教程(七)界面安装
- ECMAScript 6 入门之变量的解构赋值
- Online handwriting recognition using multi convolution neural networks
- Zookeeper -- 命令
- a &;a &;a[0]之间的区别和联系
- mysql覆盖索引
热门文章
- ruby中Hash排序
- maven中文乱码问题——编译错误
- The connection to adb is down, and a severe error has occured.(DDMS中没有真机)
- position 属性和 z-index 属性对页面节点层级影响的例子
- android自定义之 5.0 风格progressBar
- PHP __DIR__, __FILE__, __FUNCTION__, __CLASS__, __METHOD__, __LINE__, __NAMESPACE__
- 表上的DELETE操作
- 警惕SQL语句陷井
- [团队项目]expat不兼容BUG
- sprint3 总结