第5章
5.1 单链表
/* -------------------------------- list.h -------------------------------- */
#ifndef LIST_H
#define LIST_H #include <stdlib.h> /* Define a structure for linked list elements.*/
typedef struct ListElmt_
{
void *data;
struct ListElmt_ *next;
} ListElmt; /* Define a structure for linked lists.*/
typedef struct List_
{
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
ListElmt *head;
ListElmt *tail;
} List; /* --------------------------- Public Interface --------------------------- */
void list_init(List *list, void (*destroy)(void *data));//whl-?其destroy参数的用法？
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 <stdlib.h>
#include <string.h>
#include "list.h"
/* ------------------------------- list_init ------------------------------ */
void list_init(List *list, void (*destroy)(void *data))//若链表包含不该释放的数据，则destroy应设置为NULL
{
/* Initialize the list. */
list->size = ;
list->destroy = destroy;//把函数指针成员destroy设置为定义的析构函数
list->head = NULL;
list->tail = NULL;
return;
}
/* ----------------------------- list_destroy ----------------------------- */
void list_destroy(List *list)//若传给list_init的参数destroy不为NULL，则移除链表中每个元素时都调用该函数一次
{
void *data;
/* Remove each element. */
while (list_size(list) > )
{
if (list_rem_next(list, NULL, (void **)&data) == && list->destroy != NULL)
{
/* Call a user-defined function to free dynamically allocated data. */
list->destroy(data);
}
}
/* No operations are allowed now, but clear the structure as a precaution. */
memset(list, , sizeof(List));
return;
}
/* ----------------------------- list_ins_next ---------------------------- */
int list_ins_next(List *list, ListElmt *element, const void *data) //在list指定的链表中element后面插入一个新元素
{
ListElmt *new_element;
/* Allocate storage for the element. */
if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
{
return -;
}
/* Insert the element into the list. */
//new_element->data = (void *)data;
new_element->data = (void *)data;
if (element == NULL) //若element设置为NULL，则新元素插入链表头部
{
/* Handle insertion at the head of the list. */
if (list_size(list) == )
list->tail = new_element;
new_element->next = list->head;
list->head = new_element;
}
else
{
/* Handle insertion somewhere other than at the head. */
if (element->next == NULL)
list->tail = new_element;
new_element->next = element->next;
element->next = new_element;
}
/* Adjust the size of the list to account for the inserted element. */
list->size++;
return ;
}
/* ----------------------------- list_rem_next ---------------------------- */
int list_rem_next(List *list, ListElmt *element, void **data)//移除由list指定的链表中element后的那个元素
{
ListElmt *old_element; /* Do not allow removal from an empty list. */
if (list_size(list) == )
return -; /* Remove the element from the list. */
if (element == NULL)//若element设置为NULL，则移除链表头部元素
{
/* Handle removal from the head of the list. */
*data = list->head->data;
old_element = list->head;
list->head = list->head->next;
if (list_size(list) == )
list->tail = NULL;
}
else {
/* Handle removal from somewhere other than the head. */
if (element->next == NULL)
return -;
*data = element->next->data;
old_element = element->next;
element->next = element->next->next;
if (element->next == NULL)
list->tail = element;
}
/* Free the storage allocated by the abstract data type. */
free(old_element);
/* Adjust the size of the list to account for the removed element. */
list->size--;
return ;
}