Python 實(shí)現(xiàn)鏈表實(shí)例代碼

前言

算法和數(shù)據(jù)結(jié)構(gòu)是一個(gè)亙古不變的話題，作為一個(gè)程序員，掌握常用的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)是非常非常的有必要的。

實(shí)現(xiàn)清單

實(shí)現(xiàn)鏈表，本質(zhì)上和語(yǔ)言是無(wú)關(guān)的。但是靈活度卻和實(shí)現(xiàn)它的語(yǔ)言密切相關(guān)。今天用Python來(lái)實(shí)現(xiàn)一下，包含如下操作：

['addNode(self, data)']['append(self, value)']['prepend(self, value)']['insert(self, index, value)']['delNode(self, index)']['delValue(self, value)']['isempty(self)']['truncate(self)']['getvalue(self, index)']['peek(self)']['pop(self)']['reverse(self)']['delDuplecate(self)']['updateNode(self, index, value)']['size(self)']['print(self)']

生成這樣的一個(gè)方法清單肯定是不能手動(dòng)寫(xiě)了，要不然得多麻煩啊，于是我寫(xiě)了個(gè)程序，來(lái)匹配這些自己實(shí)現(xiàn)的方法。代碼比較簡(jiǎn)單，核心思路就是匹配源文件的每一行，找到符合匹配規(guī)則的內(nèi)容，并添加到總的結(jié)果集中。

代碼如下：

# coding: utf8# @Author: 郭 璞# @File: getmethods.py                                 # @Time: 2017/4/5                  # @Contact: 1064319632@qq.com# @blog: http://blog.csdn.net/marksinoberg# @Description: 獲取一個(gè)模塊或者類(lèi)中的所有方法及參數(shù)列表import redef parse(filepath, repattern):  with open(filepath, 'rb') as f:    lines = f.readlines()  # 預(yù)解析正則  rep = re.compile(repattern)  # 創(chuàng)建保存方法和參數(shù)列表的結(jié)果集列表  result = []  # 開(kāi)始正式的匹配實(shí)現(xiàn)  for line in lines:    res = re.findall(rep, str(line))    print("{}的匹配結(jié)果{}".format(str(line), res))    if len(res)!=0 or res is not None:      result.append(res)    else:      continue  return [item for item in result if item !=[]]if __name__ == '__main__':  repattern = "def (.[^_0-9]+/(.*?/)):"  filepath = './SingleChain.py'  result = parse(filepath, repattern)  for item in result:    print(str(item))

鏈表實(shí)現(xiàn)

