Python 实现链表实例代码

Python 实现链表实例代码

前言

算法和数据结构是一个亘古不变的话题，作为一个程序员，掌握常用的数据结构实现是非常非常的有必要的。

实现清单

实现链表，本质上和语言是无关的。但是灵活度却和实现它的语言密切相关。今天用Python来实现一下，包含如下操作：

    ['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)']

生成这样的一个方法清单肯定是不能手动写了，要不然得多麻烦啊，于是我写了个程序，来匹配这些自己实现的方法。代码比较简单，核心思路就是匹配源文件的每一行，找到符合匹配规则的内容，并添加到总的结果集中。

代码如下：

    # coding: utf8

    # @Author: 郭 璞
    # @File: getmethods.py                                 
    # @Time: 2017/4/5                  
    # @Contact: 1064319632@qq.com
    # @blog: http://blog.csdn.net/marksinoberg
    # @Description: 获取一个模块或者类中的所有方法及参数列表

    import re

    def parse(filepath, repattern):
      with open(filepath, 'rb') as f:
        lines = f.readlines()
      # 预解析正则
      rep = re.compile(repattern)
      # 创建保存方法和参数列表的结果集列表
      result = []
      # 开始正式的匹配实现
      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))

链表实现

    # coding: utf8

    # @Author: 郭 璞
    # @File: SingleChain.py                                 
    # @Time: 2017/4/5                  
    # @Contact: 1064319632@qq.com
    # @blog: http://blog.csdn.net/marksinoberg
    # @Description: 单链表实现

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

    class LianBiao(object):

      def __init__(self):
        self.root = None

      # 给单链表添加元素节点
      def addNode(self, data):
        if self.root==None:
          self.root = Node(data=data, next=None)
          return self.root
        else:
          # 有头结点，则需要遍历到尾部节点，进行链表增加操作
          cursor = self.root
          while cursor.next!= None:
            cursor = cursor.next
          cursor.next = Node(data=data, next=None)
          return self.root

      # 在链表的尾部添加新节点，底层调用addNode方法即可
      def append(self, value):
        self.addNode(data=value)

      # 在链表首部添加节点
      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

      # 在链表的指定位置添加节点
      def insert(self, index, value):
        if self.root == None:
          return
        if index<=0 or index >self.size():
          print('index %d 非法， 应该审视一下您的插入节点在整个链表的位置！')
          return
        elif index==1:
          # 如果index==1， 则在链表首部添加即可
          self.prepend(value)
        elif index == self.size()+1:
          # 如果index正好比当前链表长度大一，则添加在尾部即可
          self.append(value)
        else:
          # 如此，在链表中部添加新节点，直接进行添加即可。需要使用计数器来维护插入未知
          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

      # 删除指定位置上的节点
      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的链表节点元素
      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
              # 千万记得更新这个节点，否则会出现死循环。。。
              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

      # 获取指定位置的节点的值
      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

      # 获取链表尾部的值，且不删除该尾部节点
      def peek(self):
        return self.getvalue(self.size())

      # 获取链表尾部节点的值，并删除该尾部节点
      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

      # 单链表逆序实现
      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


      # 修改指定位置节点的值
      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__':
      # 创建一个链表对象
      lianbiao = LianBiao()
      # 判断当前链表是否为空
      print("链表为空%d"%lianbiao.isempty())
      # 判断当前链表是否为空
      lianbiao.addNode(1)
      print("链表为空%d"%lianbiao.isempty())
      # 添加一些节点，方便操作
      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()))
      # 测试指定位置节点值的获取
      print('测试指定位置节点值的获取')
      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()
      # 测试在链表首部添加节点
      print('测试在链表首部添加节点')
      lianbiao.prepend(77)
      lianbiao.prepend(108)
      lianbiao.print()
      # 测试在链表尾部添加节点
      print('测试在链表尾部添加节点')
      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
    测试指定位置节点值的获取
    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  
    测试在链表首部添加节点
    108 77 1  2  6  5  7  
    测试在链表尾部添加节点
    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

刚好实现了目标需求。

总结

今天的内容还是比较基础，也没什么难点。但是看懂和会写还是两码事，没事的时候写写这样的代码还是很有收获的。