专栏首页算法与编程之美Python|快速掌握单双链表和树

Python|快速掌握单双链表和树

前言:

单双链表、树、二叉树等数据结构的代码实现都存在相似之处,本文将从单链表入手,轻松掌握单双链表、树、二叉树的代码实现。友情提示:请提前了解什么是链表和树。

具体内容

1.单链表

单链表由一个个节点连接而成每个节点包含两部分信息:值(val)、下一个节点(next)。

图一单链表示意图

在接触单链表时,书上说的是节点1指向节点2,也就是next指向下一个节点。在代码实现的时候“next指向下一个节点”就等同于“next”就是下一个节点。

一个节点由两部分组成:值(val)、下一个节点(next)。下一个节点(next)也由两部分组成:val和next。层层嵌套,就形成了一个单链表。

图二单链表结构图

理解这些后,实现单链表的代码就很简单。

class Node(): def __init__(self,val): self.elem=val self.next=None #定义单链表link,第一个节点的值是10link=Node(10)#第一个节点的下一个节点是节点20link.next=Node(20)#第二个节点的下一个节点是30link.next.next=Node(30)#打印第一个节点的值print(link.elem)#返回10#打印第二个节点的值print(link.next.elem) #返回20#打印第三个节点的值print(link.next.next.elem) #返回30

根据上方的代码,用节点类Node实现了一个单链表,但是很明显,这个单链表的操作看起来有点蠢,当需要添加新节点时,还需要知道链表中有多少个节点,节点一多就需要手敲很多个next。

所以需要另一个类,来实现在添加节点时直接添加,而不用去管之前有多少节点。这个类如果还能实现遍历节点之类的操作就更好了。

节点添加:尾插法

#节点类class Node(): def __init__(self,val): self.elem=val #next初始化为空 self.next=None#定义一个空链表类class SigleLink():def __init__(self,node=None): #单链表必须从头部访问,空链表需要记录头部,初始化为空 self.__head=node

尾插法,顾名思义,在单链表的尾部添加元素,如果链表为空,令头部__head等于新加入节点即可。链表不为空,令最后一个节点的next等于新加入的节点,就完成了新节点的插入,由于单链表只能从头部开始操作,所以需要先从头部遍历到最后一个节点。

#从尾部插入元素def add_tail(self,val): #用户只需传入节点值,由函数自带处理成节点 node=Node(val) #分别处理链表为空和不为空的情况 if self.__head==None: #头部为空,链表为空 self.__head=node else: #需要对最后一个节点进行操作,需要先遍历到最后一个节点 cur=self.__head #从头节点开始遍历,cur记录当前操作的节点 while cur.next!=None: #当前节点的next不为空,就将cur移向下一个节点 cur=cur.next cur.next=node

在尾插法的实现中已经包含了节点的遍历,还要再实现从头部插入节点,以及从任意位置插入节点的代码也就很简单了。

#链表节点遍历 def travel(self): cur=self.__head while cur!=None: print(cur.elem,end=' ') cur=cur.next print('')#换行

节点添加:头插法

在链表头部插入新节点(node),令node.next等于原来的头节点,将node标识为新的头节点即可。

#头插法 def add_top(self,val): node=Node(val) node.next=self.__head self.__head=node

节点添加:任意位置插入节点

在下标为pos处插入新节点node,通过遍历找出第pos-1个节点,令node.next等于第pos-1的节点的next,再令第pos-1的节点的next等于node即可.

#获取链表的长度 def length(self): #cur游标,表示当前操作的节点 cur=self.__head #统计有多少节点 count=0 while cur!=None: count+=1 #将cur替换为下一个节点 cur=cur.next return countdef insert(self,pos,val): #输入的位置<0,调用头插法 if pos<=0: self.add_top(val) #输入的位置>节点个数,调用头插法 elif pos>self.length()-1: self.add_tail(val) else: node=Node(val) cur=self.__head count=0 #表示当前节点的下标,从0开始 #遍历到第pos-1个节点时停止 while count<pos-1: count+=1 cur=cur.next node.next=cur.next cur.next=node

