Python数据结构与算法DAY1
Python数据结构与算法DAY1
顺序表
- 顺序表的基本形式
- 元素内置的顺序表
- 元素外置的顺序表
- 顺序表的结构
一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。 - 顺序表的两种基本实现方式
- 一体式结构
存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。
一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。 - 分离式结构
表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。
- 元素存储区替换
一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。
分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。 - 元素存储区的扩充
- 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。
- 特点：节省空间，但是扩充操作频繁，操作次数多。
- 每次扩充容量加倍，如每次扩充增加一倍存储空间。
- 特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。
- 顺序表的操作
-
增加元素（以增加元素111为例）
【1】尾端加入元素，时间复杂度为O(1)
【2】非保序的加入元素（不常见），时间复杂度为O(1)
【3】保序的元素加入，时间复杂度为O(n) -
删除元素（以删除元素111为例）
【1】删除表尾元素，时间复杂度为O(1)
【2】非保序的元素删除（不常见），时间复杂度为O(1)
【3】保序的元素删除，时间复杂度为O(n) -
在Python的官方实现中，list是一种采用分离式技术实现的动态顺序表。