了解单链表

27. 移除元素 - 力扣(LeetCode)

思路一: 创建新的数组,遍历原数组,将不为val的值放到新数组当中。空间复杂度不为O(1)

思路二:双指针法

我们设置两个指针src(源数据)和dst(目标数据)分别指向数组的第一个位置,如果src指向的数值是我们要删除的数据,那么src++,如果src要的数据不是我们要删除的数据,那么把src的数据赋值给dst,并让src++,dst++。

int removeElement(int* nums, int numsSize, int val) {
    int src,dst;
    src=dst=0;
    while(src<numsSize)//numsSize表示数组的长度
    {
        if(nums[src]==val)
        {
            src++;
        }
        else
        {
            nums[dst]==nums[src];
            dst++;
            src++;
        }
        return dat;//此时dst的值就是新数组的有效长度
    }
    
}

88. 合并两个有序数组 - 力扣(LeetCode)

思路一:将num2中数据依次放入到num1数组的后面,用排序算法对num1进行排序

思路二:

 

l1和l2进行比较。   

思路三:

从后往前比大小:比谁大,谁大谁就往后放

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    //nums1Size:nums1数组的长度
    //nums2Size:nums2数组的长度
    int l1=m-1;
    int l2=n-1;
    int l3=m+n-1;
    while(l1>=0&&l2>= 0)//只要有一个条件为假,就跳出循环
    {
        if(nums1[l1]<nums2[l2])
        {
            nums1[l3--]=nums2[l2--];
        }
        else
        {
            nums1[l3--]=nums1[l1--];
        }

    }
    //出了循环有两种情况:l1大于等于0或者l2大于等于0,不存在l1和l2同时大于等于0的情况
    //只需要处理一种情况,那就是l2大于等于0,说明l2中的数据还没有完全放入num1中
    while(l2>=0)
    {
        nums1[l3--]=nums2[l2--];
    }
//此时nums1中包含了nums2中的数据,num1为升序数组
}

  我们需要有一个定义链表的节点的结构,并且将它们连接在一起,就成了链表。

 SList.h

typedef int SLDataType;
struct SListNode
{
    SLDataType data;
    struct SListNode*next;//指向下一节点的指针
}SLTNode;

void SLTPrint(SLTNode*phead);
void SLTPushBack(SLTNode* phead,SLTDataType x);
void SLTPushFront(SLTNode* phead,SLTDataType x);

SList.c

void SLTPrint(SLTNode* phead)
{
   SLTNode*pcur=phead;
   while(pcur)
   {
       printf("%d->",pcur->data);
       pcur=pur->next;
    }
   printf("\n");
}
//申请新的节点
SLTNode*SLTBuyNode(SLTDataType x)
{
  
   SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));
   if(newnode==NULL)
   {
      perror("malloc fail!");
      exit(1);//异常退出,正常退出为0
   }
   newnode->data=x;
   newnode->next=NULL;
   
   return newnode;
}
//尾插
void SLTPushBack(SLTNode**phead,SLTDataType x)
{
   assert(pphead);
   SLTNode*newnode=SLTBuyNode(x);//在创建 空间之前判断空间是否够用
   if(phead==NULL)//处理空链表和非空链表两种情况
   {
      phead=newnode;
    }
   else
   {
   //找尾
   SLNode*ptail=phead;
   while(ptail->next)
   {
       ptail=ptail->next;//ptail指向的就是尾结点
    }
    ptail->next=newnode;//完成了尾插的动作
    }
}
//头插
 void SLTPushFront(SLTNode**phaed,SLTDataType x)
{
    assert(pphead);
    STNode*newnode=SLBuyNode(x);
    newnode->next=*phead;
    *pphead=newnode;
 }
