实现通用的双向链表（c语言实现） |
您所在的位置：网站首页 › c语言链表实例 › 实现通用的双向链表（c语言实现） |
实现通用的双向链表（c语言实现）
|
国庆8天在家阅读李先静大神的书籍，抽空把一些笔记记录下来。从实现一个通用的双向链表开始。 1. 构建链表节点链表节点存值还是存值的地址(指针)？对于通用链表首先要做到能够存放任何数据类型的数据，首先可能会想到的是union，但是数据类型无穷无尽，不可能在union中全部表示。那么可行的办法有两种： (1) 存值 typedef struct _DListNode DListNode; struct _DListNode { DListNode* prev; DListNode* next; void* data; size_t length; };存值即在构建节点时实现深度拷贝源数据，void* data;用于保存拷贝的目的地址，size_t length;用于保存目的地址占据的内存大小。 (2) 存变量的地址 typedef struct _DListNode DListNode; struct _DListNode { DListNode* prev; DListNode* next; void* data; };只保存值的地址，存取效率高，是c语言中常见的做法，在存放整数时可以把void*强制转换整数使用。 c语言的结构体并没有构造函数，要实现深度拷贝会比较麻烦，所以在c语言中的链表的节点通常是以存指针的方式。 2. 链表打印函数对专用双向链表，链表打印函数的实现非常简单，若里面存放的是整数即用%d打印，存放的字符串则用%s打印。但是对于通用的双向链表，程序员无法事先预知里面的数据类型，这就需要到回调函数：程序员无法事先知道链表里面的数据类型，但是使用该链表的用户知道，所以打印函数可以让用户提供。 DListNode* iter = thiz->first; while (iter != NULL) { print(iter->data); iter = iter->next; }显然需要定义一个函数指针：变量指针指向的是一块数据，指针指向不同的变量则可取到不同的数据；函数指针指向的是一个函数，即一段代码，指针指向不同的函数即具有不同的行为。 定义函数指针类型： typedef DListRet (*DListDataPrintFunc)(void* data);实现链表打印函数dlist_print()： void dlist_print(DList* thiz, DListDataPrintFunc print) { DListNode* iter = thiz->first; while (iter != NULL) { print(iter->data); iter = iter->next; } }使用方法： static DListRet print_int(void* data) { printf("%d", (int*)data); return DLIST_RET_OK } //... dlist_print(dist, print_int); 3. 链表遍历函数实现功能：在一个存放整数的双向链表中找出其中的最大值、累加链表中的所有整数。针对这两个功能初学者一般会编写两个函数：dlist_find_max()和dlist_print()，但是仔细一想就会发现，这两个函数的实现体大部分是跟dlist_print()一样的，即同样的要遍历链表，因此我们可以提供dlist_foreach()函数遍历双向链表，至于遍历过程要做什么，可以通过回调函数让调用者做这些事情。 回调函数的原型为： DListRet dlist_foreach(DList* thiz, DListVisitFunc visit, void* ctx) { DListRet ret = DLIST_RET_OK; DListNode* iter = thiz->first; while (iter != NULL && ret != DLIST_RET_STOP) { ret = visit(ctx, iter->data); iter = iter->next; } return ret; }dlist_foreach()函数有3个参数，thiz指向该双向链表，DListVisitFunc是一个函数指针，用于遍历链表节点时候的回调，ctx是传给DListVisitFunc的参数。DListVisitFunc的原型为： typedef DListRet (*DListVisitFunc)(void* ctx, void* data);那么累加求和的回调函数为： static DListRet sum_cb(void* ctx, void* data) { long *ret = ctx; *ret += (int)data; return DLIST_RET_OK; }调用dlist_foreach()： long sum = 0; dlist_foreach(thiz, sum_cb, &sum); 4. 实现代码不论是哪种链表都可以分为有头链表/无头链表，前者是头节点是一个节点变量，后者是头节点是一个头节点指针，也就是它只是占据一个地址大小。在这里的双向链表是无头链表，但是链表的开头是一个DList结构体指针，成员为： first指针：用于指向链表的真正头节点 data_destroy()：销毁链表节点的回调 data_destroy_ctx：销毁回调函数的传参具体实现如下： //dlist.h #include #ifndef __DLIST_H__ #define __DLIAT_H__ //用c语言的方式编译 #ifdef __cplusplus extern "C"{ #endif /* _cplusplus */ //枚举，函数的返回值类型 typedef enum _DListRet { DLIST_RET_OK, DLIST_RET_OOM, DLIST_RET_STOP, DLIST_RET_PARAMS, DLIST_RET_FAIL }DListRet; //DList用于描述整个链表，定义在dlist.cpp中 struct _DList; typedef struct _DList DList; //销毁节点的回调 typedef void (*DListDataDestroyFunc)(void* ctx, void* data); //节点数据比较回调 typedef int (*DListDataCompareFunc)(void* ctx, void* data); //遍历链表时的回调 typedef DListRet (*DListDataVisitFunc)(void* ctx, void* data); //可供调用者使用的链表操作函数 DList* dlist_create(DListDataDestroyFunc data_destroy, void* data_destroy_ctx); DListRet dlist_insert(DList* thiz, size_t index, void* data); DListRet dlist_prepend(DList* thiz, void* data); DListRet dlist_append(DList* thiz, void* data); DListRet dlist_delete(DList* thiz, size_t index); DListRet dlist_get_by_index(DList* thiz, size_t index, void** data); DListRet dlist_set_by_index(DList* thiz, size_t index, void* data); size_t dlist_length(DList* thiz); int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx); DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx); void dlist_destroy(DList* thiz); #ifdef __cplusplus } #endif /* _cplusplus */ #endif /* __DLIST_H__ */ #include "dlist.h" //链表节点描述 typedef struct _DListNode { struct _DListNode* pre; struct _DListNode* next; void* data; }DListNode; //链表描述 struct _DList { DListNode* first; DListDataDestroyFunc data_destroy; void* data_destroy_ctx; }; /************************** 内部使用的函数 ****************************/ //销毁一个节点的data成员，调用回调函数销毁 static void _dlist_destroy_data(DList* thiz, void* data) { if (thiz->data_destroy != NULL) { thiz->data_destroy(thiz->data_destroy_ctx, data); } return; } //产生一个节点 static DListNode* _dlist_create_node(DList* thiz, void* data) { DListNode* node = malloc(sizeof(DListNode)); if (node != NULL) { node->pre = NULL; node->next = NULL; node->data = data; } return node; } //通过index获取一个节点 static DListNode* _dlist_get_node(DList* thiz, size_t index, int fail_return_last) { DListNode* iter = thiz->first; while (iter != NULL && iter->next != NULL && index > 0) { iter = iter->next; index--; } if (!fail_return_last) { iter = index > 0 ? NULL : iter; } return iter; } //销毁一个节点 static void _dlist_destroy_node(DList* thiz, DListNode* node) { if (node != NULL) { node->next = NULL; node->pre = NULL; _dlist_destroy_data(thiz, node->data); free(node); } return; } /************************** 调用者可使用的函数 ****************************/ //链表生成，参数分别为销毁节点data的回调以及回调的参数 DList* dlist_create(DListDataDestroyFunc data_destroy, void* data_destroy_ctx) { DList* thiz = malloc(sizeof(DList)); if (thiz != NULL) { thiz->first = NULL; thiz->data_destroy = data_destroy; thiz->data_destroy_ctx = data_destroy_ctx; } return thiz; } DListRet dlist_insert(DList* thiz, size_t index, void* data) { DListNode* node = NULL; DListNode* cursor = NULL; //构造节点 if ((node = _dlist_create_node(thiz, data)) == NULL) { return DLIST_RET_OOM; } //第一个节点 if (thiz->first == NULL) { thiz->first = node; return DLIST_RET_OK; } //获取目标节点位置，1表示若超过链表长度length，则插在最后 cursor = _dlist_get_node(thiz, index, 1); //插入链表中间位置 if (index first == cursor) { thiz->first = node; } //插入数据中间 else { node->pre = cursor->pre; cursor->pre->next = node; } node->next = cursor; cursor->pre = node; } //尾插 else { cursor->next = node; node->pre = cursor; } } //头插 DListRet dlist_prepend(DList* thiz, void* data) { return dlist_insert(thiz, 0, data); } //尾插 DListRet dlist_append(DList* thiz, void* data) { return dlist_insert(thiz, -1, data); } //删除一个节点 DListRet dlist_delete(DList* thiz, size_t index) { //获取目标节点位置，0表示index超过length就返回NULL DListNode* cursor = _dlist_get_node(thiz, index, 0); if (cursor != NULL) { if (cursor == thiz->first) { thiz->first = cursor->next; } if (cursor->next != NULL) { cursor->pre->next = cursor->next; } if (cursor->pre != NULL) { cursor->next->pre = cursor->pre; } _dlist_destroy_node(thiz, cursor); } return DLIST_RET_OK; } //通过index获取一个节点的data DListRet dlist_get_by_index(DList* thiz, size_t index, void** data) { DListNode *cursor = _dlist_get_node(thiz, index, 0); if (cursor != NULL) { *data = cursor->data; } return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL; } //通过index设置一个节点的data DListRet dlist_set_by_index(DList* thiz, size_t index, void* data) { DListNode *cursor = _dlist_get_node(thiz, index, 0); if (cursor != NULL) { cursor->data = data; } return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL; } //获取链表的长度 size_t dlist_length(DList* thiz) { size_t length = 0; DListNode* iter = thiz->first; while (iter != NULL) { length++; iter = iter->next; } return length; } //插摘目标数据所在的节点，比较函数采用回调的方法 int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx) { int i = 0; DListNode* iter = thiz->first; while (iter != NULL) { if (cmp(ctx, iter->data) == 0) { break; } i++; iter = iter->next; } return i; } //遍历链表，并调用回调函数 DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx) { DListRet ret = DLIST_RET_OK; DListNode* iter = thiz->first; while (iter != NULL && ret != DLIST_RET_STOP) { ret = visit(ctx, iter->data); iter = iter->next; } return ret; } //销毁整个链表 void dlist_destroy(DList* thiz) { DListNode* iter = thiz->first; DListNode* next = NULL; while (iter != NULL) { next = iter->next; _dlist_destroy_node(thiz, iter); iter = next; } thiz->first = NULL; free(thiz); return; }main.c中首先测试链表操作： //main.c #include "dlist.h" #include DListRet print(void* ctx, void* data) { printf("%c ", *(int*)data); return DLIST_RET_OK; } static void dlist_temp(void) { int char_arr[] = {'a', 'b', 'c', 'd', 'e'}; int i; char tmpc = 'A'; char *tmppc = &tmpc; DList* dlist = dlist_create(NULL, NULL); for (i = 0; i < 5; i++) { dlist_append(dlist, &char_arr[i]); } dlist_foreach(dlist, print, NULL); printf("\n"); dlist_insert(dlist, 0, &tmpc); dlist_foreach(dlist, print, NULL); printf("\n"); dlist_prepend(dlist, &tmpc); dlist_foreach(dlist, print, NULL); printf("\n"); dlist_append(dlist, &tmpc); dlist_foreach(dlist, print, NULL); printf("\n"); dlist_delete(dlist, 2); dlist_foreach(dlist, print, NULL); printf("\n"); dlist_get_by_index(dlist, 4, (void**)&tmppc); printf("**tmppc = %c\n", *(char*)tmppc); } int main(int argc, char* argv[]) { dlist_temp(); return 0; } 运行： |
【本文地址】
今日新闻 |
推荐新闻 |