浅谈【数据结构】链表之其他形态

ops/2024/9/20 1:26:08/ 标签: 数据结构, 链表, c语言, c++, 算法

目录

1、带头结点的链表

2、创建步骤

3、循环链表

3.1创建循环链表

3.2循环链表的遍历

3.3链表中的闭环

4、静态链表

4.1静态链表初始化

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

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

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

1、带头结点的链表

引入：链表的操作起来比较舒服，但是如果记录（获取）链表长度比较麻烦。需要遍历链表，一个一个 计数，比较费时间（占CPU资源）

所以可以不可以用一个比较特殊一点的结点来保存链表相关的信息？->头结点

  • 头结点

头节点其实就是一个特殊的结点，它的类型和其他的结点不一样的，它是专门用来存储链表的一些属性 信息。

struct head {

        int length; // 链表长度

        结点类型*first; // 首结点地址

        结点类型*final; // 尾结点地址

};

注意：

  • 头节点不参与链表的长度计数
  • 头节点也是不参与链表遍历
  • 头节点也不会作为链表的结点

带头结点链表，头节点是在链表中存储链表信息的作用。

注意：当对链表进行增删操作的时候需要对头节点进行及时的更新。

2、创建步骤

  • 从无到有
    • 创建一个头结点
  • 从少到多
    • 一个一个正常增加（注意：及时更新头节点的信息）

图示：

***增加节点***

***删除节点(4种情况)***

代码示例：

#include <iostream>// 结点类型
struct node
{int data;struct node *next;
};// 头节点类型
struct head
{int length;struct node *first;struct node *final;
};/*@brief 创建链表@return 链表的头节点地址
*/
struct head *createNewList()
{// 申请一个空间struct head *newList = new struct head;// 初始化链表属性信息newList->length = 0;newList->first  = nullptr;newList->final  = nullptr;// 返回创建好的链表头节点地址return newList;
}/*@brief 头插法增加结点进链表@param list 需要增加结点的链表的地址@param data 新结点数据
*/
void addNodeHead(struct head*list,int data)
{// 先判断链表是否存在if(!list)return;// 申请新结点空间struct node *newNode = new struct node;// 结点数据的初始化newNode->data = data;newNode->next = nullptr;// 开始头插法// 让新节点的next指针指向头节点里面的首结点newNode->next = list->first; // list->first 表示首结点地址// 更新头结点中首结点（first）和长度list->first = newNode; // 让newNode成为新的首结点list->length++;// 更新链表长度
}/*@brief 尾插法增加结点进链表@param list 需要增加结点的链表的地址@param data 新结点数据
*/
void addNodeTail(struct head*list,int data)
{// 先判断链表是否存在if(!list)return;// 申请新结点空间struct node *newNode = new struct node;// 结点数据的初始化newNode->data = data;newNode->next = nullptr;// 进行尾插法增加list->final->next = newNode; // list->final 表示尾结点地址// 更新头结点中尾结点（final）和长度list->final = newNode;list->length++;
}/*@brief 删除一个置顶的结点@param list 需要删除结点的链表地址@param data 需要删除的那个结点的数据@return true表示成功，false表示失败
*/
bool delListNode(struct head*list,int data)
{// 先判断链表是否存在if(!list)return;// 遍历查找元素struct node *node_ptr = list->first;// 一个结点的时候if(list->first->data == data&&list->length == 1){// 直接释放空间delete list->first;// 更新首尾结点信息list->first = nullptr;list->final = nullptr;list->length--;return ;}// 判断是否为首结点且数量大于1if(list->first->data == data&&list->length > 1){// 更新首结点list->first = node_ptr->next; node_ptr->next = nullptr;delete node_ptr;list->length--;return true;}while(node_ptr->next){// 找到了需要删除的元素if(node_ptr->next->data == data){// 判断是不是尾结点且数量大于1if(node_ptr->next == list->final&&list->length > 1){// 更新尾结点list->final = node_ptr; // 释放需要删除的元素，再置空// 原因：node_ptr并非需要删除的元素，它是被删除元素的前一个元素。delete node_ptr->next;node_ptr->next = nullptr;list->length--;return true;}else if(list->length > 1){// 临时存储被删除元素的地址struct node *delNode = node_ptr->next;// 更新被被删除元素的next指针：实际就是跳过被删除元素node_ptr->next = node_ptr->next->next;// 断开被删除元素的链接delNode->next = nullptr;// 释放元素空间delete delNode;list->length--;return ;}}}
}

