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

刚好实现了目标需求。

总结

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

(0)

相关推荐

  • Python 数据结构之旋转链表

    题目描述:给定一个链表,旋转链表,使得每个节点向右移动k个位置,其中k是一个非负数 样例:给出链表1->2->3->4->5->null和k=2:返回4->5->1->2->3->null 首先,观察一下这个题目要达到的目的,其实,换一种说法,可以这样来描述:给出一个k值,将链表从倒数第k个节点处起之后的部分移动到链表前面,就样例来说,其实是将4->5这一部分移动到整个链表前面,变成4->5->1->2->3->

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python数据结构之翻转链表

    翻转一个链表 样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null 一种比较简单的方法是用"摘除法".就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点. 那样例来说,步骤是这样的: 1. 新建空节点:None 2. 1->None 3. 2->1->None 4. 3->2->1->None 代码就非常简单了: """

  • python单链表实现代码实例

    链表的定义:链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址.由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列.也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域:另一部分用于存储下一个数据元素地址的指针,称为指针域.链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点.链表中的最后一个结点没有后继元素,其指针域为空. python单链表实现代码: 复制代码

  • python双向链表实现实例代码

    示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

  • Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

  • python数据结构之链表的实例讲解

    在程序中,经常需要将⼀组(通常是同为某个类型的)数据元素作为整体 管理和使⽤,需要创建这种元素组,⽤变量记录它们,传进传出函数等. ⼀组数据中包含的元素个数可能发⽣变化(可以增加或删除元素). 对于这种需求,最简单的解决⽅案便是将这样⼀组元素看成⼀个序列,⽤ 元素在序列⾥的位置和顺序,表示实际应⽤中的某种有意义的信息,或者 表示数据之间的某种关系. 这样的⼀组序列元素的组织形式,我们可以将其抽象为线性表.⼀个线性 表是某类元素的⼀个集合,还记录着元素之间的⼀种顺序关系.线性表是 最基本的数据结构

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • python数据结构链表之单向链表(实例讲解)

    单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i

  • Python单链表的简单实现方法

    本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.

随机推荐