数据结构第二章：顺序表

基本顺序表

基本数据 int = 1,2,3 对应 3 个存储单元，

但是他们是连续的整数，那么在存储的时候就可以将它们连续储存。

按此顺序存放的数据，其地址也是连续的，且每个位置存储数据存储的数据大小也是一样的。

要想获取往后元素的位置，只需要按照第一个为参考系进行一次运算得出。

这就是顺序表。

此时 list 的存储地址，指向的就是第一个元素的地址；在读取 list[2] 的时候，他的地址是通过 0x01 进行推算的。例如：2 的位置是由 0x01+4Byte = 0x05 得出，4Byte 是因为存储的是 int 占位 4 字节。

对于任意 list[n] = 0x01 +4n

假如，list = [1, “ab”]，字符串”ab”与 整数 1 所占位的存储空间大小不一样，那么就不能够使用上述公式来计算出 list[n] 的存储位置。但是我们发现，每个元素对应的地址都是固定字节的，是不变的、可以计算得出的，于是这个时候，我们可以把元素进行外置，将存储地址存入表中，见右图。

例如：list=[12,”ab”,1.324,999]，在存储时，将每个元素随机存储一个物理地址，然后把四个存储地址变成一个顺序表，这样的话顺序表中的数据地址就是连续的了。

这个时候，去索引 list[2] 的读取步骤就是：

0x200 + 4x2 = 0x208—–>0x007—–>1.324

在 python 语言种已经对该顺序表进行封装了，就不用考虑用 python 实现了。

顺序表的结构与实现

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的** 容量** 和当前表中已有的** 元素个数** 两项。

两种实现方式

图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

在构建顺序表的时候，要对存储空间大小和元素数量有一个预估。

一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略：

• 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。
  • 特点：节省空间，但是扩充操作频繁，操作次数多。
• 每次扩充容量加倍，如每次扩充增加一倍存储空间。
  • 特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

顺序表的操作

增加元素

a. 尾端加入元素，时间复杂度为O(1)；

b. 非保序的加入元素（不常见），时间复杂度为O(1)；

c. 保序的元素加入，时间复杂度为O(n)。

删除元素

a. 删除表尾元素，时间复杂度为O(1)；

b. 非保序的元素删除（不常见），时间复杂度为O(1)；

c. 保序的元素删除，时间复杂度为O(n)。