//尾删
void SLTPopBack(SLTNode**pphead)
{
    assert(pphead&&*pphead);//链表不能为空
    //链表只有一个节点
    if((*pphead)->next==NULL)//->优先级高于*
    {
        free(*pphead);
        *pphead=NULL;
     }
    else{//链表有多个节点
    SLTNode*prev=*pphead;
    SLTNode*ptail=*pphead;
    while(ptail->next)
    {
        prev=ptail;
        ptail=ptail->next;
     }
    free(ptail);
    ptail=NULL;
    prev->next=NULL;
    }
}
//头删
void SLPopFront(SLTNode**pphead)
{
    //链表不能为空
    assert(pphead&&*pphead);//链表不能为空
    SLTNode*next=(*pphead)->next;//->优先级高于*
    free(*pphead);
    *pphead=next;
}
//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
      SLTNode*pcur=phead;
      while(pcur)//等价于pcur不等于空
      {
         if(pcur->data==x)
         {
            return pcur;
         }
         pcur=pcur->next;
      }
      return pcur;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x)
{
    assert(pphead&&*pphead);//如果没有这个数据,就不能插入数据
    assert(pos);
//在指定位置之前插入数据
//找pos指针的前一个节点
    STNode*newnode=SLBuyNode(x);
    if(pos==*pphead)
    {
        SLTPushFront(pphead,x);
    }
    else
    {
    SLTNode*prev=*pphead;//初始情况下指向第一个节点
    while(prev->next!=pos)
    {
        prev=prev->next;
    }
    // 把prev newnode pos三者连接在一起
    newnode->next=pos;
    pre->next=newnode;
    }
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x)
{
    assert(pos);
    STNode*newnode=SLBuyNode(x);
    newnode->next=pos->next;   
    pos->next=newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead,SLTNode*pos)
{
     assert(pphead&&*pphead);//链表不能为空
     assert(pos);
     if(pos==*pphead)
     {
        SLTNode* next=(*pphead)->next;//先把头结点的下一个节点储存起来
        free(*pphead);
           *pphead=next;//或者直接采用SLTPopFront(pphead);
     }
     else
     {
        SLTNode*prev=*pphead;
        while(prev->next!=pos)
        {
            prev=prev->next;
         }
         free(pos);
        pos=NULL;
      }
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
    assert(pos&&pos->next);
    SLTNode*del=pos->next;
    pos->next=del->next;
    free(del);
    del=NULL;

}
//销毁链表(销毁一个一个的节点)   
void SListDestory(SLTNode**pphead)
{
    assert(pphead&&*pphead);
    SLTNode*pcur=*pphead;
    while(pcur)
    {
         SLTNode*next=pcur->next;
         free(pcur);
         pcur=next;
     }
    *pphead=NULL;
}
          

如果链表为空,不能对空指针进行解引用,代码会报错。

但是当我们运行之后发现,形参改变了,实参并没有改变。

把头结点释放掉, 再把*pphead走到next指针当中。

当pos=*pphead时,走不通。 

上面这两种插入节点的方式是否相同?

1  newnode->next=pos->next;   pos->next=newnode;

2  pos->next=newnode;   newnode->next=pos->next;

 

像下面这么操作,是否可行呢? 

这样操作就把节点4释放了。我们可以创建一个临时变量del。

test.c

#include"SList.h"
void SListTest()
{
  //链表是由一个一个的节点组成
  //创建几个节点
  SLNode*node1=malloc(sizeof(SLTNode));//对于节点,我们不会涉及到增容的概念,所以我们使用malloc,而不是使用realloc
  node->data=1;
  SLNode*node2=malloc(sizeof(SLTNode));
  node->data=2;
  SLNode*node3=malloc(sizeof(SLTNode));
  node->data=3;
  SLNode*node4=malloc(sizeof(SLTNode));
  node->data=4;//创建好了4个节点,但是此时这四个节点不能相互找到
  //通过每个节点里的next指针,将各个节点连接起来
  node1->next=node2;
  node2->next=node3;
  node3->next=node4;
  node4->next=NULL;
//调用链表的打印
  //再定义一个节点,指向node1,然后作为实参传入
  SLTNode*plist=node1;
  SLTPrint(plist);

}

int main()
{
    return 0;
}

尾插

