美文网首页
[数据结构]第二章线性表(3)——单链表

[数据结构]第二章线性表(3)——单链表

作者: 不会秃头的阿Kim | 来源:发表于2020-06-19 17:41 被阅读0次

    单链表

    image-20200618221439465 image-20200618221516210

    什么是单链表?

    image-20200618221658525

    单链表的定义

    image-20200618221959788

    别名

    image-20200618222203154 image-20200618222313544

    注释:或者可以理解为指向头节点的指针既可以表示整个单链表也可以表示头节点,为了便于区分才建议使用 typedef 进行重命名,以方便区别其不同的含义

    头插法建立单链表

    image-20200619095117732

    单链表的基本操作

    单链表的初始化

    不带头节点的单链表的初始化

    image-20200619095400757

    带头节点的单链表的初始化

    image-20200619095545238

    两者区别是什么?

    image-20200619095738329

    总结

    image-20200619095821536

    插入和删除

    image-20200619104612536

    插入

    按位序插入(带头节点的单链表)
    image-20200619105030154

    具体实现

    分析在表头插入

    image-20200619105401211

    分析为什么不能颠倒

    image-20200619105451377

    分析在表中插入

    image-20200619105800111

    分析在表尾插入

    image-20200619110039686

    分析插入位置超出表长

    image-20200619110159253

    总结

    image-20200619110309541
    按位插入(不带头节点)
    image-20200619110418752

    具体实现

    image-20200619110547637

    结论:不带头节点的单链表,写代码更不方便,除非特别声明,默认推荐使用带头节点的实现方式,还有要注意在考试中带头、不带头都有可能考察,注意审题。

    指定节点的后插操作
    image-20200619111032277

    指定节点的前插操作

    通过传入头指针实现前插

    image-20200619111607840

    先进行后插,然后交换前后数据,以此实现前插

    image-20200619111716141 image-20200619111814873

    删除

    带有头节点版本
    image-20200619111915877

    具体实现

    image-20200619135048885
    删除指定结点
    image-20200619135226089

    如果P是最后一个节点,咋办?

    只能从表头表头依次寻找前驱,时间复杂度O(n)

    image-20200619135401028

    单链表的局限性:无法逆向检索!!

    总结

    image-20200619135623242

    查找

    按位查找(带头节点)
    image-20200619152704151
    按值查找(带头节点)
    image-20200619153147639
    求表的长度(带头节点)
    image-20200619153411974

    总结

    image-20200619153525681

    单链表的建立方法

    image-20200619153742876

    PS:找不到对象就娶一个数据元素吧!哈哈

    尾插法

    第一种方法:

    image-20200619154012867

    问题:时间复杂度太高!!可以用一个指针记录最后一个数据元素的位置来优化时间。

    优化之后:

    image-20200619172815577

    头插法

    image-20200619172945304

    具体实现:

    image-20200619173800669

    总结

    image-20200619173925151

    相关文章

      网友评论

          本文标题:[数据结构]第二章线性表(3)——单链表

          本文链接:https://www.haomeiwen.com/subject/pwlbxktx.html