数据结构之带头双向循环链表

Ne0inhk

— 8 min read
数据结构之带头双向循环链表

前言：前面我们实现了顺序表和单链表，这次来实现一个结构更复杂的链表-----带头双向循环链表。不要被它的名字吓到哦，只是结构复杂而已，它的结构更有利于代码的实现。

1 双向循环链表的介绍

有了单链表的基础，要实现这个双向循环带头链表其实并不难。下面我们先来了解一下什么是双向循环带头链表。

在这里插入图片描述

这就是双向循环带头链表的结构图，可以很清晰的看到，这个链表需要两个指针，一个指向后继结点，一个指向前驱节点，其次还需要一个头结点。只是这个头结点并不需要存储有效数据。

2 双向循环链表的实现

2.1 双向循环带头链表的定义

//存储的数据类型typedefint LDataType;//链表的定义typedefstructListNode{ LDataType val;structListNode* next;//指向后继节点structListNode* prev;//指向前驱节点}LTNode;

2.2 双向循环带头链表的接口

//初始化双向循环带头链表‘ LTNode*ListInit();//打印voidListPrint(plist);//尾插voidListPushBack(LTNode* phead, LDataType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LDataType x);//头删voidListPopFront(LTNode* phead);//查找 LTNode*ListFind(LTNode* phead, LDataType x);//pos位置之前插入voidListInsert(LTNode* pos, LDataType x);//删除pos位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

2.2.1 初始化链表

//初始化双向循环带头链表 LTNode*ListInit(){//哨兵位头结点 LTNode* phead =(LTNode*)malloc(sizeof(LTNode));if(phead ==NULL){printf("malloc fail\n");exit(-1);} phead->next = phead; phead->prev = phead;return phead;}
在这里插入图片描述

2.2.2 创建新节点

//创建新节点 LTNode*BuyListNode(LDataType x){ LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);} newnode->val = x; newnode->prev=newnode->next=NULL;return newnode;}

2.2.3 链表尾插

//尾插voidListPushBack(LTNode* phead, LDataType x){assert(phead); LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->val = x;*/ LTNode* newnode =BuyListNode(x); newnode->next = phead; phead->prev = newnode; newnode->prev = tail; tail->next = newnode;}
在这里插入图片描述
通过phead->prev就可以找到链表的尾节点，增加的节点newnode->prev 应该链接链表尾节点，链表的尾节点链接newnode,newnode->next应 该链接链表的头结点，链表的头结点的prev保存newnode的地址，使 newnode成为链表新的尾节点。

2.2.4 链表头插

//头插voidListPushFront(LTNode* phead, LDataType x){assert(phead); LTNode* newnode =BuyListNode(x); LTNode* pheadNext = phead->next; phead->next = newnode; newnode->prev = phead; pheadNext->prev = newnode; newnode->next = pheadNext;}
在这里插入图片描述
先创建一个指针指向头结点的后继结点，再让newnode->next保存该 节点的地址，该节点的prev保存newnode的地址，phead->next保存 newnode的地址，newnode->prev保存头结点的地址。

2.2.5 链表尾删

//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; tailPrev->next = phead; phead->prev = tailPrev;free(tail);}
在这里插入图片描述
通过phead->prev找到链表尾节点，再通过尾节点的prev找到尾节点 的前驱节点，让该前驱节点的next指向phead,phead->prev指向该前 驱节点，最后释放尾节点。

2.2.6 链表头删

//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* head = phead->next; LTNode* next = head->next; next->prev = phead; phead->next = next;free(head);}
在这里插入图片描述
首先通过phead->next找到链表头结点的后继结点，再通过该后继结点找到下一个节点，使该节点的prev保存头结点的地址，头结点的next保存该节点的地址，最后释放该后继结点。

2.2.7 链表的查找

//查找 LTNode*ListFind(LTNode* phead, LDataType x){assert(phead); LTNode* cur = phead->next;while(cur != phead){if(cur->val == x){return cur;}else{ cur = cur->next;}}returnNULL;}

从头结点的后继结点开始遍历查找，找到了就返回该节点的地址，找不到返回NULL（当再一次遍历到头结点时，说明未找到）。

2.2.8 从pos位置之前插入

//pos位置之前插入voidListInsert(LTNode* pos, LDataType x){assert(pos !=NULL); LTNode* newnode =BuyListNode(x); LTNode* posPrev = pos->prev; posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode;}
在这里插入图片描述
首先找到pos位置的前驱节点，再让newnode->prev指向该前驱节 点，该前驱节点的next指向newnode,pos->prev指newnode, newnode->next指向pos。

2.2.9 删除pos位置

