數據結構是計算機科學必須掌握的一門學問，之前很多的教材都是用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 pythonclass 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
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網
新聞熱點
疑難解答
