<file_sep>/* dlist.c */

#include <stdlib.h>
#include <string.h>

#include "dlist.h"

/* dlist_init */
void dlist_init(Dlist *list, void (*destory)(void *data)){
	/* Initialize the list */
	list->size = 0;
	list->destory = destory;
	list->head = NULL;
	list->tail = NULL;
	return;
}

/* dlist_destory  */
void dlist_destory(Dlist *list){
	void *data;
	/* remove  each element*/
	while(dlist_size(list) > 0){
		if(dlist_remove(list,dlist_tail(list), (void **)&data) == 0 && list->destory != NULL){
			/*Call a user-defined function to free dynamixally allcoated data */
			list->dstory(data);
		}
	}
	/* No operations are allowed now , but clear the structure as a precaution */
	memset(list, 0, sizeof(Dlist));
	return;
}

/* dlist_ins_next */
int dlist_ins_next(Dlist *list, DlistElmet *element, const void *data){
	DlistElmet *new_element;
	/* Do not allow a NULL element unless the list is empty */
	if(element == NULL && dlist_size(list) != 0)
		return -1;
	/* Allcoate storage for the element */
	if((new_element = (DlistElmet *)malloc (sizeof(DlistElmet))) == NULL )
		return -1;
	/* Insert the new element into the list*/
	new_element->data = (void *)data;
	if(dlist_size(list) == 0){
		/* Handle insertion when the list is empty*/
		list->head = new_element;
		list->head->prev = NULL;
		list->head->next = NULL;
		list->tail = new_element;
	}
	else{
		/* Handle inseration when the list is not empty*/
		new_element->next = element->next;
		new_element->prev = element;
		if(element->next == NULL)
			list->tail = new_element;
		else
			element->next->prev = new_element;
		element->next = new_element;
	}

	/* Adjust the size of the list to account for the inserted element */
	list->size++;
	return 0;
}

/* dlist_ins_prev */
int dlist_ins_prev(Dlist *list, DlistElmet *element, const void *data){
	DlistElmet *new_element;
	/* Do not allow a NULL element unless the list is empty */
	if(element == NULL && dlist_size(list) != 0)
		return -1;
	/* Allcoate storage for the element */
	if((new_element = (DlistElmet *)malloc (sizeof(DlistElmet))) == NULL )
		return -1;
	/* Insert the new element into the list*/
	new_element->data = (void *)data;
	if(dlist_size(list) == 0){
		/* Handle insertion when the list is empty*/
		list->head = new_element;
		list->head->prev = NULL;
		list->head->next = NULL;
		list->tail = new_element;
	}
	else{
		/* Handle inseration when the list is not empty*/
		new_element->next = element;
		new_element->prev = element->prev;
		if(element->next == NULL)
			list->head = new_element;
		else
			element->prev = new_element;
		element->prev = new_element;
	}

	/* Adjust the size of the list to account for the inserted element */
	list->size++;
	return 0;
}

/* dlist_remove*/
int dlist_remove(Dlist *list, DlistElmet *element, void **data){
	/* Do not allow a NULL element or removal from an empty list*/
	if(element == NULL || dlist_size(list) == 0)
		return -1;
	/* remove the elemnet from the list*/
	*data = element->data;
	if(element == list->data){
		/*Handle removal from thee head of the list*/
		list->head = element->next;
		if(list->head == NULL)
			list->tail =NULL;
		else
			element->next->prev = NULL;
	}
	else{
		/* Handle removal from other than the head of the list*/
		element->prev->next == element->next;
		if(element->next == NULL)
			list->tail = element->prev;
		else
			element->next->prev = element->prev;

	}
	/*Free the storage allcoated by the abstract datatype*/

	free(element);

	list->size--;
	return 0;

}
<file_sep>/* list.c */
#include <stdllib.h>
#include <string.h>

#include "list.h"

/* list_init */
void list_init(List *list, void (*destory)(void *data)){
	list->size = 0;
	list->head = NULL;
	list->tail = NULL;
	return;
}

/* list_destory */
void list_destory(List *list){
	void *data;
	while(list_size(list) > 0){
		if(list_rem_next(list, NULL, (void **)&data) == 0 && list->destory != NULL){
			/*call a user-defined function to free dynamically allocated data */
			list->destory(data);
		}
	}
	memset(list, 0, sizeof(List));
	return;
}

/* list_ins_next */
int list_ins_next(List *list, ListElmt *element, const void *data){
	ListElmt *new_element;
	/* Allocate storge 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{
			/*  */
			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;
	if(list_size(list) == 0)
		return -1;
	if(element == NULL){
		/*handle remeoval from th head of the list*/
		*data = list->head->data;
		old_element = list->head;
		if(list_size(list) == 1)
			list->tail =NULL;
	}
	else{
		if(element->naxt == NULL)
			return -1;
		*data =  element->next->data;
		old_element = element->nextl
		element0->next = element0->next->next;
		if(element->next =NULL)
			list->tail = element;
	}

	/* Fress the sorafe allcoated by the abstract datatype  */
	free(old_element);
	/*Adjust the size of the list to account for the emoved element*/
	list->size--;
	return 0;

}<file_sep>/* stack.h */
#ifndef STACK_H_
#define STACK_H_

#include <stdlib.h>

#include "list.h"

/*  Implement stacks as linked lists*/
typedef List Stack;

/* Public interface */
#define stack_init list_init
#define stack_destory list_destory;
int stack_push(Stack *stack, const void *data);
int stack_pop(Stock *stack, void **data);
#define stack_peek(stack)((stack)->head == NULL ? NULL : (stack)->head->data)
#define stack_size list_size
#endif<file_sep>/*  list.h  */
/*  单链表的实现   */

#ifndef LIST_H_
#define LIST_H_

#include <stdlib.h>

/* Define a structure for linked list element elements */

typedef struct ListElmt_{
	void *data;
	struct ListElmt_ *next;
}ListElmt_;

/* define a structue for linked lists */
typedef struct  struct_List_{
	int size;//链表中元素的个数
	int (*match)(const void *key1, const void *key2);
	void (*destory) (void *data);//封装之后传递给list_init的析构函数
	ListElmt_ *head;//指向链表中头结点元素的指针
	ListElmt_ *tail;//指向链表中尾结点元素的指针
}List;

/* Public Intrerface */
void list_init(*list, void(*destory)(void * data));
void list_dedtory(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_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