顺序表和链表对应的经典算法

这篇具有很好参考价值的文章主要介绍了顺序表和链表对应的经典算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一,移除元素

二,合并两个有序数组

三,环形链表的约瑟夫问题

四,链表的中间节点

五,合并两个有序链表

六,反转链表

七,移除链表元素


一,移除元素

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

思路:定义一个循环遍历数组,如果遇到的不是val就记录下来这个元素,如果不是就跳过

定义两个指针,一个用于保留非val元素,一个用于遍历nums

int removeElement(int* nums, int numsSize, int val)
{
      int*pst=nums;//用于遍历的指针
      int*prev=nums;//用于保留元素的指针
      int size = 0;//被保留下来的元素个数
  
      for(int i=0;i<numsSize;i++ )
      {
            if(pst[i]!=val)
            {
                prev[size]=pst[i];
                size++;
            }
      }
      return size;//题目要求只要返回保留的元素个数即可
}

二,合并两个有序数组

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

思路:边合并边排序

思路一:指定三个标记

               L1=m-1;

               L2=n-1;

               L3=m+n-1;

从后向前比较L1对应的数据与L2对应的数据的大小,谁大就把谁放在L3处,每次比较完,大的数据对应的标记向前走一个,L3也向走一个,最后会有两种情况

一种是L1对应的数据全部放入后三个空位,此时L1已经走到头部对应1的位置,L2还没有全部放入大的数组里面,因为数组是非递减排列的,所以最后只需将剩下L2所有元素一一放入大数组。

一种是L2对应的数据全部放入后三个空位,此时在大数组所有元素均已有序。顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

void merge(int*nums1,int nums1Size,int m,int*nums2,int nums2Size,int n)
{
    int L1=m-1;
    int L2=n-2;
    int L3=m+m-1;
    while(L1>=0&&L2>=0)
    {
        if(nums1[L1]>nums2[l2])
        {
            nums1[L3]=nums1[L1];
            L3--;
            L1--;
        }
        else
        {
            nums1[L3]=nums2[L2];
            L3--;
            L2--;
        }
    }
    while(L2>=0)//此时L1对应数据全部放入尾部,因为两数组均是递增,所以直接将nums2放入尾部即可
    {
        nums1[L3]=nums2[L2];
        L3--;
        L2--;
    }
}

三,环形链表的约瑟夫问题

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

分析:

本题需要有一个能够循环遍历的链表,并且每次数到第m个数都需要删除该节点。

int ysf(int n, int m ) 这个是题目给我们的函数,按照题目意思,我们需要在此函数里循环遍历链 表,删除m节点;

首先我们需要自己创建一个函数,这个函数能够将每个人包装成节点,其次还需要一个函数可以将每个节点连接起来。

包装节点函数可以这样写

#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode ListNode;//将结构体重命名方便使用
 
ListNode*Newnode(int m)
{
    ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));
    if(newnode==NULL)
    {
        perror("newnode");//如果开辟空间失败及时报错
        exit(1);//退出
    }
    //开辟成功,将m值放入放入节点
    newnode->val=m;
    newnode->next=NULL;//将指向下一节点的指针置空避免野指针
    return newnode;
}

有了包装节点的函数,

还需一个可以将其连接起来的函数

ListNode*Contact(int n) //一共有n个人,也就是n个节点
{
    ListNode*phead=Newnode(1);//先定一个头节点作为链表的头指向第一个人
    ListNode*cur=phead;//在cur中保留一份链表头节点
    int i = 0;
    for(i=2;i<=n;i++)从第二个人开始链结
    {
        ListNode*next = Newnode(i);
        cur->next=next;//使cur链接下一节点
        cur=cur->next;//使cur向后移动,作为新创建的节点
    }
    //到这里cur已成为尾节点
    cur->next=phead;//使尾节点的下一节点为头节点,成为循环链表
    return cur;//返回尾节点

}

这里有个疑惑,为什么我不返回头节点,而返回一个尾节点呢,因为在最后的主函数中要循环链表,如果返回头节点那么还没有循环时就已经是第一个人了,刚向下走一步就已经是第二个人了,不方便计数。

