python數(shù)據(jù)結構之鏈表詳解
更新時間：2017年09月12日 10:52:47 作者：King_DIG
這篇文章主要為大家詳細介紹了python數(shù)據(jù)結構之鏈表的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下
數(shù)據(jù)結構是計算機科學必須掌握的一門學問，之前很多的教材都是用C語言實現(xiàn)鏈表，因為c有指針，可以很方便的控制內存，很方便就實現(xiàn)鏈表，其他的語言，則沒那么方便，有很多都是用模擬鏈表，不過這次，我不是用模擬鏈表來實現(xiàn)，因為python是動態(tài)語言，可以直接把對象賦值給新的變量。
好了，在說我用python實現(xiàn)前，先簡單說說鏈表吧。在我們存儲一大波數(shù)據(jù)時，我們很多時候是使用數(shù)組，但是當我們執(zhí)行插入操作的時候就是非常麻煩，看下面的例子，有一堆數(shù)據(jù)1,2,3,5,6,7我們要在3和5之間插入4,如果用數(shù)組，我們會怎么做？當然是將5之后的數(shù)據(jù)往后退一位，然后再插入4,這樣非常麻煩，但是如果用鏈表，我就直接在3和5之間插入4就行，聽著就很方便。
那么鏈表的結構是怎么樣的呢？顧名思義，鏈表當然像鎖鏈一樣，由一節(jié)節(jié)節(jié)點連在一起，組成一條數(shù)據(jù)鏈。
鏈表的節(jié)點的結構如下：
data為自定義的數(shù)據(jù)，next為下一個節(jié)點的地址。
鏈表的結構為，head保存首位節(jié)點的地址：
接下來我們來用python實現(xiàn)鏈表
python實現(xiàn)鏈表
首先，定義節(jié)點類Node：
class Node:
'''
data: 節(jié)點保存的數(shù)據(jù)
_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
以上就是鏈表類的要實現(xiàn)的方法。
執(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實現(xiàn)順序表的簡單代碼
- Python中順序表的實現(xiàn)簡單代碼分享
- Python數(shù)據(jù)結構之順序表的實現(xiàn)代碼示例
- python數(shù)據(jù)結構之線性表的順序存儲結構
- python數(shù)據(jù)結構學習之實現(xiàn)線性表的順序
- Python實現(xiàn)的數(shù)據(jù)結構與算法之鏈表詳解
- python數(shù)據(jù)結構鏈表之單向鏈表(實例講解)
- Python數(shù)據(jù)結構之翻轉鏈表
- Python數(shù)據(jù)結構之單鏈表詳解
- Python 數(shù)據(jù)結構之旋轉鏈表
- Python中順序表原理與實現(xiàn)方法詳解
相關文章
這篇文章主要介紹了Python如何根據(jù)字典中的值排序問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-02-02
這篇文章主要介紹了Python探索之實現(xiàn)一個簡單的HTTP服務器，具有一定參考價值，需要的朋友可以了解下。2017-10-10
使用Python獲取愛奇藝電視劇彈幕數(shù)據(jù)的示例代碼
這篇文章主要介紹了用Python獲取愛奇藝電視劇彈幕數(shù)據(jù),本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
Python私有pypi源注冊自定義依賴包Windows詳解
這篇文章主要介紹了Python私有pypi源注冊自定義依賴包Windows,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
正則表達式是可以匹配文本片段的模式，今天的Python就跟大家一起討論一下python中的re模塊，python re模塊感興趣的朋友一起學習吧2016-03-03
今天小編就為大家分享一篇對Python中gensim庫word2vec的使用詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05
Python pandas 重命名索引和列名稱的實現(xiàn)
本文主要介紹了Python pandas 重命名索引和列名稱的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
這篇文章主要為大家詳細介紹了python廣度優(yōu)先搜索得到兩點間最短路徑，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
Centos安裝python3與scapy模塊的問題及解決方法
這篇文章主要介紹了Centos安裝python3與scapy模塊的問題，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-07-07
這篇文章主要介紹了Python2及Python3如何實現(xiàn)兼容切換,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-09-09