2.双链表

单链表每个节点包含:值(val)、下一个节点(next)。双链表多一个信息:上一个节点(last)。只需要对节点类稍加更改即可。

#双链表节点类class Node(): def __init__(self,val): self.elem=val self.last=None self.next=None

(1)遍历

从头部开始遍历,操作和单链表一样。从链表中的某个节点开始遍历,只需要分别向前(last)和向后(next)遍历一次即可。

(2)插入

单链表从尾部插入只需更改上一个节点的next,双链表多一步,还需要更改插入节点的last。其他插入方式,也只需要注意多出来的last即可。

3.二叉树

二叉树与双链表相比,上一个和下一个节点变为左节点和右节点

根据逻辑结构的变化,对遍历,插入等操作做相应变化即可。

#二叉树节点类class Node(): def __init__(self,val): self.elem=val self.left=None self.right=None

4.树

树稍微麻烦一点,因为树中的某个节点有多少子节点是不确定的,所以需要将子节点(son)用列表储存。在遍历节点的时候,注意用个for循环去遍历当前节点的son即可。

#树节点类class Node(): def __init__(self,val): self.elem=val self.son=[]

结语

单双链表、二叉树、树的代码实现都有其共同之处,在弄清楚单链表的实现后,在编写双链表、二叉树、树的代码时,多思考,举一反三,便能很快上手。

END

编 辑 | 王楠岚

责 编 | 马原涛

where2go 团队


本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:马原涛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • laya核心API五分钟速记

    大部分的laya UI组件都可以看做节点,可以看做web开发中,使用JavaScript对html节点进行操作。

    算法与编程之美
  • 谈一谈|如何写好一篇博客

    博客也就是blog,全称Web blog,中文意思是“网络杂志”。后被缩写为blog。博客可以说是一种互联网用户的交流方式,又可以说是记录生活趣事,重要事件,技...

    算法与编程之美
  • Python|字符串的知识

    字符串是字符的序列表示,可以由一对单引号(‘),双引号(“)或三引号(‘’’)构成。其中单引号和双引号都可以表示单行字符,两者作用相同。使用单引号时,双引号可以...

    算法与编程之美
  • python技术面试题(二十二)

    Ask how something can be done rather than say it can't be done.

    小闫同学啊
  • 每日算法题:Day 13

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中...

    算法工程师之路
  • 零基础如何做一个不花钱的个人网站?

    很多网友在后台留言,或者私聊作者有关于作者独立博客是怎么做的,想要作者写一篇教程关于建立独立博客的,由此开始准备建立独立博客的教程。

    机器学习和大数据挖掘
  • SpriteKit动画小游戏

    Spritekit简介 Spritekit是苹果IOS7中引入的一个2D游戏引擎框架,可以实现各种动画效果,在这之前业界比较优秀的游戏引擎是cocos2d,支持...

    MelonTeam
  • [PyQT5]初体验-编译ui文件-自定义槽函数

    原文链接:https://blog.csdn.net/humanking7/article/details/80403189

    祥知道
  • MDK5.30带来两个好消息,RL-TCPnet终于支持多网口了,并且有emWin6.1x可以用了,开心不已

    http://www2.keil.com/mdk5/530 软件更新这块有三件事让我干活又有劲了,真的开心不已: 1、2014年我们发布首版DSP教...

    armfly
  • Scrapy框架系列--数据不保存,就是耍流氓(3)

    OK,通过签名两篇文章《爬虫利器初体验(1)》《听说你的爬虫又被封了?(2)》,我们初体验也过了,爬虫代码健壮性也升级为 PLUS 了。都分析到这个地步了,是不...

    1480

扫码关注云+社区

领取腾讯云代金券