1、线性表简介
在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用。最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。我们将其抽象为线性表。
根据线性表的实际存储方式，分为两种实现模型：
- 顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
- 链表，将元素存放在通过链接构造起来的一系列存储块中。
2、顺序表怎样存储
下面我们将着重于顺序表。
还记的上一节的内存吗？
顺序表，作为一种存储结构，他需要在内存中申请空间进行存储，而它的特点就是必须要连续存储，也就是要拿出连号的‘柜子’进行存储，那么虽然内存有很多存储空间，但在其连续的空间内，可能有局部内存已经被其他东西占用，
| 0x03 | 0x04 | XXXX |
| 0x06 | 0x07 | 0x08 |
| XXXX | 0x10 | 0x11 |
假设我们拿出了03、04两个柜子进行存储，但是我们现在需要三个柜子来存储，而05的位置已经被占用，这时候，我们就要吧03、04柜子里的东西重新拿出来，再找一个三个连续的柜子放进去，比如06~08的位置，此时，如果我们又要存储别的东西，就又要重新找满足要求的连续的“柜子”。这就是顺序表的存储特性，不过为了避免经常“搬迁”，采用一中策略：提前开辟更多的位置来等待你存储，如果满了，那么就再去新开辟二倍的空间，满了再二倍，当然也会有个界限，否则就造成空间浪费了。
3、从0开始
| 0x03 | 1 | 0x04 | 2 |
| 0x05 | 3 | 0x06 | 4 |
li = [1, 2, 3, 4]
假设我们在一块连续的位置存储了数组li，那么取li[0]的时候, 就是先找到li所在的地址Ox03, 然后从这个地址读取4个字节(因为是整型), 如果是取li[3], 也是先找到li所在的地址Ox03,再往后跳过三个数据类型字节的位置, li[3] = Ox03 + 3*4Btye所以li[0]的**0 **的意思就是偏移量,所以数据是从零开始。
4、元素外置的顺序表
上面介绍的是基本的顺序表，就是存储的空间里都是类型相同的数据，那么你可能会问了，明明在Python中数组里存储的可以是任何类型的数据。这时候，我们就要寄出元素外置的顺序表了，这是个什么意思呢？其实这种存储不同类型数据的数组，其本身并没有把那些数据存储在自己的空间里，而是把这些数据对应的地址存在了自己的空间里，这样自己空间里还是类型一致的数据。
假如还是上面的那块地址，
| 0x03 | 0x10 | 0x04 | 0x31 |
| 0x05 | 0x52 | 0x06 | 0x43 |
这次在这里存储的是四个内存地址，而这些地址又对应相应的数据。
| 0x10 | ‘abb’ | 0x31 | 233 |
| 0x52 | {1, 2} | 0x43 | {'ha':'ho'} |
这时候我们在访问li[0]的时候将进行已下操作:
首先找到li所对应的地址Ox03, 再通过这个地址存储的地址Ox10 找到数据'abb', 这种存储地址的地址空间连续称作数据外置表, 可以通过列表存储不同类型的数据。
5、顺序表的实现
这里Python已经内置，但我们来考虑自己如何实现顺序表。
顺序表的两种基本实现方式
除了需要数据部分, 还需要表头信息用来存储表的大小以及已存储数据量。
a> 一体式结构：把表头信息和数据区连续存储
b> 分离式结构：把表的大小与已存储量以及存储地址放到一个地方, 地址指向另一块存储位置
优劣问题,数据存储问题:
连续: 读取方便, 当存储数据超过预先支配的大小, 那就需要重新申请一块连续空间, 进行数据搬迁, 释放老的空间, 表头也需要改变, 起始地址就会改变。
分离: 间接读取,当存储数据超过预先支配的大小, 只需要改变存储的地址, 并不需要改变表头的位置。
当存储空间不足的时候，扩充带来的问题: 扩充预留多少大小。
下面有两种解决策略。
两种策略:
1> 每次申请扩充固定数目的位置, 每次都扩充10个空间,
特点: 节省空间, 但是扩充操作频繁, 操作次数多
2> 每次申请都扩充倍数, 4->8->16->32
特点: 空间换取时间
允许扩充的顺序表叫做动态顺序表, 位置不够了可以取扩充位置
6、顺序表操作:
增加元素:
a>表尾端加入元素
b>非保序的元素插入
c>保序的元素插入
a>O(1)
b>直接把需求位置的数据放到尾端, 再把数据放入改位置,不常见, O(1)
c>O(n), 需要把所有数据往后移一位, 才能在空位加入元素
删除元素:
a>删除表尾元素 O(1)
b>非保序元素删除 O(1) 删除元素, 把末尾填入空位
c>保序删除 O(n) 删除元素在把每位上移
7、Python中的顺序表：list和tuple
a>按下表位置索引：复杂度O(1)
b>允许加入任意元素, 表对象标识(id地址)不变：表头和数据区分离式存储
c>可以存储不同类型的数据：元素外置方式
扩充策略:
建立空表(或很小的表), 系统分配一块能容纳8个元素的存储区, 进行插入时, 如果存储器满了, 存储区就换一块4倍大的存储区, 但是此时表已经很大(阀值50000),则改变策略,采用加一倍的方法, 避免出现过多的空闲位置
小结
1、顺序表属于线性表的一种。
2、从0开始。
3、存储同样类型的数据。不同数据是如何存储的？
4、怎么构造的？都有什么优劣？
5、添加和删除元素的复杂度？
网友评论