用Python玩轉數(shù)據(jù)結構

鏈表

節(jié)點類

根據(jù)在前學過的數(shù)據(jù)結構看成，那么必須有節(jié)點缠借，Python里面沒有指針的說法柿估，所以我們用引用來實現(xiàn)

節(jié)點類的方法

節(jié)點類最基本的功能包括：更新數(shù)據(jù)歧譬，查詢數(shù)據(jù)岸浑，更新后繼節(jié)點和查詢后繼節(jié)點。

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next_node = None

    def get_data(self):
        """
        獲取當前節(jié)點的數(shù)據(jù)
        :return: 返回當前節(jié)點的數(shù)據(jù)
        """
        return self.data

    def set_data(self, data):
        """
        設置節(jié)點的數(shù)據(jù)為傳入的數(shù)據(jù)
        :param data:
        :return: 無返回
        """
        self.data = data

    def get_next(self):
        """
        獲取當前節(jié)帶點的指向
        :return: 返回指向的對象
        """
        return self.next

    def set_next(self, next_node):
        """
        修改節(jié)點的指向
        :param next_node:
        :return:無返回
        """
        self.next_node = next_node

鏈表類

我們把節(jié)點類先實現(xiàn)瑰步，然后再來實現(xiàn)鏈表類矢洲。我們定義一個鏈表類，并實現(xiàn)初始化方法缩焦。在初始化方法中定義了兩個屬性读虏，分別是head 和length屬性。head屬性表明頭節(jié)點袁滥，在初始化的時候指向None盖桥。length屬性表明鏈表的長度，方便判斷列表是否為空和返回鏈表的長度题翻。

class Linked_list(object):
    def __init__(self):
        """
        初始化方法揩徊，定義一個長度屬性方便統(tǒng)計和判斷
        """
        self.head = None
        self.length = 0

鏈表類的方法

然后我們一個想想我們的鏈表類需要哪些方法，這是有鏈表的特性覺得的不是嗎嵌赠？大概列一個列表吧：

• 在末尾插入數(shù)據(jù)
• 在開頭插入數(shù)據(jù)
• 在指定位置插入 數(shù)據(jù)
• 修改指定位置的數(shù)據(jù)
• 獲取指定位置的數(shù)據(jù)
• 查找數(shù)據(jù)在鏈表中的數(shù)據(jù)
• 刪除指定位置的數(shù)據(jù)
• 展示整個鏈表
• 刪除整個鏈表
• 判斷這個鏈表是否為空

大概就是這些看起來是不是有點多塑荒，但是不用擔心，我們一點一點的來實現(xiàn)姜挺。

判斷鏈表是否為空

首先是判斷一個鏈表是否為空齿税，這個很好實現(xiàn)，我們先看代碼：

    def isEmpty(self):
        """
        判斷鏈表是否為空初家，如果為空返回True偎窘，否則為False
        :return:
        """
        return self.length == 0

除去注釋也就一行代碼的事情，用鏈表的長度和0做一個比較溜在，不相等返回False相等返回True然后就能很好的判斷了陌知。

獲取鏈表的長度

同樣的獲取鏈表的長度也很簡單：

    def get_length(self):
        return self.length

在鏈表末尾插入數(shù)據(jù)

然后就是在末尾插入數(shù)據(jù)：

    def append(self, data_or_node):
        """
        在鏈表的末尾增加一個節(jié)點
        :param data_or_node:
        :return:
        """
        item = None
        # 這一個判斷是為了判斷傳進來的數(shù)據(jù)是什么類型的
        if isinstance(data_or_node, Node):
            item = data_or_node
        else:
            item = Node(data_or_node)

        if not self.head:
            self.head = item
            self.length += 1
        else:
            node = self.head
            while node.next_node:
                node = node.next_node
            node.next_node = item
            self.length += 1

