欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄

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

系統(tǒng) 1608 0

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

前言

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

實現(xiàn)清單

實現(xiàn)鏈表，本質上和語言是無關的。但是靈活度卻和實現(xiàn)它的語言密切相關。今天用Python來實現(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)']

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

代碼如下： 

            
# coding: utf8

# @Author: 郭 璞
# @File: getmethods.py                                 
# @Time: 2017/4/5                  
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 獲取一個模塊或者類中的所有方法及參數(shù)列表

import re

def parse(filepath, repattern):
  with open(filepath, 'rb') as f:
    lines = f.readlines()
  # 預解析正則
  rep = re.compile(repattern)
  # 創(chuàng)建保存方法和參數(shù)列表的結果集列表
  result = []
  # 開始正式的匹配實現(xiàn)
  for line in lines:
    res = re.findall(rep, str(line))
    print("{}的匹配結果{}".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))

鏈表實現(xiàn) 

            
# coding: utf8

# @Author: 郭 璞
# @File: SingleChain.py                                 
# @Time: 2017/4/5                  
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: 單鏈表實現(xiàn)

class Node(object):
  def __init__(self, data, next):
    self.data = data
    self.next = next

class LianBiao(object):

  def __init__(self):
    self.root = None

  # 給單鏈表添加元素節(jié)點
  def addNode(self, data):
    if self.root==None:
      self.root = Node(data=data, next=None)
      return self.root
    else:
      # 有頭結點，則需要遍歷到尾部節(jié)點，進行鏈表增加操作
      cursor = self.root
      while cursor.next!= None:
        cursor = cursor.next
      cursor.next = Node(data=data, next=None)
      return self.root

  # 在鏈表的尾部添加新節(jié)點，底層調用addNode方法即可
  def append(self, value):
    self.addNode(data=value)

  # 在鏈表首部添加節(jié)點
  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é)點
  def insert(self, index, value):
    if self.root == None:
      return
    if index<=0 or index >self.size():
      print('index %d 非法， 應該審視一下您的插入節(jié)點在整個鏈表的位置！')
      return
    elif index==1:
      # 如果index==1， 則在鏈表首部添加即可
      self.prepend(value)
    elif index == self.size()+1:
      # 如果index正好比當前鏈表長度大一，則添加在尾部即可
      self.append(value)
    else:
      # 如此，在鏈表中部添加新節(jié)點，直接進行添加即可。需要使用計數(shù)器來維護插入未知
      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é)點
  def delNode(self, index):
    if self.root == None:
      return
    if index<=0 or index > self.size():
      return
    # 對第一個位置需要小心處理
    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é)點元素
  def delValue(self, value):
    if self.root == None:
      return
    # 對第一個位置需要小心處理
    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
          # 千萬記得更新這個節(jié)點，否則會出現(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

  # 刪除鏈表及其內部所有元素
  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é)點的值
  def getvalue(self, index):
    if self.root is None or self.size()==0:
      print('當前鏈表為空！')
      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é)點
  def peek(self):
    return self.getvalue(self.size())

  # 獲取鏈表尾部節(jié)點的值，并刪除該尾部節(jié)點
  def pop(self):
    if self.root is None or self.size()==0:
      print('當前鏈表已經為空！')
      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

  # 單鏈表逆序實現(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
      # 千萬不要忘記了把逆序后的頭結點賦值給root，否則無法正確顯示
      self.root = pre

  # 刪除鏈表中的重復元素
  def delDuplecate(self):
    # 使用一個map來存放即可，類似于變形的“桶排序”
    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
    # 開始實施刪除重復元素的操作
    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é)點的值
  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)建一個鏈表對象
  lianbiao = LianBiao()
  # 判斷當前鏈表是否為空
  print("鏈表為空%d"%lianbiao.isempty())
  # 判斷當前鏈表是否為空
  lianbiao.addNode(1)
  print("鏈表為空%d"%lianbiao.isempty())
  # 添加一些節(jié)點，方便操作
  lianbiao.addNode(2)
  lianbiao.addNode(3)
  lianbiao.addNode(4)
  lianbiao.addNode(6)
  lianbiao.addNode(5)
  lianbiao.addNode(6)
  lianbiao.addNode(7)
  lianbiao.addNode(3)
  # 打印當前鏈表所有值
  print('打印當前鏈表所有值')
  lianbiao.print()
  # 測試對鏈表求size的操作
  print("鏈表的size: "+str(lianbiao.size()))
  # 測試指定位置節(jié)點值的獲取
  print('測試指定位置節(jié)點值的獲取')
  print(lianbiao.getvalue(1))
  print(lianbiao.getvalue(lianbiao.size()))
  print(lianbiao.getvalue(7))
  # 測試刪除鏈表中指定值， 可重復性刪除
  print('測試刪除鏈表中指定值， 可重復性刪除')
  lianbiao.delNode(4)
  lianbiao.print()
  lianbiao.delValue(3)
  lianbiao.print()
  # 去除鏈表中的重復元素
  print('去除鏈表中的重復元素')
  lianbiao.delDuplecate()
  lianbiao.print()
  # 指定位置的鏈表元素的更新測試
  print('指定位置的鏈表元素的更新測試')
  lianbiao.updateNode(6, 99)
  lianbiao.print()
  # 測試在鏈表首部添加節(jié)點
  print('測試在鏈表首部添加節(jié)點')
  lianbiao.prepend(77)
  lianbiao.prepend(108)
  lianbiao.print()
  # 測試在鏈表尾部添加節(jié)點
  print('測試在鏈表尾部添加節(jié)點')
  lianbiao.append(99)
  lianbiao.append(100)
  lianbiao.print()
  # 測試指定下標的插入操作
  print('測試指定下標的插入操作')
  lianbiao.insert(1, 10010)
  lianbiao.insert(3, 333)
  lianbiao.insert(lianbiao.size(), 99999)
  lianbiao.print()
  # 測試peek 操作
  print('測試peek 操作')
  print(lianbiao.peek())
  lianbiao.print()
  # 測試pop 操作
  print('測試pop 操作')
  print(lianbiao.pop())
  lianbiao.print()
  # 測試單鏈表的逆序輸出
  print('測試單鏈表的逆序輸出')
  lianbiao.reverse()
  lianbiao.print()
  # 測試鏈表的truncate操作
  print('測試鏈表的truncate操作')
  lianbiao.truncate()
  lianbiao.print()

