第二章线性表

数据结构的第二章有关线性表中的知识点。包含线性表的链式表达及实现、线性表的应用、线性表定义及特点、等等。

第二章线性表

• 2.1线性表定义及特点
  • 定义：由n（n>=0）个数据特性相同的元素构成的有序列表
    • 空表：线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表
  • 特点：非空线性表或线性结构
    • 1.存在唯一的一个被称为“第一个”的数据元素
    • 2.存在唯一的一个被称为“最后一个”的数据元素
    • 3.除第一个之外，结构中的每一个数据元素均只有一个前驱
    • 4.除最后一个之外，结构中的每个数据元素均只有一个后继
• 2.2案例
  • 一元多项式运算：例：p=(p1,p2,p3,...pn),q=(q1,q2.....qn) R=p1+q1,p2+q2......pn+qn:
  • 稀疏多项式的运算：n元多项式：pn(x)=p1xe1+p2xe2.....
  • 图书管理系统：实现需6个功能
    • 查找
    • 插入
    • 删除
    • 修改
    • 排序
    • 计数
• 2.3线性表的类型定义
  • InitList(&L):初始化线性表，构造一个新的线性表
  • DestroyList(&L):销毁线性表
  • ClearList(&L):L存在但无元素
  • ListEmpty(&L):判断其是否为空
  • ListLength(&L):求L得长度
  • GetElem(L,I,&e)：
    • 初始条件：i>=1&&i<=ListLength(L)
    • 操作结果：获取L中的指定元素位置
  • LocateElem(L,e):返回L中第一个值与e相同的元素在L的位置，若不存在，则返回0
  • PriorElem(L,cur_e,&pre_e):求前驱
  • NextElem(L,cur_e&next_e):求后继
  • ListInsert(&L,i,e):插入元素
  • ListDelete(&L,i)：删除元素
  • TraverseList(L)：遍历
• 2.4线性表的顺序表示和实现
  • 定义：使用一组地址连续的存储单元依次存储线性表的数据元素
  • 特点：逻辑上相邻的数据元素，其物理次序也相邻
  • 随机存取：线性表中任一数据元素都可随机存取，所以其存储结构为随机存取
  • 线性表中i+1和i元素之间关系满足：LOC(ai+1)=LOC(ai)+L
  • 第i个元素的存储位置：LOC=Lo+(i-1)*m m是所占空间大小
• 2.9小结
  • 带头结点的单链表L
    • 查找表头结点：L->next时间复杂度为O(1)
    • 查找尾结点：从L->next依次向后遍历，时间复杂度为O(n)
    • 查找结点*p的前驱结点：通过P->next无法找到其前驱
  • 带头结点仅设头指针L的循环单链表
    • 查找表头结点：L->next时间复杂度为O(1)
    • 查找表尾结点：从L->next依次向后遍历，时间复杂度为O(n)
    • 查找结点*p的前驱结点：通过P->next可以找到前驱结点时间复杂度为O(n)
  • 带头结点仅设尾指针R的循环单链表
    • 查找表头结点：R->next时间复杂度为O(1)
    • 查找表尾结点：R，时间复杂度为O(1)
    • 查找结点*p的前驱结点：通过P->next可以找到其前驱时间复杂度为O(n)
  • 带头结点的双向循环链表
    • 查找表头结点：L->next时间复杂度为O(1)
    • 查找表尾结点：L->prior时间复杂度为O(1)
    • 查找结点*p的前驱结点：P->prior时间复杂度为O(1)
• 2.7线性表的应用
  • 线性表的合并：例如集合的并
  • 有序表的合并
    • 顺序有序表的合并
      • 创建一个表长为m+n的空表LC
      • 指针pc初始化，指向LC中第一个元素
      • 指针pa和pb初始化，分别指向LA,LB的第一个元素
      • 当指针pa，pb均未到达相应表尾，依次比较papb所指向的元素，从LA或LB中摘取元素值较小的结点插入到LC的最后
      • 如果pb已到LB的表尾，依次将LA的剩余元素插入LC的最后
      • 如果pa已到LA的表尾，依次将LB剩余的元素插入LC的最后
    • 链式有序表的合并
      • 指针papb初始化，分别指向LALB的第一个结点
      • LC的结点取值为LA的头结点
      • 指针pc初始化。指向LC的头结点
      • 当指针PAPB均未到达结尾，依次比较papb所指向的元素值，从LA或LB中摘取元素值较小的结点插入LC的最后
      • 将非空表的剩余段插入到pc所指结点之后
      • 释放LB的头结点
• 2.6顺序表和链表的比较
  • 空间性能的比较
    • 存储空间
      • 顺序表：预先分配，会导致空间闲置或溢出现象
      • 链表：动态分配，不会出现溢出或空闲状态
    • 存储密度
      • 顺序表：不用为表示结点间逻辑关系而增加额外开销，存储密度为1
      • 链表：需要借助指针来表示元素间的逻辑关系
  • 时间性能的比较
    • 存取元素
      • 顺序表：随机存取，按位置访问元素的时间复杂度为O(1)
      • 链表：顺序存取，按位置访问元素的时间复杂度为O(n)
    • 插入，删除
      • 顺序表：平均移动约表中一半元素，时间复杂度为O(n)
      • 链表：不需移动元素，确定插入删除位置后，时间复杂度为O(1)
  • 适用情况
    • 顺序表
      • 1.表长变化不大，且能事先确定变化范围
      • 2.很少进行插入或删除操作。经常按元素位置访问数据元素
    • 链表
      • 1.长度变化较大
      • 2.频繁进行插入，删除操作
• 存储密度=数据元素本身占用的存储量/结点结构占用的存储量
• 2.5线性表的链式表达及实现
  • 特点：用一组任意的存储单元存储线性表的数据元素（可以是连续，也可以是不连续）
  • 定义：例如（a1,a2....an）的链式存储结构，又由于此链表的每个结点中只包含一个指针域（n个结点链结成一个链表）
  • 结点：数据域和指针域组成数据元素ai的存储映像
    • 数据域：存储数据元素信息的域
    • 指针域：存储直接后继存储位置的域
  • 首元结点:链表中存储第一个数据元素a1的结点
  • 头结点：是在首元结点之前附设的一个结点，其指针域指向首元结点
    • 其数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息
    • 作用：1.便于首元结点处理2.便于空表与非空表的统一处理
  • 头指针：是指向链表中第一个结点的指针
    • 若链表设有头结点，则头指针所指结点为线性表的头结点
    • 若链表没有设头结点，则头指针所指结点为该线性表的首元结点
  • 清空与销毁的区别
    • 销毁没有头结点
    • 清除还省头结点
• 单链表，双链表，循环链表的比较
• 双向链表
  • 为克服单链表的单向性缺点，可利用双向链表
• 循环链表：
  • 定义：是另一种形式的链式存储结构
  • 特点：表中最后一个结点的指针域指向头结点
• 单链表基本操作实现
  • 初始化
  • 取值
  • 查找
  • 插入
  • 删除
  • 单链表的删除
  • 创建单链表
    • 前插法
    • 尾插法
• 顺序表中基本操作的实现
  • 初始化
  • 取值
  • 查找
  • 插入
  • 删除
  • 销毁
  • 求线性表的长度