双向链表专题

news/2024/10/19 21:32:25/

文章目录

  • 目录
    • 1. 双向链表的结构
    • 2. 双向链表的实现
    • 3. 顺序表和双向链表的优缺点分析

目录

1. 双向链表的结构

带头双向循环<a class=链表" />
注意：

这⾥的“带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

  1. 定义双向链表中节点的结构
//定义双向链表中节点的结构
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;
  1. 初始化

注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位

void LTInit(LTNode** pphead)
{*pphead = (LTNode*)malloc(sizeof(LTNode));if (NULL == *pphead){perror("malloc fail!");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}

也可以这样写：

LTNode* LTInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (NULL == phead){perror("malloc fail!");exit(1);}phead->data = -1;phead->next = phead->prev = phead;return phead;
}
  1. 尾插

概念： 当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的。

不需要改变哨兵位，则不需要传二级指针；如果需要修改哨兵位的话，则传二级指针。

尾插

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (NULL == newnode){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev(ptail) newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

因为写了申请新节点的函数，所以上面的初始化代码可以优化：

LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}
  1. 打印
void LTPrint(LTNode* phead)
{//phead不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
  1. 头插

头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
  1. 尾删

尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表为空：只有一个哨兵位节点assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
  1. 头删

头删

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* del = phead->next;LTNode* next = del->next;//phead del nextnext->prev = phead;phead->next = next;free(del);del = NULL;
}
  1. 查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (x == pcur->data){return pcur;}pcur = pcur->next;}return NULL;
}
  1. 在pos位置之后插入数据
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
  1. 删除pos位置的数据

删除pos位置的数据

//删除pos位置的数据
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
  1. 销毁
void LTDesTroy(LTNode** pphead)
{assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* next = pcur->next;free(pcur);pcur = next;}//链表中只有一个哨兵位free(*pphead);*pphead = NULL;
}

也可以这样写：

void LTDesTroy(LTNode* phead)
{//哨兵位不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//链表中只有一个哨兵位free(phead);phead = NULL;
}

但是要注意：这样写要在调用完函数后再写一句 plist = NULL;

这两种写法我们更推荐第二种：推荐传一级指针**（保持接口一致性）**

完整代码：

//List.h#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义双向链表中节点的结构
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);//推荐传一级指针（保持接口一致性）void LTPrint(LTNode* phead);//概念：当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的
//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);

