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

Python  /  管理员 发布于 7年前   137

本文实例讲述了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):#知道下标查找元素    return self.data[x]  def chazhao1(self,x):#知道元素查找下标    if self.weikong():      print('表为空')      return -1    for i in range(self.biao+1):      if self.data[i]==x:       return i       break       print('查找的元素不存在')  def biaoweijia(self,x): #给顺序表表尾加一个元素    if self.mande():      print('biaoyiman')    else:     self.data.append(x)    self.biao+=1  def charu(self,index,x):#想顺序表的index位置插入x元素    if self.mande():      print('biayiman')    elif index<0 or index>self.biao-1:      print('bunengcharu')    else:      for i in range(self.biao,index-1):        self.data[i+1]=self.data[i]        self.data[index-1]=x      self.biao+=1  def shanchu(self,x):#删除指定元素x    if self.weikong():#判断是不是空表      print('kongde,bunengshanchu')    index=-1#用index来找x的位置    for i in (self.data):      index+=1      if i == x:        break    for i in range(index,self.biao-1):#把x元素之后的元素都向前推进一格      self.data[i]=self.data[i+1]    self.biao-=1c=shunxubiao(6)c.data=[2,4,5,6]c.biao=3c.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程序设计有所帮助。