当前位置：首页 > news >正文

【数据结构】双链表

news 来源：原创 2024/9/20 14:43:15

带头双向循环链表。

List.h

#pragma once#include<stddef.h>//NULL
#include<stdlib.h>//free
#include<assert.h>//asserttypedef 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<stdio.h>
#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\n");
}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\n", SLPopBack(list1)); print(list1);printf("Del = %d\n", SLPopFront(list1)); print(list1);SLDestroy(&list1);
}int main()
{test1();return 0;
}