摘要：線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)基礎(chǔ)。鏈表之單鏈表線性表的定義，它是一些元素的序列，維持著元素之間的一種線性關(guān)系。

線性表學(xué)習(xí)筆記，python語言描述-2019-1-14

在程序中，經(jīng)常需要將一組（通常是同為某個類型的）數(shù)據(jù)元素作為整體管理和使用，需要創(chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個數(shù)可能發(fā)生變化（可以增加或刪除元素）。

對于這種需求，最簡單的解決方案便是將這樣一組元素看成一個序列，用元素在序列里的位置和順序，表示實際應(yīng)用中的某種有意義的信息，或者表示數(shù)據(jù)之間的某種關(guān)系。

這樣的一組序列元素的組織形式，我們可以將其抽象為線性表。一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關(guān)系。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)基礎(chǔ)。

根據(jù)線性表的實際存儲方式，分為兩種實現(xiàn)模型：

順序表，將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關(guān)系由它們的存儲順序自然表示。
鏈表，將元素存放在通過鏈接構(gòu)造起來的一系列存儲塊中。

2.1、順序表的基本形式

圖a表示的是順序表的基本形式，數(shù)據(jù)元素本身連續(xù)存儲，每個元素所占的存儲單元大小固定相同，元素的下標(biāo)是其邏輯地址，而元素存儲的物理地址（實際內(nèi)存地址）可以通過存儲區(qū)的起始地址Loc (e0)加上邏輯地址（第i個元素）與存儲單元大小（c）的乘積計算而得，即：

Loc(ei) = Loc(e0) + c*i

故，訪問指定元素時無需從頭遍歷，通過計算便可獲得對應(yīng)地址，其時間復(fù)雜度為O(1)。

如果元素的大小不統(tǒng)一，則須采用圖b的元素外置的形式，將實際數(shù)據(jù)元素另行存儲，而順序表中各單元位置保存對應(yīng)元素的地址信息（即鏈接）。由于每個鏈接所需的存儲量相同，通過上述公式，可以計算出元素鏈接的存儲位置，而后順著鏈接找到實際存儲的數(shù)據(jù)元素。注意，圖b中的c不再是數(shù)據(jù)元素的大小，而是存儲一個鏈接地址所需的存儲量，這個量通常很小。

圖b這樣的順序表也被稱為對實際數(shù)據(jù)的索引，這是最簡單的索引結(jié)構(gòu)。

2.2、順序表的基本實現(xiàn)
順序表的基本實現(xiàn)方式：表中元素順序存放在一片足夠大的連續(xù)存儲區(qū)里，首元素存入存儲區(qū)的開始位置，其余元素依次順序存放。元素之間的邏輯順序關(guān)系通過元素在存儲區(qū)的物理地址表示。

順序表最常見的一種基本實現(xiàn)方式是一個表里保存的元素類型相同，因此存儲每個表元素所需的存儲量相同，可以在表里等距安排相同大小的存儲位置。如下圖，一個順序表，存放的元素是整型的數(shù)據(jù)類型，整型在32位的操作系統(tǒng)中，一個整型數(shù)字占用內(nèi)存的空間大小是4Byte,因此，內(nèi)存中連續(xù)存放幾個整型數(shù)字，每個存放元素的空間的地址值之間是等距。其中Li變量指向的通常是順序表的表頭元素的地址值，也就是0x23。

線性表的定義，它是一些元素的序列，維持著元素之間的一種線性關(guān)系。實現(xiàn)線性表的基本需要是：

能夠找到表中的首元素

從表中的任一元素出發(fā)，都能找到它的下一個元素

實現(xiàn)它除了連續(xù)存儲的順序表之外，鏈表也能做到。

鏈表是用鏈接關(guān)系顯示表示元素之間的順序關(guān)系，基本實現(xiàn)方式如下:

把表中的元素分別存儲在一批獨立的存儲塊里

保證從組成表結(jié)構(gòu)中的任一結(jié)點可找到與其相關(guān)的下一個結(jié)點

在前一結(jié)點用鏈接的方式顯示地記錄與下一結(jié)點的關(guān)聯(lián)。

單鏈表

單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節(jié)點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節(jié)點，而最后一個節(jié)點的鏈接域則指向一個空值。

表元素域elem用來存放具體的數(shù)據(jù)。

鏈接域next用來存放下一個節(jié)點的位置（python中的標(biāo)識）

變量p指向鏈表的頭節(jié)點（首節(jié)點）的位置，從p出發(fā)能找到表中的任意節(jié)點。

而表示一條鏈表的結(jié)束，只需要將最后一個結(jié)點的鏈接域設(shè)置為None。
節(jié)點的實現(xiàn)

一個鏈表的最基本組成是一個結(jié)點，一個結(jié)點的實現(xiàn)如下：

class SingleNode(object):
    """單鏈表的結(jié)點"""
    def __init__(self,item):
        # _item存放數(shù)據(jù)元素
        self.item = item
        # _next是下一個節(jié)點的標(biāo)識
        self.next = None

單鏈表的操作

is_empty() 鏈表是否為空

length() 鏈表長度

travel() 遍歷整個鏈表

add(item) 鏈表頭部添加元素

append(item) 鏈表尾部添加元素

insert(pos, item) 指定位置添加元素

remove(item) 刪除節(jié)點

search(item) 查找節(jié)點是否存在

python中單鏈表的實現(xiàn)

class SingleLinkList(object):
    """單鏈表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判斷鏈表是否為空"""
        return self._head == None

    def length(self):
        """鏈表長度"""
        # cur初始時指向頭節(jié)點
        cur = self._head
        count = 0
        # 尾節(jié)點指向None，當(dāng)未到達(dá)尾部時
        while cur != None:
            count += 1
            # 將cur后移一個節(jié)點
            cur = cur.next
        return count

    def travel(self):
        """遍歷鏈表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""