代碼運行的結果如何呢？是否能滿足我們的需求，且看打印的結果: 

            
D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py
鏈表為空1
鏈表為空0
打印當前鏈表所有值
1  2  3  4  6  5  6  7  3  
鏈表的size: 9
測試指定位置節(jié)點值的獲取
1
3
6
測試刪除鏈表中指定值， 可重復性刪除
can be here!
1  2  3  6  5  6  7  3  
1  2  6  5  6  7  
去除鏈表中的重復元素
1  2  6  5  7  
指定位置的鏈表元素的更新測試
1  2  6  5  7  
測試在鏈表首部添加節(jié)點
108 77 1  2  6  5  7  
測試在鏈表尾部添加節(jié)點
108 77 1  2  6  5  7  99 100 
測試指定下標的插入操作
10010  108 333 77 1  2  6  5  7  99 99999  100 
測試peek 操作
100
10010  108 333 77 1  2  6  5  7  99 99999  100 
測試pop 操作
100
10010  108 333 77 1  2  6  5  7  99 99999  
測試單鏈表的逆序輸出
99999  99 7  5  6  2  1  77 333 108 10010  
測試鏈表的truncate操作

Process finished with exit code 0

剛好實現(xiàn)了目標需求。

總結

今天的內容還是比較基礎，也沒什么難點。但是看懂和會寫還是兩碼事，沒事的時候寫寫這樣的代碼還是很有收獲的。


更多文章、技術交流、商務合作、聯(lián)系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯(lián)系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧，站長會非常 感謝您的哦！！！

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板： 亚洲欧美另类视频 | 国产1区在线观看 | 久久久久无码国产精品一区 | 2021国产精品成人免费视频 | 日韩中文字幕在线有码视频网 | 久久久久国产精品人 | 国产精品国色综合久久 | 日本一区中文字幕 | 蜜桃在线视频 | 国产98在线传媒在线视频 | 国产二区在线播放 | 国产精品爱久久久久久久电影 | 亚洲不卡视频 | 成年美女黄的视频网站 | 久久www免费人成看片高清 | 欧美亚洲一区二区三区在线 | 成人在线小视频 | 免费看国产片在线观看 | 91亚洲国产成人久久精品网站 | 色偷偷噜噜噜亚洲男人 | 亚洲高清视频一区二区 | 国产一卡2卡三卡4卡免费网站 | 亚洲视频www | 久久亚洲国产成人亚 | 在线中文字幕视频 | 三A级做爰片免费观看国产电影 | 黄色片免费看网站 | 国产精品成人观看视频国产 | 欧美日韩中文在线 | 国产日本在线播放 | 亚洲综合色视频在线观看 | 久久久亚洲欧洲日产国码606 | 欧美在线观看a | 久久国产精品免费网站 | 欧美另类视频一区 | 午夜精品久久久久久久99蜜桃i | 亚洲 欧美 日韩 在线 香蕉 | 91在线视频免费观看 | 天天插天天操天天射 | 日日摸夜夜添夜夜添亚洲女人 | 国产情侣啪啪 |