0. 學(xué)習(xí)目標(biāo)

線性表在計(jì)算機(jī)中的表示可以采用多種方法，采用不同存儲(chǔ)方法的線性表也有著不同的名稱和特點(diǎn)。線性表有兩種基本的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。本節(jié)將介紹順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)以及各種基本運(yùn)算的實(shí)現(xiàn)。
通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

線性表的順序存儲(chǔ)及實(shí)現(xiàn)方法

順序表基本操作的實(shí)現(xiàn)

利用順序表的基本操作實(shí)現(xiàn)復(fù)雜算法

1. 線性表的順序存儲(chǔ)結(jié)構(gòu)

1.1 順序表基本概念

線性表的順序存儲(chǔ)是把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組連續(xù)的存儲(chǔ)單元中，即邏輯結(jié)構(gòu)上相鄰的兩個(gè)數(shù)據(jù)元素存儲(chǔ)在計(jì)算機(jī)內(nèi)的物理存儲(chǔ)位置也是相鄰的，這種存儲(chǔ)方法為整個(gè)線性表分配一整個(gè)內(nèi)存塊保存線性表的元素，借助數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的物理位置表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。采用順序存儲(chǔ)結(jié)構(gòu)表示的線性表簡稱順序表 (Sequential List)。

順序表具有以下兩個(gè)基本特點(diǎn)：

順序表的所有元素所占的存儲(chǔ)空間是連續(xù)的；

順序表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

由于線性表的所有數(shù)據(jù)元素屬于同一數(shù)據(jù)類型，所以每個(gè)元素占用的空間(字節(jié)數(shù))相同。因此，要在此結(jié)構(gòu)中查找某一個(gè)元素是很方便的，即只要知道順序表首地址和每個(gè)數(shù)據(jù)元素在內(nèi)存所占字節(jié)的大小，就可求出第 i ii 個(gè)數(shù)據(jù)元素的地址。通過使用特定元素的序號(hào)，可以在常數(shù)時(shí)間內(nèi)訪問數(shù)據(jù)元素，因此可以說順序表具有按數(shù)據(jù)元素的序號(hào)隨機(jī)存取的特點(diǎn)。

假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址(即順序表第一個(gè)字節(jié)的地址，也稱首地址)為id(a₁)，每一個(gè)數(shù)據(jù)元素占k個(gè)字節(jié)，則線性表中第i個(gè)元素a_i在計(jì)算機(jī)中的存儲(chǔ)地址為：

id(a_i)=id(a₁)+(i−1)×k (1≤i≤n)

從上式可以看出，訪問順序表數(shù)據(jù)元素的過程只需要一次乘法和一次加法。由于這兩個(gè)操作只需要常數(shù)時(shí)間，因此可以說順序表訪問可以在常數(shù)時(shí)間內(nèi)進(jìn)行。

也就是說，順序表中的每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線性表中的序號(hào)惟一確定。假設(shè)有一長度為n的線性表 (a₁,a₂,...,a_n)，那么其在計(jì)算機(jī)中的順序存儲(chǔ)結(jié)構(gòu)可以用下圖表示：

1.2 順序表的優(yōu)缺點(diǎn)

順序表的優(yōu)點(diǎn)：

• 簡單易用
• 可以快速訪問元素

順序表的缺點(diǎn)：

• 固定大小：順序表的大小是靜態(tài)的(使用前需要指定順序表大小)
• 基于位置插入元素較復(fù)雜：要在給定位置插入元素，可能需要移動(dòng)現(xiàn)有元素來創(chuàng)建一個(gè)空位置，以便在所需位置插入新元素；如果要在開頭添加元素，那么移位操作的開銷就更大了

為了解決順序表具有固定大小的缺陷，動(dòng)態(tài)順序表的概念被提出。

1.3 動(dòng)態(tài)順序表

動(dòng)態(tài)順序表(也稱為可增長順序表、可調(diào)整大小的順序表、動(dòng)態(tài)表)是一種隨機(jī)訪問、大小可變的順序表數(shù)據(jù)結(jié)構(gòu)，允許添加或刪除元素，Python 內(nèi)置的 list 就是一種動(dòng)態(tài)順序表。

實(shí)現(xiàn)動(dòng)態(tài)順序表的一種簡單方法是從一些固定大小的順序表開始。一旦該順序表變滿，就創(chuàng)建高于原始順序表大小的新順序表；同樣，如果順序表中的元素過少，則將縮小順序表大小。

接下來，為了更好的理解順序表，我們將使用 Python 實(shí)現(xiàn)順序表。

2. 順序表的實(shí)現(xiàn)

