🌈带头双向循环链表
描述:一个节点内包含两个指针,一个指向上一个节点,另一个指向下一个节点。哨兵位指向的下一个节点为头节点,哨兵位的上一个指向尾节点。
结构优势:高效率找尾节点;高效率插入与删除;无需判断多种复杂情况,如尾节点、空节点等。
🌈实现带头双向循环链表
☀️list.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
typedef struct ListNode {
struct ListNode* prev;
struct ListNode* next;
DataType data;
}ListNode;
ListNode* BuyListNode(DataType x);
ListNode* InitList();
void DestroyList(ListNode* phead);
void Print(ListNode* phead);
int CountSize(ListNode* phead);
void PushBack1(ListNode* phead, DataType x);
void PushBack2(ListNode* phead, DataType x);
void PopBack1(ListNode* phead);
void PopBack2(ListNode* phead);
void PushFront1(ListNode* phead, DataType x);
void PushFront2(ListNode* phead, DataType x);
void PopFront1(ListNode* phead);
void PopFront2(ListNode* phead);
void Insert(ListNode* pos, DataType x);
void Erase(ListNode* pos);
☀️list.c
BuyListNode节点创建函数()
ListNode* BuyListNode(DataType x) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL) {
perror("malloc fail");
exit(-1);
}
node->data = x;
node->prev = NULL;
node->next = NULL;
return node;
}
InitList链表初始化函数()
ListNode* InitList() {
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
DestroyList链表销毁函数()
void DestroyList(ListNode* phead) {
assert(phead);
ListNode* cur = phead->next;
while (cur != phead) {
ListNode* curnext = cur->next;
free(cur);
cur = curnext;
}
free(phead);
}
打印节点信息函数Print()
void Print(ListNode* phead) {
assert(phead);
printf("phead<=>");
ListNode* cur = phead->next;
while (cur != phead) {
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
统计节点个数函数CountSize()
int CountSize(ListNode* phead) {
assert(phead);
int size = 0;
ListNode* cur = phead->next;
while (cur != phead) {
size++;
cur = cur->next;
}
return size;
}
在pos位置节点前插入函数Insert()
//在pos前插入
void Insert(ListNode* pos, DataType x) {
assert(pos);
ListNode* posprev = pos->prev;
ListNode* newnode = BuyListNode(x);
posprev->next = newnode;
newnode->prev = posprev;
newnode->next = pos;
pos->prev = newnode;
}
删除pos位置节点函数Erase()
void Erase(ListNode* pos) {
assert(pos);
ListNode* posprev = pos->prev;
ListNode* posnext = pos->next;
free(pos);
posprev->next = posnext;
posnext->prev = posprev;
}
尾插(两种方法)PushBack1()&PushBack2()
void PushBack1(ListNode* phead, DataType x) {
ListNode* tail = phead->prev;
ListNode* newnode = BuyListNode(x);
newnode->next = phead;
phead->prev = newnode;
tail->next = newnode;
newnode->prev = tail;
}
void PushBack2(ListNode* phead, DataType x) {
//尾插就相当于在哨兵位head前插入
Insert(phead, x);
}
尾删(两种方法)PopBack1()&PopBack2()
void PopBack1(ListNode* phead) {
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* tailprev = tail->prev;
free(tail);
tailprev->next = phead;
phead->prev = tailprev;
}
void PopBack2(ListNode* phead) {
//尾节点就是phead的prev节点
Erase(phead->prev);
}
头插(两种方法)PushFront1()&PushFront2()
void PushFront1(ListNode* phead, DataType x) {
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* pheadnext = phead->next;
newnode->next = pheadnext;
pheadnext->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
void PushFront2(ListNode* phead, DataType x) {
//头插就相当于在phead后一个节点的前面插入
assert(phead);
Insert(phead->next, x);
}
头删(两种方法)PopFront1()&PopFront2()
void PopFront1(ListNode* phead) {
assert(phead);
assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
void PopFront2(ListNode* phead) {
//头节点时哨兵位phead的下一个节点
Erase(phead->next);
}
☀️测试
测试尾插:test_PushBack(()
#define _CRT_SECURE_NO_WARNINGS
#include"list.h"
void test_PushBack() {
ListNode* plist = InitList();
PushBack1(plist, 1);
PushBack1(plist, 2);
PushBack1(plist, 3);
PushBack2(plist, 1);
PushBack2(plist, 2);
PushBack2(plist, 3);
Print(plist);
DestroyList(plist);
}
测试结果:
测试尾删:test_PopBack()
void test_PopBack() {
ListNode* plist = InitList();
PushBack1(plist, 1);
PushBack1(plist, 2);
PushBack1(plist, 3);
PushBack2(plist, 1);
PushBack2(plist, 2);
PushBack2(plist, 3);
Print(plist);
PopBack1(plist);
Print(plist);
PopBack2(plist);
Print(plist);
DestroyList(plist);
}
测试结果:
测试头插:test_PushFront()
void test_PushFront() {
ListNode* plist = InitList();
PushFront1(plist, 1);
PushFront1(plist, 2);
PushFront1(plist, 3);
PushFront2(plist, 1);
PushFront2(plist, 2);
PushFront2(plist, 3);
Print(plist);
DestroyList(plist);
}
测试结果:
文章来源:https://www.toymoban.com/news/detail-688364.html
测试头删:test_PopFront()
void test_PopFront() {
ListNode* plist = InitList();
PushFront1(plist, 1);
PushFront1(plist, 2);
PushFront1(plist, 3);
PushFront2(plist, 1);
PushFront2(plist, 2);
PushFront2(plist, 3);
Print(plist);
PopFront1(plist);
Print(plist);
PopFront2(plist);
Print(plist);
DestroyList(plist);
}
测试结果:
文章来源地址https://www.toymoban.com/news/detail-688364.html
测试用主函数
int main() {
//测试尾插
test_PushBack();
//测试尾删
test_PopBack();
//测试头插
test_PushFront();
//测试头删
test_PopFront();
}
到了这里,关于实现带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!