大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C技巧 > C语言泛型编程--抽象数据类型

C语言泛型编程--抽象数据类型(1)

关键词:抽象数据类型语言编程  阅读(1234) 赞(12)

[摘要]本文是对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 0;
}

七、实现

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

实现--Set

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

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

«上一页12下一页»


相关评论