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

本文实例讲述了python实现的数据结构与算法之链表。分享给大家供大家参考。具体分析如下:

一、概述

链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接。
根据结构的不同,链表可以分为单向链表、单向循环链表、双向链表、双向循环链表等。其中,单向链表和单向循环链表的结构如下图所示:

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

二、ADT

这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异。单向循环链表ADT(抽象数据类型)一般提供以下接口:

立即学习“Python免费学习笔记(深入)”;

① SinCycLinkedlist() 创建单向循环链表
② add(item) 向链表中插入数据项
③ remove(item) 删除链表中的数据项
④ search(item) 在链表中查找数据项是否存在
⑤ empty() 判断链表是否为空
⑥ size() 返回链表中数据项的个数

单向循环链表操作的示意图如下:

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

三、Python实现

Python的内建类型list底层是由C数组实现的,list在功能上更接近C++的vector(因为可以动态调整数组大小)。我们都知道,数组是连续列表,链表是链接列表,二者在概念和结构上完全不同,因此list不能用于实现链表。
在C/C++中,通常采用“指针+结构体”来实现链表;而在Python中,则可以采用“引用+类”来实现链表。在下面的代码中,SinCycLinkedlist类代表单向循环链表,Node类代表链表中的一个节点:

#!/usr/bin/env python# -*- coding: utf-8 -*-class Node:  def __init__(self, initdata):    self.__data = initdata    self.__next = None  def getData(self):    return self.__data  def getNext(self):    return self.__next  def setData(self, newdata):    self.__data = newdata  def setNext(self, newnext):    self.__next = newnextclass SinCycLinkedlist:  def __init__(self):    self.head = Node(None)    self.head.setNext(self.head)  def add(self, item):    temp = Node(item)    temp.setNext(self.head.getNext())    self.head.setNext(temp)  def remove(self, item):    prev = self.head    while prev.getNext() != self.head:      cur = prev.getNext()      if cur.getData() == item:        prev.setNext(cur.getNext())      prev = prev.getNext()  def search(self, item):    cur = self.head.getNext()    while cur != self.head:      if cur.getData() == item:        return True      cur = cur.getNext()    return False  def empty(self):    return self.head.getNext() == self.head  def size(self):    count = 0    cur = self.head.getNext()    while cur != self.head:      count += 1      cur = cur.getNext()    return countif __name__ == '__main__':  s = SinCycLinkedlist()  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))  s.add(19)  s.add(86)  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))  print('86 is%s in s' % ('' if s.search(86) else ' not',))  print('4 is%s in s' % ('' if s.search(4) else ' not',))  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))  s.remove(19)  print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

登录后复制

运行结果:

$ python sincyclinkedlist.pys.empty() == True, s.size() == 0s.empty() == False, s.size() == 286 is in s4 is not in ss.empty() == False, s.size() == 2s.empty() == False, s.size() == 1

登录后复制

希望本文所述对大家的Python程序设计有所帮助。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至253000106@qq.com举报,一经查实,本站将立刻删除。

发布者:PHP中文网,转转请注明出处:https://www.chuangxiangniao.com/p/2295454.html

(0)
上一篇 2025年2月28日 02:59:08
下一篇 2025年2月28日 02:59:25

AD推荐 黄金广告位招租... 更多推荐

相关推荐

  • Python实现的数据结构与算法之基本搜索详解

    本文实例讲述了python实现的数据结构与算法之基本搜索。分享给大家供大家参考。具体分析如下: 一、顺序搜索 顺序搜索 是最简单直观的搜索方法:从列表开头到末尾,逐个比较待搜索项与列表中的项,直到找到目标项(搜索成功)或者 超出搜索范围 (…

    编程技术 2025年2月28日
    000
  • Python实现的飞速中文网小说下载脚本

    1.javascript 加密什么的最讨厌了 :-( 1).eval 一个不依赖外部变量的函数立即调用很天真,看我 nodejs 来干掉你!2).HTTP 请求的验证首先尝试 Referer,「小甜饼」没有想像中的那么重要。3).curl …

    编程技术 2025年2月28日
    200
  • Python中使用PyQt把网页转换成PDF操作代码实例

    代码很简单,功能也很简单 =w= webpage2pdf #!/usr/bin/env python3 import sys try: from PyQt4 import QtWebKit from PyQt4.QtCore import …

    编程技术 2025年2月28日
    200
  • Python里disconnect UDP套接字的方法

    udp 套接字是可以使用 connect 系统调用连接到指定的地址的。从此以后,这个套接字只会接收来自这个地址的数据,而且可以使用 send 系统调用直接发数据而不用指定地址。可以再次调用 connect 来连接到别的地方。但是在 pyth…

    编程技术 2025年2月28日
    200
  • Python实现的Google IP 可用性检测脚本

    需要 python 3.4+,一个参数用来选择测试搜索服务还是 gae 服务。测试 gae 服务的话需要先修改开头的两个变量。从标准输入读取 ip 地址或者 ip 段(形如 192.168.0.0/16)列表,每行一个。可用 ip 输出到标…

    编程技术 2025年2月28日
    200
  • Python实现提取文章摘要的方法

    本文实例讲述了python实现提取文章摘要的方法。分享给大家供大家参考。具体如下: 一、概述 在博客系统的文章列表中,为了更有效地呈现文章内容,从而让读者更有针对性地选择阅读,通常会同时提供文章的标题和摘要。 一篇文章的内容可以是纯文本格式…

    编程技术 2025年2月28日
    200
  • Python与Redis的连接教程

    今天在写zabbix storm job监控脚本的时候用到了python的redis模块,之前也有用过,但是没有过多的了解,今天看了下相关的api和源码,看到有ConnectionPool的实现,这里简单说下。在ConnectionPool…

    编程技术 2025年2月28日
    200
  • python中map、any、all函数用法分析

    本文实例讲述了python中map、any、all函数用法。分享给大家供大家参考。具体分析如下: 最近想学python,就一直比较关注python,昨天在python吧看到有个帖子提问怎么在python中怎么判断密码是否符合规范,回帖中有很…

    编程技术 2025年2月28日
    200
  • Python的Flask框架中web表单的教程

     概要 在前面章节我们为主页定义了一个简单的模板,部分尚未实现的模块如用户或帖子等使用模拟的对象作为临时占位。 本章我们将看到如何利用web表单填补这些空白。 web表单是web应用中最基本的构建要素,我们将通过表单来实现用户发帖和应用登录…

    2025年2月28日
    200
  • python实现的jpg格式图片修复代码

    最近为客户修复损坏的jpg写的,效果还可以,但不保证适用任何情况。 如果你有损坏照片,不妨试一试,如果可以使用给我留个言哦。 复制代码 代码如下:# -*- coding: utf8 -*-# !/usr/bin/env python __…

    编程技术 2025年2月28日
    200

发表回复

登录后才能评论