Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之鏈表詳解

本文實(shí)例講述了Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之鏈表。分享給大家供大家參考。具體分析如下：

一、概述

鏈表（linked list）是一組數(shù)據(jù)項(xiàng)的集合，其中每個(gè)數(shù)據(jù)項(xiàng)都是一個(gè)節(jié)點(diǎn)的一部分，每個(gè)節(jié)點(diǎn)還包含指向下一個(gè)節(jié)點(diǎn)的鏈接。
根據(jù)結(jié)構(gòu)的不同，鏈表可以分為單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表等。其中，單向鏈表和單向循環(huán)鏈表的結(jié)構(gòu)如下圖所示：

二、ADT

這里只考慮單向循環(huán)鏈表ADT，其他類型的鏈表ADT大同小異。單向循環(huán)鏈表ADT（抽象數(shù)據(jù)類型）一般提供以下接口：

① SinCycLinkedlist() 創(chuàng)建單向循環(huán)鏈表
② add(item) 向鏈表中插入數(shù)據(jù)項(xiàng)
③ remove(item) 刪除鏈表中的數(shù)據(jù)項(xiàng)
④ search(item) 在鏈表中查找數(shù)據(jù)項(xiàng)是否存在
⑤ empty() 判斷鏈表是否為空
⑥ size() 返回鏈表中數(shù)據(jù)項(xiàng)的個(gè)數(shù)

單向循環(huán)鏈表操作的示意圖如下：

三、Python實(shí)現(xiàn)

Python的內(nèi)建類型list底層是由C數(shù)組實(shí)現(xiàn)的，list在功能上更接近C++的vector（因?yàn)榭梢詣?dòng)態(tài)調(diào)整數(shù)組大小）。我們都知道，數(shù)組是連續(xù)列表，鏈表是鏈接列表，二者在概念和結(jié)構(gòu)上完全不同，因此list不能用于實(shí)現(xiàn)鏈表。
在C/C++中，通常采用“指針+結(jié)構(gòu)體”來實(shí)現(xiàn)鏈表；而在Python中，則可以采用“引用+類”來實(shí)現(xiàn)鏈表。在下面的代碼中，SinCycLinkedlist類代表單向循環(huán)鏈表，Node類代表鏈表中的一個(gè)節(jié)點(diǎn)：

#!/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()))
運(yùn)行結(jié)果：    
$ 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程序設(shè)計(jì)有所幫助。