土豆味番茄酱


个人记录的地方

线性表概念

2020-02-25 分类于 作者 xybz

基本概念

前驱：逻辑上前一个结点

后继：逻辑上后一个结点

线性表特点：

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

线性表：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;    
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2020-02-25