数据结构——带头双向循环链表

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

一、带头双向循环链表的定义

带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势。
带头双向循环链表包括一个带有哨兵位的头节点,该节点既可以作为链表的第一个节点,也可以作为链表的最后一个节点.
这种链表的特点是每个节点都有两个指针,一个指向前一个节点,一个指向后一个节点,这样就可以实现双向遍历。
同时,链表的最后一个节点的后继指针指向头节点,形成了循环的结构。这样,我们可以在任意一个节点上进行前后移动,插入和删除操作,而不需要像单链表那样遍历整个链表去找到前一个节点。
需要注意的是,带头双向循环链表为空并不意味着没有一个节点,而是只有一个带哨兵位的头节点,所以在使用之前需要对链表进行初始化。

二、带头双向循环链表的实现

2.1初始化创建带头双向循环链表的节点

typedef struct ListNode
{
	Listdatatype data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

数据结构——带头双向循环链表,数据结构,数据结构,链表

在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针,目的在与存储前一个节点的地址,便于将整个链表连在一起。

2.2申请新节点

//创建新节点
LTNode* BuyLTNode(Listdatatype x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

动态申请内存结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断是否为空,如为空就perror,显示错误信息。反之则把需要存储的数据x存到newnode指向的空间里面,并且把newnode->next,newnode->prev置为空。

2.3节点的初始化

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

通过动态内存申请节点,申请了一个头节点。并且将它的phead->next ,phead->prev 都置为phead,得到如下图的头节点。
数据结构——带头双向循环链表,数据结构,数据结构,链表

2.4带头双向循环链表的尾插

void LTPushBack(LTNode* phead, Listdatatype x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

尾插节点的方法:首先通过内存申请一个节点, 然后改变四个指针的指向,便可以完成带头双向循环链表的尾插。
数据结构——带头双向循环链表,数据结构,数据结构,链表
数据结构——带头双向循环链表,数据结构,数据结构,链表

2.5带头双向循环链表的头插

void LTFrontBack(LTNode* phead, Listdatatype x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

数据结构——带头双向循环链表,数据结构,数据结构,链表
数据结构——带头双向循环链表,数据结构,数据结构,链表

2.6判空函数

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

2.7带头双向循环链表的打印函数

//打印
void LTPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	printf("guard<->");
	while (cur != phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.8带头双向循环链表的尾删

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(! LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	//改变指针的指向
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
}

数据结构——带头双向循环链表,数据结构,数据结构,链表

2.9带头双向循环链表的头删

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);
	phead->next = firstnext;
	firstnext->prev = phead;
}

数据结构——带头双向循环链表,数据结构,数据结构,链表

2.11带头双向循环链表的在pos之前插入

void LTInsert(LTNode* pos, Listdatatype x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* posprev = pos->prev;
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;
}

数据结构——带头双向循环链表,数据结构,数据结构,链表

2.12带头双向循环链表的在pos位置删除

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
}

数据结构——带头双向循环链表,数据结构,数据结构,链表文章来源地址https://www.toymoban.com/news/detail-707060.html

2.14带头双向循环链表的销毁

//销毁
LTNode* LTDestory(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

三、完整代码

3.1LIst.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int  Listdatatype;
typedef struct ListNode
{
	Listdatatype data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

//初始化
LTNode* LTInit();

//尾插
void LTPushBack(LTNode* phead, Listdatatype x);

//尾删
void LTPopBack(LTNode* phead);

//头插
void LTFrontBack(LTNode* phead, Listdatatype x);

//头删
void LTPopFront(LTNode* phead);

//打印
void LTPrint(LTNode* phead);

//判空
bool LTEmpty(LTNode* phead);

//在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x);

//在pos之前删除
void LTErase(LTNode* pos);

//寻找
LTNode* LTFind(LTNode* phead, Listdatatype x);

//销毁
LTNode* LTDestory(LTNode* phead);

3.2List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
LTNode* BuyLTNode(Listdatatype x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}


LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
//尾插
void LTPushBack(LTNode* phead, Listdatatype x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}


//头插
void LTFrontBack(LTNode* phead, Listdatatype x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

//打印
void LTPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	printf("guard<->");
	while (cur != phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(! LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	//改变指针的指向
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
}


//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);
	phead->next = firstnext;
	firstnext->prev = phead;
}


//寻找
LTNode* LTFind(LTNode* phead, Listdatatype x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}



//在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* posprev = pos->prev;
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;
}

在pos之前删除
//void LTErase(LTNode* pos)
//{
//	assert(pos);
//	LTNode* posprev = pos->prev;
//	free(posprev);
//	posprev->prev->next = pos;
//	pos->prev = posprev->prev;
//	
//}


//在pos位置删除
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
}

//销毁
LTNode* LTDestory(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

3.3test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//void test1()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPrint(plist);
//	LTPopBack(plist);
//	LTPrint(plist);

//}
void test2()
{
	LTNode* plist = LTInit();
	LTFrontBack(plist, 1);
	LTFrontBack(plist, 2);
	LTFrontBack(plist, 3);
	LTFrontBack(plist, 4);
	LTPrint(plist);
	LTErase(3);
	LTPrint(plist);
}
int main()
{
	//test1();
	test2();
	return 0;
}

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

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

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

相关文章

  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(61)
  • 数据结构课程设计题目——链表综合算法设计、带头双向循环链表、插入、显示、删除、修改、排序

      课程设计题目1–链表综合算法设计   一、设计内容   已知简单的人事信息系统中职工记录包含职工编号(no)、职工姓名(name)、部门名称(depname)、职称(title)和工资数(salary)等信息(可以增加其他信息),设计并完成一个简单的人事信息管理系统,要求完成但不

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

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

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

    在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针,目的在与存储前一个节点的地址,便于将整个链表连在一起。 动态申请内存结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断

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

    什么是双向带头循环链表? 上面简单的一个非空 带头循环双向链表逻辑图 如何定义一个双向链表? 根据图和代码可以看双向链表就是单链表的每个结点中,在设置一个指向前驱节点的指针 简单认识之后,对他进行初始化(申请一个头节点,让前驱和后驱指针都指向自己) 代码

    2024年02月07日
    浏览(69)
  • 【数据结构】带头双向循环链表

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

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

    前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用

    2023年04月09日
    浏览(50)
  • 【数据结构】实现带头双向循环链表

    之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~ 结构最复杂 ,一般用在单独存储数据。 实际中使用的链表数据结构,都是带头双向循环链表 。另外这个结构虽然结构复杂,但是使用代码实现以后会发现 结构会带来很多优势 ,实现反而简单

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

    相较于之前的顺序表和单向链表,双向链表的逻辑结构稍微复杂一些,但是在实现各种接口的时候是很简单的。因为不用找尾,写起来会舒服一点。(也可能是因为最近一直在写这个的原因) 在实现接口的时候,除了没有找尾,其他的操作和单向链表是差不多的,这里就不多

    2024年04月14日
    浏览(63)
  • 数据结构之带头双向循环链表

    目录 链表的分类 带头双向循环链表的实现 带头双向循环链表的结构 带头双向循环链表的结构示意图 空链表结构示意图 单结点链表结构示意图  多结点链表结构示意图 链表创建结点 双向链表初始化 销毁双向链表 打印双向链表  双向链表尾插 尾插函数测试 双向链表头插

    2024年02月08日
    浏览(74)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包