Skip to main content

第二章

2.5.1 单链表的定义和表示​

image-20210927120239466

2.5.2 单链表上基本操作的实现​

  • 单链表的初始化
    1. 构造一个空表
      1. 生成头部节点，使用变量存储期内存地址（指针）
      2. 将头部节点的指针和数据设置为空

  • 链表的非空判断

    • 判断头部节点的指针是否为空

  • 链表的销毁

    • 使用一个p变量存储头部节点L的地址
    • L节点重新指向下一个数据节点
    • 释放P变量的内存数据，循环上述步骤把整个链表清空

  • 链表的清空
  • 计算链表的表长
  • 取链表中某个元素n
    • 添加一个 i 变量，没查找一个元素i+1
    • 当i=n的时候，返回该元素数据
    • 错误处理，n不存在时的处理

2.5 线性表的链式表示和实现​

如何表示空表​

  • 无头结点：头指针为空时表示空表
  • 有头节点：当头节点的指针域为空时表示空表

头结点​

  • 便于首页节点的处理
  • 头结点由数据域和指针域组成，数据域为空，可以自由使用

链表的存储特点​

  • 顺序存取法
    • 要取任何元素，必须顺序读取该元素前面的所有元素，才能找到目标元素，时间复杂度是 O(n)