下面是主函数的定义

int ysf(int n,int m)
{
    int count = 1;//用来计数第几个人
    ListNode*prev=Newnode(m); //prev为尾节点
    ListNode*pcur=prev->next;//pcur为头节点
    while(pcur->next!=cpur)//开始循环,终止条件是下一个节点指向自己,说明只剩一个人
    {
        if(count==m)
        {
            //此时pcur为要删除的节点
            prev->next=pcur->next//使前置节点prev的下一节点指向pcur后一节点
            free(pcur);//删除当前节点
            pcur=prev->next;//使pcur重新指向被删除节点的后一节点
        }
        else
        {
            prev=pcur;//prev始终为pcur的前一节点
            pcur=pcur->next;
            count++; //既然不是要删的节点,就pcur指向下一个节点,count增加
        }
    }
//最后只剩下一人,返回它对应的人
    return pcur->val              
}

最后将三段代码合并即可


四,链表的中间节点

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

本题可以有两个思路,只介绍思路二。

思路一:寻常方法一一遍历计算节点个数找到中间节点

思路二:算法思想:快慢指针法,定义两个指针,当快指针走到尾节点或者NULL, 慢指针刚好走到中间节点。

如何使快指针走到尾,慢指针刚好是中间节点呢?可以使快指针每次走两步,慢指针每次走一步。


typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode*fast,*slow;
    fast=slow=head;  //两个指针均从头开始
    while(fast&&fast->next)
    {
        slow=slow->next;//一次走一步
        fast=fast->next->next;//一次走两步
    }
    return slow;
}

五,合并两个有序链表

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

分析:

由两个链表合并为一个链表,我们可以创建第三个链表来存放。

定义三个指针,其中两个指针去遍历链表,哪个指针指向的节点较小,就将其放入第三个指针指向指向的链表中,被放入节点的指针向后移动一个单位。

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    ListNode*L1=list1;
    ListNode*L2=list2;
    ListNode*newhead=NULL;
    ListNode*newptail=newhead;
    while(L1&&L2)
    {
        if(L1->val < L2->val)
        {
            if(newhead==NULL)// 如果新链表还没有放入节点,直接是其头尾指针指向第一个节点
            {
                newhead=newptail=L1;
                L1=L1->next;//被放入节点的指针向后移动
            }
            else
            {       //新链表中已经放入元素,直接尾节点指向被放入的节点,
                    //使被放入的节点为新的尾节点。
                newptail->next = L1;
                newptail = newptail->next;
                L1=L1->next;
            }
        }
        else
        {
            if(newhead==NULL)
            {
                newhead=newptail=L2;
                L2 = L2->next;
            }
            else
            {
                newptail->next = L2;
                newptail = newptail->next;
                L2=L2->next;
            }
        }
    }
    if(L1) //如果L1指向的链表还有元素未被放完,直接其尾插新的链表
    {
        newptail->next = L1;
    }
    if(L2) //如果L2指向的链表还有元素未被放完,直接其尾插新的链表
    {
        newptail->next = L2;
    }
    return newhead;
}
六,反转链表

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

分析:

一般单链表的性质就是单项连接不循环的,先要反转链表可能会不太好想。

这里有一种非常让人难以想到的方法:

可以定义三个指针,分别指向NULL,第一个节点和第三个节点。

以第二个指针不为空,也就是走到最后一个节点就结束为条件

每循环一次就是第一个指针指向第二个指针的节点,

然后第二个指针指向第三个指针的节点,最后第三个指针向后移动一个单位

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

这样一来就可以使链表反向。上面只展示循环的一个过程啦,后面的过程照着这样循环,

最后n2和n3都会为空,而n1会变成指向5节点的指针。

下面是代码:短小精悍

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode*head)
{
    if(head==NULL)
    {
        return head;
    }
    ListNode*n1=NULL;
    ListNode*n2=head;
    ListNode*n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        {
           n3=n3->next;
        }
    }
    return n1;
}
七,移除链表元素

