第二章：线性表

数据结构第二章#线性表，涵盖了链表的多种类型、基本操作以及相关代码示例等，能够帮助学习者系统地掌握链表的概念、类型和操作方法。

第二章

• 线性表
  • 定义
  • 基本操作
    • 初，销，空，度，获，定，插，删，遍
  • 存储结构
    • 1、结构（顺序存储／链式存储） 2、别名 3、存储 4、定义 5、元素 6、密度大小 7、空间利用率 8、占用空间大小 9、分配空间形式 10、结点之间关系 11、插入删除效率 12、访问元素效率 13、时间复杂度 14、第i个元素地址
• 顺序表基本操作
  • ①初始化
    • if（L.elem＝＝NULL）return error； L.length＝＝0；
  • ②获取元素
    • if（i＜1｜｜i＞L.length）return error； e＝L.elem[i-1]；
  • ③定位操作
    • if（i＜1｜｜i＞L.length）return error； for（j＝0；j＜L.length；j++） if（L.elem[j]＝＝e）return（j+1）；
  • ④插入操作
    • if（i＜1｜｜i＞L.length+1）return error； for（j＝L.length；j＞＝i；j--） L.elem[j]＝L.elem[j-1]； L.elem[i-1]＝e； L.length++；
  • ⑤删除操作
    • if（i＜1｜｜i＞L.length）return error； L.elem[i-1]＝e； for（j＝i；j＜L.length；j++） L.elem[j-1]＝L.elem[j]； L.length--；
  • ⑥遍历操作
    • if（i＜1｜｜i＞L.length）return error； for（j＝0；j＜L.length；j++） printf（L.elem[j]）
  • ⑦归并操作
• 单链表基本操作
  • ①初始化。
  • ②遍历操作
  • ③获取元素操作。
  • ④插入操作。
  • ⑤删除操作。
• 双向链表
  • 密度更小。
  • 前驱后继。
    • p→prior（直接前驱）
    • p→next（直接后继）
  • 三块内容。
    • prior
    • data
    • next
• 循环链表
  • 特点
  • 如何找某结点直接前驱
  • 判空
  • 判指向尾结点
• 双向循环链表
  • 判空
  • 判指向尾结点