C语言实现双向链表(DoublyLinkedList)
#ifndef DOUBLY_LINKED_LIST#define DOUBLY_LINKED_LIST#include<stdio.h>#include<stdlib.h>#include<memory.h>/*链表节点*/typedef struct DoublyLinkedListNodeS{ struct DoublyLinkedListNodeS *prev,*next;}DoublyLinkedListNode;typedef struct DoublyLinkedList{ DoublyLinkedListNode root;//sentinel list element, only &root, root.prev, and root.next are used int length;}DoublyLinkedList;//初始化双向链表DoublyLinkedList* DoublyLinkedList_Init();//销毁链表void DoublyLinkedList_Destory(DoublyLinkedList* list);//链表长度int DoublyLinkedList_Len(DoublyLinkedList* list);//求头节点DoublyLinkedListNode* DoublyLinkedList_Front(DoublyLinkedList* list);//求尾节点DoublyLinkedListNode* DoublyLinkedList_Back(DoublyLinkedList* list);//在at位置后面插入eDoublyLinkedListNode* DoublyLinkedList_InsertAfter(DoublyLinkedList* list, DoublyLinkedListNode* at,DoublyLinkedListNode* e);//在at前面插入e,成功返回eDoublyLinkedListNode* DoublyLinkedList_InsertBefore(DoublyLinkedList* list, DoublyLinkedListNode* at, DoublyLinkedListNode* e);//在头部插入eDoublyLinkedListNode* DoublyLinkedList_PushFront(DoublyLinkedList* list, DoublyLinkedListNode* e);//在尾部插入eDoublyLinkedListNode* DoublyLinkedList_PushBack(DoublyLinkedList* list, DoublyLinkedListNode* e);//删除节点e,并返回被删除的eDoublyLinkedListNode* DoublyLinkedList_Remove(DoublyLinkedList* list, DoublyLinkedListNode* e);//将e移动到头部void DoublyLinkedList_MoveFront(DoublyLinkedList* list, DoublyLinkedListNode* e);//将e移动到尾部void DoublyLinkedList_MoveBack(DoublyLinkedList* list, DoublyLinkedListNode* e);#endif // DOUBLY_LINKED_LIST
#include "doublyLinkedList.h"DoublyLinkedList* DoublyLinkedList_Init() { DoublyLinkedList *list = (DoublyLinkedList *)malloc(sizeof(DoublyLinkedList)); if (list == NULL) { fprintf(stderr,"malloc DoublyLinkedList error.\n"); return NULL; } list->length = 0; list->root.next = &list->root; list->root.prev = &list->root; return list;}//销毁链表void DoublyLinkedList_Destory(DoublyLinkedList* list) { if (list != NULL) { free(list); list = NULL; }}int DoublyLinkedList_Len(DoublyLinkedList* list) { if (list == NULL) { return 0; } return list->length;}//求头节点DoublyLinkedListNode* DoublyLinkedList_Front(DoublyLinkedList* list) { if (list == NULL || list->length == 0) { return 0; } return list->root.next;}//求尾节点DoublyLinkedListNode* DoublyLinkedList_Back(DoublyLinkedList* list) { if (list == NULL || list->length == 0) { return 0; } return list->root.prev;}//在at后面插入e,成功返回eDoublyLinkedListNode* DoublyLinkedList_InsertAfter(DoublyLinkedList* list, DoublyLinkedListNode* at, DoublyLinkedListNode* e) { if (list == NULL || at == NULL) { fprintf(stderr,"wrong argument\n"); return NULL; } DoublyLinkedListNode* next = at->next; at->next = e; e->prev = at; e->next = next; next->prev = e; list->length++; return e;}//在at前面插入e,成功返回eDoublyLinkedListNode* DoublyLinkedList_InsertBefore(DoublyLinkedList* list, DoublyLinkedListNode* at, DoublyLinkedListNode* e) { if (list == NULL || at == NULL) { fprintf(stderr, "wrong argument\n"); return NULL; } return DoublyLinkedList_InsertAfter(list, at->prev, e);}//在头部插入e,返回eDoublyLinkedListNode* DoublyLinkedList_PushFront(DoublyLinkedList* list, DoublyLinkedListNode* e) { return DoublyLinkedList_InsertAfter(list,&list->root,e);}//在尾部插入e,返回eDoublyLinkedListNode* DoublyLinkedList_PushBack(DoublyLinkedList* list, DoublyLinkedListNode* e) { return DoublyLinkedList_InsertBefore(list, &list->root, e);}//删除节点e,并返回被删除的eDoublyLinkedListNode* DoublyLinkedList_Remove(DoublyLinkedList* list, DoublyLinkedListNode* e) { if (list == NULL || e == NULL) { return NULL; } e->prev->next = e->next; e->next->prev = e->prev; e->next = NULL; e->prev = NULL; list->length--; return e;}//将e移动到头部void DoublyLinkedList_MoveFront(DoublyLinkedList* list, DoublyLinkedListNode* e) { if(list == NULL || e == NULL){ return; } DoublyLinkedList_InsertAfter(list, &list->root, DoublyLinkedList_Remove(list,e));}//将e移动到尾部void DoublyLinkedList_MoveBack(DoublyLinkedList* list, DoublyLinkedListNode* e) { if (list == NULL || e == NULL) { return; } DoublyLinkedList_InsertBefore(list, &list->root, DoublyLinkedList_Remove(list, e));}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。