首先是判斷傳入進來的數(shù)據(jù)是什么類型，如果已經是一個節(jié)點類的話我們就不用轉換掖肋，如果不是仆葡，我們就將其轉換為節(jié)點類。這里用到了isinstance()方法，這個方法的作用是判一個對象是否是一個已知的類型沿盅，考慮繼承的情況把篓。然后判斷這個鏈表的頭結點是否存在，也可以通過判斷鏈表的長度來實現(xiàn)腰涧。如果頭節(jié)點不存在韧掩，就將這個節(jié)點變?yōu)轭^節(jié)點。所以有了這個引用窖铡，將item的值賦值給head疗锐。如果不是的話我們首先就要找到尾節(jié)點，通過頭節(jié)點開始循環(huán)费彼，一直找到尾節(jié)點滑臊，然后引用。不管是那種情況都不能忘記將鏈表的長度加上1

在鏈表的頭部插入數(shù)據(jù)

在頭部插入數(shù)據(jù)也很簡單箍铲，

    def add(self, data_or_node):
        """
        在鏈表的最前方插入一個數(shù)據(jù)
        :param data_or_node:
        :return:
        """
        if isinstance(data_or_node, Node):
            item = data_or_node
        else:
            item = Node(data_or_node)

        if not self.head:
            self.head = item
            self.length += 1
        else:
            next_node = self.head
            self.head = item
            item.next_node = next_node
            self.length += 1

大部分都差不多雇卷，只是在判斷不是空鏈表之后的處理有點不一樣。我們將之前頭節(jié)點的值賦值給一個變量颠猴，然后將我們傳入的變量指向給原頭節(jié)點关划，同時將頭節(jié)點指向我們傳入的變量。

在指定位置插入節(jié)點

我們可以通過指定位置插入節(jié)點這個是很必要的一個方法芙粱，先看代碼：

    def insert(self, index, data_or_node):
        """
        根據(jù)給定的索引在鏈表中插入一個節(jié)點
        :param index: 索引
        :param data_or_node: 數(shù)據(jù)
        :return: 無返回
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return
        item = None
        if isinstance(data_or_node, Node):
            item = data_or_node
        else:
            item = Node(data_or_node)

        if index == 0:
            self.add(item)
            return

        j = 0
        node = self.head
        prev = self.head
        while j < index:
            prev = node
            node = node.next_node
            j += 1
        prev.next_node = item
        item.next_node = node
        self.length += 1

對于所有給出索引的方法來說祭玉，我們都需要判斷這個鏈表是否為空和給定的索引是否越界。然后再把傳入的節(jié)點通過判斷轉換為節(jié)點類春畔。如果索引的值是0的話就是在頭部插入脱货，我們直接調用在前面定義的內部方法就好，然后記得return結束函數(shù)律姨，不然那你會將你的所有的節(jié)點的值都改變振峻。然后就是關鍵的步驟，我們定義三個變量择份，作用分別是：計數(shù)器扣孟、記錄前置節(jié)點和記錄當前節(jié)點。最開始的節(jié)點都為頭節(jié)點荣赶，然后開始循環(huán)凤价，當j小于索引值的時候呢，循環(huán)拔创，同時將node的值賦值給prev佛吓，將節(jié)點記錄下來鼻吮。當找到插入節(jié)點的位置的時候眷蚓，我們將prev指向我們傳入的節(jié)點阀圾，然后將傳入的節(jié)點再指向給item就完成在指定位置插入。只要是涉及到節(jié)點個數(shù)的變化的操作的時候一定要記得對length進行對應的操作。

刪除指定位置的節(jié)點

說完了增加侣滩，按照慣例就是刪除了口注。首先是刪除指定位置的節(jié)點：

    def delete(self, index):
        """
        根據(jù)給定的索引刪除一個節(jié)點
        :param index: 索引
        :return: 無返回
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return

        if index == 0:
            self.head = self.head.next_node
            self.length -= 1

        j = 0
        node = self.head
        prev = self.head
        while j < index:
            prev = node
            node = node.next_node
            j += 1
        prev.next_node = node.next_node
        self.length -= 1

