【数据结构】链表的分类和双向链表

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

本篇是基于上篇单链表所作,推荐与上篇配合阅读,效果更加

http://t.csdnimg.cn/UhXEj

1.链表的分类

链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构:
【数据结构】链表的分类和双向链表,链表,数据结构我们一般叫这个头为哨兵位
我们上回讲的单链表就是不带头单项不循环链表。
今天我们要讲带头双向循环的链表。
不过在次之前容我先为大家画一画8种链表结构:

1.带头单向循环链表:

【数据结构】链表的分类和双向链表,链表,数据结构

2.带头单向不循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

3.带头双向循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

4.带头双向不循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

5.不带头单向循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

6.不带头单向不循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

7.不带头双向循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

8.不带头双向不循环链表

【数据结构】链表的分类和双向链表,链表,数据结构

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构: 单链表 双向带头循环链表
1. 无头单向非循环链表:结构简单,⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表:结构最复杂,⼀般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。

2.双向带头循环链表

我们还是经典三个文件:

【数据结构】链表的分类和双向链表,链表,数据结构

我们先定义头文件所需要的函数

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//注意,双向链表是带有哨兵位的,插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);   //推荐一级(保持接口一致性)

void LTPrint(LTNode* phead);

//不需要改变哨兵位,则不需要传二级指针
//如果需要修改哨兵位的话,则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);

首先我们还是得先定义节点,由于是双向链表,所以节点内存在两个节点的地址,一个是前驱节点的(指向其前一个节点),一个是尾结点的(指向其后一个节点)

【数据结构】链表的分类和双向链表,链表,数据结构

这一段代码,是为了确保数据类型

我们节点定义成这样:

【数据结构】链表的分类和双向链表,链表,数据结构

接下来又是完成各个功能:增,删,查,改。但是,由于我们长线的是带头的链表,所以我们需要对头初始化

3.初始化

我们先定义初始化函数,然后写函数:

void LTInit(LTNode** pphead);
void ltinit(ltnode** pphead) {
	*pphead = (ltnode*)malloc(sizeof(ltnode));
	if (*pphead == null) {
		perror("malloc fail!");
		exit(1);
	}
	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead;
}

和上回写单链表差不多,检测开辟是否成功,成功就接着给数据赋值,由于此时只有一个节点,即哨兵节点,且是循环链表,所以存放的前驱和尾节点就是哨兵节点自己

【数据结构】链表的分类和双向链表,链表,数据结构

所以我们可以得出,如果哨兵节点的next指针或者prev指针指向自己,说明当前链表为空。

4.创建新的节点

我们写法和上次差不多

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

	return newnode;
}

只是这回,多了一个前驱节点,我们定义时间默认前驱和后去节点指向的是本身。

但是既然我们都这么写了一个创建新节点的函数,那么我们可不可以用这个函数直接去进行哨兵节点的创建?

答案是肯定的,我们首先先改变以下我们定义的函数,

LTNode* LTInit();

然后调用创建新节点的函数,得到哨兵节点

