python數據結構之鏈表詳解

更新時間：2017年09月12日 10:52:47 作者：King_DIG

這篇文章主要為大家詳細介紹了python數據結構之鏈表的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下

數據結構是計算機科學必須掌握的一門學問，之前很多的教材都是用C語言實現鏈表，因為c有指針，可以很方便的控制內存，很方便就實現鏈表，其他的語言，則沒那么方便，有很多都是用模擬鏈表，不過這次，我不是用模擬鏈表來實現，因為python是動態(tài)語言，可以直接把對象賦值給新的變量。

好了，在說我用python實現前，先簡單說說鏈表吧。在我們存儲一大波數據時，我們很多時候是使用數組，但是當我們執(zhí)行插入操作的時候就是非常麻煩，看下面的例子，有一堆數據1,2,3,5,6,7我們要在3和5之間插入4,如果用數組，我們會怎么做？當然是將5之后的數據往后退一位，然后再插入4,這樣非常麻煩，但是如果用鏈表，我就直接在3和5之間插入4就行，聽著就很方便。

那么鏈表的結構是怎么樣的呢？顧名思義，鏈表當然像鎖鏈一樣，由一節(jié)節(jié)節(jié)點連在一起，組成一條數據鏈。

鏈表的節(jié)點的結構如下：

data為自定義的數據，next為下一個節(jié)點的地址。

鏈表的結構為，head保存首位節(jié)點的地址：

接下來我們來用python實現鏈表

python實現鏈表

首先，定義節(jié)點類Node：

class Node:
  '''
  data: 節(jié)點保存的數據
  _next: 保存下一個節(jié)點對象
  '''
  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

增加一個節(jié)點(在鏈表尾添加): 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

刪除一個節(jié)點: delete()

#刪除一個節(jié)點之后記得要把鏈表長度減一
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
  #要注意刪除第一個節(jié)點的情況
  #如果有空的頭節(jié)點就不用這樣
  #但是我不喜歡弄頭節(jié)點
  if index == 0:
    self.head = self.head._next
    self.length -= 1
    return

  #prev為保存前導節(jié)點
  #node為保存當前節(jié)點
  #當j與index相等時就
  #相當于找到要刪除的節(jié)點
  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

修改一個節(jié)點: 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

查找一個節(jié)點: 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

查找一個節(jié)點的索引: 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

插入一個節(jié)點: 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

以上就是鏈表類的要實現的方法。

執(zhí)行的結果：

接下來是完整代碼：

# -*- 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

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

Python如何根據字典中的值排序
這篇文章主要介紹了Python如何根據字典中的值排序問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-02-02
Python探索之實現一個簡單的HTTP服務器
這篇文章主要介紹了Python探索之實現一個簡單的HTTP服務器，具有一定參考價值，需要的朋友可以了解下。
2017-10-10
使用Python獲取愛奇藝電視劇彈幕數據的示例代碼
這篇文章主要介紹了用Python獲取愛奇藝電視劇彈幕數據,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2021-01-01
Python私有pypi源注冊自定義依賴包Windows詳解
這篇文章主要介紹了Python私有pypi源注冊自定義依賴包Windows,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2023-11-11
Python基礎教程之正則表達式基本語法以及re模塊
正則表達式是可以匹配文本片段的模式，今天的Python就跟大家一起討論一下python中的re模塊，python re模塊感興趣的朋友一起學習吧
2016-03-03
對Python中gensim庫word2vec的使用詳解
今天小編就為大家分享一篇對Python中gensim庫word2vec的使用詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-05-05
Python pandas 重命名索引和列名稱的實現
本文主要介紹了Python pandas 重命名索引和列名稱的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2022-07-07
python廣度優(yōu)先搜索得到兩點間最短路徑
這篇文章主要為大家詳細介紹了python廣度優(yōu)先搜索得到兩點間最短路徑，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-01-01
Centos安裝python3與scapy模塊的問題及解決方法
這篇文章主要介紹了Centos安裝python3與scapy模塊的問題，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
2022-07-07
Python2及Python3如何實現兼容切換
這篇文章主要介紹了Python2及Python3如何實現兼容切換,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-09-09

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python數據結構之鏈表詳解

相關文章

最新評論

大家感興趣的內容

最近更新的內容

常用在線小工具