带头循环双向链表专题

news/2024/5/24 0:26:03/ 标签: 链表, 数据结构, c语言

1. 双向链表的结构

带头链表⾥的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这⾥“放哨 的” “哨兵位”存在的意义: 遍历循环链表避免死循环。

2. 双向链表的实现

2.1双向链表结构

typedef  int DataType;
typedef struct ListNode
{struct ListNode* perv;DataType val;struct ListNode* next;
}ListNode; 

双向链表有两个方向,所以要定义两个是指针,perv指向前一个节点,next指向后一个节点。

2.2开辟新节点

ListNode* NewNode(DataType x)
{ListNode* note = (ListNode*)malloc(sizeof(ListNode));if (note == NULL){perror("malloc");exit(0);}note->val = x;note->next = note->perv = note;return note;
}

当我们要插入新节点,或者初始化头结点时,需要开辟一个新节点。因为链表要循环,所以新节点的perv和next指针不能只想为NULL,要指向自己。

2.3初始化链表

void STInit(ListNode** pphead)
{*pphead = NewNode(-1);
}

双向带头循环链表的初始化就是建立头节点(哨兵位)。随便赋一个值就可以。

2.4双向链表头插

void HeadAdd(ListNode* phead, DataType x)
{assert(phead);ListNode* newnote = NewNode(x);newnote->next = phead->next;newnote->perv = phead;phead->next->perv = newnote;phead->next = newnote;
}

头插实际上是在头节点之后插入新节点。只需将新节点的perv指针指向phead,next指针指向phead->next节点。然后将phead->next的perv指针指向newnote。头节点的next指针指向新节点。

2..5双向链表打印

void ListPrint(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->val);pcur = pcur->next;}
}

双向链表的打印实际上是打印头节点之后的内容。先定义一个指针指向头结点的下一个节点。然后打印,最后让pcur指向下一个节点,重复这个过程,直到pcur指向phead。

2.6尾插

void TailAdd(ListNode* phead, DataType x)
{assert(phead);ListNode* newnode = NewNode(x);newnode->next = phead;newnode->perv = phead->perv;newnode->perv->next = newnode;phead->perv = newnode;
}

双向链表的尾插,首先要向内存申请一个新节点。新节点的perv指针指向phead->perv节点,next指针指向phead节点。phead->perv的next指针指向新节点。头结点的perv节点指向新节点。

2.7尾删

void TailDel(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->perv;del->perv->next = phead;phead->perv = del->perv;free(del);del = NULL;
}

先将要删除的节点的地址存起来,否则改完指针指向后就找不到了。改完指针指向后再释放del。

2.8头删

void HeadDel(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->next;del->next->perv = phead;phead->next = del->next;free(del);del = NULL;
}

头删即删除头节点之后的节点。同样要先把要删除的节点存起来。在改变指针指向之后把del释放。

2.9查找某一结点是否存在

ListNode* Find(ListNode* phead, DataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x){return pcur;}}return -1;
}

遍历链表,查找某节点是否存在,如果存在则返回该节点的地址,若不存在返回一个小于0的值。

2.10在指定位置指点之后插入节点

void PosBAdd(ListNode* pop, DataType x)
{ListNode* newnode = NewNode(x);newnode->next = pop->next;newnode->perv = pop;pop->next->perv = newnode;pop->next = newnode;
}

同样也是简单的改变指针的指向。

2.11删除指定位置节点

void PosDel(ListNode* pop)
{pop->perv->next = pop->next;pop->next->perv = pop->perv;free(pop);pop = NULL;
}

改变指针指向后在释放掉要删除的节点。

2.12销毁链表

void ListDesTroy(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}
}

销毁链表即逐个节点释放,但是在释放结点之前要先将下一个结点的地址存起来,因为如果不存起来就无法找到下一个节点。


http://www.ppmy.cn/news/1434723.html

相关文章

Vue实现SM4加密

前端先看有无.eslintrc.js文件,添加 rules 和 ‘globals’ rules: {no-console: process.env.NODE_ENV production ? warn : off,no-debugger: process.env.NODE_ENV production ? warn : off,},"globals":{"base64js": true,}安装SM4 np…

ETL工具-nifi干货系列 第十六讲 nifi Process Group实战教程,一文轻松搞定

1、目前nifi系列已经更新了10多篇教程了,跟着教程走的同学应该已经对nifi有了初步的解,但是我相信同学们应该有一个疑问:nifi设计好的数据流列表在哪里?如何同时运行多个数据流?如启停单个数据流? 带着这些…

Android Compose页面跳转Demo

1.引入依赖 //jetpack compose导航 implementation("androidx.navigation:navigation-compose:2.5.3") 2.代码 import android.os.Bundle import androidx.activity.ComponentActivity import androidx.activity.compose.setContent import androidx.compose.foundat…

Day43:LeedCode 1049. 最后一块石头的重量 II 494. 目标和 474.一和零

1049. 最后一块石头的重量 II 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < y。那么粉碎的可能结果…

微信小程序手机授权报错:pad block corrupted

微信小程序手机号授权登录&#xff0c;传参至后台解密&#xff0c;大概率都会成功&#xff0c;但是&#xff0c;偶尔会遇到解密失败&#xff0c;报错信息为&#xff1a; javax.crypto.BadPaddingException: pad block corrupted&#xff1b;在此记录一下解决方案。 更改前获取…

excel相同行不同列查询

