學習筆記，僅供參考，有錯必糾

---

文章目錄

• • 算法與數據結構–基于python
  • • 順序表
    • • 什么是線性表
      • 什么是順序表
    • 順序表的基本形式
    • 順序表的結構與實現
    • • 順序表的結構
      • 順序表的兩種基本實現方式
      • 擴容策略
    • 順序表的操作
    • • 插入元素
      • 刪除元素
    • Python中的順序表
    • • 列表的基本實現

---

算法與數據結構–基于python

順序表

什么是線性表

• 在程序中，經常需要將一組數據元素作為整體管理和使用，我們需要創建一種元素組，并用變量記錄它們。

• 一組數據中包含的元素個數可能發生變化(增加或刪除元素)。

• 對于這種需求，最簡單的解決方案便是將這樣一組元素看成一個序列，用元素在序列里的位置和順序，表示數據之間的某種關系。

• 這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。

• 一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關系。

• 線性表是最基本的數據結構之一，在實際程序中應用非常廣泛，它還經常被用作更復雜的數據結構的實現基礎。

什么是順序表

根據線性表的實際存儲方式，分為兩種實現模型：

• 順序表，將元素有順序地存放在一塊連續的存儲區里，元素間的順序關系由它們的存儲順序自然表示。

• 鏈表，將元素存放在通過鏈接構造起來的一系列存儲塊中。

順序表的基本形式

• 基本存儲形式(L = [1, 2, 3])

• 元素外置的順序表(L = [1, 2.5, true])

順序表的結構與實現

順序表的結構

一個順序表的完整信息包括兩部分：

• 一部分是表中的元素集合;

• 另一部分是有關表的整體情況的信息，這部分信息主要包括元素存儲區的容量和當前表中已有的元素個數兩項.

順序表的兩種基本實現方式

• 一體式存儲，類似于數組，不可變長度

• 分離式存儲，類似于列表，可變長度

擴容策略

• 每次擴充增加固定數目的存儲位置，如每次擴充增加10個元素位置，這種策略可稱為線性增長。

• 每次擴充容量加倍，如每次擴充增加一倍存儲空間。

順序表的操作

插入元素

在順序表中插入新元素111的三種方式：

解釋：

• a: 在順序表的末尾插入111
• b: 在順序表中索引為1處存入111，將索引1處原來的元素693放入順序表末尾
• c: 在順序表中索引為1處放入111，并將后面的元素向后依次移動1格

復雜度：

• a: $O(1)$
• b: $O(1)$
• c: $O(n)$

刪除元素

刪除順序表中元素的三種方式：

解釋：

• a:刪除順序表的末尾的元素
• b: 刪除順序表中索引為1處的元素，并將末尾的元素154存放在索引1處
• c: 刪除順序表中索引為1處的元素，并將索引1后的元素向前依次移動1格

復雜度：

• a: $O(1)$
• b: $O(1)$
• c: $O(n)$

Python中的順序表

Python中的list和tuple兩種類型采用了順序表的實現技術，具有前面討論的順序表的性質；

tuple是不可變類型，即不變的順序表，因此不支持改變其內部狀態的任何操作，而其他方面，則與list的性質類似；

列表的基本實現

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

• 基于下標（位置）的高效元素訪問和更新，時間復雜度為$O(1)$，為滿足該特征，應該采用順序表技術，表中元素保存在一塊連續的存儲區中。

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

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

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

• 在建立空表（或者很小的表）時，系統分配一塊能容納8個元素的存儲區。

• 在執行插入操作（insert或append）時，如果元素存儲區滿就換一塊4倍大的存儲區。

• 但如果此時的表已經很大（目前的閾值為50000），則改變策略，采用加一倍的方法。引入這種改變策略的方式，是為了避免出現過多空閑的存儲位置。

總結

以上是生活随笔為你收集整理的算法与数据结构(part4)--顺序表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。