《算法精讲：C语言描述》-单链表实现代码

list.h

#ifndef LIST_H #define LIST_H #include <stdlib.h> typedef struct ListElmt_ { void *data; struct ListElmt_ *next; }ListElmt; typedef struct List_ { int size; int (*match)(const void *key1, const void *key2); void(*destroy)(void *data); ListElmt *head; ListElmt *tail; }List; void list_init(List *list,void(*destroy)(void *data)); void list_destroy(List *list); int list_ins_next(List *list, ListElmt *element, const void *data); int list_rem_next(List *list, ListElmt *element, void **data); #define list_size(list) ((list)->size) #define list_head(list) ((list)->head) #define list_tail(list) ((list)->tail) #define list_is_head(list,element) ((element)==(list)->head?1:0) #define list_is_tail(element) ((element)->next==NULL?1:0) #define list_data(element) ((element)->data) #define list_next(element) ((element)->next) #endif

list.c

#include "list.h" #include <stdlib.h> #include <string.h> /* 函数名称：list_init 函数功能：初始化由参数list指定的链表 返回值：无 */ void list_init(List *list, void(*destroy)(void *data)) { list->size = 0; list->destroy = destroy; list->head = NULL; list->tail = NULL; return; } /* 函数名称：list_destroy 函数功能：销毁由参数list指定的链表 返回值：无 */ void list_destroy(List *list) { void *data; while (list_size(list) > 0) { /* 条件判断：1 移除是否成功 2 销毁指针函数是否为空 */ if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) list->destroy(data); } memset(list, 0, sizeof(List)); return; } /* 函数名称：list_ins_next 函数功能：在list指定的链表element后面插入一个新的元素 返回值：如果插入成功返回0，失败返回-1 */ 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 = data; //赋值 if (element == NULL) //判断当前链表是否为空，根据此条件判断是否为头结点 { //head of the list if (list->size == 0) list->tail = new_element; //尾指针处理 new_element->next = list->head; //插入链表节点的下一个指针地址指向NULL list->head在初始化时为NULL list->head = new_element; //头结点指针赋值 } else { if (element->next == NULL) //判断是否为尾节点 list->tail = new_element; //尾指针处理 //插入处理 new_element->next = element->next; element->next = new_element; } list->size++; //链表长度加1 return; } /* 函数名称：list_rem_next 函数功能：删除在list指定的链表element后面的元素 返回值：如果移除成功返回0，失败返回-1 */ int list_rem_next(List *list, ListElmt *element, void **data) { ListElmt *old_element; if (list_size(list) == 0) //判断链表长度 如果无元素则退出 return -1; if (element == NULL) //判断是否为头结点 即只有1个元素 { //head of the list *data = list->head->data; //数据赋值 //链表删除操作 old_element = list->head; list->head = list->head->next; //删除之后的尾指针操作 if (list_size(list) == 1) list->tail = NULL; } else { //判断是否为尾指针 if (element->next == NULL) return -1; //数据获取 *data = element->next->data; //链表删除操作 old_element = element->next; element->next = element->next->next; } free(old_element); //释放申请的内存 list->size--; //链表长度减1 return; }