当前位置：首页 > news >正文

数据结构万字总结（超级详细）第二章——线性表

news 来源：原创 2024/4/27 9:12:37

线性表

定义

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列

特点

除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

操作

初始化、增、删、查、改、销毁

元素的下标与位序

下标从0开始，位序从1开始

分类（根据存储结构来划分的）

顺序表

顺序存储

定义

用顺序存储的方式实现线性表。顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
实现
- 静态分配（数组实现）
  
  扩展容量不方便，缺乏灵活性、但是内存管理简单，不存在内存泄漏的问题（内存泄漏——只申请内存不释放内存）
- 动态分配（malloc）
  
  空间利用灵活，但是内存管理复杂
特点
- 优点
  - 随机访问，即可以在 O(1) 时间内找到第 i 个元素
  - 存储密度高
- 缺点
  - 扩展容量不方便，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高
  - 插入、删除操作不方便，需要移动大量的元素
- 顺序存储、随机存取
操作
- 插入：移动元素（n/2）次
- 删除：移动元素（n-1）/ 2次
- 查找：比较次数：（n+1）/ 2
- 查找最多,即(n+1)，记住，删除肯定是要小的，即(n-1)，而插入是增多，即n

链表

链式存储

单链表
- 定义
  
  用链式存储实现的线性表，链式存储：逻辑上相邻但是物理存储结构上不相邻，每个结点除了存放数据元素外，还要存储指向下一个节点的指针
- 实现
  
  带头结点有什么好处？
  - 带头结点
    
    写代码更方便
  - 不带头结点
    
    写代码更麻烦，对第一个结点的处理需要使用不同的代码逻辑。比如判空操作
- 特点
  - 优点
    - 扩展容量方便
    - 插入、删除操作很方便、不需要移动大量的元素
  - 缺点：
    - 只能顺序访问
    - 存储密度低
  - 随机存储、顺序存取
- 操作：插入、删除、查找。三种操作的复杂度都为O(n)
- 建立
  - 尾插法
  - 头插法：可用于实现单链表逆置
双链表，如下：
定义
- 由于单链表不能逆向检索，因此出现了双向链表。
- 实现
- 特点
  - 存储密度更低，不具备随机存取特性
- 操作
  - 插入
    
    注意新插入结点、前驱结点、后继结点的指针修改边界情况∶新插入结点在最后一个位置，需特殊处理
  - 删除
    
    注意删除结点的前驱结点、后继结点的指针修改边界情况︰如果被删除结点是最后一个数据结点，需特殊处理
循环链表
- 循环单链表，如下：
- 表尾结点的next指针指向头结点
- 循环双链表
- 表头结点的 prior 指向表尾结点；表尾结点的 next 指向头结点
- 特点：存储密度低、插入、删除操作方便。相比与普通单链表和普通双向链表，循环链表可以从任意结点出发遍历整个链表，而普通链表只能从头结点开始遍历
静态链表
- 定义
  
  用数组的方式实现的链表
- 实现：每个结点的next存放下一个结点的下标
- 优点
  - 增、删操作不需要大量移动元素
- 缺点
  - 不能随机存取，容量固定不可变
- 适用场景：操作系统文件分配表