# coding: utf8# @Author: 郭 璞# @File: SingleChain.py                                 # @Time: 2017/4/5                  # @Contact: 1064319632@qq.com# @blog: http://blog.csdn.net/marksinoberg# @Description: 單鏈表實(shí)現(xiàn)class Node(object):  def __init__(self, data, next):    self.data = data    self.next = nextclass LianBiao(object):  def __init__(self):    self.root = None  # 給單鏈表添加元素節(jié)點(diǎn)  def addNode(self, data):    if self.root==None:      self.root = Node(data=data, next=None)      return self.root    else:      # 有頭結(jié)點(diǎn)，則需要遍歷到尾部節(jié)點(diǎn)，進(jìn)行鏈表增加操作      cursor = self.root      while cursor.next!= None:        cursor = cursor.next      cursor.next = Node(data=data, next=None)      return self.root  # 在鏈表的尾部添加新節(jié)點(diǎn)，底層調(diào)用addNode方法即可  def append(self, value):    self.addNode(data=value)  # 在鏈表首部添加節(jié)點(diǎn)  def prepend(self, value):    if self.root == None:      self.root = Node(value, None)    else:      newroot = Node(value, None)      # 更新root索引      newroot.next = self.root      self.root = newroot  # 在鏈表的指定位置添加節(jié)點(diǎn)  def insert(self, index, value):    if self.root == None:      return    if index<=0 or index >self.size():      print('index %d 非法， 應(yīng)該審視一下您的插入節(jié)點(diǎn)在整個(gè)鏈表的位置！')      return    elif index==1:      # 如果index==1， 則在鏈表首部添加即可      self.prepend(value)    elif index == self.size()+1:      # 如果index正好比當(dāng)前鏈表長(zhǎng)度大一，則添加在尾部即可      self.append(value)    else:      # 如此，在鏈表中部添加新節(jié)點(diǎn)，直接進(jìn)行添加即可。需要使用計(jì)數(shù)器來(lái)維護(hù)插入未知      counter = 2      pre = self.root      cursor = self.root.next      while cursor!=None:        if counter == index:          temp = Node(value, None)          pre.next = temp          temp.next = cursor          break        else:          counter += 1          pre = cursor          cursor = cursor.next  # 刪除指定位置上的節(jié)點(diǎn)  def delNode(self, index):    if self.root == None:      return    if index<=0 or index > self.size():      return    # 對(duì)第一個(gè)位置需要小心處理    if index == 1:      self.root = self.root.next    else:      pre = self.root      cursor = pre.next      counter = 2      while cursor!= None:        if index == counter:          print('can be here!')          pre.next = cursor.next          break        else:          pre = cursor          cursor = cursor.next          counter += 1  # 刪除值為value的鏈表節(jié)點(diǎn)元素  def delValue(self, value):    if self.root == None:      return    # 對(duì)第一個(gè)位置需要小心處理    if self.root.data == value:      self.root = self.root.next    else:      pre = self.root      cursor = pre.next      while cursor!=None:        if cursor.data == value:          pre.next = cursor.next          # 千萬(wàn)記得更新這個(gè)節(jié)點(diǎn)，否則會(huì)出現(xiàn)死循環(huán)。。。          cursor = cursor.next          continue        else:          pre = cursor          cursor = cursor.next  # 判斷鏈表是否為空  def isempty(self):    if self.root == None or self.size()==0:      return True    else:      return False  # 刪除鏈表及其內(nèi)部所有元素  def truncate(self):    if self.root == None or self.size()==0:      return    else:      cursor = self.root      while cursor!= None:        cursor.data = None        cursor = cursor.next      self.root = None      cursor = None  # 獲取指定位置的節(jié)點(diǎn)的值  def getvalue(self, index):    if self.root is None or self.size()==0:      print('當(dāng)前鏈表為空！')      return None    if index<=0 or index>self.size():      print("index %d不合法！"%index)      return None    else:      counter = 1      cursor = self.root      while cursor is not None:        if index == counter:          return cursor.data        else:          counter += 1          cursor = cursor.next  # 獲取鏈表尾部的值，且不刪除該尾部節(jié)點(diǎn)  def peek(self):    return self.getvalue(self.size())  # 獲取鏈表尾部節(jié)點(diǎn)的值，并刪除該尾部節(jié)點(diǎn)  def pop(self):    if self.root is None or self.size()==0:      print('當(dāng)前鏈表已經(jīng)為空！')      return None    elif self.size()==1:      top = self.root.data      self.root = None      return top    else:      pre = self.root      cursor = pre.next      while cursor.next is not None:        pre = cursor        cursor = cursor.next      top = cursor.data      cursor = None      pre.next = None      return top  # 單鏈表逆序?qū)崿F(xiàn)  def reverse(self):    if self.root is None:      return    if self.size()==1:      return    else:      # post = None      pre = None      cursor = self.root      while cursor is not None:        # print('逆序操作逆序操作')        post = cursor.next        cursor.next = pre        pre = cursor        cursor = post      # 千萬(wàn)不要忘記了把逆序后的頭結(jié)點(diǎn)賦值給root，否則無(wú)法正確顯示      self.root = pre  # 刪除鏈表中的重復(fù)元素  def delDuplecate(self):    # 使用一個(gè)map來(lái)存放即可，類(lèi)似于變形的“桶排序”    dic = {}    if self.root == None:      return    if self.size() == 1:      return    pre = self.root    cursor = pre.next    dic = {}    # 為字典賦值    temp = self.root    while temp!=None:      dic[str(temp.data)] = 0      temp = temp.next    temp = None    # 開(kāi)始實(shí)施刪除重復(fù)元素的操作    while cursor!=None:      if dic[str(cursor.data)] == 1:        pre.next = cursor.next        cursor = cursor.next      else:        dic[str(cursor.data)] += 1        pre = cursor        cursor = cursor.next  # 修改指定位置節(jié)點(diǎn)的值  def updateNode(self, index, value):    if self.root == None:      return    if index<0 or index>self.size():      return    if index == 1:      self.root.data = value      return    else:      cursor = self.root.next      counter = 2      while cursor!=None:        if counter == index:          cursor.data = value          break        cursor = cursor.next        counter += 1  # 獲取單鏈表的大小  def size(self):    counter = 0    if self.root == None:      return counter    else:      cursor = self.root      while cursor!=None:        counter +=1        cursor = cursor.next      return counter  # 打印鏈表自身元素  def print(self):    if(self.root==None):      return    else:      cursor = self.root      while cursor!=None:        print(cursor.data, end='/t')        cursor = cursor.next      print()if __name__ == '__main__':  # 創(chuàng)建一個(gè)鏈表對(duì)象  lianbiao = LianBiao()  # 判斷當(dāng)前鏈表是否為空  print("鏈表為空%d"%lianbiao.isempty())  # 判斷當(dāng)前鏈表是否為空  lianbiao.addNode(1)  print("鏈表為空%d"%lianbiao.isempty())  # 添加一些節(jié)點(diǎn)，方便操作  lianbiao.addNode(2)  lianbiao.addNode(3)  lianbiao.addNode(4)  lianbiao.addNode(6)  lianbiao.addNode(5)  lianbiao.addNode(6)  lianbiao.addNode(7)  lianbiao.addNode(3)  # 打印當(dāng)前鏈表所有值  print('打印當(dāng)前鏈表所有值')  lianbiao.print()  # 測(cè)試對(duì)鏈表求size的操作  print("鏈表的size: "+str(lianbiao.size()))  # 測(cè)試指定位置節(jié)點(diǎn)值的獲取  print('測(cè)試指定位置節(jié)點(diǎn)值的獲取')  print(lianbiao.getvalue(1))  print(lianbiao.getvalue(lianbiao.size()))  print(lianbiao.getvalue(7))  # 測(cè)試刪除鏈表中指定值， 可重復(fù)性刪除  print('測(cè)試刪除鏈表中指定值， 可重復(fù)性刪除')  lianbiao.delNode(4)  lianbiao.print()  lianbiao.delValue(3)  lianbiao.print()  # 去除鏈表中的重復(fù)元素  print('去除鏈表中的重復(fù)元素')  lianbiao.delDuplecate()  lianbiao.print()  # 指定位置的鏈表元素的更新測(cè)試  print('指定位置的鏈表元素的更新測(cè)試')  lianbiao.updateNode(6, 99)  lianbiao.print()  # 測(cè)試在鏈表首部添加節(jié)點(diǎn)  print('測(cè)試在鏈表首部添加節(jié)點(diǎn)')  lianbiao.prepend(77)  lianbiao.prepend(108)  lianbiao.print()  # 測(cè)試在鏈表尾部添加節(jié)點(diǎn)  print('測(cè)試在鏈表尾部添加節(jié)點(diǎn)')  lianbiao.append(99)  lianbiao.append(100)  lianbiao.print()  # 測(cè)試指定下標(biāo)的插入操作  print('測(cè)試指定下標(biāo)的插入操作')  lianbiao.insert(1, 10010)  lianbiao.insert(3, 333)  lianbiao.insert(lianbiao.size(), 99999)  lianbiao.print()  # 測(cè)試peek 操作  print('測(cè)試peek 操作')  print(lianbiao.peek())  lianbiao.print()  # 測(cè)試pop 操作  print('測(cè)試pop 操作')  print(lianbiao.pop())  lianbiao.print()  # 測(cè)試單鏈表的逆序輸出  print('測(cè)試單鏈表的逆序輸出')  lianbiao.reverse()  lianbiao.print()  # 測(cè)試鏈表的truncate操作  print('測(cè)試鏈表的truncate操作')  lianbiao.truncate()  lianbiao.print()