171 python - 顺序表

简介: 171 python - 顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术,具有前面讨论的顺序表的所有性质。

tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类似。

1. list的基本实现技术

Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元素的顺序(即保序),而且还具有以下行为特征:

  • 基于下标(位置)的高效元素访问和更新,时间复杂度应该是O(1);
  • 为满足该特征,应该采用顺序表技术,表中元素保存在一块连续的存储区中。
  • 允许任意加入元素,而且在不断加入元素的过程中,表对象的标识(函数id得到的值)不变。

为满足该特征,就必须能更换元素存储区,并且为保证更换存储区时list对象的标识id不变,只能采用分离式实现技术。

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

在Python的官方实现中,list实现采用了如下的策略:在建立空表(或者很小的表)时,系统分配一块能容纳8个元素的存储区;在执行插入操作(insert或append)时,如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大(目前的阀值为50000),则改变策略,采用加一倍的方法。引入这种改变策略的方式,是为了避免出现过多空闲的存储位置。

目录
相关文章
|
6月前
|
存储 机器学习/深度学习 算法
【数据结构与算法】:手搓顺序表(Python篇)
【数据结构与算法】:手搓顺序表(Python篇)
|
算法 Python
python与算法:顺序表和链接表之间的相互转化
python与算法:顺序表和链接表之间的相互转化
85 0
|
存储 算法 Python
数据结构-顺序表的定义及python实现
数据结构-顺序表的定义及python实现
183 0
数据结构-顺序表的定义及python实现
|
算法 Python
Python高级语法3:方法解析顺序表MRO
Python高级语法3:方法解析顺序表MRO
149 0
|
存储 索引 Python
顺序表数据结构在python中的应用
数据结构不仅仅指的数据值在逻辑上的结构,更有在存储空间上的位置结构,顺序表,故名思意是有一定顺序的数据结构。 顺序表最基本模型如图: 对于基本布局顺序表而言,它存储相同单元大小并且在内存地址上连续的数据,逻辑地址是其元素的逻辑顺序,物理地址第一个元素的内存地址加上离第一个元素的距离,如:e1物理地址是l0,那么e2的物理地址是e1的地址加上e1所占用的大小c,以此类推,en的物理地址是l0+(n-1)*c。
18114 0
|
算法 Python 搜索推荐
python链表冒泡排序、二叉树顺序递归遍历、顺序表的快排
一、python实现链表冒泡排序 - 冒泡排序的概念:冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直至没有反序的记录为止。
1990 0
|
存储 算法 Python
Python数据结构与算法——顺序表
概念 在程序中,经常需要将一组(通常为同一个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等(例如,Python中的列表)。
1831 0
|
14天前
|
人工智能 数据可视化 数据挖掘
探索Python编程:从基础到高级
在这篇文章中,我们将一起深入探索Python编程的世界。无论你是初学者还是有经验的程序员,都可以从中获得新的知识和技能。我们将从Python的基础语法开始,然后逐步过渡到更复杂的主题,如面向对象编程、异常处理和模块使用。最后,我们将通过一些实际的代码示例,来展示如何应用这些知识解决实际问题。让我们一起开启Python编程的旅程吧!
|
13天前
|
存储 数据采集 人工智能
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。