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

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

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

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

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

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

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

2.1、順序表的基本形式

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

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

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

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

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

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

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

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

能夠找到表中的首元素

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

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

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

把表中的元素分別存儲(chǔ)在一批獨(dú)立的存儲(chǔ)塊里

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

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

單鏈表

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

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

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

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

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

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

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

單鏈表的操作

is_empty() 鏈表是否為空

length() 鏈表長度

travel() 遍歷整個(gè)鏈表

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

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

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

remove(item) 刪除節(jié)點(diǎn)

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

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

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

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

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

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