数据结构和算法-3-顺序表

「爱情、让人受尽委屈。」 2022-01-21 22:25 182阅读 0赞

这篇来学习下顺序表和顺序表在内存中的结构和顺序表的简单操作。顺序表是其他封装的数据结构的基础，了解这个之后，我们开始来学习常见数据结构。

**1.顺序表和链表的引出**

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量纪录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化。（可以增加或删除元素）

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列。用元素在序列里的位置和顺序，表示实际应用中某种有意义的信息，或者表示数据之间的某种关系。

这样一组序列元素的组织形式，我们可ui将其抽象为**线性表**。一个线性表是某类元素的一个结合，还纪录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更赋值的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：  
顺序表：将元素顺序地存放在一块连续的存储区里，元素间的关系由它们的存储顺序自然表示。  
链表：将元素存放在通过链接构造起来的一系列存储快中。

**2.图解顺序表**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

图a表示顺序表的借本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc（e0）加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得。  
Loc(ei) = Loc(e0) + c\*i

所以，访问指定元素时无需从头遍历，通过计算变可以或者对应地址，其时间复杂度为O(1)

如果元素大小不统一，则必须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需要的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

简单可以这样理解（java）：

图a就是存储例如 1 3 5 7 这样的int类型的数据，每个int类型默认是4 个字节，每个字节有8位。知道1（第一个元素）的存储位置，很快可以根据公司计算出后面5这个元素的位置，这里c就等于4.

图b，就是我们存储一些自定义的高级对象，例如有一个用户对象User类，里面有用户id,username,password,email,birthday等信息。图b实际上顺序表存储是每一个元素对应地址信息，上面说的链接，其实就是java中的内存地址，指针指向实际存储元素的地址。

**3.元素存储区扩充**

若将数据区更好为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有  
使用这个表的地方都不必修改。扩充的两种策略：  
1）每次扩充增加指定数目的存储位置，如每次扩充增加10个元素位置，这种策略称为线性增长  
特点：节省空间，但是扩充操作频繁，操作次数多。（以时间换取空间）

2）每次扩充容量加倍，如每次扩充增加一倍存储空间。  
特点：减少扩充操作的执行次数，但可能会浪费空间资源，以空间换取时间  
这两个方法，在当今时代，空间我们可以增加磁盘，内存，所以推荐以空间换取时间的做法。

**4.顺序表添加和删除元素实现原理**

增加元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70 1][]

python中的list和tuple两种类型采用顺序表的实现技术，tuple是不可变类型，即不可变的顺序表，因此不支持改变其内部状态的任何操作，其他与list性值类似。

**list的基本实现技术**  
python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各自操作中维持已有的元素的顺序而且具有以下特征：  
1.基于下标的高效元素访问和更新，时间复杂度应该是O(1)

2.允许任意加入元素，而且在不断加入元素的过程中，表对象的标识不变

在Python的官方实现中,list就是一种采用分离式技术实现的动态顺序表。这就是为什么使用list.apend(x)  
或list.insert()尾部插入）比在指定位置插入元素效率高的原因。

在python官方实现中，list实现采用如下策略：  
在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区；但如果此时的表已经很大（目前阀值5000），则改变策略，采用加一倍的方式，避免浪费空间。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220122/6b3963dfa4914586adfe5310cb1216f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70 1]: /images/20220122/919ad2ef90344406869eba4cb7d6a460.png