//删除pos位置voidListErase(LTNode* pos){assert(pos !=NULL); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev;free(pos);}
在这里插入图片描述
找到pos位置的前驱节点和后继结点，让该前驱节点的next指向该后 继结点，该后继结点的prev指向该前驱节点。

2.2.10 链表的打印

//打印voidListPrint(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->val); cur = cur->next;}printf("\n");}

从头结点的后继结点开始遍历链表，当节点不是头结点时就打印该节点的值。

2.2.11 销毁链表

//销毁链表voidListDestroy(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){ LTNode* tmp = cur; cur = cur->next;free(tmp); tmp =NULL;} cur =NULL; phead =NULL;}

从头结点的后继结点开始销毁，先记录该后继结点的下一个节点，再销毁该后继结点。重复上述操作，直到再一次回到头结点的位置，此时销毁该头结点。

3 完整代码的实现

List.h文件

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LDataType;typedefstructListNode{ LDataType val;structListNode* next;structListNode* prev;}LTNode;//初始化双向循环带头链表‘ LTNode*ListInit();//打印voidListPrint(plist);//尾插voidListPushBack(LTNode* phead, LDataType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LDataType x);//头删voidListPopFront(LTNode* phead);//查找 LTNode*ListFind(LTNode* phead, LDataType x);//pos位置之前插入voidListInsert(LTNode* pos, LDataType x);//删除pos位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

List.c文件

#define_CRT_SECURE_NO_WARNINGS#include"List.h"//初始化双向循环带头链表 LTNode*ListInit(){//哨兵位头结点 LTNode* phead =(LTNode*)malloc(sizeof(LTNode));if(phead ==NULL){printf("malloc fail\n");exit(-1);} phead->next = phead; phead->prev = phead;return phead;}//打印voidListPrint(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->val); cur = cur->next;}printf("\n");}//销毁链表voidListDestroy(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){ LTNode* tmp = cur; cur = cur->next;free(tmp); tmp =NULL;} cur =NULL; phead =NULL;}//创建新节点 LTNode*BuyListNode(LDataType x){ LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);} newnode->val = x;//newnode->prev = newnode->next = NULL;return newnode;}//尾插voidListPushBack(LTNode* phead, LDataType x){assert(phead); LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->val = x;*/ LTNode* newnode =BuyListNode(x); newnode->next = phead; phead->prev = newnode; newnode->prev = tail; tail->next = newnode;}//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev;//free(tail); tailPrev->next = phead; phead->prev = tailPrev;free(tail);}//头插voidListPushFront(LTNode* phead, LDataType x){assert(phead); LTNode* newnode =BuyListNode(x); LTNode* pheadNext = phead->next; phead->next = newnode; newnode->prev = phead; pheadNext->prev = newnode; newnode->next = pheadNext;}//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* head = phead->next; LTNode* next = head->next; next->prev = phead; phead->next = next;free(head);}//查找 LTNode*ListFind(LTNode* phead, LDataType x){assert(phead); LTNode* cur = phead->next;while(cur != phead){if(cur->val == x){return cur;}else{ cur = cur->next;}}returnNULL;}//pos位置之前插入voidListInsert(LTNode* pos, LDataType x){assert(pos !=NULL); LTNode* newnode =BuyListNode(x); LTNode* posPrev = pos->prev; posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode;}//删除pos位置voidListErase(LTNode* pos){assert(pos !=NULL); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev;free(pos);}

test.c文件

#define_CRT_SECURE_NO_WARNINGS#include"List.h"voidListTest1(){ LTNode* plist =ListInit();ListPushBack(plist,1);ListPushBack(plist,2);ListPushBack(plist,3);ListPushBack(plist,4);ListPushBack(plist,5);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPushFront(plist,6);ListPushFront(plist,7);ListPushFront(plist,8);ListPushFront(plist,9);ListPushFront(plist,10);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist); LTNode* pos =ListFind(plist,2);if(NULL!= pos){printf("找到了\n");}else{printf("找不到\n");}ListInsert(pos,10);ListPrint(plist); pos =ListFind(plist,1);ListErase(pos);ListPrint(plist);ListDestroy(plist); plist =NULL;//ListPrint(plist);}intmain(){ListTest1();return0;}

4 顺序表与链表的对比

在这里插入图片描述

Read more

SpringBoot之拦截器

SpringBoot之拦截器

