程序员经验分享-hwhale

五大板块（4）——链表

2023-10-28

参考：五大板块（4）——链表
作者：丶PURSUING
发布时间： 2021-02-15 09:33:29
网址：https://blog.csdn.net/weixin_44742824/article/details/114981905

一、对比链表与数组

同样是存放一串数据，链表与数组的区别在哪里？

在这里插入图片描述

数组是申请连续的地址存放数据，在增加或删除某一元素不方便。

而链表可以很好地解决这个问题。

链表方便增删

大致思路：

  • 增加节点

在这里插入图片描述

  • 删除节点
    在这里插入图片描述

二、链表的静态创建

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;
                    //t1.next是一个结构体指针，访问里面的data自然要用->
        printf("%d %d %d\n",t1.data,t1.next->data,t1.next->next->data);
        return 0;
}

链表的动态遍历：统计节点个数与查找节点

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

//遍历链表，把节点数据打印出来
void printLink(struct Test *head)
{
        int i;
        struct Test *p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
}
//统计链表节点个数
void getNodeNum(struct Test *head)
{
        int cnt = 0;
        struct Test *p = head;
        while(p != NULL){
                cnt++;
                p = p->next;
        }
        printf("链表节点的个数是:%d\n",cnt);
}

//找节点
void findNode(struct Test *head,int data)
{
        struct Test *p = head;
        while(p != NULL){
                if(p->data == data){
                        printf("找到了\n");
                        return;//直接退出子函数，返回main函数
                }
                p = p->next;
        }
        printf("没找到\n");
}

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;

        printLink(&t1);
        getNodeNum(&t1);
        findNode(&t1,2);
        
        return 0;
}

结果：

1 2 3 链表节点的个数是:3
找到了
  • 1
  • 2

要重点理解的是：p = p->next
指针p指向了下一个结构体的地址，p->next中存放的正是下一个链表节点的地址。
p本身是一个结构体指针，所以用->访问成员next.

三、插入节点与删除节点

从指定节点的后方插入新节点

思路：
（1）找到指定节点
（2）把指定节点的的next指向new节点的地址
（3）new节点的next指向下一个节点

靠，真拗口，看图！
在这里插入图片描述
举例：要从链表1 2 3 4 中，在 2 后插入 5 。

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

void addBehind(struct Test *head,int data,struct Test *new)
{
        struct Test *p = head;
        while(p != NULL){
                if(data == p->data){
                        new->next = p->next;//先连新节点的后面
                        p->next = new;      //再连新节点的前面
                        return;
                }
                p = p->next;
        }
}

void printLink(struct Test *head)
{
        int i;
        struct Test *p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};
        struct Test t4 ={4,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;
        t3.next = &t4;

        struct Test new ={5,NULL};
        addBehind(&t1,2,&new);

        printLink(&t1);

        return 0;
}

结果：

1 2 5 3 4
  • 1

思考一下，为什么上面要传入结构体new的地址？

像下图一样修改，传入的是结构体变量new，然后p->next再指向new的地址不就行啦？还不是一样把地址串了起来。

void addBehind(struct Test *head,int data,struct Test new)
{
        struct Test *p = head;
        while(p != NULL){
                if(data == p->data){
                        new.next = p->next;
                        p->next = &new;//形参函数结束就释放了 p->next指向这个位置会发生断错误
                        return;
                }
                p = p->next;
        }
}

addBehind(&t1,2,new);

结果是：段错误

Segmentation fault
  • 1

为啥？

因为上述中new只是子函数的一个形式参数罢了，地址空间是临时分配，当函数调用结束空间回收，你让一个指针p->next指向这里，必然导致段错误！

在指定节点前方插入新节点

第一种情况：不是1之前插入，链表头未发生改变

在这里插入图片描述第二种情况：是在1之前插入，链表头发生改变
在这里插入图片描述

举个栗子：（1）要从链表1 2 3 4 中，在 3 前插入 5 。

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

struct Test *addInfront(struct Test *head,int data,struct Test *new)
{
        struct Test *p = head;
        if(data == head->data){
                new->next = head;    //先连新节点的后面
                head = new;
                return head;
        }
        while(p->next != NULL){
                if(data == p->next->data){
                        new->next = p->next;//先连新节点的后面
                        p->next = new;      //再连新节点的前面
                        return head;
                }
                p = p->next;//让链表遍历起来
        }
}