EXCEL中e列和f列是每一行对应的&#xff0c;我想在d列中找和e列一样的元素&#xff0c;然后获取同一行中f列的值 IFERROR(VLOOKUP(D1, E:F, 2, FALSE), "")

python之singledispatch单分派问题

singledispathch是Pyhton的functools里的方法&#xff0c;在使用时&#xff0c;一般当做装饰器。 作用&#xff1a;类似c中的重载&#xff0c;一个函数提供多种实现&#xff0c;根据参数类型的不同&#xff0c;调用不同的实现。 使用方法&#xff1a; 1. 必须有一个基函数&a…

前端css中filter(滤镜)的使用

前端css中filter的使用 一、前言二、补充内容说明三、模糊&#xff08;一&#xff09;、模糊效果&#xff0c;源码1&#xff08;二&#xff09;、源码1运行效果1.视频演示2.截图演示 四、阴影&#xff08;一&#xff09;、阴影效果&#xff0c;源码2&#xff08;二&#xff09;…

【Java | 多线程】可重入锁的概念以及示例

什么是可重入锁&#xff08;Reentrant Lock&#xff09;&#xff1f; 可重入锁&#xff08;又名递归锁&#xff09;是一种特殊类型的锁&#xff0c;它允许同一个线程在获取锁后再次进入该锁保护的代码块或方法&#xff0c;而不需要重新获取锁。 说白了&#xff0c;可重入锁的…

Python第五章之集合,切片,推导式,公共方法

集合 Set set 被称为集合, 是无序的, 并且集合中的元素都是唯一的 1. 集合的创建 s {"zs", "ls", "ww"} print(p) 打印的结果是不固定, 所以集合无序 结果为 : {"ww", "zs", "ls"} s {"zs", &quo…

Laravel 6 - 第十三章 请求

​ 文章目录 Laravel 6 - 第一章 简介 Laravel 6 - 第二章 项目搭建 Laravel 6 - 第三章 文件夹结构 Laravel 6 - 第四章 生命周期 Laravel 6 - 第五章 控制反转和依赖注入 Laravel 6 - 第六章 服务容器 Laravel 6 - 第七章 服务提供者 Laravel 6 - 第八章 门面 Laravel 6 - …

Mysql全局优化总结

Mysql全局优化总结 从上图可以看出SQL及索引的优化效果是最好的&#xff0c;而且成本最低&#xff0c;所以工作中我们要在这块花更多时间 服务端系统参数 官方文档&#xff1a;https://dev.mysql.com/doc/refman/8.0/en/server-system-variables.html#sysvar_max_connections…

MySQL中的死锁预防和解决

MySQL中的死锁预防和解决 死锁是数据库管理系统中常见的问题&#xff0c;特别是在高并发的应用场景下。MySQL数据库中的死锁会导致事务处理速度减慢&#xff0c;甚至完全停止&#xff0c;因此理解并预防死锁至关重要。本文将详细介绍如何预防MySQL中的死锁&#xff0c;包括常用…

oracle 12c+ max_string_size参数

一个客户的数据库版本是19.3,在做数据库复制的时候,目标端报错了,查看了一下问题发现表的字段长度有不对,在12c以前我们都知道varchar的长度最大是4000,但是客户这里居然有32767: 把客户的建表语句弄出来,放到我的一个19c的测试环境进行测试: 发现报错了: 这里报错很明显了,是M…

重发布实验:

要求&#xff1a; 配置&#xff1a; 配置IP地址&#xff1a; Ar1&#xff1a; [a1]int g 0/0/0 [a1-GigabitEthernet0/0/0]ip add 100.1.1.1 24 [a1-GigabitEthernet0/0/0]int l 0 [a1-LoopBack0]ip add 192.168.0.1 32 [a1-LoopBack0]int l1 [a1-LoopBack1]ip add 192…

Java | 冒泡排序算法实现

大家可以关注一下专栏&#xff0c;方便大家需要的时候直接查找&#xff0c;专栏将持续更新~ 题目描述 编写一个Java程序&#xff0c;实现冒泡排序算法。程序需要能够接收一个整型数组作为输入&#xff0c;并输出排序后的数组。 冒泡排序是一种简单的排序算法&#xff0c;它…

计算机网络 TCP/IP体系 物理层

一. TCP/IP体系 物理层 1.1 物理层的基本概念 物理层作为TCP/IP网络模型的最低层&#xff0c;负责直接与传输介质交互&#xff0c;实现比特流的传输。 要完成物理层的主要任务&#xff0c;需要确定以下特性&#xff1a; 机械特性&#xff1a;物理层的机械特性主要涉及网络…

一些常见的Windows命令

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言看版本号查找端口启动程序杀死某个端口查看全部端口看ip进入目录就是总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 例如&#x…

云服务器搭建XSS-platform、DVWA靶机和Permeate论坛

目录 前言准备环境安装步骤一、 部署MySQL二、 系统部署三、系统安装主页介绍 前言 我发现目前网上的xss-platform的搭建教程都是基于本地搭建的&#xff0c;这样搭建好的xss平台只能在本地使用&#xff0c;无法测试别的网站。而网络上的大部分xss平台又几乎都是收费的&#x…

ubuntu 查询mysql的用户名和密码 ubuntu查看username

ubuntu 查询mysql的用户名和密码 ubuntu查看username 文章标签mysqlUbuntu用户名文章分类MySQL数据库 一.基本命令 1.查看Ubuntu版本 $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.5 LTS Release: 16.04 Coden…