顺序表和链表对应的经典算法,c语言,算法,数据结构,开发语言,链表

思路:

这题可以创建一个新的链表,在创建一个指针指向原来的链表,遍历原来的链表,只要是要删除的值就跳过,如果不是要删除的值,就把对应的节点尾插给新链表

typedef struct ListNode ListNode;

struct ListNode* removeElements(struct ListNode* head, int val) {
  
  if(head==NULL)
    {
        return  head;
    }
    ListNode*NewHead=NULL;
    ListNode*NewTail=NULL;
    ListNode*pcur=head;
    while(pcur)
    {
     if(pcur->val!=val)
     {
        //链表为空
        if(NewHead==NULL)
        {
            NewHead=NewTail=pcur;
        }
        else
        {     //不为空
            NewTail->next=pcur;//使新链表的尾节点为pcur
            NewTail=NewTail->next;//使NewTail指向尾节点
        }
     }
     pcur=pcur->next;
    }
    if(NewTail)//至关重要的一步
    {
        NewTail->next=NULL;//最后尾节点nxet要置为空,否则
        //新链表最后的元素会粘连原链表
    }
    return NewHead;
}

以上几题蕴含着一些巧妙的算法思想,希望对各位有帮助。文章来源地址https://www.toymoban.com/news/detail-831974.html

到了这里,关于顺序表和链表对应的经典算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构顺序表和链表(超详细)

    线性表 ( linear list ) 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的, 线性表在

    2024年02月13日
    浏览(55)
  • 数据结构:2_顺序表和链表

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的 ,线性表在物理上

    2024年01月18日
    浏览(54)
  • 【手撕数据结构】(三)顺序表和链表

    🎗️线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 🎗️线性表在逻辑上是线性结构,也就说是一条连续的直线。但是在物理结构上并不一定是连续的,线性表在物理上存储

    2024年02月05日
    浏览(54)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(242)
  • 数据结构奇妙旅程之顺序表和链表

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年02月05日
    浏览(66)
  • 数据结构修炼第二篇:顺序表和链表

    第一章 时间复杂度和空间复杂度 第二章 顺序表,列表 第三章 栈和队列 第四章 二叉树 第五章 排序 作者:🎈乐言🎈 简介:🎈大一学生,目前在致力于c/c++/python,高数的学习,有问题尽管问我,关注后私聊! 持续更新专栏:《c进阶》,《数据结构修炼》 🚀 (优质好文持

    2024年02月02日
    浏览(118)
  • 【数据结构篇C++实现】- 线性表 - 顺序表和链表

    友情链接:C/C++系列系统学习目录 故事导入: 幼儿园放学时,一个班级的小朋友,一个跟着一个排队出校,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面和后面的一个是谁,就如同一根线把他们串联了起来。如此具有像线一样的性质的表就叫线性表 线性表(

    2024年02月07日
    浏览(57)
  • <数据结构>顺序表和链表的比较|缓存命中率

    💭前言:通过之前对顺序表和链表的实现,我们可以发现在增删查改某些操作上两者的效率前言有所差异,本篇文章将总结二者的异同。 顺序表的实现 http://t.csdn.cn/Lxyg2 单链表的实现 http://t.csdn.cn/rHgjG 双链表的实现 http://t.csdn.cn/j3amO 📚顺序表通过数组来实现的,所以在物理

    2024年02月05日
    浏览(52)
  • 数据结构(王道)——线性表之静态链表&顺序表和链表的比较

      如何定义一个静态链表     初始化静态链表:   静态链表的查找、插入、删除           创: 销:   增、删:   查:   顺序表、链表该如何选择?  

    2024年02月16日
    浏览(125)
  • 顺序表和链表

    首先,数据结构中的顺序表和链表都属于线性表。何为线性表?线性表可以描述为: 具有相同数据类型的n个数据元素的有限序列。 形象理解线性表的要素: 幼儿园小朋友放学,需要在校内站成一队,等待家长来接。这是一个 有限 的序列。 总共有几个小朋友,称之为线性表

    2024年02月06日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包