浅谈【数据结构】链表之双链表

server/2024/12/21 20:34:02/

目录

1、删除结点

2、双向链表

2.1增加结点

2.2删除结点

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

本文主要以图示+代码为主  

数据结构最多的操作：增删改查

1、删除结点

但是我们发现单链表存在一个弊端：不能回溯（没法直接回到前一个结点）

有木有方法可以解决这个问题？

双向链表它可以解决单向链表只有一个指针指向下一个结点没法回溯的这么一个问题。

2、双向链表

双向链表它包含数据域和指针域（但是指针域相对单链表而言多出了一个指针：prev指针）

struct node
{
// 数据域ElementType data;
// 指针域struct node *prev; // 前指针struct node *next; // 后指针
};

2.1增加结点

图示：

头插：

尾插：

中间位置插入：

2.2删除结点

图示：删除头结点  删除中间节点 删除尾结点    图示示例+代码示例

***双链表示例***

/*双向链表
*/
#include <iostream>
// 换一种方式来实现双向链表：对象template <typename DataType>
class ddl
{
public:ddl(); // 创建一个双向链表~ddl(); // 销毁一个双向链表// 增删改查// 增加bool addNode(DataType d){// 中、头、尾插入...// 尾插法// 如果链表是空的那么需要将新节点作为第一个结点增加if(firstNode == nullptr){firstNode = new struct node;firstNode->data = d;firstNode->next = nullptr;firstNode->prev = nullptr;}else{// 先找尾结点struct node *tail_ptr = firstNode;while(tail_ptr->next)tail_ptr = tail_ptr->next;// 进行插入struct node *newNode = new struct node;newNode->data = d;newNode->next = nullptr;newNode->prev = nullptr;tail_ptr->next = newNode;newNode->prev  = tail_ptr;}length ++;return true;}// 删除bool delNode(DataType d){if(length == 0)return false;// 查找要删除的结点struct node *delNode_ptr = firstNode;while(delNode_ptr){// 进行数据比较，是否尾需要删除的结点if(delNode_ptr->data == d){// 进行删除// 需要判断一下是不是只有一个元素if(length == 1){// 断开当前结点的指向，让它脱离链表firstNode->next = nullptr;firstNode->prev = nullptr;delete firstNode;length -- ;return true;}// 第一步：把前驱和后继的指向更新// 更新前驱结点指向:让前驱结点的next指针指向当前结点的后继结点// delNode_ptr 当前结点，delNode_ptr->prev 就是当前结点的前驱结点if(delNode_ptr->prev != nullptr)(delNode_ptr->prev)->next = (delNode_ptr->next);// 更新后继结点的指向：让后继结点的prev指针指向当前结点的前驱结点// delNode_ptr 当前结点，delNode_ptr->next 就是当前结点的后继结点if(delNode_ptr->next != nullptr)(delNode_ptr->next)->prev = (delNode_ptr->prev);// 第二步：断开当前结点的指向，让它脱离链表delNode_ptr->next = nullptr;delNode_ptr->prev = nullptr;// 第三步：释放当前结点的空间delete delNode_ptr;length -- ;return true;}// 更新指针delNode_ptr = delNode_ptr->next;}return false;}// 修改bool chgNode(DataType od,DataType nd){if(length == 0){std::cout << "修改失败：空的" << std::endl;return false;}// 查找需要修改的元素struct node *chgNode_ptr = firstNode;while(chgNode_ptr){// 判断是不是需要修改的元素if(chgNode_ptr->data == od){chgNode_ptr->data = nd;return true;}chgNode_ptr = chgNode_ptr->next;}std::cout << "修改失败：没有找到指定元素" << std::endl;return false;}// 查找bool srhNode(DataType d){if(length == 0){std::cout << "查找失败：空的" << std::endl;return false;}// 查找需要修改的元素struct node *srhNode_ptr = firstNode;while(srhNode_ptr){// 判断是不是需要修改的元素if(srhNode_ptr->data == d)return true;srhNode_ptr = srhNode_ptr->next;}std::cout << "查找失败：没有找到指定元素" << std::endl;return false;}// 打印void prtList(){// for(int i = 0;i < length;i++)// {//     std::cout << node_ptr->data;//     node_ptr = node_ptr->next;// }struct node *node_ptr = firstNode;std::cout << "DoubleDirectionList( ";while(node_ptr){std::cout << node_ptr->data << " ";node_ptr = node_ptr->next;}std::cout << ")"<<std::endl;}private:// 首结点地址struct node{DataType data;struct node *prev;struct node *next;}*firstNode;// // 尾结点地址// struct node// {//     DataType data;//     struct node *prev;//     struct node *next;// }lastNode;// 统计一下个数int length;
};template <typename DataType>
ddl<DataType>::ddl(): firstNode(nullptr), length(0)
{
}// 析构：用于销毁链表
template <typename DataType>
ddl<DataType>::~ddl()
{struct node *delNode_ptr = firstNode;while(delNode_ptr){// 更新指针firstNode = firstNode->next;// 销毁结点delNode_ptr->next = nullptr;delNode_ptr->prev = nullptr;delete delNode_ptr;length--;delNode_ptr = firstNode;}
}int main()
{ddl<int> d;d.addNode(10);d.addNode(11);d.addNode(13);d.prtList();d.chgNode(10,100);d.prtList();d.delNode(13);d.prtList();// d.delNode(13);// d.prtList();return 0;
}

***增删改查***

        

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
struct node
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct node *next;
};//----------------------------------------------------------增加----------------------------------------------------
/*@brief：头部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeHead(struct node *list,int data)
{// list 表示就是一个链表（链表首地址/首结点的地址）头插法其实就是在它的首结点前面插入struct node *newNode = new struct node;newNode->data = data; // 数据存入结点数据域newNode->next = list; // 因为新结点作为新的首结点存入链表，那么原有的首结点就变成了新节点后继结点return newNode; // 返回newNode因为newNode变成了新的首结点了。更新链表的首地址
}/*@brief: 尾部插入@param: list 需要增加新数据的链表指针@param: data 是需要存入链表的数据@return : 链表首地址
*/
struct node* addNodeTail(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 搞一个临时指针，来指向首结点struct node *node_ptr = list;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;return list;
}/*@brief : 中间插入法@param : list 需要增加数据的链表首地址@param : data 需要增加到链表的数据@return : 链表首地址
*/
struct node *addNodeMid(struct node *list,int data)
{struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 循环比较数据 大到小  小到大// struct node *node_previce = nullptr;// struct node *node_current = list;// 第一种方法两个指针// while(node_current)// {//     if(node_current->data > data)//         break; // 找到插入位置了//     // 把两个指针往后移//     node_previce = node_current;//     node_current = node_current->next;// }// // 进行插入// if(node_previce == nullptr) // 说明需要作为首结点插入（头插入)// {//     // 头插代码// }// else// {//     // 直接插入到node_previce的后面//     newNode->next = node_previce->next; // 要成为node_previce下一个结点的前驱结点//     node_previce->next = newNode; // 然后让newNode成为node_previce的后继结点// }// 第二种方法提前判断struct node *node_ptr = list;// 如果第一个结点就比data大说明要插入到最前面（头插法）if(node_ptr->data > data){// 头插法list = addNodeHead(list,data);return list;} while(node_ptr&&node_ptr->next){if(node_ptr->data < data && node_ptr->next->data >= data) // 大于前一个小于后一个{// 将新结点的next指向当前结点的后继结点node_ptr->nextnewNode->next = node_ptr->next;// 让newNode成为node_ptr的后继结点node_ptr->next = newNode;return list; // 退出增加}// 把指针往后移node_ptr = node_ptr->next;}// 严谨判断一下node_ptr->next是不是为空if(node_ptr->next == nullptr) // 尾插法{node_ptr->next = newNode;}return list;
}//----------------------------------------------------------删除----------------------------------------------------
/*@brief:删除指定结点数据@param：list 需要删除元素的链表首地址@param：data 需要删除的那个元素的值@return : 链表首地址
*/
struct node *delNodeData(struct node*list,int data)
{// 严谨判断链表是否存在if(list == nullptr)return list;// 找需要删除的元素// 是不是首结点if(list->data == data){// 第一步：获取后继结点指针struct node *newHeadNode = list->next;// 第二步：将需要删除的首结点的next置空list->next = nullptr; // 此时的它和链表没有关系了// 第三步：将list结点删除/释放delete list;// 第四步：返回新的首结点return newHeadNode;}// 不是首结点struct node *node_ptr = list;while(node_ptr->next) // 判断下一个的原因：是能够找到需要删除的元素的前一个，next才是实际要比对的结点{ // 找到那个结点了/*node_ptr: 表示需要删除的结点的前驱结点(node_ptr->next): 表示需要删除的结点(node_ptr->next)->data : 表示需要删除的结点的数据*/if((node_ptr->next)->data == data){// 第一步：获取需要删除的结点指针struct node*needDelNode = node_ptr->next;// 第二步：将前驱结点的next指向当前删除结点的nextnode_ptr->next = needDelNode->next;// 第三步：将当前删除结点的next置空needDelNode->next = nullptr;// 第四步：将当前删除结点进行释放delete needDelNode;// 第五步：返回结点首地址return list;}// 移动指针node_ptr = node_ptr->next;}// 为空退出：表示没找到啊return list;
}//----------------------------------------------------------修改----------------------------------------------------
/*@brief:修改指定数据的结点@param：list 需要修改元素的链表首地址@param：oldData 需要修改的那个元素的值@param：newData 新数据
*/
void changeNodeData(struct node*list,int oldData,int newData)
{// 严谨判断链表是否存在if(list == nullptr){std::cout << "链表为空" << std::endl; return;}// 查找需要修改的数据是否存在while(list){// 判断if(list->data == oldData){list->data = newData;return;}// 移动指针list = list->next;}// 如果循环都结束了还没找到，那么就是没有这个数据std::cout << "链表不存在" << std::endl;return;
}//----------------------------------------------------------查找----------------------------------------------------
/*@brief:修改指定数据的结点@param：list 需要查找元素的链表首地址@param：data 需要查找的那个元素的值
*/
void searchNodeData(struct node*list,int data)
{// 严谨判断链表是否存在if(list == nullptr){std::cout << "链表为空" << std::endl; return;}// 查找需要修改的数据是否存在while(list){// 判断if(list->data == data){std::cout << "找到链表" << std::endl;return;}// 移动指针list = list->next;}// 如果循环都结束了还没找到，那么就是没有这个数据std::cout << "链表不存在" << std::endl;return;
}/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct node *createNewList()
{// 新链表的首结点指针struct node *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 做第一次判断：链表中有没有结点if(newList == nullptr){struct node *newNode = new struct node;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue;}// 通过中间插入法增加结点newList = addNodeMid(newList,data);// 通过尾插法增加结点// newList = addNodeTail(newList,data);}return newList;
}/*@brief: 销毁一个链表@list : 需要销毁的链表@return : 销毁成功返回空指针
*/
struct node *destoryList(struct node *list)
{while(list){// 保存当前结点的后继结点，以防等会找不到了struct node * next_node = list->next;// 将当前结点的next指针置空list->next = nullptr;// 释放当前结点delete list;// 移动下一个待删除结点list = next_node;}return list;
}// 打印链表（遍历方法）
void printList(struct node *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct node *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址int data;std::cin >> data;// 销毁链表destoryList(newList);return 0;
}


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

相关文章

《通义千问AI落地—上》：后端接口

《通义千问AI落地—上》：后端接口

一、前言 本文源于微博客且已获授权,请尊重版权. 通义&#xff0c;由通义千问更名而来&#xff0c;是阿里云推出的语言模型 &#xff0c;于2023年9月13日正式向公众开放。 属于(AI Generated Content&#xff0c;AIGC)领域&#xff0c; 是一个MaaS&#xff08;模型即服务&#…
阅读更多...
45+用户占比近30%，网文产业如何赋能IP长链？

45+用户占比近30%，网文产业如何赋能IP长链？

网文市场加速发展&#xff0c;巨头抢占中老年用户 作者&#xff5c;吕娆炜 排版&#xff5c;张思琪 干货抢先看 1. 我国网文产业市场规模突破3000亿元&#xff0c;在用户方面&#xff0c;截至2023年底&#xff0c;我国网文用户数量达5.37亿&#xff0c;同比增长9%&#xff0c…
阅读更多...
MySQL字符串比较忽略尾随空格

MySQL字符串比较忽略尾随空格

问题 今天遇到一个线上问题&#xff0c;排查过程中发现&#xff0c;MySQL 查询条件使用字符串判断等时会自动忽略字符串尾部的空格&#xff0c;示例如下&#xff1a; MySQL 表格结构&#xff1a; CREATE TABLE users (id int(11) NOT NULL,name varchar(50) DEFAULT NULL,ag…
阅读更多...
基于Spring Cloud的房产销售平台设计与实现

基于Spring Cloud的房产销售平台设计与实现

你好呀&#xff0c;我是计算机专业毕业生&#xff0c;很高兴与大家分享我的毕业设计。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;Spring Cloud&#xff0c;前端使用HTML5、CSS3、JavaScript 工具&#xff1a;IDEA、Tomcat、MySQL 系统展示 首页…
阅读更多...
从React服务器组件（RSC）反思Jakarta Faces技术

从React服务器组件（RSC）反思Jakarta Faces技术

从React服务器组件&#xff08;RSC&#xff09;反思Jakarta Faces技术 2024.8.20版权声明&#xff1a;本文为博主chszs的原创文章&#xff0c;未经博主允许不得转载。 1 引言 React 服务器组件&#xff08;React Server Components&#xff0c;RSC&#xff09;标志着 React …
阅读更多...
微服务的基本理解和使用

微服务的基本理解和使用

目录​​​​​​​ 一、微服务基础知识 1、系统架构的演变 &#xff08;1&#xff09;单体应用架构 &#xff08;2&#xff09;垂直应用架构 &#xff08;3&#xff09;分布式SOA架构 &#xff08;4&#xff09;微服务架构 &#xff08;5&#xff09;SOA与微服务的关系…
阅读更多...
在vs+QT中使用QT的库(multimedia.lib)

在vs+QT中使用QT的库(multimedia.lib)

在链接器中添加外部库在链接器中添加附加依赖项目添加 #include <QtMultimedia/QMediaPlayer> // VS向.pro文件添加代码的方式 #pragma execution_character_set("utf-8") // qt支持显示中文 检查所用的配置和设定配置是否相同:
阅读更多...
标准版v5.4安卓手机小程序扫码核销读取不到核销码的问题

标准版v5.4安卓手机小程序扫码核销读取不到核销码的问题

修改这个文件&#xff0c;红色的那块代码替换成绿色的这段代码&#xff0c;然后重新打包上传。 文件地址&#xff1a;template/uni-app/pages/admin/order_cancellation/index.vue let path decodeURIComponent(res.path); self.verify_code path.split(‘code’)[1]; h5…
阅读更多...
最新文章

Copyright @ 2022~2023