首先還是幾個判斷，然后如果是刪除頭節(jié)點君珠，我們將頭節(jié)點的值指向頭節(jié)點的下一個寝志。如果不是，就和插入很像了策添，找到索引對應的位置澈段，然后將prev直接指向node的下一個，然后鏈表長度減1舰攒。

刪除整個鏈表

刪除了一個節(jié)點就像刪除整個鏈表，這個代碼也超級簡單：

    def clear(self):
        """
        清除鏈表
        :return: 無返回
        """
        self.head = None
        self.length = 0

我們只需要將鏈表的頭節(jié)點再指向為空悔醋，然后長度變?yōu)?就好摩窃。

修改指定位置的節(jié)點的值

刪除也很簡單，下面來說修改芬骄，修改指定位置節(jié)點的值：

    def updata_node_item(self, index, data):
        """
        根據(jù)給出的索引更新一個節(jié)點的值
        :param index: 索引
        :param data: 更新的值
        :return: 無返回
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return

        j = 0
        node = self.head
        while j < index:
            node = node.next_node
            j += 1
        node.data = data

就只是常規(guī)的判斷然后是循環(huán)找到節(jié)點后修改值就好猾愿。

根據(jù)索引獲得對應節(jié)點的值

查找是一個很重要的功能，有兩種需要我們實現(xiàn)账阻，先來第一種：根據(jù)索引查找對應的值：

 def get_node_item(self, index):
        """
        根據(jù)索引獲取獲取節(jié)點的值
        :param index: 索引
        :return: 返回索引對應節(jié)點的值
        """
        if self.isEmpty():
            print("this Linked list is Empty")
            return

        if index < 0 or index >= self.length:
            print("error: out of index ")
            return

        j = 0
        node = self.head
        while j < index:
            node = node.next_node
            j += 1
        return node.data

和修改很類似蒂秘，不同的是我們直接返回值就好

根據(jù)值查對應的節(jié)點的索引

我們也可以傳一個值然后找對應的索引，這樣就能做到：

    def get_node_index(self, data):
        """
        查找一個數(shù)據(jù)的索引
        :param data:數(shù)據(jù)
        :return:索引
        """
        node = self.head
        j = 0
        while node.next_node:
            if node.data == data:
                return j
            else:
                node = node.next_node
            j += 1
        if j == self.length:
            print("%s is not found " % str(data))

其實都差不多淘太，但是呢有一種情況需要注意姻僧，就是如果當j的值都等于鏈表的長度的時候說明，鏈表當中沒有這個值蒲牧。

展示鏈表

其實到這里就差不多了撇贺，然后就是一個展示整個鏈表的方法：

    def show(self):
        """
        展示鏈表
        :return:
        """
        if self.isEmpty():
            print("this is a empty linked list")
        n = 0
        node = self.head
        while n < self.length:
            print("node %d : %s" % (n, node.data))
            node = node.next_node
            n += 1

試試效果

mylinked = Linked_list()
for i in range(10):
    mylinked.append(i)
mylinked.show()
print(mylinked.get_length())
print(mylinked.get_node_index(4))
print(mylinked.get_node_item(5))
print(mylinked.updata_node_item(4, 20))
print(mylinked.delete(8))
print(mylinked.insert(0, 420))
mylinked.show()

結果：

node 0 : 0
node 1 : 1
node 2 : 2
node 3 : 3
node 4 : 4
node 5 : 5
node 6 : 6
node 7 : 7
node 8 : 8
node 9 : 9
10
4
5
None
None
None
node 0 : 420
node 1 : 0
node 2 : 1
node 3 : 2
node 4 : 3
node 5 : 20
node 6 : 5
node 7 : 6
node 8 : 7
node 9 : 9

Process finished with exit code 0

完整代碼傳送門：點這里