Python實現的資料結構與演算法之連結串列詳解

Python實現的資料結構與演算法之連結串列詳解

本文例項講述了Python實現的資料結構與演算法之連結串列。分享給大家供大家參考。具體分析如下:

一、概述

連結串列(linked list)是一組資料項的集合,其中每個資料項都是一個節點的一部分,每個節點還包含指向下一個節點的連結。
根據結構的不同,連結串列可以分為單向連結串列、單向迴圈連結串列、雙向連結串列、雙向迴圈連結串列等。其中,單向連結串列和單向迴圈連結串列的結構如下圖所示:

二、ADT

這裡只考慮單向迴圈連結串列ADT,其他型別的連結串列ADT大同小異。單向迴圈連結串列ADT(抽象資料型別)一般提供以下介面:

① SinCycLinkedlist() 建立單向迴圈連結串列
② add(item) 向連結串列中插入資料項
③ remove(item) 刪除連結串列中的資料項
④ search(item) 在連結串列中查詢資料項是否存在
⑤ empty() 判斷連結串列是否為空
⑥ size() 返回連結串列中資料項的個數

單向迴圈連結串列操作的示意圖如下:

三、Python實現

Python的內建型別list底層是由C陣列實現的,list在功能上更接近C 的vector(因為可以動態調整陣列大小)。我們都知道,陣列是連續列表,連結串列是連結列表,二者在概念和結構上完全不同,因此list不能用於實現連結串列。
在C/C 中,通常採用“指標 結構體”來實現連結串列;而在Python中,則可以採用“引用 類”來實現連結串列。在下面的程式碼中,SinCycLinkedlist類代表單向迴圈連結串列,Node類代表連結串列中的一個節點:


#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
  def __init__(self, initdata):
    self.__data = initdata
    self.__next = None
  def getData(self):
    return self.__data
  def getNext(self):
    return self.__next
  def setData(self, newdata):
    self.__data = newdata
  def setNext(self, newnext):
    self.__next = newnext
class SinCycLinkedlist:
  def __init__(self):
    self.head = Node(None)
    self.head.setNext(self.head)
  def add(self, item):
    temp = Node(item)
    temp.setNext(self.head.getNext())
    self.head.setNext(temp)
  def remove(self, item):
    prev = self.head
    while prev.getNext() != self.head:
      cur = prev.getNext()
      if cur.getData() == item:
        prev.setNext(cur.getNext())
      prev = prev.getNext()
  def search(self, item):
    cur = self.head.getNext()
    while cur != self.head:
      if cur.getData() == item:
        return True
      cur = cur.getNext()
    return False
  def empty(self):
    return self.head.getNext() == self.head
  def size(self):
    count = 0
    cur = self.head.getNext()
    while cur != self.head:
      count  = 1
      cur = cur.getNext()
    return count
if __name__ == '__main__':
  s = SinCycLinkedlist()
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
  s.add(19)
  s.add(86)
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
  print('86 is%s in s' % ('' if s.search(86) else ' not',))
  print('4 is%s in s' % ('' if s.search(4) else ' not',))
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
  s.remove(19)
  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

執行結果:


$ python sincyclinkedlist.py
s.empty() == True, s.size() == 0
s.empty() == False, s.size() == 2
86 is in s
4 is not in s
s.empty() == False, s.size() == 2
s.empty() == False, s.size() == 1

希望本文所述對大家的Python程式設計有所幫助。

您可能感興趣的文章:

python資料結構之二叉樹的建立例項Python中列表、字典、元組、集合資料結構整理Python中的高階資料結構詳解python資料結構之圖深度優先和廣度優先例項詳解python實現bitmap資料結構詳解python資料結構樹和二叉樹簡介Python實現的資料結構與演算法之佇列詳解Python中3種內建資料結構:列表、元組和字典C 資料結構與演算法之哈夫曼樹的實現方法圖文詳解JAVA實現哈夫曼樹Python資料結構之哈夫曼樹定義與使用方法示例