1. 双向带头循环链表
1. 双链表的功能
1. 初始化
2. 销毁
3. 打印
4. 检查链表是否为空
5. 尾插
6. 尾删
7. 头插
8. 头删
9. 在目标节点之后插入数据
10. 删除目标节点
11. 查找
2. 双链表的定义
结构体需要包含三个成员，一个成员存储数据，一个成员存储前一个节点的地址，一个成员存储下一个节点的地址。
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;//指针保存后一个节点的位置struct ListNode* prev;//指针保存前一个节点的位置
}LTNode;3. 双链表功能实现
创建节点
缩减代码，避免代码冗余
LTNode* CreateNode(LTDataType x) {LTNode* node = (LTNode*)malloc(sizeof(LTNode));//创建节点if (node == NULL) {printf("创建节点失败\n");exit(-1);}node->data = x;node->prev = node;node->next = node;return node;
}1. 初始化
LTNode* LTInit() {LTNode* phead = CreateNode(-1);return phead;
}2. 销毁
void LTDestroy(LTNode* phead) {LTNode* ptail = phead->next;LTNode* pointer = NULL;//先释放非哨兵节点//因为链表的最后一个节点的 next 指向哨兵位，// 哨兵位的 prev 指向最后一个节点，形成一个循环。while (ptail!=phead) {pointer = ptail;ptail = ptail->next;free(pointer);}free(phead);
}3. 打印
void LTPrint(LTNode* phead) {LTNode* ptail = phead->next;while (ptail != phead) {printf("%d ", ptail->data);ptail = ptail->next;}printf("\n");
}4. 检查链表是否为空
bool LTEmpty(LTNode* phead) {return phead->next == phead;
}5. 尾插
void LTPushBack(LTNode* phead, LTDataType x) {//assert(phead);//LTNode* node = CreateNode(x);将新节点插入链表尾部//node->prev = phead->next;//node->next = phead;//phead->prev->next = node;//phead->prev = node;LTInsert(phead->prev, x);
}6. 尾删
void LTPopBack(LTNode* phead) {//assert(phead);//assert(phead->next != phead);//LTNode* pointer = phead->prev;//pointer->prev->next = phead;//phead->prev = pointer->prev;//free(pointer);pointer = NULL;LTErase(phead->prev);
}7. 头插
void LTPushFront(LTNode* phead, LTDataType x) {//assert(phead);//LTNode* node = CreateNode(x);//node->prev = phead;//node->next = phead->next;//phead->next->prev = node;//phead->next = node;LTInsert(phead, x);
}8. 头删
void LTPopFront(LTNode* phead) {//assert(phead && phead->next);//LTNode* pointer = phead->next;//phead->next = pointer->next;//pointer->next->prev = phead;//free(pointer);LTErase(phead->next);
}9. 在目标节点之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* node = CreateNode(x);node->prev = pos;node->next = pos->next;pos->next->prev = node;pos->next = node;
}10. 删除目标节点
void LTErase(LTNode* pos) {assert(pos);LTNode* pointer = pos;pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pointer);
}11. 查找
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pointer = phead->next;while (pointer != phead) {if (pointer->data == x) {printf("找到了\n");return pointer;}pointer = pointer->next;}return NULL;
}4. 完整代码
1. DList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;//指针保存后一个节点的位置struct ListNode* prev;//指针保存前一个节点的位置
}LTNode;//初始化
LTNode* LTInit();
//销毁链表
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//检查链表是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);2. DList.c
#include "DList.h"
//创建节点
LTNode* CreateNode(LTDataType x) {LTNode* node = (LTNode*)malloc(sizeof(LTNode));//创建节点if (node == NULL) {printf("创建节点失败\n");exit(-1);}node->data = x;node->prev = node;node->next = node;return node;
}
//初始化
LTNode* LTInit() {LTNode* phead = CreateNode(-1);return phead;
}
//销毁链表
void LTDestroy(LTNode* phead) {LTNode* ptail = phead->next;LTNode* pointer = NULL;//先释放非哨兵节点//因为链表的最后一个节点的 next 指向哨兵位，// 哨兵位的 prev 指向最后一个节点，形成一个循环。while (ptail!=phead) {pointer = ptail;ptail = ptail->next;free(pointer);}free(phead);
}
//打印
void LTPrint(LTNode* phead) {LTNode* ptail = phead->next;while (ptail != phead) {printf("%d ", ptail->data);ptail = ptail->next;}printf("\n");
}
//检查链表是否为空
bool LTEmpty(LTNode* phead) {return phead->next == phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x) {//assert(phead);//LTNode* node = CreateNode(x);将新节点插入链表尾部//node->prev = phead->next;//node->next = phead;//phead->prev->next = node;//phead->prev = node;LTInsert(phead->prev, x);
}
//尾删
void LTPopBack(LTNode* phead) {//assert(phead);//assert(phead->next != phead);//LTNode* pointer = phead->prev;//pointer->prev->next = phead;//phead->prev = pointer->prev;//free(pointer);pointer = NULL;LTErase(phead->prev);
}
//头插
void LTPushFront(LTNode* phead, LTDataType x) {//assert(phead);//LTNode* node = CreateNode(x);//node->prev = phead;//node->next = phead->next;//phead->next->prev = node;//phead->next = node;LTInsert(phead, x);
}
//头删
void LTPopFront(LTNode* phead) {//assert(phead && phead->next);//LTNode* pointer = phead->next;//phead->next = pointer->next;//pointer->next->prev = phead;//free(pointer);LTErase(phead->next);
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* node = CreateNode(x);node->prev = pos;node->next = pos->next;pos->next->prev = node;pos->next = node;
}
//删除pos节点
void LTErase(LTNode* pos) {assert(pos);LTNode* pointer = pos;pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pointer);
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pointer = phead->next;while (pointer != phead) {if (pointer->data == x) {printf("找到了\n");return pointer;}pointer = pointer->next;}return NULL;
}3. text.c
#include "DList.h"
void Realize(void) {LTNode* phead = LTInit();//创建哨兵节点//检查链表是否为空LTEmpty(phead);if (LTEmpty(phead)) {printf("链表为空\n");}else {printf("链表不为空\n");}//尾插LTPushBack(phead, 5);LTPushBack(phead, 7);//尾删LTPopBack(phead);//头插LTPushFront(phead, 6);//头删LTPopFront(phead);//在pos位置之后插入数据LTInsert(phead->next->next, 8);//删除pos节点LTErase(phead->next);//查找LTFind(phead, 8);//打印LTPrint(phead);//销毁链表LTDestroy(phead);phead = NULL;}
int main() {Realize();return 0;
}
