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实现采用了如下的策略：
/*Thisover-allocatesproportionaltothelistsize,makingroom
*foradditionalgrowth.Theover-allocationismild,butis
*enoughtogivelinear-timeamortizedbehavioroveralong
*sequenceofappends()inthepresenceofapoorly-performing
*systemrealloc().
*Thegrowthpatternis:0,4,8,16,25,35,46,58,72,88,...
*/
new_allocated=(newsize>>3)+(newsize<9?3:6);
/*checkforintegeroverflow*/
if(new_allocated>PY_SIZE_MAX-newsize){
PyErr_NoMemory();
return-1;
}else{
new_allocated+=newsize;
}
python顺序表增删查实现
classshunxubiao:
def__init__(self,length):#length表示顺序表的长度，决定此顺序表最多存储多少元素
self.length=length
self.data=[]#data表示顺序表内容
self.biao=-1#元素下标
defweikong(self):#判断这个顺序表是否是空的
ifself.biao==-1:
returnTrue
else:
returnFalse
defmande(self):#判断此顺序表是否是满的
ifself.biao+1==self.length:
returnTrue
else:
returnFalse
defqingkong(self):
ifnotself.weikong():
self.data=[]
self.biao=-1
defgeshu(self):
returnself.biao+1
defchazhao(self,x):#知道下标查找元素
returnself.data[x]
defchazhao1(self,x):#知道元素查找下标
ifself.weikong():
print('表为空')
return-1
foriinrange(self.biao+1):
ifself.data[i]==x:
returni
break
print('查找的元素不存在')
defbiaoweijia(self,x):#给顺序表表尾加一个元素
ifself.mande():
print('biaoyiman')
else:
self.data.append(x)
self.biao+=1
defcharu(self,index,x):#想顺序表的index位置插入x元素
ifself.mande():
print('biayiman')
elifindex<0orindex>self.biao-1:
print('bunengcharu')
else:
foriinrange(self.biao,index-1):
self.data[i+1]=self.data[i]
self.data[index-1]=x
self.biao+=1
defshanchu(self,x):#删除指定元素x
ifself.weikong():#判断是不是空表
print('kongde,bunengshanchu')
index=-1#用index来找x的位置
foriin(self.data):
index+=1
ifi==x:
break
foriinrange(index,self.biao-1):#把x元素之后的元素都向前推进一格
self.data[i]=self.data[i+1]
self.biao-=1
c=shunxubiao(6)
c.data=[2,4,5,6]
c.biao=3
c.weikong()
print(c.chazhao(2))#知道尾标2查找元素
print(c.chazhao1(4))#知道元素查找尾标
c.biaoweijia(7)#给表尾加元素
print(c.data)
print(c.biao)
c.charu(3,9)
print(c.data)
print(c.biao)
c.shanchu(7)
print(c.data)
print(c.biao)
输出结果：
[2,4,5,6,7]4[2,4,5,6,7]5[2,4,5,6,7]4
思考：为什么没有把9添加进去，也没有把7删除掉
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。