第二章 线性表

数据结构第二章思维导图，汇总了概念及运算、顺序存储、链式存储、顺序表和链表比较的知识，欢迎大家学习。

第二章 线性表

• 概念及运算
  • 定义
    • 由n（n>=0）个类型相同的数据元素a1,a2,a3,...,组成的有限序列
  • 特点
    • （1）同一性（2）有穷性（3）有序性
  • 基本操作
    • （1）InitearList(L)（2）Destroy（L）（3）ClearList（L）（4）EmptyList（L）（5）ListLength（L）（6）Locate（L,e）（7）GetData（L,i）(8)InsList(L,i,e)(9)DelList(L,i,&e)
• 顺序存储
  • 顺序表
    • 定义：采用顺序存储结构的线性表
    • 优点：(1)存储密度高，无需为了表示元素同的逻情关系而增加额外的辅助空间；(2)按序号可能的消同。
    • 缺点：(1)插入删除需移动大量元素：(2)霸占用连续内存空间；(3)静志分配。
    • 基本运算
      • 1.查找操作 2.插入操作 3.删除操作
• 链式存储
  • 单链表
    • 优点：(1)插入删除不需要移动元素；(2)动态分配；(3)元素占摇内存可不连续。
    • （1）数据域用来存储结点的值（2）指针域用来存储数据元素的直接后继的地址
    • 缺点：（1）存储国度低，需要额外指针域空间表示元素闻的逻错关系；(2)无法随机访问。
    • 建表：1.头插法建表 2.尾插法建表
    • 查找：1.按序号查找 2.按值查找
  • 双向链表
    • 每个结点两个指针域，分别指向读结点的前驱和嘴继结点。
  • 循环链表
    • 尾结点的指针城指向头结点或首元素结点，构成一个环。
  • 静态链表（借助数组实现）
    • 用一组连续的空间来存放元素，但元素是按链表形式组织的，需要额外空间来表示它们的逻相关系。
• 顺序表和链表比较
  • 基于空间的考虑
  • 基于时间的考虑
  • 基于语言的考虑