AbstractDataTypes

C語(yǔ)言的靈活

C語(yǔ)言很靈活，不但有基礎(chǔ)數(shù)據(jù)類型，char、int、double等，還允許程序員自定義類型，如：

定義一個(gè)鏈表使用的數(shù)據(jù)類型，其中有Node節(jié)點(diǎn)和自己需要使用的其他數(shù)據(jù)信息。

typedef struct node {struct node * next;... information ... } node;

一個(gè)小例子-set

set會(huì)有這些操作：

#ifndef SET_H #define SET_Hextern 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就是一個(gè)抽象數(shù)據(jù)類型，而這些方法描述的是我們能對(duì)set進(jìn)行的操作。

add向set中添加一個(gè)element

find查找一個(gè)element是否在set中

drop將一個(gè)element從set中剔除

contains將find的結(jié)果轉(zhuǎn)變?yōu)檎婕僦?/p>

set類型定義成void類型是為了能夠像set傳遞任何類型的數(shù)據(jù)+

內(nèi)存管理函數(shù)方法

在new.h中定義了內(nèi)存管理的方法

new和delete是用來(lái)代替ANSI-C中的calloc還有free方法的

#ifndef NEW_H #define NEW_Hvoid * new (const void * type, ...); void delete (void * item);#endif

對(duì)象

想讓set更有意思，我們需要另外一個(gè)抽象數(shù)據(jù)類型Object

#ifndef OBJECT_H #define OBJECT_Hextern const void * Object; /* new(Object); */int differ (const void * a, const void * b);#endif

differ用于對(duì)比Objects是否相等。

一個(gè)小應(yīng)用

這也是這里說(shuō)明的重點(diǎn)，不同的實(shí)現(xiàn)方式但是表現(xiàn)形式是一樣的，這就達(dá)到了數(shù)據(jù)抽象的效果，同一個(gè)應(yīng)用程序框架，底層更換之后，程序還是能正常運(yùn)行。

#include <stdio.h>#include "new.h" #include "Object.h" #include "Set.h"int main () { /* 新建一個(gè)Set對(duì)象 */void * s = new(Set); //*s = 10/* 將一個(gè)新建的Object添加到s中 */void * a = add(s, new(Object)); //*a = 1/* 將一個(gè)新建的Object添加到s中 */ void * b = add(s, new(Object)); // *b = 1/* 新建一個(gè) Object 對(duì)象*/void * c = new(Object); // *c = 10/* s中是佛包含 a 是否包含b */if (contains(s, a) && contains(s, b))puts("ok");/* s中是否含有c */if (contains(s, c))puts("contains?");/* a, add(s, a)) 相同*/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; } #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/* 定義一個(gè)數(shù)組用于模擬堆 */ static int heap [MANY];/* 創(chuàng)建一個(gè)對(duì)象，這里使用在堆里賦值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; } /* 刪除一個(gè)對(duì)象，將對(duì)應(yīng)數(shù)組中的值進(jìn)行清空表示 */ void delete (void * _item) { int * item = _item;if (item){ assert(item > heap && item < heap + MANY);* item = 0;} } /* 向_set中添加一個(gè) _element元素 */ 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;elseassert(* element == set - heap);return (void *) element; } /* 查找_set中是否有_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; } /* 將_set是否包含_element轉(zhuǎn)換為是否為真 */ int contains (const void * _set, const void * _element) {return find(_set, _element) != 0; } /* 從_set中刪除 _element */ void * drop (void * _set, const void * _element) { int * element = find(_set, _element);if (element)* element = MANY;return element; } /* 對(duì)比a與b是否相同 */ int differ (const void * a, const void * b) {return a != b; }

到這里整個(gè)set的例子就結(jié)束了，接下來(lái)看下Bags的例子，通過(guò)這兩個(gè)例子的對(duì)比你就能明白如何通過(guò)設(shè)計(jì)良好的數(shù)據(jù)類型也就是對(duì)數(shù)據(jù)進(jìn)行抽象，來(lái)達(dá)到代碼復(fù)用，同一個(gè)應(yīng)用程序，調(diào)用同樣的接口來(lái)達(dá)到不同的目的。

---

另外一個(gè)例子—Bag

Bag例子使用的主函數(shù)和set一樣但是實(shí)現(xiàn)不一樣，達(dá)到的效果就是對(duì)數(shù)據(jù)進(jìn)行抽象之后，使用同一個(gè)框架運(yùn)行不同的底層程序。

在不改變方法的情況下，我們可以改變方法的實(shí)現(xiàn)，在Bag中我們使用動(dòng)態(tài)內(nèi)存管理來(lái)實(shí)現(xiàn)

