数据结构——双向链表（带头、循环）

server/2025/1/22 18:28:23/

1、双链表

        双链表也是链表的一种，双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点

数据节点如下图所示： 

 2、双向带头循环链表

         带头双向循环链表是链表中带头（哨兵位）、双向、循环三种属性的结合体

（1）带头（哨兵位）：哨兵位只负责存储第一个具有有效数据的节点，本身不存放数据，该处因为为双向循环链表，代表也可访问该链表的尾节点；

（2）双向：每个节点不仅能访问该节点的后一个节点，同时也可访问本节点的前一个节点；

（3）循环：第一个节点的pre指向尾节点；

3、操作

3.1 结构体声明

typedef int elementType;
typedef struct DLink_List_Node {
    struct DLink_List_Node* pre;  //指向上一个节点指针
    elementType val;  //存储节点元素
    struct DLink_List_Node* next;  //指向下一个节点指针
}DLK;

3.2 初始化链表

        链表为带头双向循环练表，因为存在哨兵位，所以在插入数据之前应给链表安排一个哨兵位，并对哨兵位进行初始化 

        在对哨兵位进行初始化时同时也要注意该链表的结构为双向循环链表，在只有哨兵位的情况下，哨兵位的next与pre都指向自己 

//辅助函数：创建新节点
DLK* create_dnode() {
    DLK* newnode = (DLK*)malloc(sizeof(DLK));
    if (newnode == NULL) {
        printf("内存申请失败！\n");
        return NULL;
    }
    memset(newnode, 0, sizeof(DLK));
    return newnode;
}

//链表初始化，初始化一个哨兵位（不包含元素）
DLK* create_dlink() {
    //创建新节点
    DLK* newnode = create_dnode();
    newnode->pre = newnode;
    newnode->next = newnode;
    printf("初始化成功！\n");
    return newnode;
}

3.3 插入

3.3.1 头插

        因为该链表存在哨兵位，故在进行头插时需要插入至头节点（哨兵位）之后         

void head_Insert(DLK* DList, elementType value) {
    //(1)创建新节点
    DLK* newnode = create_dnode();
    //(2)存储节点元素
    newnode->val = value;
    //(3)插入
    newnode->next = DList->next;
    DList->next->pre = newnode;
    newnode->pre = DList;
    DList->next = newnode;
    printf("头插成功！\n");
}

3.3.2 中间插

//链表的中间插，在指定元素的后边插入元素

void mid_insert(DLK* temp, elementType newvalue) {
    //(1)创建新节点
    DLK* newnode = create_dnode();
    //(2)存储节点元素
    newnode->val = newvalue;
    //(3)插入
    newnode->next = temp->next;
    temp->next->pre = newnode;
    temp->next = newnode;
    newnode->pre = temp;
    printf("插入成功！\n");
}

3.3.3 尾插

void tail_insert(DLK* DList, elementType value) {
    assert(DList);
    //(1)创建新节点
    DLK* newnode = create_dnode();
    //(2)存储节点元素
    newnode->val = value;
    //(3)插入
    newnode->pre = DList->pre;  //DList->pre：原链表的最后一个节点
    DList->pre->next = newnode;
    DList->pre = newnode;
    newnode->next = DList;
    printf("尾插成功！\n");
}

3.4 删除 

3.4.1 头删

        同样的带头双向循环链表在进行头删时只需要删除头节点（哨兵位）后的节点即可

void head_delete(DLK* DList) {
    assert(DList);
    //(1)保存头节点（哨兵位的下一个元素节点）
    DLK* temp = DList->next;  
    //(2)将哨兵位与头节点的下一个元素节点相连
    DList->next = temp->next;
    temp->next->pre = DList;
    //(3)释放头节点
    free(temp);
    printf("头删成功！\n");
}

3.4.2 中间删

//思路：先查找要删除的元素位置，在进行删除操作
void middle_delete(DLK* temp) {  //temp：要删除的元素节点
    temp->pre->next = temp->next;  //temp->pre：要删除的元素节点的前一个元素
    temp->next->pre = temp->pre;
    free(temp);
    printf("删除成功！\n");
}

