线性表概念

基本概念

前驱:逻辑上前一个结点

后继:逻辑上后一个结点

线性表特点:

  • 存在唯一一个被称为第一个元素的数据元素
  • 存在唯一一个被称为最后一个元素的数据元素
  • 除开第一个数据元素,其他数据元素均只有一个前驱
  • 除开最后一个数据元素,其他数据元素均只有一个后继

线性表:n个数据元素有限序列

线性表顾名思义,‘’用线穿在一起的表‘’,从开始到结束,one by one;

如单链表

顺序存储结构和链式存储结构

从逻辑上看线性表的数据元素之间是“一对一”关系,从存储方式上看分为了顺序存储和链式存储

借用网上的图地址就能很好的看出它们得到区别:

顺序存储是连续的内存空间,链式存储并非一定要在连续内存空间

操作对比

操作 顺序存储结构 链式存储结构
创建 简单,申请一段连续内存 较简单,需定义结点等
增加 新建一段足够的连续内存,把旧数组存入 方便,通过指针连接新的添加数据
删除 把要删除的数据后面的数据前移覆盖 修改要删除的链表数据的前一个的变量的指针
修改 通过索引修改数据 遍历数组修改
查询 通过索引查找,速度快 遍历数组查询,速度较慢

注:这里有两种操作,头插法和尾插法,其实就是存储的顺序不同;头插法是后来的数据从头部插入,尾插法是后来的数据插到尾节点后;其实没有什么不同,不必纠结选哪种,就好像吃鸡蛋从大头或小头打一样

如果它们同时插入12345(示例Graphviz 使用的bot语言)

头插法

1
2
3
4
5
6
7
digraph example {
node [shape=record];
struct1 [label="<head> head | <tail>5 | 4 | ... | 1"];
6 -> struct1:tail;
struct1:head ->struct1:tail[style=dotted,]
struct1:head ->6
}

尾插法

1
2
3
4
5
6
7
digraph example {
node [shape=record];
struct1 [label="<head> head | 1 | 2 | ... | <tail>5"];
struct1:tail -> last[style=dotted];
struct1:tail -> 6;
6 -> last;
}