在具體實(shí)現(xiàn)時(shí)，使用 Python 中的列表來對應(yīng)連續(xù)的存儲(chǔ)空間。設(shè)最多可存儲(chǔ) max_size 個(gè)元素，為保存線性表的長度需定義一個(gè)整型變量 num_items。由于，Python 列表中索引從 0 開始，因此，線性表的第i(1≤i≤n)個(gè)元素存放在列表索引為i−1的列表元素中，為保持一致性，我們實(shí)現(xiàn)的順序表的序號(hào)同樣從 0 開始(也可以根據(jù)需要索引從 1 開始，只需要進(jìn)行簡單修改)。

2.1 順序表的初始化

順序表的初始化需要三部分信息：items 列表用于存儲(chǔ)數(shù)據(jù)元素，max_size 用于存儲(chǔ) items 列表的最大長度，以及 num_items 用于記錄 items 列表的當(dāng)前使用的位置，即順序表中的數(shù)據(jù)元素?cái)?shù)量。

class SequentialList:
    def __init__(self, max_size=10):
        self.items = [None] * max_size
        self.num_items = 0
        self.max_size = max_size

初始化代碼通過創(chuàng)建一個(gè)包含 10 個(gè) None 值的列表來構(gòu)建一個(gè) SequentialList 對象，內(nèi)部 items 列表的初始大小 max_size 默認(rèn)為 10，也可以傳遞更大的順序表大小作為初始大小，該列表也可以在需要時(shí)會(huì)動(dòng)態(tài)增長。創(chuàng)建 SequentialList 對象的時(shí)間復(fù)雜度為O(1)。

如下圖所示，是一個(gè)包含 5 個(gè)數(shù)據(jù)元素的 SequentialList 對象：

2.2 獲取順序表長度

這里所說的順序表長度，指順序表中數(shù)據(jù)元素的個(gè)數(shù)，由于我們在順序表中使用 num_items 跟蹤順序表中的項(xiàng)數(shù)，求取順序表長度只需要重載 __len__ 從對象返回 num_items 的值，因此時(shí)間復(fù)雜度為O(1)：

    def __len__(self):
        return self.num_items

如果在 SequentialList 對象中沒有跟蹤列表的項(xiàng)數(shù)，那么計(jì)算順序表長度的時(shí)間復(fù)雜度為O(n)。

2.3 讀取指定位置元素

為了實(shí)現(xiàn)讀取順序表指定位置元素的操作，我們將重載 __getitem__ 操作，操作的復(fù)雜度為O(1)。同時(shí)，我們希望確保索引在可接受的索引范圍內(nèi)，否則將像內(nèi)置列表類一樣引發(fā) IndexError 異常：

    def __getitem__(self, index):
        if index >= 0 and index < self.num_items:
            return self.items[index]
        raise IndexError('SequentialList index out of range')

我們也可以實(shí)現(xiàn)修改指定位置元素的操作，只需要重載 __setitem__ 操作，其復(fù)雜度同樣為O(1)：

    def __setitem__(self, index, val):
        if index >= 0 and index < self.num_items:
            self.items[index] = val
            return
        raise IndexError("SequentialList assignment index out of range")

2.4 查找指定元素

要確定值為 x 的元素在順序表中的位置，需要依次比較各元素。當(dāng)查詢到第一個(gè)滿足條件的數(shù)據(jù)元素時(shí)，返回其下標(biāo)，否則像內(nèi)置列表類一樣引發(fā) ValueError 異常，表示查找失敗。

    def locate(self, item):
        for i in range(self.num_items):
            if self.items[i] == item:
                return i
        raise ValueError("{} is not in sequential list".format(item))

在查找過程中，數(shù)據(jù)元素比較次數(shù)的平均值為(n+1)/2，因此時(shí)間復(fù)雜度為O(n)。

2.5 在指定位置插入新元素

實(shí)現(xiàn)在指定位置插入新元素之前，我們首先看下如何在順序表末尾追加元素。追加時(shí)，如果有空閑空間，只需要在 self.items 列表的末尾再添加一項(xiàng)，而當(dāng) self.items 列表填滿時(shí)，我們必須增加 self.items 列表的大小，為需要追加的新元素創(chuàng)建空間，創(chuàng)建的新 self.items 大小與 self.items 的當(dāng)前長度成正比。