3.4.3 尾删

 void tail_delete(DLK* DList) {
    assert(DList);
    //(1)保存尾节点（哨兵位的上一个元素节点）
    DLK* temp = DList->pre;
    //(2)将哨兵位与尾节点的上一个元素节点相连
    DList->pre = temp->pre;
    temp->pre->next = DList;
    //(3)释放尾节点
    free(temp);
    printf("尾删成功！\n");
}

3.5 链表销毁

 //思路：遍历节点，一个一个释放，最后修改DList=NULL
void destroy(DLK** DList) {
    DLK* temp = (*DList)->next;  //->的优先级高，所以要用()
    while (temp != *DList) {
        DLK* ptr = temp->next;  //保存下一个元素节点
        free(temp);
        temp = ptr;
    }
    free(*DList);  //释放哨兵位
    *DList = NULL;  
}

4、完整代码

4.1 02双向链表.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h> 
#include <assert.h>
//双向链表//逻辑结构：线性结构//存储结构：链式存储//双向、带头、循环链表
typedef int elementType;
typedef struct DLink_List_Node {struct DLink_List_Node* pre;  //指向上一个节点指针elementType val;  //存储节点元素struct DLink_List_Node* next;  //指向下一个节点指针
}DLK;void print_menu();
DLK* create_dnode();
DLK* create_dlink();
void head_Insert(DLK* DList, elementType value);
void print_dlink(DLK* DList);
void tail_insert(DLK* DList, elementType value);
void head_delete(DLK* DList);
void tail_delete(DLK* DList);
DLK* find_item(DLK* DList, elementType value);
void middle_delete(DLK* temp);
void mid_insert(DLK* temp, elementType newvalue);
void edit_dlink(DLK* DList, elementType value, elementType newvalue);
void destroy(DLK** DList);void fn4();

4.2 main.c

#include "02双向链表.h"
int main() {fn4();return 0;
}

4.3 02双向链表.c