void printLink(struct Test *head)
{
        int i;
        struct Test *p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};
        struct Test t4 ={4,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;
        t3.next = &t4;

        struct Test new ={5,NULL};
        struct Test *head = &t1;

        head = addInfront(head,3,&new);

        printLink(head);

        return 0;
}

结果：

1 2 5 3 4
  • 1

（2）更改程序，在1之前插入5，结果:

5 1 2 3 4
  • 1

删除指定节点

在这里插入图片描述
当删除的是头节点时，还要注意新头的替换！

举例：删除 1 2 3 4中的 1

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

struct Test *deNode(struct Test *head,int data)
{
        struct Test *p = head;
        if(data == head->data){
                head = head->next;
                return head;
        }

        while(p->next != NULL){
                if(data == p->next->data){
                        p->next = p->next->next;
                        return head;
                }
                p = p->next;
        }
}

void printLink(struct Test *head)
{
        int i;
        struct Test *p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};
        struct Test t4 ={4,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;
        t3.next = &t4;

        struct Test *head = &t1;

        head = deNode(head,1);

        printLink(head);

        return 0;
}

结果：

2 3 4
  • 1

删除 1 2 3 4中的4，结果：

1 2 3
  • 1

四、链表的动态创建

头插法创建链表

头一直是在变化的
在这里插入图片描述关键步骤：

new->next = head;//new直接指向原来的链表头
head = new;//赋予新的链表头

实际例子：

运用头插法创建链表，直接输入数据自动串成链表，想要结束时，输入数据999.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct test
{
        int data;
        struct test *next;
}test,*ptest;

