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

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

前言:

之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~

一、介绍带头双向循环链表

1.带头双向循环链表的结构

结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单。

【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

2.带头双向循环链表的功能

单链表可以实现对数据的增删查改,带头双向循环链表也同样能做到,而且实现起来比单链表简单得多。

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

1.创建节点的结构

一个节点的结构:

存放数据:data
前指针:prev
后指针:next

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

2.函数的声明

//创建一个新节点
LTNode* BuyListNode(LTDataType x);
//初始化哨兵位节点
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x);
//在pos位置删除
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);

2.函数的实现

(1)创建一个新节点

这里与单链表的实现的方式是一样的,多了一个前指针(prev)。

LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

(2)初始化哨兵位(带头)节点

刚开始给头指针初始化为哨兵位节点,方便后面可以直接连接新节点。不需要用二级指针

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

(3)打印链表

定义一个指针变量cur为哨兵位的下一个节点,也就是第一个节点。然后遍历链表,只要cur不是phead(哨兵位),就打印节点的数据。

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

(4)尾插

双向链表的尾插比单链表要简单多了。单链表尾插新节点要从头开始遍历找尾,双向链表的尾就是哨兵位的前一个节点。然后尾节点与新节点连接,新节点与哨兵位连接就行了。

刚开始没有节点(除了哨兵位)也是一样的

【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

(5)尾删

这里要多断言一句代码,哨兵位的下一个节点不能等于它自己,因为只有一个哨兵位就说明没有其他节点,不能再删了。
还是定义一个指针变量为尾节点,再定义一个为尾节点的前一个节点,free释放掉尾节点,然后尾节点的前一个节点与哨兵位连接起来。
【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

(6)头插

定义一个指针变量first为哨兵位的下一个节点(可能是空),然后新节点与first连接,first与哨兵位连接,思路和单链表的头插如出一辙。
【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

(7)头删

与尾删相同,为了防止没有节点了(除了哨兵位)不能再删,所以要对哨兵位下一个节点不能为自己就行断言。
定义一个变量first为第一个节点,另一个变量second为第二个节点(如果只有一个节点,second指向的是哨兵位),free释放first,然后哨兵位与second连接。
【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

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

(8)查找

与单链表的查找基本相同,从哨兵位的下一个节点开始找,当循环到哨兵位就停下,找到返回这个节点,否则返回NULL

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

(9)在pos位置前插入

首先要对pos进行断言,判断除了哨兵位是否还有其他节点。
定义一个变量posPrev为pos的前一个节点,然后posPrev与新节点连接,新节点与pos连接。
【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posPrev = pos->prev;
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

(10)在pos位置删除

定义两个变量分别为pos前后的节点,free释放pos,连接两个前后节点
【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言

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

(11)销毁

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

三、全部代码

1.List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
//创建一个新节点
LTNode* BuyListNode(LTDataType x);
//初始化哨兵位节点
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置前插入
void LTInsert(LTNode* pos, LTDataType x);
//在pos位置删除
void LTErase(LTNode* pos);
//销毁
void LTDestroy(LTNode* phead);

2.List.c

#include "List.h"
//创建一个新节点
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}
//初始化哨兵位节点
LTNode* LTInit()
{
	LTNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("phead<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType 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, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(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;
	LTNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}
//销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

3.Test.c

#include "List.h"
void test()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 11);
	LTPushBack(plist, 12);
	LTPushBack(plist, 13);
	LTPushBack(plist, 14);
	LTPushBack(plist, 15);
	LTPrint(plist);

	LTPopBack(plist);
	LTPopBack(plist);
	LTPopBack(plist);
	LTPrint(plist);

	LTPushFront(plist, 99);
	LTPushFront(plist, 89);
	LTPushFront(plist, 79);
	LTPushFront(plist, 69);
	LTPushFront(plist, 59);
	LTPrint(plist);

	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);

	LTNode* pos1 = LTFind(plist, 11);
	{
		if (pos1)
		{
			LTInsert(pos1, 666);
		}
	}
	LTPrint(plist);

	LTNode* pos2 = LTFind(plist, 89);
	{
		if (pos2)
		{
			LTErase(pos2);
		}
	}
	LTPrint(plist);

	LTDestroy(plist);

}
int main()
{
	test();
	return 0;
}

【数据结构】实现带头双向循环链表,数据结构,链表,c语言,开发语言
感谢观看~文章来源地址https://www.toymoban.com/news/detail-689307.html

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

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

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

相关文章

  • 【数据结构】链表:带头双向循环链表的增删查改

    本篇要分享的内容是带头双向链表,以下为本片目录 目录 一、链表的所有结构 二、带头双向链表 2.1尾部插入 2.2哨兵位的初始化 2.3头部插入 2.4 打印链表 2.5尾部删除 2.6头部删除  2.7查找结点 2.8任意位置插入 2.9任意位置删除  在刚开始接触链表的时候,我们所学仅仅所学的

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

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

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

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

    2024年02月10日
    浏览(45)
  • 【数据结构】带头双向循环链表及其实现

    目录 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日
    浏览(41)
  • 【数据结构】双向带头循环链表的实现

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

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

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

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

    目录 1、双向带头循环链表的介绍 2、双向带头循环链表的接口 3、接口实现 3.1 开辟结点 3.2 创建返回链表的头结点 3.3 判断链表是否为空 3.4 打印 3.5 双向链表查找 3.6 双向链表在pos的前面进行插入 3.6.1 头插 3.6.2 尾插 3.6.3 更新头插、尾插写法 3.7 双向链表删除pos位置的节点

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

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

    2024年02月05日
    浏览(54)
  • 数据结构入门(C语言版)线性表带头双向循环链表接口实现

    在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。 如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客: 线性表中链表介绍及无头单向非循环链

    2023年04月12日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包