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):#知道下標查找元素
    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-=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

python是什么意思

Python是一種跨平臺的、具有解釋性、編譯性、互動性和面向對象的腳本語言，其最初的設計是用于編寫自動化腳本，隨著版本的不斷更新和新功能的添加，常用于用于開發獨立的項目和大型項目。

關于Python中順序表的原理是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。