[数据结构与算法]双向循环链表

#ifndef _DLINKED_LIST_H__
#define _DLINKED_LIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ETYPE;

typedef struct DNode{
	ETYPE elem;
	struct DNode *prev; //prior
	struct DNode *next; 
}DNode,*DLinkedList; 

#define DNODESIZE sizeof(struct DNode)


DLinkedList dlinked_list_create(void);//创建双向循环链表
bool dlinked_list_empty(DLinkedList head);//是否为空
size_t dlinked_list_size(DLinkedList head);//返回元素个数
int dlinked_list_insert(DLinkedList head,size_t pos,ETYPE elem);//指定位置插入元素
int dlinked_list_delete(DLinkedList head,size_t pos,ETYPE *pelem);//删除指定位置元素
int dlinked_list_get(DLinkedList head,size_t pos,ETYPE *pelem);//获取指定位置元素
ETYPE *dlinked_list_find(DLinkedList head,ETYPE *pelem);//查找元素
void dlinked_list_clear(DLinkedList head);//清空元素
void dlinked_list_destroy(DLinkedList head);//销毁链表

#endif //_DLINKED_LIST_H__

#include "dlinkedlist.h"

static struct DNode *create_dnode(ETYPE elem,struct DNode *prev,struct DNode *next){
	struct DNode *node = (struct DNode *)malloc(DNODESIZE);
	if(node != NULL){
		node->elem = elem;
		node->prev = prev;
		node->next = next;
	}
	return node;
}

DLinkedList dlinked_list_create(void){
	return create_dnode(0,NULL,NULL);
}
bool dlinked_list_empty(DLinkedList head){
	return head->next == NULL;
}
size_t dlinked_list_size(DLinkedList head){
	size_t size = 0;
	struct DNode *node = head->next;
	for(;node!=NULL;node=node->next){
		++size;
	}
	return size;
}
static struct DNode *dlinked_list_get_prev_node(DLinkedList head,size_t pos){
	size_t i;
	struct DNode *node = head;
	for(i=0;i<pos&&node!=NULL;++i){
		node = node->next;
	}
	return node;
}

int dlinked_list_insert(DLinkedList head,size_t pos,ETYPE elem){
	struct DNode *prev = dlinked_list_get_prev_node(head,pos);
	//dlinked_list_insert_back(prev,elem);
	if(prev == NULL){
		return -1;
	}
	/*
	struct DNode *curr = (struct DNode *)malloc(DNODESIZE);
	curr->next = prev->next;
	curr->prev = prev;
	curr->elem = elem; 
	*/
	struct DNode *curr = create_dnode(elem,prev,prev->next);//1,2接了两个指针 
	if(curr == NULL){
		return -1;
	}
	if(prev->next != NULL)
		prev->next->prev = curr;//3 
	
	prev->next = curr;//4 
	return 0;	
}
//int dlinked_list_delete(DNode *p);
int dlinked_list_delete(DLinkedList head,size_t pos,ETYPE *pelem){
	struct DNode *prev = dlinked_list_get_prev_node(head,pos);
	if(prev == NULL || prev->next == NULL){
		return -1;
	}
	struct DNode *curr = prev->next;
	*pelem = curr->elem;
	if(curr->next!=NULL)
		curr->next->prev = prev;
	prev->next = curr->next;
	free(curr);
	return 0;
}
int dlinked_list_get(DLinkedList head,size_t pos,ETYPE *pelem){
	struct DNode *curr = dlinked_list_get_prev_node(head,pos+1);
	if(curr == NULL){
		return -1;
	}
	*pelem = curr->elem;
	return 0;
}
ETYPE *dlinked_list_find(DLinkedList head,ETYPE *pelem){
	struct DNode *node = head->next;
	for(;node!=NULL;node = node->next){
		if(node->elem == *pelem){
			return &node->elem;
		}
	}
	return NULL;
}

void dlinked_list_clear(DLinkedList head){
	struct DNode *node,*next;
	for(node=head->next;node!=NULL;node = next){
		next = node->next;
		free(node);
	}
	head->next = NULL;
}
void dlinked_list_destroy(DLinkedList head){
	dlinked_list_clear(head);
	free(head);
}