void printLink(ptest head)
{
        int i;
        ptest p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

ptest insertHead(ptest head,ptest new)
{
        if(head == NULL){
                head = new;
        }else{
                new->next = head;//先连新节点的后面   new往前拱
                head = new;      //再连新节点的前面   new变成新头（头插）
        }
        return head;

}

ptest creatLink(ptest head)
{
        ptest new;
        while(1){
                new = (ptest)malloc(sizeof(test));
                printf("请输入新的节点,输入999结束输入\n");
                scanf("%d",&new->data);
                if(new->data == 999){
                        free(new);
                        new = NULL;
                        return head;
                }
                head = insertHead(head,new);
        }
}

int main()
{
        ptest head = NULL;
        head = creatLink(head);
        printLink(head);
        return 0;
}

结果：

请输入新的节点,输入999结束输入
3
请输入新的节点,输入999结束输入
4
请输入新的节点,输入999结束输入
5
请输入新的节点,输入999结束输入
6
请输入新的节点,输入999结束输入
999
6 5 4 3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

尾插法创建链表

在这里插入图片描述

关键步骤：

（1）遍历找到链表的尾部

while(p->next != NULL){
	p = p->next;
}
  • 1
  • 2
  • 3

（2）在尾部添加new

p->next = new;
  • 1

实际例子：

运用尾插法创建链表，直接输入数据自动串成链表，想要结束时，输入数据999.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct test
{
        int data;
        struct test *next;
}test,*ptest;

void printLink(ptest head)
{
        int i;
        ptest p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

ptest insertTail(ptest head,ptest new)
{
        ptest p = head;
        if(p == NULL){
                head = new;
                return head;//没有此句段错误
        }
        while(p->next != NULL){
                p = p->next;//遍历找到尾巴
        }
        p->next = new;//new跟在屁股后面（尾插）

        return head;
}

ptest creatLink(ptest head)
{
        ptest new;
        while(1){
                new = (ptest)malloc(sizeof(test));
                printf("请输入新的节点,输入999结束输入\n");
                scanf("%d",&new->data);
                if(new->data == 999){
                        free(new);
                        new = NULL;
                        return head;
                }
                head = insertTail(head,new);
        }
}

int main()
{
        ptest head = NULL;
        head = creatLink(head);
        printLink(head);
        return 0;
}

结果：

请输入新的节点,输入999结束输入
3
请输入新的节点,输入999结束输入
4
请输入新的节点,输入999结束输入
5
请输入新的节点,输入999结束输入
999
3 4 5
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

思考：当上面的inserTail函数更改为如下，会发生什么？

ptest insertTail(ptest head,ptest new)
{
        ptest p = head;
        if(head == NULL){
                head = new;
        }else{
                p->next = new;
        }
        return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

结果：可以发现无论怎样输入链表都只有第一个和最后一个数据

请输入新的节点,输入999结束输入
1
请输入新的节点,输入999结束输入
3
请输入新的节点,输入999结束输入
5
请输入新的节点,输入999结束输入
6
请输入新的节点,输入999结束输入
8
请输入新的节点,输入999结束输入
999
1 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

那是因为：使用尾插法，链表头一直未改变。然而在每一次的循环中，p->next都指向new，即为每次头都指向new。到最后链表中自然只有头和最新的new啦。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

C语言基础

链表

五大板块（4）——链表 的相关文章

  • 【考研】数据结构——线索二叉树

    CSDN话题挑战赛第2期 参赛话题 学习笔记 前言 本文内容源于对 数据结构 C语言版 第2版 王道讲解学习所得心得 笔记整理和总结 本文针对线索二叉树 在最后的练习中 以举例子说明该排序方法 配以图文 讲解详细 含408真题 可搭配以下链

  • 剑指offer（16）——C++实现两个链表合并

    题目 输入两个单调递增的链表 输出两个链表合成后的链表 当然我们需要合成后的链表满足单调不减规则 考察点 链表 解题思路 递归实现 比较每个节点大小 将较小的放入新链表 非递归 原理同上 完整代码 16 合并两个链表 include

  • 005. 反转链表-双指针

    题目链接 力扣 代码 01 双指针 class Solution public ListNode reverseList ListNode head ListNode temp 保存cur的下一个节点 ListNode cur head L

  • 双链表嵌套的简单学生信息管理系统

    参考 实现双链表嵌套的简单学生信息管理 作者 三速何时sub20 发布时间 2020 07 20 10 44 40 网址 https blog csdn net weixin 44234294 article details 1074581

  • C++中的.和-＞

    C 中的 和 gt 1 C 中的点 的应用 如果是一个对象或者引用去调用成员变量或者成员函数函数的话 会使用到点 include

  • ArrayList与顺序表

    目录 编辑 一 线性表 二 顺序表 1 接口的实现 1 打印顺序表 2 新增元素 3 判定是否包含某个元素 4 查找某个元素对应的位置下标 5 获取 pos 位置的元素 6 获取顺序表长度 7 给 pos 位置的元素设为 value 更新的

  • leetcode138.复制带随即指针的链表

    思路 struct Node copyRandomList struct Node head struct Node cur head while cur struct Node copy struct Node malloc sizeof

  • 【数据结构】复杂度

    博客主页 小王又困了 系列专栏 数据结构 人之为学 不日近则日退 感谢大家点赞 收藏 评论 目录 一 什么是数据结构 二 什么是算法 三 算法的效率 四 时间复杂度 4 1大O渐进表示法 4 2常见时间复杂度计算举例 4 3例题 消失的数字

  • 链式二叉树的基本操作(C语言实现)

    目录 一 链式二叉树的创建 1 1 定义节点结构 1 2 节点的创建 1 3 节点的链接 二 树的深度遍历 1 前序 中序 后序遍历 1 2 三种方式的遍历顺序图 2 代码实现 3 遍历检测 三 树的层序遍历 3 1 层序遍历 3 2 完全

  • 95-34-030-Context-DefaultChannelHandlerContext

    文章目录 1 概述 2 继承体系 3 源码 1 概述 2 继承体系 3 源码 final class DefaultChannelHandlerContext

  • 模拟实现 队列 - JAVA（使用链表，数组）

    以链表实现 以数组实现 以链表实现 class Node public int val public Node next public Node int val this val val public class MyQueue publi

  • 如何学好C语言的数据结构与算法？

    C语言的数据结构与算法 难就难在链表 学会了链表 可能后面就一点都不难了 书籍推荐 数据结构与算法分析 C语言描述版 要深入学习的话可以选择这本书 因为针对链表的讲解是比较详细的 所以可以很快理解链表 跟着书上一点点实现基本操作 增删改查

  • OJ-合并两个有序链表

    题目描述 代码如下 Definition for singly linked list struct ListNode int val struct ListNode next struct ListNode mergeTwoLists s

  • 【C++】STL中list容器内部元素的移动和交换

    文章目录 前言 一 list是什么 二 元素移动 1 插入 删除 2 切除 拼接 三 元素交换 1 元素值交换 2 元素 节点 交换 总结 前言 提示 list insert list erase list splice std iter

  • C/C++---------------LeetCode第876. 链表的中间结点

    链表的中间结点 题目及要求 双指针 在main内使用 题目及要求 给你单链表的头结点 head 请你找出并返回链表的中间结点 如果有两个中间结点 则返回第二个中间结点 示例 1 示例 2 双指针 思路 分别定义快慢指针即慢指针一次走一步 快

  • 链表【1】

    文章目录 2 两数相加 1 题目 2 算法原理 3 代码实现 445 两数相加 II

  • LeetCode21. Merge Two Sorted Lists

    文章目录 一 题目 二 题解 一 题目 You are given the heads of two sorted linked lists list1 and list2 Merge the two lists into one sort

  • 《LeetCode力扣练习》代码随想录——双指针法（反转链表---Java）

    LeetCode力扣练习 代码随想录 双指针法 反转链表 Java 刷题思路来源于 代码随想录 206 反转链表 双指针 Definition for singly linked list public class ListNode int

  • 【LeetCode:114. 二叉树展开为链表 | 二叉树 + 递归】

    算法题 算法刷题专栏 面试必备算法 面试高频算法 越难的东西 越要努力坚持 因为它具有很高的价值 算法就是这样 作者简介 硕风和炜 CSDN Java领域新星创作者 保研 国家奖学金 高中学习JAVA 大学完善JAVA开发技术栈 面试刷题

  • 链表的中间节点

    链表的中间节点 力扣 LeetCode 官网 全球极客挚爱的技术成长平台 备战技术面试 力扣提供海量技术面试资源 帮助你高效提升编程技能 轻松拿下世界 IT 名企 Dream Offer https leetcode cn problems

随机推荐

  • Vue.js 下的瀑布流组件 vue-waterfall

    vue waterfall 详细介绍 Vue js 下的瀑布流组件 ES5 ES6 UMD 兼容 享受数据驱动带来的便利 让事情变得简单

  • 判断t1树中是否有与t2树完全相同的子树

    描述 给定彼此独立的两棵二叉树 树上的节点值两两不同 判断 t1 树是否有与 t2 树完全相同的子树 示例1 输入 1 2 3 4 5 6 7 8 9 2 4 5 8 9 返回值 true 备注 1 n 500000 方法一 递归 要判断t

  • 使用echarts实现简单的关系图谱

    使用echarts实现简单的关系图谱 如图 代码

  • pytorch载入数据与对应的标签，使用torch.utils.data详解，DataLoader的使用

    在进行深度学习处理的时候 我们需要将数据输入到神经网络中进行训练 训练网络的学习能力 其实是根据一定的规则更新网络节点中的参数 而这个规则的来源就是依赖于数据与标签 我们需要将数据与标签相匹配 才能让网络进行训练 比如说网络学习到了一定的特

  • stem教育资源

    人生不同阶段都有不同的使命 在学生阶段 学习掌握知识为以后的人生获得成就的能力 就是这个阶段使命 为了这个使命 他们必须要学习忍耐 学会放弃 学会付出 这不仅仅是学习的需要 也是人生的一种修炼 纵观我们身边的人 但凡取得一定成就的都是要经过

  • 用 LangChain 构建基于资料库的问答机器人（三）：ReAct

    大家好 我是 Jambo 我们已经学习了如何使用 LangChain 的一些基本功能 解下我们就应该要结合这些功能来做一些复杂的东西了 但在这之前 为了让同学们更好的理解 LangChain 在这其中做了什么 我想先介绍一下关于 GPT 使

  • 修改索引值python_pandas DataFrame的修改方法(值、列、索引)

    对于DataFrame的修改操作其实有很多 不单单是某个部分的值的修改 还有一些索引的修改 列名的修改 类型修改等等 我们仅选取部分进行介绍 一 值的修改 DataFrame的修改方法 其实前面介绍loc方法的时候介绍了一些 1 loc方法

  • STM32 IAP Ymodem

    STM32 IAP采用Ymodem协议升级固件 公司最近软件需要通过IAP来升级所有板卡的固件 其中板卡有2块 一块主控板卡 一块子控板卡 其中 主控板卡与子控板卡之间采用RS485通信 PC与主控板卡采用RS232通信 具体框架 一 PC

  • pc817光耦参数_光耦在电子电路中有什么作用？关键参数有哪些？一起了解一下...

    光耦作为一个可以对信号进行电气隔离的电子元器件 常用于开关电源电压反馈隔离 电路隔离控制 光耦在电子电路中有不可或缺的地位 了解光偶的特性对学习电子电路有不少帮助 开关电源电压反馈 光耦隔离控制继电器 今天就一起来了解一下光耦吧 电子元器件

  • linkstack头文件 c语言,链式栈的基本操作——LinkStack（C语言版）

    include stdafx h include define OK 1 define ERROR 0 define TRUE 1 define FALSE 0 define MAXSIZE 20 存储空间初始分配量 typedef int

  • odoo10源码win系统开发环境安装图文教程

    前言 odoo10的源码安装教程不太完整或对新手不够友好 本新手再次整合出一份友好的新手教程 老鸟慎入 准备工作 一个干净的window系统 事先没有其他python环境的系统 如果怕系统污染可以先用虚拟机安装熟悉了再正式安装 亲测wind

  • 【论文写作】——设置中英文字体

    打开文件 点击选项 选择高级 取消中文字体也应用于西文的勾选 然后选中全文 设置中文字体为宋体 设置英文字体为times new Roman

  • flask框架

    flask框架 一 flask简介 二 初体验 三 flask配置 1 开启debug模式 2 如何正确显示中文 2 1 配置文件的优化 四 URL与视图 1 构造URL url for 五 指定HTTP方法 六 页面跳转和重定向 七 模板

  • 【PostMan】postman如何发送并发请求

    1 概述 假设我们有一个接口 单次调用可以调通 然后我们将这个接口加入到集合 也可以复制一个接口或者多个到集合 然后点击 后面点击运行就可以模拟 20个线程 轮训集合中的接口 并发的调用

  • [423]定时任务（saturn）

    项目地址 https github com vipshop Saturn 参考文档 https vipshop github io Saturn zh cn 3 0 https vipshop github io Saturn zh cn

  • 揭秘python函数：编程艺术的核心力量

    文章目录 前言 什么是 python 函数 函数的使用步骤 1 定义函数 2 调用函数 带有参数的函数 函数的返回值 函数的说明文档 函数的嵌套调用 实现简易的计算器 前言 当我们深入研究 Python 的内心深处 我们将会发现 函数是其内

  • c语言的文件末尾没有换行符,为什么文本文件应该以换行符结尾？

    这个答案是一种技术性的回答 而不是意见 如果我们想成为POSIX纯粹主义者 我们定义一条线为 零个或多个非字符加上终止字符的序列 不完整的一行 如 文件末尾一个或多个非字符的序列 文本文件 如 包含组织成零行或多行的字符的文件 这些行不包含

  • 面向对象基础--类和对象

    类和对象的关系 一 对象 用来描述客观事物的一个实体 由一组属性和方法构成 对象是由静态特征和动态特征组成 1 静态特征 属性 2 动态特征 方法 对象的特征 属性 属性 对象具有的各种特征 每个对象的每个属性都拥有特定值 对象的特征 方法

  • npm : 无法将“npm”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。请检查名称的拼写，如果包括路径，请确保路径正确，然后再试一次。

    npm 无法将 npm 项识别为 cmdlet 函数 脚本文件或可运行程序的名称 请检查名称的拼写 如果包括路径 请确保路径正确 然后再试一次 目录 一 报错 二 解决 1 安装node js node js安装过程中的报错问题 解决nod

  • 五大板块（4）——链表

    参考 五大板块 4 链表 作者 丶PURSUING 发布时间 2021 02 15 09 33 29 网址 https blog csdn net weixin 44742824 article details 114981905 目录 一

热门标签