目录 拦截器 拦截器的使用 自定义拦截器 注册配置拦截器 拦截器详解 拦截器路径 拦截器执行流程 修改之前登录校验功能 定义拦截器 注册配置拦截器 DispatcherServlet源码解析（重要） 初始化 编辑 处理请求（核心） 适配器模式 适配器模式定义 适配器模式角色 适配器模式的实现 适配器模式的优缺点 适配器模式的应用场景 拦截器 之前我们完成的图书管理系统完成了强制登录的功能, 实现原理是后端在用户登录成功后会把用户信息存储到了Session中，后端程序根据Session来判断用户是否登录, 但是这样是⽐较麻烦的： • 需要修改每个接⼝的处理逻辑 • 需要修改每个接⼝的返回结果 • 接⼝定义修改, 前端代码也需要跟着修改 有没有更简单的办法, 统⼀拦截所有的请求, 并进⾏Session校验呢？ 这⾥我们学习⼀种新的解决办法: 拦截器。  拦截器是Spring框架提供的核⼼功能之⼀, 主要⽤来拦截⽤⼾的请求,

By Ne0inhk
最新Python爬虫实战（入门爬虫篇）——案例14：某度热榜数据采集（详细爬虫思路截图+抓包动图演示＋完整爬虫代码＋详细注释）

最新Python爬虫实战（入门爬虫篇）——案例14：某度热榜数据采集（详细爬虫思路截图+抓包动图演示＋完整爬虫代码＋详细注释）

【爬取目标】 目标网站：某度热搜 在热点舆情分析、内容选题策划、SEO优化、新媒体运营等场景中，某度热榜是反映全网用户搜索焦点的核心数据源。手动整理热榜中的排名、标题、热度指数、描述等信息耗时且易出错，本文将教你使用 Python 编写爬虫程序，批量爬取某度热榜数据并自动保存到 Excel 文件，快速搭建专属热点信息库！ 【实现效果】 代码实现批量爬取某度热榜榜单数据，整理结构化信息后存放到 Excel 文件中，包含热榜排名、热搜标题、热度指数、热搜描述、跳转链接等核心字段： 文章目录 * 一、技术栈和环境版本 * 二、爬虫实战分析 * 2.1 导入模块 * 2.2 分析网页 * 2.3 发送请求，获取网页源码 * 2.4 解析数据 * 2.5 存储数据

By Ne0inhk
直击复杂 SQL 瓶颈：基于代价的连接条件下推技术落地

直击复杂 SQL 瓶颈：基于代价的连接条件下推技术落地

一、引言 在数据库理论的学习过程中，我们常常接触到简洁优美的SQL示例——单表查询、简单连接、基础过滤，这些案例清晰地展示了关系代数的基本原理。然而，当我们步入真实的业务系统，面对的SQL语句往往如同缠绕的线团：公用表表达式(CTE)层层嵌套，子查询彼此交织，窗口函数与聚集计算随处可见。 这种复杂性并非开发人员的炫技，而是业务逻辑的自然映射。遗憾的是，这种为提升可读性而组织的SQL结构，却给查询优化器带来了严峻考验。在众多性能瓶颈中，有一个问题尤为突出：高选择性的连接条件无法穿透复杂的子查询结构，导致数据过滤发生在错误的时间点。本文将深入探讨这一问题的本质，并介绍一种基于代价模型的连接条件下推解决方案，展示如何让优化器既懂“安全”，又知“成本”。 二、性能困境：过滤迟到的代价 2.1 真实场景的切面分析 在大量客户业务系统中，一种常见的SQL编写模式反复出现：开发人员习惯先在子查询或CTE中完成复杂的预处理逻辑——去重、排序、窗口计算，然后再将这些预处理结果与其它表进行连接，最后施加过滤条件。从业务语义角度看，这种写法清晰自然；但从执行效率角度看，却暗藏危机。 考虑

By Ne0inhk
Spring Boot 消息队列与异步通信

Spring Boot 消息队列与异步通信

Spring Boot 消息队列与异步通信 21.1 学习目标与重点提示 学习目标：掌握Spring Boot消息队列与异步通信的核心概念与使用方法，包括消息队列的定义与特点、Spring Boot与ActiveMQ的集成、Spring Boot与RabbitMQ的集成、Spring Boot与Kafka的集成、Spring Boot异步通信的基本方法、Spring Boot的实际应用场景，学会在实际开发中处理消息队列与异步通信问题。 重点：消息队列的定义与特点、Spring Boot与ActiveMQ的集成、Spring Boot与RabbitMQ的集成、Spring Boot与Kafka的集成、Spring Boot异步通信的基本方法、Spring Boot的实际应用场景。 21.2 消息队列概述 消息队列是Java开发中的重要组件。 21.2.1 消息队列的定义 定义：消息队列是一种异步通信机制，用于在应用程序之间传递消息。 作用： * 实现应用程序之间的异步通信。 * 实现应用程序之间的解耦。 * 提高应用程序的性能。 常见的消息队列： * Activ

By Ne0inhk