在Bag中Set和Object表現(xiàn)形式如下，是兩個(gè)結(jié)構(gòu)體

count -- 用于記錄Set中元素的個(gè)數(shù)，也可以說(shuō)count是記錄有多少次element add到Set中了 struct Set { unsigned count; }; struct Object { unsigned count; struct Set * in; };

因?yàn)槭褂脛?dòng)態(tài)內(nèi)存呈現(xiàn)sets和objects我們需要初始化描述下Set和Object，new可以定位到需要為新的對(duì)象申請(qǐng)多少內(nèi)存。

static const size_t _Set = sizeof(struct Set); static const size_t _Object = sizeof(struct Object);const void * Set = & _Set; const void * Object = & _Object;

主函數(shù)中申請(qǐng)內(nèi)存使用的方式是void * s = new(Set); * (const size_t *) type就相當(dāng)于* (const size_t *) Set大小剛好等于Set

new函數(shù)很好理解就是使用calloc申請(qǐng)固定大小的內(nèi)存，并將內(nèi)存的指針賦返回給要New的對(duì)象

void * new (const void * type, ...) { const size_t size = * (const size_t *) type;void * p = calloc(1, size);assert(p);return p; } The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

delete方法只是對(duì)free的一個(gè)簡(jiǎn)單封裝而已，直接將需要釋放內(nèi)存的指針傳遞給free就可以了，當(dāng)然這里只是一個(gè)玩具代碼，真正使用的代碼需要對(duì)釋放的對(duì)象進(jìn)行合法性檢測(cè)。

void delete (void * item) {free(item); }

add方法將element元素add到對(duì)應(yīng)的set對(duì)象中，add之后對(duì)set中的count和element中的count進(jìn)行遞增，用于統(tǒng)計(jì)set中add element個(gè)數(shù)。

void * add (void * _set, const void * _element) { struct Set * set = _set;struct Object * element = (void *) _element;assert(set);assert(element);if (! element -> in)element -> in = set;elseassert(element -> in == set);++ element -> count, ++ set -> count;return element; }

find 函數(shù)作用就是檢查對(duì)應(yīng)的element是否已經(jīng)add進(jìn) set了，一旦add之后element -> in == _set將會(huì)成立🉑

void * find (const void * _set, const void * _element) { const struct Object * element = _element;assert(_set);assert(element);return element -> in == _set ? (void *) element : 0; }

contains和Set.c中實(shí)現(xiàn)的一樣，contains函數(shù)依然時(shí)對(duì)find函數(shù)的一個(gè)封裝，find函數(shù)返回非0的時(shí)候也就是在set中已經(jīng)添加了對(duì)應(yīng)的元素element

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

drop函數(shù)

void * drop (void * _set, const void * _element) { struct Set * set = _set;struct Object * element = find(set, _element);if (element){ if (-- element -> count == 0)element -> in = 0;-- set -> count;}return element; }

Count函數(shù)，用于提供set中add的element個(gè)數(shù)

雖然更加快捷的方法是直接調(diào)用set->Count但是最好不要這樣做，這樣會(huì)破壞數(shù)據(jù)的封裝性。

unsigned count (const void * _set) { const struct Set * set = _set;assert(set);return set -> count; }

differ函數(shù)

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

主函數(shù)

#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; }

---

執(zhí)行結(jié)果

andrew@DESKTOP-GDC67HT:/mnt/u/linux-sys/ooc/test/c.01$ ./sets ok andrew@DESKTOP-GDC67HT:/mnt/u/linux-sys/ooc/test/c.01$ ./bags ok drop?

執(zhí)行結(jié)果可以看出bags比sets多一個(gè)drops打印，這是因?yàn)閍被add了兩次，但是sets中無(wú)論添加多少次都只是被添加一次，所以drop之后就不在set里面了，但是bags能夠添加多次，a添加了兩次到那時(shí)drop一次，所以a還是在s中。

總結(jié)

對(duì)比Set.c和Bag,c可以發(fā)現(xiàn)，抽象數(shù)據(jù)類型其實(shí)實(shí)現(xiàn)的就是將數(shù)據(jù)進(jìn)行抽象之后，表現(xiàn)出同樣的接口。

在抽象數(shù)據(jù)中屏蔽所有的數(shù)據(jù)類型實(shí)現(xiàn)細(xì)節(jié)，暴露給用戶的是一個(gè)個(gè)應(yīng)用調(diào)用的接口。

總結(jié)

以上是生活随笔為你收集整理的面向对象C语言编程--抽象数据类型-AbstractDataTypes的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。