要找到尾结点,再把尾结点和新节点连接起来。我们让尾结点的下一节点不要指向NULL,而是指向newNode。这样就实现了尾插。

如果我们设置找到ptail的循环条件是while(ptail!=NULL),那么此时不满足。应该是ptail->next不为空。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532475.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STM32G030F6P6 HSE时钟不能使用无源晶振,只能使用有源晶振!

STM32G030F6P6 HSE时钟不能使用无源晶振&#xff0c;只能使用有源晶振。 参见STM32CubeMX配置 使能RCC中 BYPASS CLOCK SOURCE后只有一个 PC14引脚。 查手册中 5.2.1 HSE clock章节 部分引脚少的封装&#xff0c;HSE时钟只有 OSC-IN&#xff0c;因此只能使用有源晶振 查Data…

mybatis-动态sql

动态sql 1、if标签2、where标签3、trim标签4、set标签5、choose when otherwise6 、foreach6.1 用in来删除6.2 用or来删除6.3 批量添加 7、 sql标签与include标签 1、if标签 需求&#xff1a;多条件查询。 可能的条件包括&#xff1a;品牌&#xff08;brand&#xff09;、指导…

SQL注入sqli_labs靶场第二题

解题思路与第一题相同 ?id1 and 11 和?id1 and 12进行测试如果11页面显示正常和原页面一样&#xff0c;并且12页面报错或者页面部分数据显示不正常&#xff0c;那么可以确定此处为数字型注入。 联合查询&#xff1a; 猜解列名数量&#xff1a;3 ?id1 order by 4 判断回显…

20240410解决OK3588-C的核心板刷机之后无法启动的问题

20240410解决OK3588-C的核心板刷机之后无法启动的问题 2024/4/10 19:38 1、编译OK3588的LINUX/Buildroot&#xff1f;forlinxubuntu: ~/3588/OK3588_Linux_fs$ sudo ./build.sh BoardConfig-linuxfs-ok3588.mk 2、进行全编译 forlinxubuntu: ~/3588/OK3588_Linux_fs$ sudo ./bu…

ArrayList中多线程的不安全问题

ArrayList中的不安全问题 正常的输出 List<String> list Arrays.asList("1","2","3"); list.forEach(System.out::println);为什么可以这样输出&#xff0c;是一种函数是接口&#xff0c;我们先过个耳熟 Arrys.asList是返回一个ArrayL…

ruoyi-nbcio-plus基于vue3的flowable的自定义业务提交申请组件的升级修改

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a…

nandgame中的Tokenize(标记化)

题目说明&#xff1a; "Tokenize" "标记化"标记器预先配置为识别数字和符号 。请配置标记器以额外识别符号减号 - 和括号 ( 和 )。您可以编辑源代码区域中的代码以测试它的标记化。level help 我们将构建一种高级编程语言。 高级语言具有更加人性化和灵…

Android 输入法框架

输入法属于输入系统的一部分&#xff0c;区别于输入系统只能向系统产生时间&#xff0c;输入法能向系统输入具体的内容&#xff0c;下面来认识输入法的大体框架&#xff0c;以下内容参考清华大学出版社出版的《Android图形显示系统》。 输入法框架包含3个组件&#xff0c;各组件…

AI智能滤镜解决方案,全新的视觉创作体验

一张精美的图片&#xff0c;一段引人入胜的视频&#xff0c;往往能够瞬间抓住观众的眼球&#xff0c;为企业带来不可估量的商业价值。然而&#xff0c;如何快速、高效地制作出高质量的视觉内容&#xff0c;一直是困扰众多企业的难题。美摄科技凭借其领先的AI智能滤镜解决方案&a…

处理慢查询时使用explain一般看哪些字段

explain之后会出现这些&#xff0c;一般就只看下面这几个字段 select_type就是查询类型&#xff0c;在我司的业务里基本上用的都是简单查询&#xff0c;在内存中处理逻辑&#xff0c;复杂查询的话排查问题比较麻烦&#xff0c;引起慢查询还会拖累数据库&#xff0c;数据库里还…