//List.c#include "List.h"//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//
//	if (NULL == *pphead)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (NULL == newnode){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//LTNode* LTInit()
//{
//	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//
//	if (NULL == phead)
//	{
//		perror("malloc fail!");
//		exit(1);
//	}
//
//	phead->data = -1;
//	phead->next = phead->prev = phead;
//
//	return phead;
//}LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev(ptail) newnodenewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}void LTPrint(LTNode* phead)
{//phead不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表为空：只有一个哨兵位节点assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空LTNode* del = phead->prev;LTNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* del = phead->next;LTNode* next = del->next;//phead del nextnext->prev = phead;phead->next = next;free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (x == pcur->data){return pcur;}pcur = pcur->next;}return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除pos位置的数据
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//void LTDesTroy(LTNode** pphead)
//{
//	assert(pphead);
//	//哨兵位不能为空
//	assert(*pphead);
//
//	LTNode* pcur = (*pphead)->next;
//
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//	}
//
//	//链表中只有一个哨兵位
//	free(*pphead);
//	*pphead = NULL;
//}void LTDesTroy(LTNode* phead)
{//哨兵位不能为空assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//链表中只有一个哨兵位free(phead);phead = NULL;
}

//Test.c#include "List.h"void ListTest01()
{//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist = LTInit();//尾插//LTPushBack(plist, 1);//LTPushBack(plist, 2);//LTPushBack(plist, 3);//LTPushBack(plist, 4);//LTPrint(plist);//头插LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);LTPopBack(plist);LTPrint(plist);//头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* findRet = LTFind(plist, 3);//if (NULL == findRet)//{//	printf("未找到！\n");//}//else//{//	printf("找到了！\n");//}//在指定位置之后插入数据//LTInsert(findRet, 66);//LTPrint(plist);//删除pos位置的节点LTErase(findRet);LTPrint(plist);//LTDesTroy(&plist);LTDesTroy(plist);plist = NULL;
}int main()
{ListTest01();return 0;
}

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

顺序表和双向<a class=链表的优缺点分析" />


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

相关文章

阿里云ECS服务器安装docker

阿里云ECS服务器安装docker

首先查看阿里云ECS的服务器的版本 cat /etc/redhat-release如果是Alibaba Cloud Linux release 3,请执行以下命令 添加docker-ce的dnf源。 sudo dnf config-manager --add-repohttps://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo安装Alibaba Cloud Linux 3专…
阅读更多...
【bug】vuxUI组件popup弹出框在IOS中遮罩层会遮住页面

【bug】vuxUI组件popup弹出框在IOS中遮罩层会遮住页面

可以增加自定义方法v-transfer-dom <div v-transfer-dom"true"><Popup v-model"showPopup"><PopupHeader :title"policyloan.docJson.title" /><div class"noticeText"><p v-for"(item, index) in po…
阅读更多...
关于上传自己本地项目到GitHub的相关命令

关于上传自己本地项目到GitHub的相关命令

https://www.cnblogs.com/nature161/p/15014265.html 根据教程里的来&#xff0c;主要注意这个命令&#xff1a; $ git pull --rebase origin master # 对GitHub的仓库包含了readme.md文件的情况先要执行这个命令再pull 如果你的GitHub是main分支想上传到main分支&#xff0…
阅读更多...
数据库并发控制思维导图+大纲笔记

数据库并发控制思维导图+大纲笔记

思维导图 大纲笔记 多用户数据库系统 定义 允许多个用户同时使用的数据库系统特点 在同一时刻并发运行的事务数可达数百上千个多事务执行方式 事务串行执行交叉并发方式 单处理机系统同时并发方式 多处理机系统事务并发执行带来的问题 产生多个事务同时存取同一数据的情况可能…
阅读更多...
unity读写本地excel_2024.4.22

unity读写本地excel_2024.4.22

using System.Collections; using System.Collections.Generic; using UnityEngine; using OfficeOpenXml; using System.IO; using Excel; using System.Data; using System; /// <summary> /// https://blog.csdn.net/Xz616/article/details/128893023 /// Unity3D操作…
阅读更多...
Python3.11修改并运行oneforall

Python3.11修改并运行oneforall

遇到的问题 使用python3.11默认无法运行oneforall脚本&#xff0c;出现如下报错 # 解决方案 修改 /usr/local/lib/python3.11/dist-packages/exrex.py exrex.py具体文件路径报错中会显示 vim /usr/local/lib/python3.11/dist-packages/exrex.py# 修改前 from re import sre…
阅读更多...
在 TypeScript 中declare module 关键字用法

在 TypeScript 中declare module 关键字用法

在 TypeScript 中&#xff0c;declare module 关键字用于声明模块的类型信息&#xff0c;这种声明通常出现在声明文件&#xff08;通常是 .d.ts 文件&#xff09;中。这对于当你需要为现有的 JavaScript 库或模块提供类型信息时非常有用&#xff0c;尤其是对于没有提供自己的类…
阅读更多...
g 对象：Flask 应用中的“临时口袋”

g 对象：Flask 应用中的“临时口袋”

文章目录 g对象的理解Flask 中的 g 对象g 对象的特点:使用 g 对象: 示例 g对象的理解 想象一下&#xff0c;你在逛超市。你需要一个购物篮来装你挑选的商品。这个购物篮就像 Flask 应用中的 g 对象&#xff0c;它是一个临时存放东西的地方&#xff0c;方便你在购物过程中随时取…
阅读更多...
最新文章

Copyright @ 2022~2023