為了使追加操作在O(1)時(shí)間內(nèi)運(yùn)行，我們不能在每次需要更多空間時(shí)僅增加一個(gè)空閑位置，事實(shí)證明，每次增加 25% 的空間就足以保證O(1)復(fù)雜度。選擇增加空間的百分比并不重要，每次增加 10% 或100%的空間，同樣可以使時(shí)間復(fù)雜度為O(1)。這里選擇 25% 的原因是可以在不占用太多計(jì)算機(jī)內(nèi)存的情況下多次使用追加操作擴(kuò)展列表。

    def __alloc(self):
        new_size = (self.max_size // 4) + self.max_size + 1
        new_items = [None] * new_size
        for i in range(self.num_items):
            new_items[i] = self.items[i]
        
        self.items = new_items
        self.max_size = new_size

    def append(self, item):
        if self.num_items == self.max_size:
            self.__alloc()
        
        self.items[self.num_items] = item
        self.num_items += 1

要插入新數(shù)據(jù)元素到順序表中，必須為新元素騰出空間，下圖表示順序表中的列表在進(jìn)行插入操作前后，其數(shù)據(jù)元素在列表中下標(biāo)的變化情況：

完成如上的插入操作要經(jīng)過如下步驟：

1.線性表中指定位置及其之后的元素，依次向后移動(dòng)一個(gè)位置，空出索引為i的位置

2.數(shù)據(jù)元素 x 插入到第i個(gè)存儲(chǔ)位置

3.插入結(jié)束后使線性表的長度增加 1

需要注意的是，如果線性表空間已滿，首先需要分配新的空間。如果提供的索引大于列表的大小，則將新項(xiàng) x 附加到列表的末尾。插入時(shí)間元素操作的時(shí)間復(fù)雜度為O(n)。

    def insert(self, index, item):
        if self.num_items == self.max_size:
            self.__alloc()
        if index < self.num_items and index >= 0:
            for j in range(self.num_items-1, index-1, -1):
                self.items[j+1] = self.items[j]
            self.items[index] = item
            self.num_items += 1
        elif index >= self.num_items:
            self.append(item)
        else:
            raise IndexError("SequentialList assignment index out of range")

2.6 刪除指定位置元素

當(dāng)刪除列表中特定索引處的數(shù)據(jù)元素時(shí)，我們必須將其之后的所有元素向下移動(dòng)以保證內(nèi)部列表中沒有無效數(shù)據(jù)。下圖表示一個(gè)順序表在進(jìn)行刪除運(yùn)算前后，其數(shù)據(jù)元素下標(biāo)的變化：

在線性表上完成上述操作需要以下步驟：

1.在線性表中刪除下標(biāo)為i的元素，從索引為i+1到n−1的元素依次向前移動(dòng)依次向前移動(dòng)一個(gè)位置，將所刪除的索引為i的數(shù)據(jù)元素a_i+1覆蓋掉，從而保證邏輯上相鄰的元素物理位置也相鄰

2.修改順序表長度，使其減 1

為了實(shí)現(xiàn)刪除順序表指定位置元素的操作，我們將重載 __getitem__ 操作，在順序表上刪除數(shù)據(jù)元素時(shí)大約需要移動(dòng)表中一半的元素，顯然該算法的時(shí)間復(fù)雜度為Ｏ(n)。

    def __delitem__(self, index):
        for i in range(index, self.num_items-1):
            self.items[i] = self.items[i+1]
        self.num_items -= 1

2.7 其它一些有用的操作

為了更好的使用順序表，接下來將介紹其它一些很有用的操作。
例如，將順序表轉(zhuǎn)換為字符串以便進(jìn)行打印，使用 str 函數(shù)調(diào)用對象上的 __str__ 方法可以創(chuàng)建適合打印的字符串表示，__str__ 的返回結(jié)果的可讀性很強(qiáng)：

    def __str__(self):
        s = '['
        for i in range(self.num_items):
            s += repr(self.items[i])
            if i < self.num_items - 1:
                s += ', '
        s += ']'
        return s

我們也可以重載成員資格函數(shù) __contain__ 來檢查一個(gè)數(shù)據(jù)元素是否是順序表中的元素之一。這樣做的唯一方法是按順序檢查順序表中的每個(gè)數(shù)據(jù)元素。如果找到該項(xiàng)目，則返回 True，否則返回 False 這種搜索方法稱為線性搜索，之所以這樣命名是因?yàn)樗哂蠴(n)的時(shí)間復(fù)雜度：

    def __contains__(self, item):
        for i in range(self.num_items):
            if self.items[i] == item:
                return True
        return False

檢查兩個(gè)順序表的相等性首先需要兩個(gè)順序表的類型相同以及兩個(gè)順序表必須具有相同的長度。在滿足這兩個(gè)先決條件的情況下，如果兩個(gè)表中的所有元素都相等，則我們可以說兩個(gè)順序表相等，相等測試的時(shí)間復(fù)雜度為O(n)，我們重載 __eq__ 方法實(shí)現(xiàn)此操作：

    def __eq__(self, another):
        if type(another) != type(self) or self.num_items != another.num_items:
            return False
        for i in range(self.num_items):
            if self.items[i] != another.items[i]:
                return False
        return True