MySQL学习笔记(数据类型, DDL, DML, DQL, DCL)

Learning note 1、前言2、数据类型2.1、数值类型2.2、字符串类型2.3、日期类型 3、DDL总览数据库/表切换数据库查看表内容创建数据库/表删除数据库/表添加字段删除字段表的重命名修改字段名&#xff08;以及对应的数据类型&#xff09; 4、DML往字段里写入具体内容修改字段内容…

Celery使用异步、定时任务使用

一、什么是Celery 1.1、celery是什么 Celery是一个简单、灵活且可靠的&#xff0c;处理大量消息的分布式系统&#xff0c;专注于实时处理的异步任务队列&#xff0c;同时也支持任务调度。 Celery的架构由三部分组成&#xff0c;消息中间件&#xff08;message broker&#xf…

谈谈功率IC巨头—士兰微

大家好&#xff0c;我是砖一。 今天给大家分享一下士兰微电子公司&#xff0c;&#xff0c;有做功率元器件&开关电源和IC的朋友可以了解一下&#xff0c;希望对你有用~ 1 公司介绍 士兰微电子成立于1997年&#xff0c;于2003年上市&#xff0c;总部位于杭州&#xff0c;…

雪花飘,购物抛物线,进度条等四个案列,带入走进 CSS transition

前言 今天从四个案例&#xff0c;我们一起走进 CSS Transition。 源码 以及 在线演示地址 源码地址&#xff1a; 四个案例&#xff0c; CSS Transition 源码 在线演示地址&#xff1a;(兼容移动端) 贝塞尔曲线运动进度条雪花飘飘效果购物车抛物线效果 案例演示 内置贝塞…

kafka(五)——消费者流程分析(c++)

概念 ​ 消费者组&#xff08;Consumer Group&#xff09;&#xff1a;由多个consumer组成。消费者组内每个消费者负责消费不同分区的数据&#xff0c;一个分区只能由一个组内消费者消费&#xff1b;消费者组之间互不影响。所有的消费者都属于某个消费者组&#xff0c;即消费者…

猫头虎博主深度探索:Amazon Q——2023 re:Invent 大会的 AI 革新之星

摘要 大家好&#xff0c;我是猫头虎博主&#xff01;今天&#xff0c;我要带大家深入了解2023年 re:Invent 大会上发布的一款革命性产品——Amazon Q。让我们一起探索这个引领未来工作方式的新型工具吧&#xff01; 引言 在2023年的 re:Invent 大会上&#xff0c;亚马逊云科…

RAG 修炼手册|一文讲透 RAG 背后的技术

在之前的文章中《RAG 修炼手册&#xff5c;RAG敲响丧钟&#xff1f;大模型长上下文是否意味着向量检索不再重要》&#xff0c;我们已经介绍过 RAG 对于解决大模型幻觉问题的不可或缺性&#xff0c;也回顾了如何借助向量数据库提升 RAG 实战效果。 今天我们继续剖析 RAG&#xf…

docker-compose 之 OpenGauss

使用 docker 启动高斯数据库的示范脚本如下&#xff1a; docker-compose.yml version: 3.7 services:opengauss:image: enmotech/opengauss:5.1.0container_name: opengaussnetwork_mode: "host"privileged: truevolumes:- ./opengauss:/var/lib/opengaussenvironm…

前端mock数据——使用mockjs进行mock数据

前端mock数据——使用mockjs进行mock数据 一、安装二、mockjs的具体使用 一、安装 首选需要有nodejs环境安装mockjs&#xff1a;npm install mockjs 若出现像上图这样的错&#xff0c;则只需npm install mockjs --legacy-peer-deps即可 src下新建mock文件夹&#xff1a; mo…

微服务-网关

在微服务架构中&#xff0c;每个服务都是一个可以独立开发和运行的组件&#xff0c;而一个完整的微服务架构由一系列独立运行的微服务组成。其中每个服务都只会完成特定领域的功能&#xff0c;比如订单服务提供与订单业务场景有关的功能、商品服务提供商品展示功能等。各个微服…