本文共 4490 字，大约阅读时间需要 14 分钟。
typedef struct listNode { struct listNode *prev; struct listNode *next; void *value;} listNode;typedef struct list { listNode *head; listNode *tail; void *(*dup)(void *ptr); void (*free)(void *ptr); int (*match)(void *ptr, void *key); unsigned int len; listIter iter;} list; list *listCreate(void){ struct list *list; if ((list = zmalloc(sizeof(*list))) == NULL) return NULL; list->head = list->tail = NULL; list->len = 0; list->dup = NULL; list->free = NULL; list->match = NULL; return list;}void listRelease(list *list){ unsigned int len; listNode *current, *next; current = list->head; len = list->len; while(len--) { next = current->next; if (list->free) list->free(current->value); zfree(current); current = next; } zfree(list);}/* * 从头结点增加元素，即采用的是头插入法 * 发生错误时将返回NULL */list *listAddNodeHead(list *list, void *value){ listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; //空链表时的处理情况 if (list->len == 0) { list->head = list->tail = node; node->prev = node->next = NULL; } else { node->prev = NULL; node->next = list->head; list->head->prev = node; list->head = node; } list->len++; return list;}/* * 采用尾插入法向链表中增加元素 * value是向链表中增加的值 * 如果增加失败的话会返回空指针 */list *listAddNodeTail(list *list, void *value){ listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = value; if (list->len == 0) { list->head = list->tail = node; node->prev = node->next = NULL; } else { node->prev = list->tail; node->next = NULL; list->tail->next = node; list->tail = node; } list->len++; return list;}void listDelNode(list *list, listNode *node){ if (node->prev)//判断删除节点是不是第一个节点 node->prev->next = node->next; else list->head = node->next; if (node->next)//删除尾结点时的特殊处理情况 node->next->prev = node->prev; else list->tail = node->prev; //如果链表结构中定义了结点释放函数，则调用注册的函数 if (list->free) list->free(node->value); zfree(node); list->len--;} /* * 链表的复制函数 * 复制成功后，返回复制链表的头节点 */list *listDup(list *orig){ list *copy;//复制链表的头指针 listIter *iter; listNode *node; //创建链表的头节点 if ((copy = listCreate()) == NULL) return NULL; //设置链表的复制函数 copy->dup = orig->dup; //设置链表的释放函数 copy->free = orig->free; //设置链表的匹配函数 copy->match = orig->match; //获取链表的迭代器 iter = listGetIterator(orig, AL_START_HEAD); //开始遍历链表，并复制链表中的元素值 while((node = listNext(iter)) != NULL) { void *value; if (copy->dup) { value = copy->dup(node->value); if (value == NULL) { //复制失败时的情况 listRelease(copy);//将复制一半的链表释放掉 listReleaseIterator(iter);//释放链表的迭代器 return NULL; } } else//这样会产生弱拷贝 value = node->value; //将该值采用尾结点的方式进行插入 if (listAddNodeTail(copy, value) == NULL) { //插入失败的情况下进行资源的回收 listRelease(copy); listReleaseIterator(iter); return NULL; } } //复制完成后将迭代器所占用的内存空间释放掉 listReleaseIterator(iter); return copy;}listNode *listSearchKey(list *list, void *key){ listIter *iter; listNode *node; iter = listGetIterator(list, AL_START_HEAD); while((node = listNext(iter)) != NULL) { if (list->match) { //如果给链表设置了匹配函数的话，采用链表自身的匹配函数 if (list->match(node->value, key)) { //如果匹配成功的话 listReleaseIterator(iter);//释放迭代器所占用的内存空间 return node;//返回链表当前的结点 } } else { //如果未设置match函数的话 if (key == node->value) { //直接比较指针里的地址 listReleaseIterator(iter);//释放迭代器所占用的内存空间 return node;//返回链表当前的结点 } } } listReleaseIterator(iter);//释放迭代器所占用的内存空间 return NULL;}/* * 返回指定索引位置的元素 * index表示索引位置，从0开始 * 如果index超了链表的长度NULL将返回 * 负数表示从尾开始算起，即倒数 */listNode *listIndex(list *list, int index) { listNode *n; //-1表示尾节点 //-2表示的是尾节点的下一个节点 if (index < 0) { index = (-index)-1; n = list->tail; while(index-- && n) n = n->prev; } else { //从头开始进行遍历时0指向head //1指向头节点的下一个元素 n = list->head; while(index-- && n) n = n->next; } //返回索引位置的节点 return n;} 转载地址：http://kkorb.baihongyu.com/