实现带头双向循环链表

这篇具有很好参考价值的文章主要介绍了实现带头双向循环链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🌈带头双向循环链表

实现带头双向循环链表,开发语言,c语言,数据结构
描述:一个节点内包含两个指针,一个指向上一个节点,另一个指向下一个节点。哨兵位指向的下一个节点为头节点,哨兵位的上一个指向尾节点。
结构优势:高效率找尾节点;高效率插入与删除;无需判断多种复杂情况,如尾节点、空节点等。

🌈实现带头双向循环链表

☀️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);
}

测试结果:
实现带头双向循环链表,开发语言,c语言,数据结构

测试尾删: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);
}

测试结果:
实现带头双向循环链表,开发语言,c语言,数据结构

测试头插: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);
}

测试结果:
实现带头双向循环链表,开发语言,c语言,数据结构

测试头删: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);
}

测试结果:
实现带头双向循环链表,开发语言,c语言,数据结构文章来源地址https://www.toymoban.com/news/detail-688364.html

测试用主函数

int main() {
	//测试尾插
	test_PushBack();
	//测试尾删
	test_PopBack();
	//测试头插
	test_PushFront();
	//测试头删
	test_PopFront();
}

到了这里,关于实现带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(45)
  • 数据结构: 线性表(带头双向循环链表实现)

    之前一章学习了单链表的相关操作, 但是单链表的限制却很多, 比如不能倒序扫描链表, 解决方法是在数据结构上附加一个域, 使它包含指向前一个单元的指针即可. 那么怎么定义数据结构呢? 首先我们先了解以下链表的分类 链表的结构非常多样, 以下情况组合起来就有 8 中链表

    2024年02月14日
    浏览(40)
  • 数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构,它的结构是很完美的,它弥补了单链表的许多不足,让我们一起来了解一下它是如何实现的吧!         它的节点中存储着数据和两个指针,一个 指针_prev 用来记录前一个节点的地址,另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(46)
  • 【数据结构】双向带头循环链表的实现

    前言:在前面我们学习了顺序表、单向链表,今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学习!一起努力! 带头双向循环链

    2024年01月15日
    浏览(49)
  • 【数据结构】—带头双向循环链表的实现(完美链表)

    链表结构一共有八种形式,在前面的文章里已经讲完了不带头单向非循环链表的实现,但是我们发现该链表实现尾插与尾删时比较麻烦,要先从头节点进行遍历,找到尾节点,时间复杂度为O(N),而本次所讲的带头双向循环单链表,则可以直接找到尾节点。 虽然该链表看起来

    2024年01月25日
    浏览(61)
  • 数据结构之双向带头循环链表函数功能实现与详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2.带头双向循环链表函数实现 3.总结         在前面我

    2024年02月05日
    浏览(51)
  • 【数据结构和算法】实现带头双向循环链表(最复杂的链表)

    前文,我们实现了认识了链表这一结构,并实现了无头单向非循环链表,接下来我们实现另一种常用的链表结构,带头双向循环链表。如有仍不了解单向链表的,请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表,并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(76)
  • 【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!)

    在前面我们学习实现了单链表(无头单向不循环链表),这里我们引入带头双向循环链表 很明显这两种链表的结构截然不同,但都是作为链表最常使用链表结构 前者因其结构上的缺点而作为面试考题的常驻嘉宾,而且复杂麻烦 后者则是以结构最优著称,实现起来也是非常的

    2024年02月10日
    浏览(46)
  • 数据结构:链表基础OJ练习+带头双向循环链表的实现

    目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口 3.链表的打

    2024年02月02日
    浏览(49)
  • 带头双向循环链表--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏:🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的 点赞 👍和 关注 💖,支持一

    2024年02月01日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包