#include "02双向链表.h"
void fn4() {print_menu();int order = 0;DLK* DList = NULL;  //存储双链表的哨兵位elementType value = 0;DLK* temp = NULL;elementType newvalue = 0;while (1) {printf("请输入操作指令：");scanf("%d", &order);switch (order) {case 1:  //链表初始化，初始化一个哨兵位（不包含元素）DList = create_dlink();break;case 2:  //打印链表，遍历print_dlink(DList);break;case 3:  //链表头插printf("请输入要插入的元素：");scanf(" %d", &value);head_Insert(DList, value);break;case 4:  //链表尾插printf("请输入要尾插的元素：");scanf(" %d", &value);tail_insert(DList, value);break;case 5:  //链表头删，不是删除哨兵位，而是删除哨兵位的下一个元素节点head_delete(DList);break;case 6:  //链表尾删tail_delete(DList);break;case 7:  //链表的查找//思路：找到了，返回当前元素节点的指针；找不到，返回NULLprintf("请输入要查找的元素：");scanf(" %d", &value);temp = find_item(DList, value);if (temp == NULL) {printf("没有此元素！\n");}else {printf("找到了，该元素值为：%d\n", temp->val);}break;case 8:  //链表的中间删，至少要3个元素//思路：先查找要删除的元素位置，在进行删除操作printf("请输入要删除的元素：");scanf(" %d", &value);temp = find_item(DList, value);if (temp == NULL) {printf("没有此元素，无法删除！\n");}else {middle_delete(temp);}break;case 9:  //链表的中间插，在指定元素的后边插入元素//要求：至少有1个元素printf("请输入要插入的元素：");scanf(" %d", &newvalue);printf("请输入要在哪个元素的后边插入：");scanf(" %d", &value);temp = find_item(DList, value);if (temp == NULL) {printf("没有此元素，无法插入！\n");}else {mid_insert(temp, newvalue);}break;case 10:  //元素修改，把目标元素修改成指定元素/*destroy(&LinkNode);*/printf("请输入要修改的元素：");scanf(" %d", &value);printf("请输入修改后的值：");scanf(" %d", &newvalue);edit_dlink(DList, value, newvalue);break;case 11:  //链表销毁destroy(&DList);break;case 12:  //退出return;default:printf("输入错误，请重新输入！\n");}}
}
//菜单
void print_menu() {system("cls");  //屏幕清空printf("操作指令说明：\n");printf("1：链表初始化\n2：打印链表\n");printf("3：链表头插\n4：链表尾插\n");printf("5：链表头删\n6：链表尾删\n");printf("7：链表的查找\n8：链表的中间删\n");printf("9：链表的中间插\n10：元素修改\n");printf("11：链表销毁\n12：退出\n");printf("************************\n");
}//辅助函数：创建新节点
DLK* create_dnode() {DLK* newnode = (DLK*)malloc(sizeof(DLK));if (newnode == NULL) {printf("内存申请失败！\n");return NULL;}memset(newnode, 0, sizeof(DLK));return newnode;
}//链表初始化，初始化一个哨兵位（不包含元素）
DLK* create_dlink() {//创建新节点DLK* newnode = create_dnode();newnode->pre = newnode;newnode->next = newnode;printf("初始化成功！\n");return newnode;
}//链表头插
void head_Insert(DLK* DList, elementType value) {//(1)创建新节点DLK* newnode = create_dnode();//(2)存储节点元素newnode->val = value;//(3)插入newnode->next = DList->next;DList->next->pre = newnode;newnode->pre = DList;DList->next = newnode;printf("头插成功！\n");
}//打印链表，遍历
void print_dlink(DLK* DList) {assert(DList);DLK* temp = DList->next;  //存储当前节点（哨兵位的下一个）while (temp != DList) {printf("%d ", temp->val);temp = temp->next;}printf("\n");
}//链表尾插
void tail_insert(DLK* DList, elementType value) {assert(DList);//(1)创建新节点DLK* newnode = create_dnode();//(2)存储节点元素newnode->val = value;//(3)插入newnode->pre = DList->pre;DList->pre->next = newnode;DList->pre = newnode;newnode->next = DList;printf("尾插成功！\n");
}//链表头删，不是删除哨兵位，而是删除哨兵位的下一个元素节点
void head_delete(DLK* DList) {assert(DList);//(1)保存头节点（哨兵位的下一个元素节点）DLK* temp = DList->next;  //(2)将哨兵位与头节点的下一个元素节点相连DList->next = temp->next;temp->next->pre = DList;//(3)释放头节点free(temp);printf("头删成功！\n");
}//链表尾删
void tail_delete(DLK* DList) {assert(DList);//(1)保存尾节点（哨兵位的上一个元素节点）DLK* temp = DList->pre;//(2)将哨兵位与尾节点的上一个元素节点相连DList->pre = temp->pre;temp->pre->next = DList;//(3)释放尾节点free(temp);printf("尾删成功！\n");
}//链表的查找
//思路：找到了，返回当前元素节点的指针；找不到，返回NULL
DLK* find_item(DLK* DList, elementType value) {assert(DList);//遍历链表元素，判断是否是目标元素DLK* temp = DList->next;while (temp != DList) {if (temp->val == value) {return temp;}temp = temp->next;}return NULL;
}//链表的中间删，至少要3个元素
//思路：先查找要删除的元素位置，在进行删除操作
void middle_delete(DLK* temp) {temp->pre->next = temp->next;temp->next->pre = temp->pre;free(temp);printf("删除成功！\n");
}//链表的中间插，在指定元素的后边插入元素
void mid_insert(DLK* temp, elementType newvalue) {//(1)创建新节点DLK* newnode = create_dnode();//(2)存储节点元素newnode->val = newvalue;//(3)插入newnode->next = temp->next;temp->next->pre = newnode;temp->next = newnode;newnode->pre = temp;printf("插入成功！\n");
}//元素修改，把目标元素修改成指定元素
void edit_dlink(DLK* DList, elementType value, elementType newvalue) {assert(DList);//查找value元素所在的位置DLK* temp = find_item(DList, value);if (temp == NULL) {printf("没有此元素，无法修改！\n");return;}else {temp->val = newvalue;printf("修改成功！\n");}
}//链表销毁
//思路：遍历节点，一个一个释放，最后修改DList=NULL
void destroy(DLK** DList) {DLK* temp = (*DList)->next;  //->的优先级高，所以要用()while (temp != *DList) {DLK* ptr = temp->next;  //保存下一个元素节点free(temp);temp = ptr;}free(*DList);  //释放哨兵位*DList = NULL;  
}

