id *data)) { //初始化list
list->size = 0;
list->destroy = destroy; //设置为定义的析构函数
list->head = NULL;
list->tail = NULL;
return;
}
回收单链表：
void list_destroy(List *list) {
//移除每一个元素
while (list_size(list) > 0) {
if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) { //不断地移除链表的头结点
list->destroy(data); //调用一个用户定义的函数来释放动态分配的数据.
}
}
//现在没有操作了,释放结构体作为预防措施
memset(list, 0, sizeof(List));
return;
}
插入新节点作为指定结点的直接后继结点:
int list_ins_next(List *list, ListElmt *element, const void *data) {
ListElmt *new_element; //为结点动态分配存储空间
if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) //假如分配失败
return -1;
// 将元素插入链表
new_element->data = (void *)data;
if (element == NULL) {
//插入到链表的头部
if (list_size(list) == 0)
list->tail = new_element;
new_element->next = list->head;
list->head = new_element;
} else {
//插入到除了链表头部以外指定的其他地方
if (element->next == NULL)
list->tail = new_element;
new_element->next = element->next;
element->next = new_element;
}
list->size++; //表长增加
return 0;
}
删除指定结点的直接后继结点:
int list_rem_next(List *list, ListElmt *element, void **data) {
ListElmt *old_element;
//不允许从一个空的list中移除元素.
if (list_size(list) == 0)
return -1;
// 从list中移除元素.
if (element == NULL) {
// 移除表头的结点.
*data = list->head->data;
old_element = list->head;
list->head = list->head->next;
if (list_size(list) == 1) //如果list只有一个元素，则直接删除尾结点
list->tail = NULL;
} else {
// 移除非头结点.
if (element->next == NULL)
return -1;
*data = element->next->data;
old_element = element->next;
element->next = element->next->next;
if (element->next == NULL) //移除指定结点后，后继为NULL，则用尾结点指向
list->tail = element;
}
//释放分配的抽象数据类型.
free(old_element);
//调整list的长度. *
list->size--;
return 0;
}
注意：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、list_next 这些宏实现了链表中的一些简单操作，它们提供了快速访问和检测结构体成员的能力。这些操作的时间复杂度都是O(1)
完整的测试代码如下：
// Completed on 2014.10.22 21:00
// Language: C99
//
// 版权所有（C）codingwu (mail: oskernel@126.com)
// 博客地址：http://www.cnblogs.com/archimedes/
#include
#include
#include "list.h"
static void print_list(const List *list) {
ListElmt *element;
int *data, i;
fprintf(stdout, "List size is %d\n", list_size(list));
i = 0;
element = list_head(list);
while (1) {
data = list_data(element);
fprintf(stdout, "list[%03d]=%03d\n", i, *data);
i++;
if (list_is_tail(element))
break;
else
element = list_next(element);
}
return;
}
int main(int argc, char **argv) {
List list;
ListElmt *element;
int *data, i;
//初始化list
list_init(&list, free);
element = list_head(&list);
for (i = 10; i > 0; i--) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = i;
if (list_ins_next(&list, NULL, data) != 0) //逐个插入元素
return 1;