3. 順序表應(yīng)用

接下來，我們首先對上述實(shí)現(xiàn)的順序表進(jìn)行測試，以驗(yàn)證操作的有效性，然后利用實(shí)現(xiàn)的基本操作來實(shí)現(xiàn)更復(fù)雜的算法。

3.1 順序表應(yīng)用示例

首先初始化一個(gè)順序表 sample_sqlist，并在其中追加若干元素：

sample_sqlist = SequentialList()
sample_sqlist.append(11)
sample_sqlist.append(22)
sample_sqlist.append(33)

我們可以直接打印順序表中的數(shù)據(jù)元素、順序表長度等信息：

print('順序表數(shù)據(jù)元素為：', sample_sqlist)
print('順序表長度：', len(sample_sqlist))
print('順序表中第0個(gè)數(shù)據(jù)元素：', sample_sqlist[0])
# 修改數(shù)據(jù)元素
sample_sqlist[1] = 2022
print('順序表數(shù)據(jù)元素為：', sample_sqlist)

以上代碼輸出如下：

順序表數(shù)據(jù)元素為： [11, 22, 33]

順序表長度： 3

順序表中第0個(gè)數(shù)據(jù)元素： 11

順序表數(shù)據(jù)元素為： [11, 2022, 33]

接下來，我們將演示在指定位置添加/刪除元素、以及如何查找指定元素等：

print('在順序表位置1處添加元素2021')
sample_sqlist.insert(1, 2021)
print('添加元素后，順序表數(shù)據(jù)元素為：', sample_sqlist)
print('刪除順序表位置2處元素')
del(sample_sqlist[2])
print('刪除數(shù)據(jù)后，順序表數(shù)據(jù)元素為：', sample_sqlist)
print('元素11的索引為{}'.format(sample_sqlist.locate(11)))
print('11在順序表中?', 11 in sample_sqlist)
print('22在順序表中?', 22 in sample_sqlist)

以上代碼輸出如下：

在順序表位置1處添加元素2021

添加元素后，順序表數(shù)據(jù)元素為： [11, 2021, 2022, 33]

刪除順序表位置2處元素

刪除數(shù)據(jù)后，順序表數(shù)據(jù)元素為： [11, 2021, 33]

元素11的索引為0

11在順序表中? True

22在順序表中? False

3.2 利用順序表基本操作實(shí)現(xiàn)復(fù)雜操作

[1] 利用順序表的基本操作，合并兩個(gè)順序表：

def add_sqlist(sqlist1, sqlist2):
    result = SequentialList(max_size=sqlist1.num_items+sqlist2.num_items)
    for i in range(sqlist1.num_items):
        result.append(sqlist1[i])
    for i in range(sqlist2.num_items):
        result.append(sqlist2[i])
    return result
# 算法測試
sqlist1 = SequentialList()
sqlist2 = SequentialList()
for i in range(10):
    sqlist1.append(i)
    sqlist2.append(i*5)
print('順序表1：', sqlist1, '順序表2：', sqlist2)
# 合并順序表
result = add_sqlist(sqlist1, sqlist2)
print('合并順序表：', result)

可以看到合并兩個(gè)順序表的時(shí)間復(fù)雜度為O(n)，程序輸出結(jié)果如下：

順序表1： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 順序表2： [0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

合并順序表： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

[2] 利用順序表 sqlist1 和 sqlist2 中公共數(shù)據(jù)元素生成新順序表：

def commelem(sqlist1, sqlist2):
    result = SequentialList()
    for i in range(sqlist1.num_items):
        if sqlist1[i] in sqlist2 and sqlist1[i] not in result:
            result.append(sqlist1[i])
    return result
# 算法測試
sqlist1 = SequentialList()
sqlist2 = SequentialList()
for i in range(5):
    sqlist1.append(i*2)
    sqlist1.append(i)
    sqlist2.append(i*3)
print('順序表1：', sqlist1, '順序表2：', sqlist2)
# 合并順序表
result = commelem(sqlist1, sqlist2)
print('兩順序表中的公共元素：', result)

可以看到算法的時(shí)間復(fù)雜度為O(n²)，程序輸出結(jié)果如下：

合并順序表： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

順序表1： [0, 0, 2, 1, 4, 2, 6, 3, 8, 4] 順序表2： [0, 3, 6, 9, 12]

兩順序表中的公共元素： [0, 6, 3]

到此這篇關(guān)于詳解Python數(shù)據(jù)結(jié)構(gòu)與算法中的順序表的文章就介紹到這了,更多相關(guān)Python順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論