C 算法精介----链表
C算法 ---链表 链表是一种最为基础的数据结构，链表是由一组元素以一种特定的顺序组合或链接在一起的。在维护数据的集合时很有用途。在平时的数据处理过程中经常会会用链接进行数据的临时存储。但是如何才能使链表处理数据更加优化，下面简单介绍单链表处理情况！ 1 、单链表介绍 单链表是各个元素之间通过一个指针彼此连接起来而组成的。元素可以分为2个部分：数据成员和一个称为nest的指针。通过这种2成员结构，将每个元素的next指针指向其元素后面的指针。为了更能描述这种结构可以看下图：
#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 Intefaces */void list_init(List *list, void (*destroy)(void *data));void list_destory(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(list, element) ((element) == (list) -> tail ? 1:0)#define list_data(element) ((element) -> data)#define list_next(element) ((element) -> next)#endif示例2 链表抽象数据类型的实现#include <studio.h>#include <string.h>#include "../include/List.h"/*list_init */void list_init(List * list, void(* destroy)(void * data)) { /* initialize the list */ list -> size = 0; list -> destroy = destroy; list -> head = NULL; list -> tail = NULL; return ;}/*list_destroy */void list_destory(List * list) { void *data; /*Remove eah element */ while (list_size(list) > 0){ if (list_rem_next(list, NULL, (void **) &data) == 0 && list -> destroy != NULL){ /* Call a user-defined function to free dynamically allocated data*/ list -> destroy(data); } } memset(list, 0, sizeof(List)); return;}/*list_ins_nest */int list_ins_next (List * list, ListElmt * element, const void * data){ ListElmt *new_element; /* Allocate storage for the element */ if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL){ return -1; } /*insert the element into the list */ new_element ->data =(void *)data; if (element == NULL){ /* handle insertion at the head of the list */ if (list_size(list) == 0){ 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; } list->size ++; return 0; }/* list_rem_next */int list_rem_next(List * list, ListElmt * element, void * data) { ListElmt *old_element; /* Do not allow removal from an emptry list */ if (list_size(list) == 0){ return -1; } /* romove the element from the list */ if (element == NULL){ /* handle removel from the 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 { /* handle removal from somewhere other than the head */ if ( element->next == NULL){ return -1; } *data = element->next->data; old_element = element->next; element->next = element->next->next; if (element ->next == NULL){ list->tail = NULL; } } /* free the storage allocated by the abstract datatype*/ free(old_element); list->size --; return 0;}