LTNode* LTInit() {
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

5.头插和尾插

注意:头插,是把新的节点插在第一个节点前,不是哨兵节点前

头插和尾插,头删和尾删的思路整体和单链表一致,我就不详细说明了,直接上代码

定义函数:

void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

函数代码示例:

//尾插
void LTPushBack(LTNode* phead, LTDataType x) {
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev(ptail)  newnode
	newnode->next = phead;
	newnode->prev = phead->prev;

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

	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

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

不懂的你们可以再看看图:【数据结构】链表的分类和双向链表,链表,数据结构

6.头删和尾删

定义函数:

void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

函数代码示例:

//尾删
void LTPopBack(LTNode* phead) {
	assert(phead);
	//链表为空:只有一个哨兵位节点
	assert(phead->next != phead);

	LTNode* del = phead->prev;
	LTNode* prev = del->prev;

	prev->next = phead;
	phead->prev = prev;

	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead) {
	assert(phead);
	assert(phead->next != phead);

	LTNode* del = phead->next;
	LTNode* next = del->next;

	//phead del next
	next->prev = phead;
	phead->next = next;

	free(del);
	del = NULL;
}

7.查找

整体思路还是遍历,和单链表十分相似

定义函数:

LTNode* LTFind(LTNode* phead, LTDataType x);

函数代码示例:

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

8.在pos位置之后插入数据

这个和单恋表的也很相似,多了一个prev指针而已,写的时候要注意顺序,函数定义我就不写了

函数代码示例:

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}

9.删除pos位置的数据

这个和单链表还是一样的,遍历整个表,然后相爱指针指向的地址,然后释放内存

函数代码示例:

void LTErase(LTNode* pos) {
	assert(pos);

	//pos->prev pos  pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

10.打印

这个其实是用来看每个节点中间的数据的,我们可以通过前驱节点或者尾节点实现正序或逆序打印,这一步也是遍历然后看哨兵节点是否是下一位,是就中断,我这里之举一种例子,另一种只要将next改成prev

函数代码示例:

void LTPrint(LTNode* phead) {
	//phead不能为空
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

11.销毁

这个链表的销毁和点链表不大一样,因为存在哨兵节点,所以我们要分开释放内存

函数代码示例:

void LTDesTroy(LTNode* phead) {
	//哨兵位不能为空
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//链表中只有一个哨兵位
	free(phead);
	phead = NULL;
}

最后还是一如既往的测试环节就交给大家了。推荐阅读完http://t.csdnimg.cn/UhXEj

然后再阅读这个文章来源地址https://www.toymoban.com/news/detail-824671.html

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

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

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

相关文章

  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 数据结构:双向链表的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 本篇博客,将要实现的是 带头双向循环链表 ,该结构实现尾插,尾删只需要O(1)的时间复杂度。 其结构如下所示: 既然要实现的链表是双向循环的,那么对于指针域,我们就需要 指向节点上一个的指针 和 指向节点

    2024年02月14日
    浏览(51)
  • 【数据结构】链表:带头双向循环链表的增删查改

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

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

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

    2024年01月25日
    浏览(63)
  • 【数据结构】双向链表的增删查改(C 代码实现)

    引入双向链表:关于单链表的问题与讨论 单链表存在的毛病: 因为单链表 只能单向 遍历链表, 对于 前插 这个操作,单链表必 须得找到所需前插节点位置的前一个 ,那么这时就得 从头指针重新遍历一次 链表,会造成时间复杂度大大增加。 没有头节点(哨兵位)无法删除

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

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

    2024年02月02日
    浏览(51)
  • 数据结构:图文详解双向链表的各种操作(头插法,尾插法,任意位置插入,查询节点,删除节点,求链表的长度... ...)

    目录 一.双向链表的概念 二.双向链表的数据结构 三.双向链表的实现 节点的插入 头插法 尾插法 任意位置插入 节点的删除 删除链表中第一次出现的目标节点 删除链表中所有与相同的节点 节点的查找 链表的清空 链表的长度 四.模拟实现链表的完整代码 前言: 在上一

    2024年02月05日
    浏览(50)
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月26日 V1.0 发布于博客园 目录 目录 双向循环链表公式 初始化双向循环链表 构建双向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 DoubleCirLList.h

    2024年04月27日
    浏览(55)
  • 青岛大学_王卓老师【数据结构与算法】Week04_04_双向链表的插入_学习笔记

    本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享,另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权,请留言作删文处理。 课程视频链接: 数据结构与算法基础–第04周04–2.5.4双向链表2–双向链表

    2024年02月12日
    浏览(58)
  • 数据结构-链表结构-双向链表

    双向链表也叫双链表,与单向链表不同的是,每一个节点有三个区域组成:两个指针域,一个数据域 前一个指针域:存储前驱节点的内存地址 后一个指针域:存储后继节点的内存地址 数据域:存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱,后指针

    2024年02月04日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包