当前位置: 首页 > news >正文

数据结构笔记第3篇:双向链表

1、双向链表的结构

注意:这里的 "带头" 跟前面我们说的 "头结点" 是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。

带头链表里的头结点,实际为 "哨兵位" ,哨兵位节点不存储任何有效元素,只是站在这里 "放哨的"。

"哨兵位" 存在的意义:

遍历循环链表避免死循环。

注意:双向链表中,哨兵位的下一个节点是链表的第一个节点(头结点)。哨兵位的前一个节点是链表的最后一个节点(尾结点)。所以双向链表的头插是在哨兵位的后面插入数据。尾插则是在哨兵位之前插入数据。

哨兵位是作为头结点和尾结点的中点,是头结点的起点也是尾节点的终点。这样解释更容易理解。

2、 双向链表的实现

List.h 链表函数链表节点类型的声明:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct ListNode
{SLDataType data;//存储数据struct ListNode* prve;//存储前一个节点的地址struct ListNode* next;//存储下一个节点的地址
}SList;
SList* SLInit();void SLPushBack(SList* phead, SLDataType x);//尾插
void SLPrint(SList* phead);//显示链表数据
void SLPustFront(SList* phead, SLDataType x);//头插
void SLPopBack(SList* phead);//尾删
void SLPopFront(SList* phead);//头删
void SLInsert(SList* pos, SLDataType x);//指定位置插入
SList* SLfind(SList* phead, SLDataType x);//查找节点
void SLEarse(SList* pos);//指定位置删除
void SLDestory(SList** pphead);//链表销毁

List.c 链表函数的实现:

#include "List.h"
//链表初始化
SList* SLInit()
{SList* phead = (SList*)malloc(sizeof(SList));if (phead == NULL){perror("malloc error");return NULL;}phead->data = -1;//因为是循环链表,所以初始化要遵循循环格式phead->next = phead;phead->prve = phead;return phead;
}
//创建链表节点
SList* ListBuyNode(SLDataType x)
{SList* retNode = (SList*)malloc(sizeof(SList));if (retNode == NULL){perror("malloc error");return NULL;}retNode->data = x;retNode->prve = retNode;retNode->next = retNode;return retNode;
}
//链表尾插
void SLPushBack(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->prve = phead->prve;Node->next = phead;phead->prve->next = Node;phead->prve = Node;
}
//链表数据显示
void SLPrint(SList* phead)
{assert(phead);SList* pcur = phead->next;while (pcur != phead)//哨兵位作为结束标识{printf("%d", pcur->data);if (pcur->next != phead)printf("->");pcur = pcur->next;}printf("\n");
}
//链表头插
void SLPustFront(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->next = phead->next;Node->prve = phead;phead->next->prve = Node;phead->next = Node;
}
//链表尾删
void SLPopBack(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->prve;del->prve->next = phead;phead->prve = del->prve;free(del);del = NULL;
}
//链表头删
void SLPopFront(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->next;del->next->prve = phead;phead->next = del->next;free(del);del = NULL;
}
//指定位置插入
void SLInsert(SList* pos, SLDataType x)
{assert(pos);SList* Node = ListBuyNode(x);Node->next = pos->next;Node->prve = pos;pos->next = Node;Node->next->prve = Node;
}
//查找节点
SList* SLfind(SList* phead, SLDataType x)
{assert(phead);SList* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//指定位置删除
void SLEarse(SList* pos)
{assert(pos);pos->prve->next = pos->next;pos->next->prve = pos->prve;free(pos);pos = NULL;
}
//链表销毁
void SLDestory(SList** pphead)
{assert(pphead && *pphead);SList* pcur = (*pphead)->next;while (pcur != *pphead){SList* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}

test.c 函数的调用:

#include "List.h"void SLtest()
{SList* plist = NULL;plist = SLInit();//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印:1->2->3->4//头插SLPustFront(plist, 5);SLPustFront(plist, 6);SLPustFront(plist, 7);SLPrint(plist);//打印:7->6->5->1->2->3->4//尾删SLPopBack(plist);SLPrint(plist);//打印:7->6->5->1->2->3//头删SLPopFront(plist);SLPrint(plist);//打印:6->5->1->2->3//指定位置插入SList* find = SLfind(plist, 5);SLInsert(find, 11);SLPrint(plist);//打印:6->5->11->1->2->3//指定位置删除find = SLfind(plist, 1);SLEarse(find);SLPrint(plist);//打印:6->5->11->2->3//链表销毁SLDestory(&plist);
}
int main()
{SLtest();return 0;
}

3、顺序表和双向链表的优缺点分析

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持O(N)
任意位置插入或者删除元素可能需要搬移元素,效率低O(N)只需要修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁

数据结构第3篇笔记到这里也就结束了,我们下一篇笔记再见-

相关文章:

数据结构笔记第3篇:双向链表

1、双向链表的结构 注意&#xff1a;这里的 "带头" 跟前面我们说的 "头结点" 是两个概念&#xff0c;实际前面的在单链表阶段称呼不严谨&#xff0c;但是为了同学们更好的理解就直接称为单链表的头结点。 带头链表里的头结点&#xff0c;实际为 "哨兵…...

详细对比Java SPI、Spring SPI 和 Dubbo SPI

SPI&#xff08;Service Provider Interface&#xff09;概述 定义&#xff1a;SPI是一种动态替换发现机制&#xff0c;用于实现接口与实现的解耦&#xff0c;提高框架的可扩展性。核心思想&#xff1a;解耦和方便扩展。 Java SPI 约定规范&#xff1a; 扩展类文件放在META-…...

CPU的核心数和线程数

CPU的核心数和线程数 一、关系&#xff1a; 1、线程数可以模拟出不同的CPU核心数。 CPU的核心数指的是硬件上存在着几个核心&#xff0c;而线程数可以模拟出多个核心数的功能。线程数越多&#xff0c;越有利于同时运行多个程序&#xff0c;因为线程数等同于在某个瞬间CPU能同…...

电脑游戏录屏,3款实用软件推荐给你

在电竞游戏热潮席卷全球的今天&#xff0c;电脑游戏录屏早已不再是简单的画面捕捉&#xff0c;它成为了记录电竞风采、打造专属游戏记忆的重要手段。通过游戏录屏&#xff0c;我们可以定格游戏中的精彩瞬间&#xff0c;重温那些令人热血沸腾的电竞时刻。那么&#xff0c;在进行…...

C#桌面应用开发:番茄定时器

C#桌面应用开发&#xff1a;番茄定时器 1、环境搭建和工程创建&#xff1a; 步骤一&#xff1a;安装visual studio2022 步骤二&#xff1a;新建工程 2、制作窗体部件 *踩过的坑&#xff1a; &#xff08;1&#xff09;找不到工具箱控件&#xff0c;现象如下&#xff1a;…...

PHP智慧门店微信小程序系统源码

&#x1f50d;【引领未来零售新风尚】&#x1f50d; &#x1f680;升级启航&#xff0c;智慧零售新篇章&#x1f680; 告别传统门店的束缚&#xff0c;智慧门店v3微信小程序携带着前沿科技与人性化设计&#xff0c;正式启航&#xff01;这个版本不仅是对过往功能的全面优化&a…...

SerDes介绍以及原语使用介绍(2)OSERDESE2原语仿真

文章目录 前言一、SDR模式1.1、设计代码1.2、testbench代码1.3、仿真分析 二、DDR模式下2.1、设计代码2.2、testbench代码2.3、仿真分析 三、OSERDES2级联3.1、设计代码3.2、testbench代码3.3、代码分析 前言 上文通过xilinx ug471手册对OSERDESE有了简单的了解&#xff0c;接…...

【稳定检索/投稿优惠】2024年教育、人文发展与艺术国际会议(EHDA 2024)

2024 International Conference on Education, Humanities Development and Arts 2024年教育、人文发展与艺术国际会议 【会议信息】 会议简称&#xff1a;EHDA 2024 大会时间&#xff1a;点击查看 截稿时间&#xff1a;点击查看 大会地点&#xff1a;中国北京 会议官网&#…...

Docker拉取失败,利用 Git将 Docker镜像重新打 Tag 推送到阿里云等其他公有云镜像仓库里

目录 一、开通阿里云容器镜像服务 二、Git配置 三、去DockerHub找镜像 四、编写images.txt文件 ​五、演示 六、其他注意事项 最近一段时间 Docker 镜像一直是 Pull 不下来的状态&#xff0c;想直连 DockerHub 是几乎不可能的。更糟糕的是&#xff0c;很多原本可靠的国内…...

【区分vue2和vue3下的element UI Breadcrumb 面包屑组件,分别详细介绍属性,事件,方法如何使用,并举例】

在 Vue 2 中&#xff0c;Element UI 提供了 el-breadcrumb 面包屑组件&#xff0c;而在 Vue 3 中&#xff0c;Element UI 的官方版本并没有直接更新以支持 Vue 3&#xff0c;但有一个类似的库叫做 Element Plus&#xff0c;它是为 Vue 3 设计的。 Vue 2 Element UI 在 Vue 2…...

gdb调试命令大全

基本命令 #gdb test test是要调试的程序&#xff0c;由gcc test.c -g -o test生成。进入后提示符变为(gdb) 。 start &#xff1a; 指令会执行程序至main() 主函数的起始位置&#xff0c;即在main() 函数的第一行语句处停止执行&#xff08;该行代码尚未执行&#xff09; cont…...

ESP32之arduino环境安装及点灯

目录 前言 前两天安装了VS&#xff43;&#xff4f;&#xff44;&#xff45;&#xff0c;奈何资源找的困难&#xff0c;于是咨询淘宝客服&#xff0c;他说&#xff41;&#xff52;&#xff44;&#xff55;&#xff49;&#xff4e;&#xff4f;用的多,资源多.然后就安装了a…...

查看VUE中安装包依赖的版本号

查看VUE中安装包依赖的版本号 全部依赖包版本查看某个依赖的例&#xff1a;查看stompjs 应用命令npm ls stompjs 全部依赖包版本 使用npm命令 使用 npm ls 命令可以列出项目中所有已安装的依赖包及其版本。 使用 npm list --depth1 命令可以列出项目中直接依赖的包及其版本&a…...

博途通讯笔记1:1200与1200之间S7通讯

目录 一、添加子网连接二、创建PUT GET三、各个参数的意义 一、添加子网连接 二、创建PUT GET 三、各个参数的意义...

Kafka搭建(集群版)

Kafka单机版 部署前提 VMware环境 : 两台centos系统 Jdk包:jdk-8u202-linux-x64.tar.gz Kafka包:kafka_2.12-3.5.0.tgz Zookeeper包:apache-zookeeper-3.7.2-bin.tar.gz 百度网盘自取: 链接: https://pan.baidu.com/s/11EWuhBoSmH3musd_3Rgodw?pwde32t 提取码: e32t Kafka搭建…...

【康复学习--LeetCode每日一题】3115. 质数的最大距离

题目&#xff1a; 给你一个整数数组 nums。 返回两个&#xff08;不一定不同的&#xff09;质数在 nums 中 下标 的 最大距离。 示例 1&#xff1a; 输入&#xff1a; nums [4,2,9,5,3] 输出&#xff1a; 3 解释&#xff1a; nums[1]、nums[3] 和 nums[4] 是质数。因此答案是…...

【yolov8系列】ubuntu上yolov8的开启训练的简单记录

前言 yolov8的广泛使用&#xff0c;拉取yolov8源码工程&#xff0c;然后配置环境后直接运行&#xff0c;初步验证自己数据的检测效果&#xff0c;在数据集准备OK的情况下 需要信手拈来&#xff0c;以保证开发过程的高效进行。 本篇博客更注意为了方便自己使用时参考。顺便也记录…...

Scala学习笔记15: 文件和正则表达式

目录 第十五章 文件和正则表达式1- 读取行2- 从URL或者其它源读取3- 写入文本文件4- 序列化5- 正则表达式6- 正则表达式验证输入数据格式end 第十五章 文件和正则表达式 1- 读取行 在Scala中读取文件中的行可以通过不同的方法实现 ; 一种常见的方法是使用 scala.io.Source 对…...

外卖员面试现状

说明&#xff1a; 以下身份角色用符号代替 # 面试官 $ 求职者 # 看了您的简历你有两年半的送外卖经验&#xff0c;可以简单说一下您平时是怎么送外卖的吗? $ 我首先在平台接单然后到店里取餐&#xff0c;取到餐后到顾客留下的地址&#xff0c;再通知顾客取餐 # 你们也用电动…...

异步加载与动态加载

异步加载和动态加载在概念上有相似之处&#xff0c;但并不完全等同。 异步加载&#xff08;Asynchronous Loading&#xff09;通常指的是不阻塞后续代码执行或页面渲染的数据或资源加载方式。在Web开发中&#xff0c;异步加载常用于从服务器获取数据&#xff0c;而不需要用户等…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...