http://www.ppmy.cn/server/160532.html

相关文章

RavenMarket：用AI和区块链重塑预测市场

RavenMarket：用AI和区块链重塑预测市场

不论是美股市场还是加密市场&#xff0c;AI都是本轮周期里的最大叙事。本轮AI的最大受益者英伟达市值超越苹果一跃成为全球第一大公司&#xff0c;加密领域围绕着AI的创新也是层出不穷&#xff0c;很多项目方开始向着AI转型。 而近期币圈最热门的板块就是AI agent&#xff0c;…
阅读更多...
研究机构科研管控系统（源码+文档+部署+讲解）

研究机构科研管控系统（源码+文档+部署+讲解）

引言 在科研机构中&#xff0c;科研项目的管控是确保研究质量和效率的关键。科研管控系统作为一个创新的数字化解决方案&#xff0c;通过智能化管理和服务&#xff0c;提升了科研项目管理的透明度和效率。 系统概述 科研管控系统采用前后端分离的架构设计&#xff0c;服务端…
阅读更多...
React+Cesium基础教程（001）：创建基于React的Cesium项目及对Cesium进行基本配置

React+Cesium基础教程（001）：创建基于React的Cesium项目及对Cesium进行基本配置

文章目录 01-基于react的cesium项目创建基于React的Cesium项目Cesium基本配置设置默认启动视角完整项目下载地址01-基于react的cesium项目 创建基于React的Cesium项目 创建react项目： create-react-app react-cesium-basic安装[cesium1.93.0]版本： npm install cesium@1.…
阅读更多...
LLaMA Factory框架微调GLM-4大模型

LLaMA Factory框架微调GLM-4大模型

摘要&#xff1a;本论文详细阐述了在 Ubuntu 24.04 系统环境下&#xff0c;利用 LLaMA Factory 框架对 GLM - 4 - 9B - Chat 模型进行微调的全过程及其成果。首先介绍了实验环境的配置&#xff0c;包括 A10 显卡、nvidia 驱动版本 550、python 3.12 环境以及 CUDA 12.0 版本&am…
阅读更多...
【gopher的java学习笔记】Java中Mapper与Entity的关系详解

【gopher的java学习笔记】Java中Mapper与Entity的关系详解

在Java后端开发中&#xff0c;特别是在使用MyBatis等持久层框架时&#xff0c;Mapper与Entity的关系是架构设计中不可忽视的一部分。本文将从Java Web应用程序的角度出发&#xff0c;详细探讨Mapper与Entity的关系及其在技术实现中的作用。 一、Mapper与Entity的基本概念 1.1…
阅读更多...
【漫话机器学习系列】052.解释平方和（Explained Sum of Squares, ESS）

【漫话机器学习系列】052.解释平方和（Explained Sum of Squares, ESS）

解释平方和&#xff08;Explained Sum of Squares, ESS&#xff09; 定义 解释平方和&#xff08;Explained Sum of Squares, ESS&#xff09;是回归分析中用于衡量模型解释能力的一个重要指标。它表示模型通过自变量对因变量的解释程度。ESS 是因变量的预测值与其平均值之间…
阅读更多...
nacos2.3.0 接入pgsql或其他数据库

nacos2.3.0 接入pgsql或其他数据库

首先尝试使用官方插件进行扩展&#xff0c;各种报错后放弃&#xff0c;不如自己修改源码吧。 一、官方解决方案 1、nocos 文档地址&#xff1a;Nacos 配置中心简介, Nacos 是什么 | Nacos 官网 2、官方解答&#xff1a;nacos支持postgresql数据库吗 | Nacos 官网 3、源码下载地…
阅读更多...
FastAPI教程：快速构建高性能API

FastAPI教程：快速构建高性能API

FastAPI教程&#xff1a;快速构建高性能API 介绍 FastAPI是一个现代的、快速的&#xff08;高性能&#xff09;Web框架&#xff0c;用于构建APIs&#xff0c;基于标准的Python类型提示。它非常适合用于构建高效、易于维护的API服务。FastAPI支持自动生成文档&#xff0c;输入数…
阅读更多...
最新文章

Copyright @ 2022~2023