线性表的定义

线性表的逻辑结构

  1. 线性表： 钱性表是具有相同类型的 n(n > 0 ) 个数据元素的有限序列 记作: L=(a1,a2,…,an) a1──首元素 an──尾元素 ，注意线性表既可以是数组这样的顺序表也可以是链表但不能是树。
  2. 表的长度(表长)──线性表中数据元素的数目。
  3. 空表──不含数据元素的线性表

线性表的特征
对于 L=(a1,a2,…,ai-1 , ai,ai+1,…,an)

  1. ai-1在ai之前,称ai-1是ai的直接前驱 (1＜i≤n)
  2. ai+1在ai之后,称ai+1是ai的直接后继 (1≤i＜n)
  3. a1没有前驱
  4. an没有后继
  5. ai(1＜i＜n)有且仅有一个直接前驱和一个直接后继

    线性表的顺序表示（顺序存储结构：数组等）

    顺序分配： 将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中, 这种分配方式称为顺序分 配或顺序映像。由此得到的存储结构称为顺序存储结构或向量(一维数组）。

优点：

  • (1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快； 随机存取（直接存取,Random Access）指的是当存储器中的数据被读取或写入时，所需要的时间与该数据所在的物理地址无关。
  • (2)结构简单，逻辑上相邻的元素在物理上也是相邻的；
  • (3)不使用指针，节省存储空间。

缺点

  • (1)插入和删除元素要移动大量元素，消耗大量时间；
  • (2)需要一个连续的存储空间；
  • (3)插入元素可能发生“溢出”；
  • (4)自由区中的存储空间不能被其它数据占用(共享)

    线性表的链式存储结构（链表等）

    单链表

image.png

image.png
插入算法
1.尾插法
image.png

2.头插法
image.png

3.中间插入节点，修改next指针，从后往前的顺序按节点修改next的指向
image.png

image.png
删除算法

image.png

image.png

image.png

image.png

静态链表

image.png

循环链表

带有head指针
image.png

带有tail指针
image.png

双向链表

image.png

双向循环链表

image.png

image.png

image.png