Python中順序表原理與實現(xiàn)方法詳解

更新時間：2019年12月03日 09:14:55 作者：xlengji

這篇文章主要介紹了Python中順序表原理與實現(xiàn)方法,結(jié)合實例形式分析了Python順序表的概念、原理及增刪查等相關(guān)實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Python中順序表原理與實現(xiàn)方法。分享給大家供大家參考，具體如下：

Python中的順序表

Python中的list和tuple兩種類型采用了順序表的實現(xiàn)技術(shù)，具有順序表的所有性質(zhì)。

tuple是不可變類型，即不變的順序表，因此不支持改變其內(nèi)部狀態(tài)的任何操作，而其他方面，則與list的性質(zhì)類似。

list的基本實現(xiàn)技術(shù)

Python標(biāo)準(zhǔn)類型list就是一種元素個數(shù)可變的線性表，可以加入和刪除元素，并在各種操作中維持已有元素的順序（即保序），而且還具有以下行為特征：

基于下標(biāo)（位置）的高效元素訪問和更新，時間復(fù)雜度應(yīng)該是O(1)；
為滿足該特征，應(yīng)該采用順序表技術(shù)，表中元素保存在一塊連續(xù)的存儲區(qū)中。

允許任意加入元素，而且在不斷加入元素的過程中，表對象的標(biāo)識（函數(shù)id得到的值）不變。
為滿足該特征，就必須能更換元素存儲區(qū)，并且為保證更換存儲區(qū)時list對象的標(biāo)識id不變，只能采用分離式實現(xiàn)技術(shù)。

在Python的官方實現(xiàn)中，list就是一種采用分離式技術(shù)實現(xiàn)的動態(tài)順序表。這就是為什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

《數(shù)據(jù)結(jié)構(gòu)與算法 Python語言描述》裘宗燕著

在Python的官方實現(xiàn)中，list實現(xiàn)采用了如下的策略：在建立空表（或者很小的表）時，系統(tǒng)分配一塊能容納8個元素的存儲區(qū)；在執(zhí)行插入操作（insert或append）時，如果元素存儲區(qū)滿就換一塊4倍大的存儲區(qū)。但如果此時的表已經(jīng)很大（目前的閥值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現(xiàn)過多空閑的存儲位置。

在Python的官方實現(xiàn)中，list實現(xiàn)采用了如下的策略：

  /* 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順序表增刪查實現(xiàn)

class shunxubiao:
  def __init__(self,length):#length表示順序表的長度，決定此順序表最多存儲多少元素
    self.length=length
    self.data=[] #data表示順序表內(nèi)容
    self.biao=-1 #元素下標(biāo)
  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):#知道下標(biāo)查找元素
    return self.data[x]
  def chazhao1(self,x):#知道元素查找下標(biāo)
    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元素之后的元素都向前推進(jìn)一格
      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))#知道尾標(biāo)2查找元素
print(c.chazhao1(4))#知道元素查找尾標(biāo)
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)

輸出結(jié)果：