Python中顺序表原理与实现方法详解

189 浏览量更新于2023-05-04 评论收藏 64KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Python中顺序表原理与实现方法详解中顺序表原理与实现方法详解

本文实例讲述了Python中顺序表原理与实现方法。分享给大家供大家参考，具体如下：

Python中的顺序表中的顺序表

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

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

list的基本实现技术的基本实现技术

Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保

序），而且还具有以下行为特征：

基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)；

为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。

允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。

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

在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x) （或

list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

《数据结构与算法 Python语言描述》裘宗燕著

在Python的官方实现中，list实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元

素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的

表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出

现过多空闲的存储位置。

在Python的官方实现中，list实现采用了如下的策略：

/* This over-allocates proportional to the list size, making room

* for additional growth. The over-allocation is mild, but is

* enough to give linear-time amortized behavior over a long

* sequence of appends() in the presence of a poorly-performing

* system realloc().

* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */

if (new_allocated > PY_SIZE_MAX - newsize) {

PyErr_NoMemory();

return -1;

} else {

new_allocated += newsize;

}

python顺序表增删查实现顺序表增删查实现

class shunxubiao:

def __init__(self,length):#length表示顺序表的长度，决定此顺序表最多存储多少元素

self.length=length

self.data=[] #data表示顺序表内容

self.biao=-1 #元素下标

def weikong(self):#判断这个顺序表是否是空的

if self.biao==-1:

return True

else:

return False

def mande(self):#判断此顺序表是否是满的

if self.biao+1==self.length:

return True

else:

return False

def qingkong(self):

if not self.weikong():

self.data=[] self.biao=-1

def geshu(self):

return self.biao+1

def chazhao(self,x):#知道下标查找元素

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38530211

粉丝: 1
资源: 970

会员权益专享

Python中顺序表原理与实现方法详解

评论0

会员权益专享

最新资源

Python中顺序表原理与实现方法详解

评论0

什么是Python中的顺序表

Python单链表原理与实现方法详解

python数据结构与算法详解与源码

python实现顺序表的基本操作

顺序表的python

python打印顺序表

Python中SL顺序表的基本操作

python顺序表的基本操作

在Example类中，利用顺序表类实现以下功能：构建顺序表，输出顺序表长度，对顺序表中某元素进行查找

用python采用顺序表存储学生成绩

顺序表中查找元素python

python设计整数顺序表的基本运算程序

python顺序表的练习

python 学生顺序表

python 在顺序表{1，3，5，7，9}中删除最小值元素，并返回其位置完整代码

Python中的列表使用了分离式技术实现的动态顺序表

python 如何创建顺序表

创建顺序表python

python如何建立顺序表并输入数据

python实现 获取顺序表的最大元素，并输出最大元的位置。顺序表的创建、打印、求最大值等操作应以函数方式实现。

会员权益专享

最新资源

python实现获取顺序表的最大元素，并输出最大元的位置。顺序表的创建、打印、求最大值等操作应以函数方式实现。