python資料結構之連結串列詳解

python資料結構之連結串列詳解

資料結構是電腦科學必須掌握的一門學問,之前很多的教材都是用C語言實現連結串列,因為c有指標,可以很方便的控制記憶體,很方便就實現連結串列,其他的語言,則沒那麼方便,有很多都是用模擬連結串列,不過這次,我不是用模擬連結串列來實現,因為python是動態語言,可以直接把物件賦值給新的變數。

好了,在說我用python實現前,先簡單說說連結串列吧。在我們儲存一大波資料時,我們很多時候是使用陣列,但是當我們執行插入操作的時候就是非常麻煩,看下面的例子,有一堆資料1,2,3,5,6,7我們要在3和5之間插入4,如果用陣列,我們會怎麼做?當然是將5之後的資料往後退一位,然後再插入4,這樣非常麻煩,但是如果用連結串列,我就直接在3和5之間插入4就行,聽著就很方便。

那麼連結串列的結構是怎麼樣的呢?顧名思義,連結串列當然像鎖鏈一樣,由一節節節點連在一起,組成一條資料鏈。

連結串列的節點的結構如下:

data為自定義的資料,next為下一個節點的地址。

連結串列的結構為,head儲存首位節點的地址:

接下來我們來用python實現連結串列

python實現連結串列

首先,定義節點類Node:


class Node:
  '''
  data: 節點儲存的資料
  _next: 儲存下一個節點物件
  '''
  def __init__(self, data, pnext=None):
    self.data = data
    self._next = pnext

  def __repr__(self):
    '''
    用來定義Node的字元輸出,
    print為輸出data
    '''
    return str(self.data)

然後,定義連結串列類:

連結串列要包括:

屬性:

連結串列頭:head

連結串列長度:length

方法:

判斷是否為空: isEmpty()


def isEmpty(self):
  return (self.length == 0

增加一個節點(在連結串列尾新增): append()


def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if not self.head:
    self.head = item
    self.length  = 1

  else:
    node = self.head
    while node._next:
      node = node._next
    node._next = item
    self.length  = 1

刪除一個節點: delete()


#刪除一個節點之後記得要把連結串列長度減一
def delete(self, index):
  if self.isEmpty():
    print "this chain table is empty."
    return

  if index < 0 or index >= self.length:
    print 'error: out of index'
    return
  #要注意刪除第一個節點的情況
  #如果有空的頭節點就不用這樣
  #但是我不喜歡弄頭節點
  if index == 0:
    self.head = self.head._next
    self.length -= 1
    return

  #prev為儲存前導節點
  #node為儲存當前節點
  #當j與index相等時就
  #相當於找到要刪除的節點
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j  = 1

  if j == index:
    prev._next = node._next
    self.length -= 1

修改一個節點: update()


def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
    print 'error: out of index'
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j  = 1

  if j == index:
    node.data = data

查詢一個節點: getItem()


def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
    print "error: out of index"
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j  = 1

  return node.data

查詢一個節點的索引: getIndex()


def getIndex(self, data):
  j = 0
  if self.isEmpty():
    print "this chain table is empty"
    return
  node = self.head
  while node:
    if node.data == data:
      return j
    node = node._next
    j  = 1

  if j == self.length:
    print "%s not found" % str(data)
    return

插入一個節點: insert()


def insert(self, index, dataOrNode):
  if self.isEmpty():
    print "this chain tabale is empty"
    return

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

  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if index == 0:
    item._next = self.head
    self.head = item
    self.length  = 1
    return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j  = 1

  if j == index:
    item._next = node
    prev._next = item
    self.length  = 1

清空連結串列: clear()


def clear(self):
  self.head = None
  self.length = 0

以上就是連結串列類的要實現的方法。

執行的結果:

接下來是完整程式碼:


# -*- coding:utf8 -*-
#/usr/bin/env python
class Node(object):
def __init__(self, data, pnext = None):
self.data = data
self._next = pnext
def __repr__(self):
return str(self.data)
class ChainTable(object):
def __init__(self):
self.head = None
self.length = 0
def isEmpty(self):
return (self.length == 0)
def append(self, dataOrNode):
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if not self.head:
self.head = item
self.length  = 1
else:
node = self.head
while node._next:
node = node._next
node._next = item
self.length  = 1
def delete(self, index):
if self.isEmpty():
print "this chain table is empty."
return
if index < 0 or index >= self.length:
print 'error: out of index'
return
if index == 0:
self.head = self.head._next
self.length -= 1
return
j = 0
node = self.head
prev = self.head
while node._next and j < index:
prev = node
node = node._next
j  = 1
if j == index:
prev._next = node._next
self.length -= 1
def insert(self, index, dataOrNode):
if self.isEmpty():
print "this chain tabale is empty"
return
if index < 0 or index >= self.length:
print "error: out of index"
return
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if index == 0:
item._next = self.head
self.head = item
self.length  = 1
return
j = 0
node = self.head
prev = self.head
while node._next and j < index:
prev = node
node = node._next
j  = 1
if j == index:
item._next = node
prev._next = item
self.length  = 1
def update(self, index, data):
if self.isEmpty() or index < 0 or index >= self.length:
print 'error: out of index'
return
j = 0
node = self.head
while node._next and j < index:
node = node._next
j  = 1
if j == index:
node.data = data
def getItem(self, index):
if self.isEmpty() or index < 0 or index >= self.length:
print "error: out of index"
return
j = 0
node = self.head
while node._next and j < index:
node = node._next
j  = 1
return node.data
def getIndex(self, data):
j = 0
if self.isEmpty():
print "this chain table is empty"
return
node = self.head
while node:
if node.data == data:
return j
node = node._next
j  = 1
if j == self.length:
print "%s not found" % str(data)
return
def clear(self):
self.head = None
self.length = 0
def __repr__(self):
if self.isEmpty():
return "empty chain table"
node = self.head
nlist = ''
while node:
nlist  = str(node.data)   ' '
node = node._next
return nlist
def __getitem__(self, ind):
if self.isEmpty() or ind < 0 or ind >= self.length:
print "error: out of index"
return
return self.getItem(ind)
def __setitem__(self, ind, val):
if self.isEmpty() or ind < 0 or ind >= self.length:
print "error: out of index"
return
self.update(ind, val)
def __len__(self):
return self.length