3、循环链表

循环链表：第一个数据结点和最后一个数据结点相连链表

循环单链表：最后一个数据结点往后就到了第一个数据结点

循环双链表：最后一个数据结点往后就到了第一个数据结点，第一个数据结点往前走就到了最后数据结 点

3.1创建循环链表

3.2循环链表的遍历

用两个指针，一个指针跑，另一个指针不动，当两个指针重叠的时候就跑完了。

代码示例：

#include <iostream>typedef struct node 
{int data;struct node *next;
}NodeType;/*@brief 为循环链表增加结点@param list 需要增加结点的循环链表@param data 新结点数据
*/
NodeType *addNewNode(NodeType *list,int data)
{// 如果为空作为第一个结点插入if(!list){list = new NodeType;list->data = data;// 自己指向自己，这个就是形成循环的关键了list->next = list;return list; }// 不是第一结点NodeType *newNode = new NodeType;newNode->data = data;newNode->next = nullptr;// 如果list指向的是最后加入链表结点(头插/尾插)newNode->next = list->next;list->next = newNode;return newNode;
}/*@brief 创建循环链表@return 返回新循环链表的地址
*/
NodeType *createLoopList()
{NodeType *loopList = nullptr;int data = -1;do{std::cin >> data;if(data == -1)break;// 增加结点loopList = addNewNode(loopList,data);}while(1);return loopList;
}/*@brief 打印循环链表
*/
void PrintLoopList(NodeType *looplist)
{if(!looplist){std::cout << "空的" << std::endl;return;}NodeType *node_ptr = looplist;do{std::cout << node_ptr->data << std::endl;node_ptr = node_ptr->next;}while(node_ptr != looplist);
}int main()
{NodeType*looplist = createLoopList();PrintLoopList(looplist);return 0;
}

3.3链表中的闭环

链表的尾结点指向了链表中的任意一个随机的结点

求闭环的算法

  • 使用两个指针
    • 一个移动步数快
    • 一个移动步数慢
  • 如果两者发生重叠 就形成闭环
  • 如果其中一个指针出现空指针的情况 ，就是没有环的

代码示例：

***形成闭环示例***

#include <iostream>typedef struct node 
{int data;struct node *next;
}NodeType;/*@brief 为循环链表增加结点@param list 需要增加结点的循环链表@param data 新结点数据
*/
NodeType *addNewNode(NodeType *list,int data)
{// 如果为空作为第一个结点插入if(!list){list = new NodeType;list->data = data;// 自己指向自己，这个就是形成循环的关键了list->next = list;return list; }// 不是第一结点NodeType *newNode = new NodeType;newNode->data = data;newNode->next = nullptr;// 如果list指向的是最后加入链表结点(头插/尾插)newNode->next = list->next;list->next = newNode;return newNode;
}/*@brief 创建循环链表@return 返回新循环链表的地址
*/
NodeType *createLoopList()
{NodeType *loopList = nullptr;int data = -1;do{std::cin >> data;if(data == -1)break;// 增加结点loopList = addNewNode(loopList,data);}while(1);return loopList;
}/*@brief 打印循环链表
*/
void PrintLoopList(NodeType *looplist)
{if(!looplist){std::cout << "空的" << std::endl;return;}NodeType *node_ptr = looplist;do{std::cout << node_ptr->data << std::endl;node_ptr = node_ptr->next;}while(node_ptr != looplist);
}/*求闭环的算法
*/
bool IsHaveCircle(NodeType *looplist)
{if(!looplist)return true;// 是否有圈NodeType *fast = looplist;    // 慢NodeType *slow = looplist;    // 快// 循环操作do{// 移动指针if(fast->next)fast = fast->next->next;   // 移动两步else  // 如果不能移动表示其中一个next是为空return false;slow = slow->next; // 移动一步// 判断有没有为空的指针if(!fast||!slow) // 只要任意一个指针为空那么就没有环return false;}while(fast != slow);// 相等退出，就是有环return true;
}int main()
{NodeType *looplist = createLoopList();if(IsHaveCircle(looplist))std::cout << "有环" << std::endl;elsestd::cout << "没环" << std::endl;// destoryList();return 0;
}

***无闭环示例***

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
typedef struct nodeData
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct nodeData *next;
}NodeType;/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct nodeData *createNewList()
{// 新链表的首结点指针struct nodeData *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 申请了一个新结点的空间struct nodeData *newNode = new struct nodeData;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 增加到链表里面:向后增加（尾插法）// 做第一次判断：链表中有没有结点if(newList == nullptr){// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue; // 继续增加新结点}// 搞一个临时指针，来指向首结点struct nodeData *node_ptr = newList;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;}return newList;
}// 打印链表（遍历方法）
void printList(struct nodeData *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;
}bool IsHaveCircle(NodeType *looplist)
{if(!looplist)return true;// 是否有圈NodeType *fast = looplist;    // 慢NodeType *slow = looplist;    // 快// 循环操作do{// 移动指针if(fast->next)fast = fast->next->next;   // 移动两步else  // 如果不能移动表示其中一个next是为空return false;slow = slow->next; // 移动一步// 判断有没有为空的指针if(!fast||!slow) // 只要任意一个指针为空那么就没有环return false;}while(fast != slow);// 相等退出，就是有环return true;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct nodeData *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址if(IsHaveCircle(newList))std::cout << "有环" << std::endl;elsestd::cout << "没环" << std::endl;return 0;
}

4、静态链表

静态链表是一种使用数组来实现链表概念的数据结构。它通过在每个元素中存储下一个元素的索引来实 现链式存储，从而在有限的空间内实现对大量元素的有效管理。

普通链表

struct node {

        int data;

        struct node *next;

}; // 结点

静态链表

struct node {

        int data;

        int next; // 不是指针，而是下标

};

struct node static_list[100]={0};

4.1静态链表初始化

for(int i = 0;i < 100;i ++)

{

        static_list[i].data = i+1;

        if(i!=99)

                static_list[i].next = i+1;

        else

                 static_list[i].next = -1; // 下标不会出现-1

}

插入元素

// 尾插法

int i = 0;

for(i < 100;i++)

if(static_list[i].next == -1)

        break;

// 找空位

for(int l = 0; l < 100;l++)

{

         if(static_list[l] == NULL)

         {

                static_list[l] = newNode;

                static_list[i].next = l;

        }

}

注意事项：

  • 静态链表是一种在内存空间有限时使用的数据结构。
  • 使用数组和指针来实现链表的功能。
  • 初始化静态链表时，需要正确设置每个节点的 data 和 next 指针。
  • 在向静态链表添加元素时，需要检查是否已满。
  • 访问静态链表元素时，要确保索引有效。
  • 静态链表的大小是固定的，因此在设计时需要合理估计最大元素数量。

代码实例：

#include <iostream>struct node
{int data;   // 数据int next_index; // 下标
};#define MAXLEN 20void addNode(struct node *staticlist[],int data)
{// 插入元素if(staticlist[0] == nullptr){staticlist[0] = new struct node;staticlist[0]->data = 1;staticlist[0]->next_index = -1;return;}std::cout << __LINE__ << std::endl;// 找尾元素插入int pos = 0; // 第一个while(1){if(staticlist[pos]->next_index == -1)break;pos = staticlist[pos]->next_index;}// 找到尾元素了int newPos = 0;while(staticlist[newPos] != nullptr)newPos++;// 将新结点加入staticlist[newPos] = new struct node;staticlist[newPos]->data = data;staticlist[newPos]->next_index = -1;staticlist[pos]->next_index = newPos;
}int main()
{// 新建一个静态链表struct node *staticlist[MAXLEN] = {0};for(int i = 0;i < 10;i++)addNode(staticlist,i+2);// 正常打印for(int i = 0;i < MAXLEN;i++)std::cout << staticlist[i] << " ";std::cout << std::endl;int pos = 0;// 链表遍历形式打印do{std::cout << staticlist[pos]->data << " ";pos =staticlist[pos]->next_index;} while (pos != -1);std::cout << std::endl;}


http://www.ppmy.cn/ops/102513.html

相关文章

Ant Design Vue修改表格样式

Ant Design Vue修改表格样式

原效果&#xff1a; 修改背景色和字体&#xff0c;包括表头和表体&#xff0c;要分开设置&#xff1a; :deep .ant-table-thead>tr>th {background: rgba(255, 255, 255, 0);//去掉表头背景color: rgb(100, 181, 220);font-weight: bold;border: none;//去掉表头边框}:d…
阅读更多...
vue.js的设计与实现（响应系统2）

vue.js的设计与实现（响应系统2）

文章目录 概要分支切换与cleanup嵌套的effect与effect栈避免无限递归循环调度执行小结 概要 接上文&#xff0c;我们已经写出了基础的effect收集&#xff0c;但是还是会有些问题。这一篇&#xff0c;我们就是来解决这些问题的 分支切换与cleanup 首先&#xff0c;我们需要明确…
阅读更多...
自然语言处理系列四十五》Elasticsearch搜索引擎》Elasticsearch入门及技术原理

自然语言处理系列四十五》Elasticsearch搜索引擎》Elasticsearch入门及技术原理

注&#xff1a;此文章内容均节选自充电了么创始人&#xff0c;CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》&#xff08;人工智能科学与技术丛书&#xff09;【陈敬雷编著】【清华大学出版社】 文章目录 自然语言处理系列四十五Elasticsearch搜索引擎》Elasticsearch入…
阅读更多...
Mysql5.7.40安装步骤

Mysql5.7.40安装步骤

mysql5.7.40数据库部署安装_数据库_weixin_44568463-亚马逊云科技技术品牌专区
阅读更多...
使用 ASP.NET Core 与 Entity Framework Core 进行数据库操作

使用 ASP.NET Core 与 Entity Framework Core 进行数据库操作

使用 ASP.NET Core 与 Entity Framework Core 进行数据库操作 Entity Framework Core&#xff08;EF Core&#xff09;是ASP.NET Core中的一个轻量级ORM框架&#xff0c;提供了以面向对象的方式与数据库进行交互的能力。本文将通过Visual Studio 2022详细介绍如何使用EF Core进…
阅读更多...
在Android中的widge组件是什么？

在Android中的widge组件是什么？

目录 Widget 的特点 创建 Android Widget 的步骤 Widget 的主要功能 常见的 Widget 类型 总结 在 Android 中&#xff0c;Widget&#xff08;小部件&#xff09; 是一种特殊的 UI 组件&#xff0c;通常称为 "App Widget"。它是小型的、可以放置在设备主屏幕上的…
阅读更多...
【区块链 + 司法存证】印记区块链电子印章 | FISCO BCOS应用案例

【区块链 + 司法存证】印记区块链电子印章 | FISCO BCOS应用案例

电子印章作为传统物理印章的数字化锚定&#xff0c;除了拥有和物理印章一样的法律效力外&#xff0c;还能够有效地为企业增效降 本提质。近年来&#xff0c;随着国家双碳目标的提出以及全球新冠疫情&#xff0c;进一步加速了企业数字化转型的步伐&#xff0c;电子印章 的价值也…
阅读更多...
批量在多台Linux机器上安装OpenJDK

批量在多台Linux机器上安装OpenJDK

上一次我们实践了手动安装OpenJDK的过程&#xff0c;并且完成了用脚本一键安装的试验。但是本质上&#xff0c;我还是每台机器上单独进行操作。那这就产生了一个问题&#xff0c;如果我需要一次性在多台机器上部署安装&#xff0c;需要怎么操作呢。 问题分析 假设我的目的是在…
阅读更多...
扁线电机介绍

扁线电机介绍

相比于圆线&#xff0c;扁线因为扁平矩形的特殊性能够让线圈缠绕更加紧密&#xff0c;槽满率由原先的40%提升到70%。 这意味着相同体积下线圈中的导线更多&#xff0c;电流的传导效率更高&#xff0c;能够减少电阻损耗&#xff0c;产生的磁场更强&#xff0c;电机功率也就更大&…
阅读更多...
IP地址与SSL证书：保障网络安全的关键

IP地址与SSL证书：保障网络安全的关键

在数字时代&#xff0c;网络安全至关重要&#xff0c;而SSL&#xff08;安全套接层&#xff09;证书作为加密用户与服务器之间数据传输的利器&#xff0c;扮演着不可或缺的角色。然而&#xff0c;谈及SSL证书时&#xff0c;一个常见的误区是它们通常与域名绑定&#xff0c;而非…
阅读更多...
【前端】理解与使用sessionStorage、localStorage与cookie

【前端】理解与使用sessionStorage、localStorage与cookie

深入理解与高效使用 sessionStorage、localStorage 与 cookie 背景 在构建一个多页面的 Vue web 应用时&#xff0c;我面临了一个关键问题&#xff1a;如何有效地管理用户的登录状态。为了减少对服务器的不必要请求&#xff0c;我尝试了全局状态注入的方法&#xff0c;但这种…
阅读更多...
【通俗理解】深度学习特征提取——Attention机制的数学原理与应用

【通俗理解】深度学习特征提取——Attention机制的数学原理与应用

【通俗理解】深度学习特征提取——Attention机制的数学原理与应用 关键词提炼 #深度学习 #特征提取 #Attention机制 #CNN #Transformer #关联特征 #MLP #拟合处理 第一节&#xff1a;Attention机制的类比与核心概念 1.1 Attention机制的类比 Attention机制可以被视为一个“特…
阅读更多...
【kafa系列】kafka如何保证消息不丢失

【kafa系列】kafka如何保证消息不丢失

【kafa系列】kafka如何保证消息不丢失 Apache Kafka通过多种机制来确保消息不丢失&#xff0c;这些机制包括但不限于副本机制、ISR&#xff08;In-Sync Replicas&#xff09;机制、ACK&#xff08;Acknowledgment&#xff09;机制、幂等生产者&#xff08;Idempotent Producer&…
阅读更多...
K8S对接Ceph分布式存储

K8S对接Ceph分布式存储

文章目录 一、Ceph理论知识1、Ceph简介2、Ceph分布式存储的优点3、Ceph核心组件 二、部署Ceph高可用集群1、服务器环境信息2、部署前环境准备工作3、部署Ceph监控服务Monitor4、激活Ceph存储服务OSD 三、K8S对接Ceph存储1、K8S对接Ceph RBD实现数据持久化2、基于Ceph RBD生成PV…
阅读更多...
计算机视觉编程 1（图片处理）

计算机视觉编程 1（图片处理）

目录 灰色度 缩略图 拷贝粘贴区域 调整图像尺寸 旋转图像45 画图线、描点 灰色度 灰度是指图像中每个像素的亮度值&#xff0c;用来描述图像中各个像素的明暗程度。在计算机视觉中&#xff0c;灰度可以通过以下方式来计算&#xff1a; 1. 平均值法&#xff1a;将图像中每…
阅读更多...
计算机毕业设计推荐-基于python的个性化旅游路线推荐平台

计算机毕业设计推荐-基于python的个性化旅游路线推荐平台

&#x1f496;&#x1f525;作者主页&#xff1a;毕设木哥 精彩专栏推荐订阅&#xff1a;在 下方专栏&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; 实战项目 文章目录 实战项目 一、基于python的个性化旅游路线…
阅读更多...
ubuntu20 安装ros noetic版本

ubuntu20 安装ros noetic版本

【ROS】Ubuntu20.04卸载重装ROS_ubuntu20.04卸载ros-CSDN博客 错误处理——rosdep init&#xff0c;rosdep update失败解决方案_rosdep init出错-CSDN博客 ubuntu 20.04解决在处理时有错误发生&#xff1a; /var/cache/apt/archives/python3-catkin-pkg-modules_0.4.24-1_all…
阅读更多...
NoSQL数据库-Redis集群详解及案例实现

NoSQL数据库-Redis集群详解及案例实现

一、 关系型数据库和 NoSQL 数据库 1.1 数据库主要分为两大类&#xff1a;关系型数据库与 NoSQL 数据库 关系型数据库&#xff0c;是建立在关系模型基础上的数据库&#xff0c;其借助于集合代数等数学概念和方法来处理数据库中的数据主流的 MySQL、Oracle、MS SQL Server 和 D…
阅读更多...
基于JAVA的专利资源共享平台

基于JAVA的专利资源共享平台

项目介绍 基于JAVA的专利资源共享平台系统是一个集专利信息展示、资源共享、交易服务等功能于一体的综合性平台。该系统利用JAVA语言的强大功能和广泛的生态系统&#xff0c;结合数据库技术、Web开发技术等&#xff0c;为用户提供了一个高效、安全、便捷的专利资源共享和交易环…
阅读更多...
【C++】日期和时间

【C++】日期和时间

C 提供了多种处理日期和时间的功能&#xff0c;主要通过标准库 <ctime> 和 <chrono> 提供。以下是 C 中处理日期和时间的功能介绍及其用法&#xff1a; 1. <ctime> 库 <ctime> 是 C 中处理时间的传统库&#xff0c;提供了一些基本的时间操作函数。这…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站