线性表

数据结构的第二章的线性表笔记，包括线性表及其逻辑结构、顺序存储结构、链式存储结构三部分内容，需要的收藏吧。

线性表

• 2.1 线性表的定义及逻辑结构
  • 线性表的定义
    • 线性表是由n(n>=0)个数据类型相同的数据元素a1,a2,.....,ai-1,ai,...,an组成的有限序列
  • 线性表的基本操作
    • (1)初始化InitList(L)：构造一个空的线性表
    • (2)线性表判空EmptyList(L)：如果线性表L为空则返回真值，否则返回假值
    • (3)取长度LengtnList(L)：返回线性表中所含元素的个数
    • (4)取元素函数GetList(L)：若1<=i<=LengthList(L),返回线性表L中第i个元素的值或地址；否则，返回NULL
    • (5)按值查找LocatList(L,x)
    • (6)插入操作InsertList(L,i,x)
    • (7)删除操作DeleteList(L,i)
• 2.2 线性表的顺序存储结构
  • 顺序表
  • 顺序表上插入与删除操作的实现
    • 插入运算InsertList(L,i,x)
      • 定义
      • 步骤
        • 1.将ai~an顺序向下移动，为新元素让出位置
        • 2.将x置入空出的第i个位置
        • 3.修改last指针(相当于修改表长)，使之仍指向最后一个元素
      • 注意
        • 表长
        • 数据的移动方向
    • 删除运算DeleteList(L,i)
      • 定义
      • 步骤
        • 1.将ai+1~an顺序向上移动
        • 2.修改last指针(相当于修改表长)使之仍指向最后一个元素
      • 注意
        • 表空不能做删除
        • 注意i的取值
        • 数据的移动方向
  • 顺序表应用举例
    • 线性表的合并
    • 合并且排序
• 2.4 顺序表和链表的比较
  • 顺序表的优缺点
  • 链表的优缺点
• 2.3 线性表的链式存储结构
  • 1.单链表
    • 定义
    • 头指针
    • 头节点
  • 2.单链表上基本运算的实现
    • 1.建立单链表
      • 头插法
      • 尾插法
    • 2.求单链表长度的操作
    • 3.查找操作
    • 4.单链表的插入操作
    • 5.删除操作
  • 3.循环单链表
  • 4.静态链表
    • 1.初始化
    • 2.分配结点
    • 3.结点回收
    • 4.前插操作
    • 5.删除
  • 5.双向链表
    • 1.双向链表中结点的插入
    • 2.双向链表中结点的删除
  • 6.链表应用举例
    • 1.求两个集合的差
    • 2.两个循环单链表的合并