【数据结构】05.双向链表

一、双向链表的结构

在这里插入图片描述

注意:这里的“带头”跟前面我们说的“头节点”是两个概念,带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”。
“哨兵位”存在的意义:遍历循环链表避免死循环。

二、双向链表的实现

2.1 双向链表结点的创建

typedef int DLType;
//创建结构体
typedef struct DList
{DLType data;struct DList* prev;struct DList* next;
}DL;

2.2 双向链表的初始化与销毁

//初始化phead
DL* init(void)
{DL* phead = BuyNewNode(0);return phead;
}
//销毁链表,这里需要主要phead是形参,这里的最后将phead置空并不能将原链表中的phead置空,
//因此原链表中的phead需要手动置空,详细实现见源码
void DLDesdroy(DL* phead)
{assert(phead);DL* tail =phead->next;while (tail != phead){DL* next = tail->next;free(tail); tail= next;}free(phead);phead = NULL;
}

2.3 双向链表的增删查改

由于多次创建结点,因此我们将它提炼为一个函数

//创造新的节点
DL* BuyNewNode(DLType  x)
{DL* newnode = (DL*)malloc(sizeof(DL));if (newnode == NULL){perror("malloc is failed!\n");return 1;}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}
//尾插
void  DLPushBack(DL* phead,DLType x)
{assert(phead);DL* newnode = BuyNewNode(x);newnode->next = phead;phead->prev->next = newnode;newnode->prev = phead->prev;phead->prev = newnode;
}//尾删
void DLPopBack(DL* phead)
{assert(phead);assert(phead->next != phead);DL* tail = phead->prev;DL* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;  }//头插
void DLPushFront(DL* phead, DLType x)
{assert(phead);DL* newnode = BuyNewNode(x);DL* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev=phead;
}//头删
void DLPopFront(DL* phead)
{assert(phead);assert(phead->next != phead);DL* first = phead->next;DL* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}//查找
DL* DLFind(DL* phead,DLType x)
{assert(phead);DL* cur = phead->next;while ( cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//pos位置插入数据
void DLInsert(DL* pos,DLType x)
{assert(pos);DL* newnode = BuyNewNode(x);DL* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}//pos位置之后插入数据
void DLInsertAfter(DL* pos, DLType x)
{assert(pos);DL* newnode = BuyNewNode(x);DL* next = pos->next;newnode->next = next;next->prev = newnode;pos->next = newnode;newnode->prev = pos;
}//删除pos位置元素
void  DLErase(DL* pos)
{assert(pos);DL* next = pos->next;DL* prev = pos->prev;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}

2.4 双向链表的打印

//打印链表
void DLPrint(DL* phead)
{DL* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

2.5 双向链表的源码

//DL.h#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int DLType;typedef struct DList
{DLType data;struct DList* prev;struct DList* next;
}DL;//初始化
DL* init(void);
//打印
void DLPrint(DL* phead);//尾插、尾删
void  DLPushBack(DL* phead, DLType x);
void DLPopBack(DL* phead);//头插、头删
void  DLPushFront(DL* phead, DLType x);
void  DLPopFront(DL* phead);//查找
DL* DLFind(DL* phead, DLType x);//指定位置插入数据、指定位置之后插入数据
void  DLInsert(DL* pos, DLType x);
void DLInsertAfter(DL* pos, DLType x);//删除pos
void  DLErase(DL* phead);void DLDesdroy(DL** phead);
//DL.c
#include "DList.h"//创造新的节点
DL* BuyNewNode(DLType  x)
{DL* newnode = (DL*)malloc(sizeof(DL));if (newnode == NULL){perror("malloc is failed!\n");return 1;}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//初始化phead
DL* init(void)
{DL* phead = BuyNewNode(0);return phead;
}//打印链表
void DLPrint(DL* phead)
{DL* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//尾插
void  DLPushBack(DL* phead,DLType x)
{assert(phead);DL* newnode = BuyNewNode(x);newnode->next = phead;phead->prev->next = newnode;newnode->prev = phead->prev;phead->prev = newnode;
}//尾删
void DLPopBack(DL* phead)
{assert(phead);assert(phead->next != phead);DL* tail = phead->prev;DL* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;  }//头插
void DLPushFront(DL* phead, DLType x)
{assert(phead);DL* newnode = BuyNewNode(x);DL* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev=phead;
}//头删
void DLPopFront(DL* phead)
{assert(phead);assert(phead->next != phead);DL* first = phead->next;DL* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}//查找
DL* DLFind(DL* phead,DLType x)
{assert(phead);DL* cur = phead->next;while ( cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//pos位置插入数据
void DLInsert(DL* pos,DLType x)
{assert(pos);DL* newnode = BuyNewNode(x);DL* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}//pos位置之后插入数据
void DLInsertAfter(DL* pos, DLType x)
{assert(pos);DL* newnode = BuyNewNode(x);DL* next = pos->next;newnode->next = next;next->prev = newnode;pos->next = newnode;newnode->prev = pos;
}//删除
void  DLErase(DL* pos)
{assert(pos);DL* next = pos->next;DL* prev = pos->prev;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}//销毁链表
void DLDesdroy(DL* phead)
{assert(phead);DL* tail =phead->next;while (tail != phead){DL* next = tail->next;free(tail); tail= next;}free(phead);phead = NULL;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/370928.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

cs231n作业1——KNN

参考文章&#xff1a;assignment1——KNN KNN 测试时分别计算测试样本和训练集中的每个样本的距离&#xff0c;然后选取距离最近的k个样本的标签信息来进行分类。 方法1&#xff1a;Two Loops for i in range(num_test):for j in range(num_train):dist X[i, :] - self.X…

Python爬虫获取视频

验证电脑是否安装python 1.winr输入cmd 2.在黑窗口输入 python.exe 3.不是命令不存在就说明python环境安装完成 抓取快手视频 1.在phcharm应用中新建一个项目 3.新建一个python文件 4.选择python文件,随便起一个名字后按回车 5.安装requests pip install requests 6.寻找需要的…

苹果电脑能玩赛博朋克2077吗 如何在mac上运行赛博朋克2077 crossover能玩什么游戏

各位喜欢赛博朋克风的一定不能错过《赛博朋克2077》。那么《赛博朋克2077》是一款什么样的游戏&#xff1f;《赛博朋克2077》在苹果电脑上可以运行吗&#xff1f;一起来看看介绍吧。 一、《赛博朋克2077》是一款什么样的游戏&#xff1f; 《赛博朋克2077》是一款由CD Projekt …

【Java探索之旅】初识多态_概念_实现条件

文章目录 &#x1f4d1;前言一、多态1.1 概念1.2 多态的实现条件 &#x1f324;️全篇总结 &#x1f4d1;前言 多态作为面向对象编程中的重要概念&#xff0c;为我们提供了一种灵活而强大的编程方式。通过多态&#xff0c;同一种操作可以应用于不同的对象&#xff0c;并根据对象…

Spring Boot基础篇

快速上手 SpringBoot是由Pivotal团队提高的全新框架&#xff0c;其设计目的是用来简化Spring应用的初始化搭建以及开发过程 入门案例 在Idea创建 创建时要选择Spring Initializr。 Server URL为要连接的网站&#xff0c;默认为官网start.spring.io&#xff08;访问速度慢&…

【教程】新的Selenium!整合了隐藏浏览器指纹等功能

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你&#xff0c;欢迎[点赞、收藏、关注]哦~ 目录 前景提要 driver Driver() 常用driver 接口 最后的话 前景提要 新的selenium&#xff0c;整合了隐藏浏览器指纹&#xff0c;非常好用&#x…

树状数组求三元上升子序列

分析一下&#xff0c;感觉没什么思路&#xff0c;再想一下&#xff0c;结果不就是每一位的数小于它的数乘以大于大于这位数的相乘之和吗&#xff0c;我们可以利用逆序对的思维求得 关键点在于求解逆序对的时候值相同的时候&#xff0c;位置大的优先级更高处理 #define _CRT_SEC…

大型能源电力集团需要什么样的总部数据下发系统?

能源电力集团的组织结构是一个复杂的系统&#xff0c;包括多个职能部门和子分公司。这些子分公司负责具体的电力生产、销售、运维等业务。这些部门和公司协同工作&#xff0c;确保电力生产的顺利进行&#xff0c;同时关注公司的长期发展、市场拓展、人力资源管理、财务管理和公…

算法 —— 滑动窗口

目录 长度最小的子数组 无重复字符的最长子串 最大连续1的个数 将x减到0的最小操作数 找到字符串中所有字母异位词 最小覆盖子串 长度最小的子数组 sum比target小就进窗口&#xff0c;sum比target大就出窗口&#xff0c;由于数组是正数&#xff0c;所以相加会使sum变大&…

数据结构基础--------【二叉树基础】

二叉树基础 二叉树是一种常见的数据结构&#xff0c;由节点组成&#xff0c;每个节点最多有两个子节点&#xff0c;左子节点和右子节点。二叉树可以用来表示许多实际问题&#xff0c;如计算机程序中的表达式、组织结构等。以下是一些二叉树的概念&#xff1a; 二叉树的深度&a…

Ubuntu 20.04下多版本CUDA的安装与切换 超详细教程

目录 前言一、安装 CUDA1.找到所需版本对应命令2.下载 .run 文件3.安装 CUDA4.配置环境变量4.1 写入环境变量4.2 软连接 5.验证安装 二、安装 cudnn1.下载 cudnn2.解压文件3.替换文件4.验证安装 三、切换 CUDA 版本1.切换版本2.检查版本 前言 当我们复现代码时&#xff0c;总会…

计算机如何存储浮点数

浮点数组成 在计算机中浮点数通常由三部分组成&#xff1a;符号位、指数位、尾数位。IEEE-754中32位浮点数如下&#xff1a; 上图32bit浮点数包含1bit的符号位&#xff0c;8比特的指数位和23bit的尾数位。对于一个常规浮点数&#xff0c;我们来看看它是如何存储和计算的。这里…

数据库系统原理 | 查询作业2

整理自博主本科《数据库系统原理》专业课自己完成的实验课查询作业&#xff0c;以便各位学习数据库系统概论的小伙伴们参考、学习。 *文中若存在书写不合理的地方&#xff0c;欢迎各位斧正。 专业课本&#xff1a; ​ ​ ———— 本次实验使用到的图形化工具&#xff1a;Heidi…

CTF常用sql注入(一)联合注入和宽字节

0x01 前言 给自己总结一下sql注入的常用姿势吧&#xff0c;记录一下学习 0x02 联合 联合注入的关键词是union SQL的union联合注入原理是联合两个表进行注入攻击&#xff0c;使用union select关键词来进行联合查询。 那么为什么我们在题目中一般是只写一个呢 因为 $sql &quo…

SwiftData 模型对象的多个实例在 SwiftUI 中不能及时同步的解决

概览 我们已经知道,用 CoreData 在背后默默支持的 SwiftUI 视图在使用 @FetchRequest 来查询托管对象集合时,若查询结果中的托管对象在别处被改变将不会在 FetchedResults 中得到及时的刷新。 那么这一“囧境”在 SwiftData 里是否也会“卷土重来”呢?空说无益,就让我们在…

redis 如何使用 scan, go语言

建议用方案乙 文章目录 场景方案方案甲方案乙 拓展 场景 redis 中存在大量 key。 其中有一部分是用户登陆的 session_id&#xff0c; 结构是 &#xff1a; session_id:1session_id:2session_id:3需求&#xff1a; 有多少用户在线 方案 方案甲 keys session_id:*这种方式简…

FlinkSQL 开发经验分享

作者&#xff1a;汤包 最近做了几个实时数据开发需求&#xff0c;也不可避免地在使用 Flink 的过程中遇到了一些问题&#xff0c;比如数据倾斜导致的反压、interval join、开窗导致的水位线失效等问题&#xff0c;通过思考并解决这些问题&#xff0c;加深了我对 Flink 原理与机…

华为云简介

前言 华为云是华为的云服务品牌&#xff0c;将华为30多年在ICT领域的技术积累和产品解决方案开放给客户&#xff0c;致力于提供稳定可靠、安全可信、可持续创新的云服务&#xff0c;赋能应用、使能数据、做智能世界的“黑土地”&#xff0c;推进实现“用得起、用得好、用得放心…

鸿蒙应用笔记

安装就跳过了&#xff0c;一直点点就可以了 配置跳过&#xff0c;就自动下了点东西。 鸿蒙那个下载要12g个内存&#xff0c;大的有点吓人。 里面跟idea没区别 模拟器或者真机运行 真机要鸿蒙4.0&#xff0c;就可以实机调试 直接在手机里面跑&#xff0c;这个牛逼&#xf…

深度学习与CV入门

文章目录 前言历史 前言 历史 tensorflow可以安装Tensorboard第三方库用于展示效果 TensorFlow工作流程&#xff1a;p6-4:20 使用tf.data加载数据。使用tf.data实例化读取训练数据和测试数据模型的建立与调试:使用动态图模式Eager Execution和著名的神经网络高层API框架Ker…