带头双向循环链表。
List.h
#pragma once
#include//NULL
#include//free
#include//assert
typedef int SLDataType;
typedef struct SLNode
{
SLDataType data;
struct SLNode* prev;
struct SLNode* next;
} SLNode;
SLNode* SLInit();
void SLPushFront(SLNode* head, SLDataType x);
void SLPushBack(SLNode* head, SLDataType x);
SLDataType SLPopBack(SLNode* head);
SLDataType SLPopFront(SLNode* head);
SLDataType SLErase(SLNode* Del);
void SLInsertBF(SLNode* AFnode, SLDataType x);
void SLInsertAF(SLNode* AFnode, SLDataType x);
void SLDestroy(SLNode** phead);
List.c
#include"List.h"
static SLNode* BuySLNode(SLDataType x)
{
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (NULL == newNode)
{
perror("malloc failed");
exit(-1);
}
newNode->data = x;
newNode->prev = newNode;
newNode->next = newNode;
return newNode;
}
SLNode* SLInit()
{
return BuySLNode(0);
}
void SLPushFront(SLNode* head, SLDataType x)
{
assert(head);
//SLInsertBF(head->next, x);
SLInsertAF(head, x);
}
void SLPushBack(SLNode* head, SLDataType x)
{
assert(head);
//SLInsertBF(head, x);
SLInsertAF(head->prev, x);
}
SLDataType SLPopBack(SLNode* head)
{
assert(head);
assert(head->prev != head);
return SLErase(head->prev);
}
SLDataType SLPopFront(SLNode* head)
{
assert(head);
assert(head->next != head);
return SLErase(head->next);
}
SLDataType SLErase(SLNode* Del)
{
assert(Del);
Del->prev->next = Del->next;
Del->next->prev = Del->prev;
SLDataType ret = Del->data;
free(Del);
return ret;
}
void SLInsertBF(SLNode* AFnode, SLDataType x)
{
assert(AFnode);
SLNode* newnode = BuySLNode(x);
AFnode->prev->next = newnode;
newnode->prev = AFnode->prev;
AFnode->prev = newnode;
newnode->next = AFnode;
}
void SLInsertAF(SLNode* BFnode, SLDataType x)
{
assert(BFnode);
SLNode* newnode = BuySLNode(x);
BFnode->next->prev = newnode;
newnode->next = BFnode->next;
BFnode->next = newnode;
newnode->prev = BFnode;
}
void SLDestroy(SLNode** phead)
{
while ((*phead)->next != *phead)
SLPopBack(*phead);
free(*phead);
}
test.c
#include
#include"List.h"
void print(SLNode* head)
{
SLNode* Head = head;
head = head->next;
printf("Head");
while (Head != head)
{
printf("%d", head->data);
head = head->next;
}
printf("Head
");
}
void test1()
{
SLNode* list1 = SLInit();
SLPushBack(list1, 1);
SLPushBack(list1, 2);
SLPushBack(list1, 3);
SLPushBack(list1, 4);
SLPushFront(list1, 11);
SLPushFront(list1, 22);
print(list1);
printf("Del = %d
", SLPopBack(list1)); print(list1);
printf("Del = %d
", SLPopFront(list1)); print(list1);
SLDestroy(&list1);
}
int main()
{
test1();
return 0;
}