数据结构：单向链表

news/2024/9/19 0:41:50/ 标签: 数据结构, 链表, 单向链表

目录

结构体

创建链表

插入链表

头插法

尾插法

遍历打印

更新链表指定节点

查找链表指定节点

删除链表指定节点

销毁链表

找到元素中间位置

 找到链表倒数第k个节点

链表元素倒置

链表元素排序

冒泡排序

选择排序

链表
    1.空间可以不连续，访问元素不方便
    2.链表需要更大的空间存放数据和节点地址
    3.链表空间不连续,使得理论上长度是无限的
    4.链表的插入和删除效率很高

结构体

typedef int DataType;
typedef struct node
{DataType data;struct node *pnext;
}LinkNode;

创建链表

LinkNode *CreateLinklist()
{LinkNode *pHead=NULL;pHead=malloc(sizeof(LinkNode));if(pHead==NULL){return NULL;}pHead->pnext=NULL;return pHead;
}

插入链表

头插法

int HeadInsertLink(LinkNode *pHead,DataType data)
{LinkNode *pTmpnode=NULL;
//申请一个新的节点空间pTmpnode=malloc(sizeof(LinkNode));if(pTmpnode==NULL){return -1;}
//为节点data赋值pTmpnode->data=data;
//新节点的pnext指向头结点的pnextpTmpnode->pnext=pHead->pnext;
//头结点的pnext指向新节点pHead->pnext=pTmpnode;return 0;
}

尾插法

int TailInsertLinkList(LinkNode *pHead, DataType TmpData)
{LinkNode *ptmpnode=NULL;LinkNode *Newnode=NULL;ptmpnode=pHead;
//找到最后一个节点(最后一个节点的特点是pnext为空)while (ptmpnode->pnext!=NULL){ptmpnode=ptmpnode->pnext;}
//申请一个新的节点空间Newnode=malloc(sizeof(LinkNode));if(Newnode==NULL){return -1;}
//为节点数据空间赋值Newnode->data=TmpData;
//新节点的pnext指向NULLNewnode->pnext=NULL;
//最后一个节点next指向当前节点,当前节点变为最后一个节点ptmpnode->pnext=Newnode;return 0;
}

遍历打印

int Showlist(void *Element,void *arg)
{int *data = Element;printf("%d  ",*data);return 0;
}
int ShowLinkList(LinkNode *pHead,int (*pFun)(void *Element,void *arg),void *arg)
{LinkNode *pTmpnode=NULL;pTmpnode=pHead->pnext;int ret=0;while(pTmpnode!=NULL){ret=pFun(&pTmpnode->data,arg);if(ret!=0){break;}pTmpnode=pTmpnode->pnext;}return 0;
}

更新链表指定节点

int UpdateLinkList(LinkNode *pHead, DataType OldData, DataType NewData)
{LinkNode *pTmpnode=NULL;pTmpnode=pHead->pnext;while(pTmpnode!=NULL){   if(pTmpnode->data==OldData){pTmpnode->data=NewData;}pTmpnode=pTmpnode->pnext;}return 0;
}

查找链表指定节点

LinkNode *FindLinkList(LinkNode *pHead, DataType TmpData)
{LinkNode *pTmpnode=NULL;pTmpnode=pHead;while(pTmpnode->data!=TmpData){pTmpnode=pTmpnode->pnext;}return pTmpnode;
}

删除链表指定节点

