Bo2SS

课程内容#

引言#

• 【基础数据结构】课程综述
  • 
  • 重点掌握红色！
• 三个等式
  • 程序 = 算法 + 数据结构
  • 程序设计 = 算法 + 数据结构 + 编程范式
  • 数据结构 = 结构定义 + 结构操作
• 通过算法与数据结构，使计算机合理利用资源，让计算资源更有价值

顺序表#

【功能更高级的数组】

结构定义#

• 空间连续，可以存储任意类型的相同元素
  • 顺序表里也可以存顺序表
• size：顺序表的空间大小
• length：已存储的元素个数
• data_type：存储的元素类型

结构操作#

• 插入
  • 
  • 👇👇👇
  • 
  • 不能空着插，必须连续
  • 插入位置后的所有元素向后移动一位
    • 从后开始移动，每个元素向后移动一位
  • 必须要改变的属性：length + 1
    • size 有可能需要改变，扩容请看下面
• 删除
  • 
  • 👇👇👇
  • 
  • 不是真的删除，而是告诉系统这个地址的存储区可以被占用、被覆盖
  • 将后面所有的元素整体向前移动一位
    • 相当于要删除的位置的值被覆写
    • 最后一个值怎么覆写？
      • 直接将 length - 1
      • 其实都可以自定义设计
  • 必须要改变的属性：length - 1
• ⭐添加扩容操作
  • 动态内存分配函数
    • malloc：只是开辟空间，值不确定。举例：开房没有保洁阿姨
    • calloc：开辟空间，并且初始化。举例：开房后有保洁阿姨打扫清理
    • realloc：重新开辟空间。举例：升级房型

​ void* realloc (void* ptr, size_t size); // 返回新开辟空间的首地址

3 种情况【realloc】

1. 先试探能不能在原地址后面直接加空间，空间首地址不变；如果不行，
2. 换个地址找找，申请空间，然后把原空间数据拷贝到新空间，并 free 掉原空间；如果不行，（自己可以设计减少扩容）
3. 就返回空地址，不清空当前地址

链表#

结构定义#

• 

• 程序内部 + 内存内部

  • 【程序内部】只暴露头指针
    • 头指针、小抓手、鸡妈妈：记录第一个结点的地址
    • 联想老鹰捉小鸡
  • 【内存内部】是连接的结点
    • 结点：数据域 + 指针域
    • 指针域
      • 最后一个结点的指针域为 NULL
      • 单向链表的指针域又名 “后继”；双向链表有 “前驱” 和 “后继”

• 与顺序表都属于顺序存储结构

  • 链表思维逻辑上连续，但物理上不一定连续

结构操作#

• 插入
  • 
  • ①走到待插入位置的前一个位置的结点 p
  • ②先将新的结点 x 的指针域指向待插入位置的结点 p.next
  • ③将 p 的指针域指向新的结点 x
  • 顺序不能变！否则可能引发内存泄漏（你想用已经用不了，但系统却以为你在用）
• 删除
  • 走到待删除结点位置的前一个位置
• 翻转
  • 方法一
    • 用一个新链表存，使用头插法
    • 不断在 index = 0 的位置插入结点
    • 不足：浪费空间，麻烦
  • 方法二
    • 原地翻转，用两个变量倒，也是头插法
    • 前提：每次操作不要造成内存泄漏
    • NULL 地址还是在最后面，不会翻转
• 代码演示见后

单向循环链表#

• head 永远记录的是尾结点的地址～

1. 对于需在 index = 0 插入结点的情况
   • 
   • 🆒当 head 记录的是尾结点时，直接在 head 指向的尾结点后插入即可
   • ❌如果 head 记录的还是首结点的地址，不好使，因为
     • 要找 index = 0 的结点的前一个结点，可能需要遍历完整个链表找到尾结点
     • 而不像单向链表那样，可以直接在 head 后、index = 0 结点前插入
2. 对于在尾部插入结点的情况
   • 
   • 需要修改 head 指向新的尾结点【8】！

代码演示#

顺序表#

• 初始化、销毁
  • 使用 malloc 开辟空间初始化该结构
  • 从结构里到外 free，再将指针置空
• 扩容操作
  • realloc 返回地址先赋给中间变量，避免返回 NULL 的情况，导致原数据迷失
  • realloc 成功后原地址空间自动被 free
  • 可设计折半减小的扩容空间，直到确实一点空间都不剩返回失败标志 0
  • 细节很多，详见注释
• 插入、删除
  • 注意不能操作的情况
  • 插入满员时，进行扩容操作
• 打印：人性化
• main 函数测试：使用 rand ()、神奇的取模操作 (得到数据、模拟各种样例、决定操作数)，记得 clear 空间

链表#

部分结果

• 

• 虚拟头结点，方便插入和删除第一个结点

  • 使用普通变量定义 head，❓考虑的是
    • 虚拟头结点比较固定，不需要随时 free
    • 普通变量比指针变量更稳定，没必要 malloc

思考点#

• ⭐初始化数据结构 [比如链表、链表结点] 时，为什么要动态开辟内存 [用 malloc 等]，而不是定义普通变量？
  • 首先，排除盲区：不是因为指针只能接受 malloc 返回的地址，指针也能指向普通变量
  • 关键：【malloc 申请的内存在堆空间，普通变量定义在栈空间 (在函数里面定义的)】
  • 栈空间：大小只有 8MB；出了函数 [作用域] 变量就被自动释放了
  • 堆空间：可分配大内存；变量生命周期长，一般需手动释放
• ❓虚拟头结点定义为普通变量和指针变量的区别
  • 个人理解，用指针变量，是为了接收 malloc 返回的地址
  • 而虚拟头结点，在这只是一个指示作用，不需要大空间，所以不需要 malloc，用普通变量即可

Tips#

• 学习编程不局限于语言

• 课后练习题

• 

课程速记#