int DeleteLinklist(LinkNode *pHead,DataType data)
{LinkNode *pTmpnode=NULL;LinkNode *pPreNode=NULL;pTmpnode=pHead;pPreNode=pHead;while(pTmpnode!=NULL){if((pTmpnode->data!=data)) //如果不是要被删除的节点{pPreNode=pTmpnode;//保存此节点pTmpnode=pTmpnode->pnext;//指向下一个节点}else{   //前一个节点的pnext指向要被删除节点的后一个节点pPreNode->pnext=pTmpnode->pnext;free(pTmpnode);//释放要被删除的节点pTmpnode=pPreNode->pnext;//循环遍历下一个节点}}return 0;}

销毁链表

int DestoryLinklist(LinkNode **pHead)
{LinkNode *pTmpnode=NULL;LinkNode *pTmpnext=NULL;pTmpnode=*pHead;while(pTmpnode!=NULL){  //保存下一个节点pTmpnext=pTmpnode->pnext;free(pTmpnode);//释放当前节点pTmpnode=pTmpnext; //指向下一个节点}*pHead=NULL;//头结点指向空return 0;
}

找到元素中间位置

算法：

       快指针pFast每次走2步
       慢指针pSlow每次走1步
       快指针到达末尾时，慢指针所在的位置即为中间位置

LinkNode *FindMidLinkNode(LinkNode *pHead)
{LinkNode *pFast=pHead->pnext;LinkNode *pSlow=pHead->pnext;while(pFast!=NULL){
//快节点先走两步，若是只有一个节点或两个节点，就跳出循环，此时慢节点指向第一个节点pFast=pFast->pnext;if(pFast==NULL){break;}pFast=pFast->pnext;if(pFast==NULL){break;}
//快节点走完两步，慢节点走一步pSlow=pSlow->pnext;}return pSlow;
}

 找到链表倒数第k个节点

算法：

         快指针先走k步
         慢指针和快指针每次走1步(快指针总是领先慢指针k步)
          当快指针走到末尾时,慢指针即指向链表倒数第k个节点

LinkNode *FindKthLinkNode(LinkNode *pHead,int k)
{int i=0;LinkNode *pFast=pHead->pnext;LinkNode *pSlow=pHead->pnext;
//快节点先走k步for(i=0;i<k;i++){pFast=pFast->pnext;if(pFast->pnext==NULL){return NULL;}}
//快慢节点每次都走1步，当快节点到达末尾时，慢节点的位置就是第k个节点while(pFast!=NULL){pFast=pFast->pnext;pSlow=pSlow->pnext;}return pSlow;
}

链表元素倒置

算法

        使用头插法将链表元素开始到结尾重新插入链表中，即第一个插入后第二个插入，第一个就在末尾，以此类推实现倒置

int ReverseLinkList(LinkNode *pHead)
{LinkNode *pInsertNode=pHead->pnext;LinkNode *pTmpNode=pHead->pnext;pHead->pnext=NULL;while(pTmpNode!=NULL){//保留革命火种pTmpNode=pTmpNode->pnext;//将剩余链表的第一个插入头结点pnextpInsertNode->pnext=pHead->pnext;pHead->pnext=pInsertNode;//插入节点向后移动pInsertNode=pTmpNode;}return 0;
}

链表元素排序

冒泡排序

int BubbleLinkList(LinkNode *pHead)
{LinkNode *ptmpNode1=NULL;LinkNode *ptmpNode2=NULL;LinkNode *pEnd=NULL;DataType pTmpData;
//没有元素或只有一个元素直接返回if(pHead->pnext==NULL ||pHead->pnext->pnext==NULL){return -1;}while(1){ptmpNode1=pHead->pnext;ptmpNode2=pHead->pnext->pnext;
//最后一次只有两个元素，此时链表已经排好序，pEnd和pTmpNode
相等，直接结束外层循环        if(ptmpNode2==pEnd){break;}//第一次排序结束时标志为pTmpNode=NULL,但是pEnd此时还是NULL,所以这里直接写成pEndwhile(ptmpNode2!=pEnd){
//相邻节点作比较，将大数往后挪if(ptmpNode1->data > ptmpNode2->data){pTmpData=ptmpNode1->data;ptmpNode1->data=ptmpNode2->data;ptmpNode2->data=pTmpData;}
//一直向后遍历ptmpNode1=ptmpNode1->pnext;ptmpNode2=ptmpNode2->pnext;}   
//当ptmpNode2走到NULL或者end时，ptmpNode1就是此时保存的数据最大节点，下一次就不用遍历此节点 pEnd=ptmpNode1;}return 0;
}

选择排序

pTmpNode负责遍历后面的节点，当找到比pMinNode节点更小的值时，更新pMinNode,然后比较pSwapNode与pMinNode值的大小，将小的值存放在pSwapNode节点的数据中，pSwap再指向像一个节点，进行下一轮比较

//选择排序
int SelectSortLinkList(LinkNode *pHead)
{LinkNode *pSwapNode=pHead->pnext;LinkNode *pMinNode=pHead->pnext;LinkNode *pTmpNode=NULL;DataType TmpData;if(pHead->pnext==NULL){return 0;}while(pSwapNode->pnext!=NULL){
//每次先将pMinNode保存为待交换的节点pMinNode=pSwapNode;
//从待交换节点的下一个节点开始遍历pTmpNode=pSwapNode->pnext;
//找到后面最小的数据的节点，将每一个遍历的节点都与最小节点比较，让pMinNode总是指向更小的节点while(pTmpNode!=NULL){if(pMinNode->data >pTmpNode->data ){pMinNode=pTmpNode;}pTmpNode=pTmpNode->pnext;}
//如果最小的数据比带交换数据还小，就交换两个节点的数据，保证此轮最小的数据在最前面if(pMinNode->data < pSwapNode->data){TmpData=pMinNode->data;pMinNode->data=pSwapNode->data;pSwapNode->data=TmpData;}
//待交换数据向后依次遍历pSwapNode=pSwapNode->pnext;}return 0;
}

如何判断一个链表是否有环？环长？环的入口位置？

是否有环：

        快指针每次走2步,慢指针每次走1步,快慢指针相遇则说明有环
如何计算环长：

        标记相遇的位置，让指针继续向后走，没走一步计算器自加,走回到标记位置，则计算器值即为环长
如何计算环入口位置：

        将一个指针从第一个节点向后走，将一个指针从相遇点向后走，两个指针相遇的位置即为环入口的位置

LinkNode *IsHasCircle(LinkNode *pHead,int *len)
{int ret=0;*len=1;LinkNode *pFast=NULL;LinkNode *pSlow=NULL;LinkNode *pTmpNode=NULL;LinkNode *pNode1=NULL;LinkNode *pNode2=NULL;pFast=pSlow=pHead->pnext;
//判断是否有环while(1){pFast=pFast->pnext;if(pFast==NULL){ret=0;break;}pFast=pFast->pnext;if(pFast==NULL){ret=0;break;}pSlow=pSlow->pnext;if(pFast==pSlow){ret=1;break;}}if(ret==1){//获得环长
//从相遇节点的下一个节点触发，再次走到相遇节点刚好走路一圈pTmpNode=pSlow->pnext;while(pTmpNode!=pSlow){(*len)++;pTmpNode=pTmpNode->pnext;}获得环入口节点
//pNode1从第一个节点开始向后走pNode1=pHead->pnext;
//pNode2从快慢相遇位置开始走（在环内走）pNode2=pSlow;
//pNode1和pNode2节点相遇的位置即为环入口节点while(pNode1!=pNode2){pNode1=pNode1->pnext;pNode2=pNode2->pnext;}return pNode1;}return NULL;
}


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

相关文章

日常积累史2

日常积累史2

2024.08.27 1.每行固定只显示2个元素-css 方案1&#xff1a; .container1 {display: grid;grid-template-columns: repeat(2, 1fr); /* 设置两列&#xff0c;每列宽度相等 */ } .item1 {background: #0b9f00; }方案2&#xff1a; .container2 {display: flex;flex-wrap: wrap…
阅读更多...
split对大文件（tar/tar.gz）文件进行分片及合并

split对大文件（tar/tar.gz）文件进行分片及合并

文章目录 1、tar文件指定大小分片2、合并分片文件并解压 1、tar文件指定大小分片 split -b 4000M -d -a 3 cm-11.tar.gz cm-11.tar.gz.使用split命令&#xff0c;-b 4000M 表示设置每个分割包的大小&#xff0c;单位还是可以k -d "参数指定生成的分割包后缀为数字的形式 …
阅读更多...
Django REST Framework(十九)权限

Django REST Framework(十九)权限

Django REST framework (DRF) 的权限认证涉及以下几个方面&#xff1a;全局权限配置、局部权限配置、自定义权限类、以及自定义认证类。以下是关于这些方面的详细说明&#xff1a; 1. 全局权限配置 在 Django 项目的配置文件 settings.py 中&#xff0c;可以全局配置 DRF 的权…
阅读更多...
B+树的原理及实现

B+树的原理及实现

B树的原理及实现 一、引言 B树是一种基于B树的树形数据结构&#xff0c;它在数据库和文件系统的索引中有着广泛的应用。与B树相比&#xff0c;B树的所有数据记录都存储在叶节点上&#xff0c;并且增加了顺序访问的能力&#xff0c;这使得B树在处理大量数据时更加高效。 二、…
阅读更多...
Python 爬虫爬取京东商品信息

Python 爬虫爬取京东商品信息

Python 爬虫爬取京东商品信息 下面我将逐一解释每一部分的代码 导入库 from selenium import webdriver from selenium.webdriver.edge.service import Service from selenium.webdriver.edge.options import Options import time import random import csv from selenium.co…
阅读更多...
学习大数据DAY43 Sqoop 安装，配置环境和使用

学习大数据DAY43 Sqoop 安装，配置环境和使用

目录 sqoop 安装 配置 mysql sqoop 安装 sqoop 指令集 sqoop 使用 sqoop 创建 hive 表 sqoop 全量导入表 sqoop 增量导入表 sqoop 全量导出表 sqoop 分区表导入表 sqoop 分区表导出表 上机练习 sqoop 安装 配置 mysql create database test DEFAULT CHARACTER S…
阅读更多...
农产品智慧物流系统论文

农产品智慧物流系统论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱&#xff0c;出错率高&#xff0c;信息安全性差&#x…
阅读更多...
python 实现一个简单的网页爬虫程序

python 实现一个简单的网页爬虫程序

最近在学习python&#xff0c;以下为网页爬虫代码&#xff0c;供参考 1、爬取指定网页的标题和所有的连接 2、并将这些信息保存到一个文件中。 前置&#xff1a;因使用到网页相关的功能&#xff0c;故需导入requests、BeautifulSoup 库来完成 #导入网页相关的库 import requ…
阅读更多...
干货分享|分享一款高效的软件卸载神器 Geek Uninstaller

干货分享|分享一款高效的软件卸载神器 Geek Uninstaller

问题&#xff1a;卸载软件时&#xff0c;时常会留下残留文件和注册表。当遇到流氓软件&#xff0c;还常常卸载失败。 1.软件介绍 特点&#xff1a;高效快速&#xff0c;小巧便携。100% 免费 2.下载方法 官方下载网站&#xff1a;Geek Uninstaller - the best FREE uninstaller …
阅读更多...
中锂天源锂电池：为卡车驻车空调提供高效、安全、持久的能源解决方案

中锂天源锂电池：为卡车驻车空调提供高效、安全、持久的能源解决方案

随着我国运输行业的飞速发展&#xff0c;卡车司机对驾驶环境和行车舒适度的要求越来越高。在炎炎夏日或寒冷冬季&#xff0c;驻车空调已成为卡车司机的必需品。然而&#xff0c;传统驻车空调供电方式存在诸多问题&#xff0c;如电力不足、续航时间短等。为解决这一痛点&#xf…
阅读更多...
Unet改进17：添加ShuffleAttention||减少冗余计算和同时存储访问

Unet改进17：添加ShuffleAttention||减少冗余计算和同时存储访问

本文内容：在不同位置添加ShuffleAttention注意力机制 目录 论文简介 1.步骤一 2.步骤二 3.步骤三 4.步骤四 论文简介 注意机制使神经网络能够准确地关注输入的所有相关元素，已成为提高深度神经网络性能的重要组成部分。在计算机视觉研究中广泛应用的注意机制主要有空间注…
阅读更多...
ElasticSearch7.12.1详细安装

ElasticSearch7.12.1详细安装

部署ElasticSearch docker安装 因为我们还需要部署kibana容器&#xff0c;因此需要让es和kibana容器互联。这里先创建一个网络 创建网络 docker network create es-net 查看网络列表 docker network ls 获取镜像包 docker pull elasticsearch:7.12.1 运行 docker run -d \ -…
阅读更多...
【扩散模型（七）】IP-Adapter 与 IP-Adapter Plus 的具体区别是什么？

【扩散模型（七）】IP-Adapter 与 IP-Adapter Plus 的具体区别是什么？

系列文章目录 【扩散模型&#xff08;二&#xff09;】IP-Adapter 从条件分支的视角&#xff0c;快速理解相关的可控生成研究【扩散模型&#xff08;三&#xff09;】IP-Adapter 源码详解1-训练输入 介绍了训练代码中的 image prompt 的输入部分&#xff0c;即 img projection…
阅读更多...
EXO：模型最终验证的地方；infer_tensor；step；MLXDynamicShardInferenceEngine

EXO：模型最终验证的地方；infer_tensor；step；MLXDynamicShardInferenceEngine

目录 EXO：模型最终验证的地方 EXO：infer_tensor EXO:step MXNet的 mx.array 类型是什么 NDArray优化了什么 1. 异步计算和内存优化 2. 高效的数学和线性代数运算 3. 稀疏数据支持 4. 自动化求导 举例说明 EXO：模型最终验证的地方 EXO：infer_tensor 这段代码定…
阅读更多...
MariaDB 和 MySQL 版本关联

MariaDB 和 MySQL 版本关联

MariaDB 和 MySQL 是两个常用的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它们在很多方面非常相似&#xff0c;因为 MariaDB 是 MySQL 的一个分支。MariaDB 和 MySQL 之间的版本关联可以通过以下几个方面来理解&#xff1a; 1. 历史背景 MySQL: MySQL 是…
阅读更多...
数学建模强化宝典（1）级比检验

数学建模强化宝典（1）级比检验

前言 级比检验是灰色预测中一个重要的步骤&#xff0c;主要用于判断原始数据是否满足准指数规律&#xff0c;从而确定数据是否适合进行灰色预测分析。 一、级比检验的定义 级比检验是通过计算原始数据与其前一期数据的比值&#xff08;即级比&#xff09;&#xff0c;并对级比进…
阅读更多...
智普大模型API调用

智普大模型API调用

接口 用python调用智普免费API接口的例子，写成函数， 类似于 def get_answer(prompt):url = http://34.132.32.68:8081/v1/chat/completionsheaders = {Content-Type: application/json,}data = {"model": "Qwen2-72B-int4","messages": [{&q…
阅读更多...
强化学习——马尔可夫决策过程的理解

强化学习——马尔可夫决策过程的理解

目录 一、马尔可夫决策过程1.策略2.状态价值函数3.动作价值函数4.贝尔曼期望方程 参考文献 一、马尔可夫决策过程 马尔可夫决策过程&#xff08;MDP&#xff09;是马尔可夫奖励过程&#xff08;MRP&#xff09;的扩展&#xff0c;它引入了“动作”这一外界的影响因素&#xff0…
阅读更多...
vscode怎么改成黑色主题？

vscode怎么改成黑色主题？

在Visual Studio Code&#xff08;简称VS Code&#xff09;中&#xff0c;将界面调整为黑色主题是一个简单的过程&#xff0c;可以通过几个步骤轻松完成。以下是详细的操作指南&#xff0c;涵盖了从基本设置到高级自定义化的不同方法。 通过用户设置更改主题 打开设置&#xf…
阅读更多...
C# 去掉字符串最后一个字符的5种方法

C# 去掉字符串最后一个字符的5种方法

C# 去掉字符串最后一个字符的 5 种方法 &#xff08;1&#xff09;Substring string original "Hello!"; string result original.Substring(0, original.Length - 1); Console.WriteLine(result); // 输出: Hello &#xff08;2&#xff09;Remove string o…
阅读更多...
最新文章

Copyright @ 2022~2023

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