QQ登录

只需要一步,快速开始

APP扫码登录

只需要一步,快速开始

手机号码,快捷登录

手机号码,快捷登录

查看: 415|回复: 0

[Python] 有关单向链表的实现

[复制链接]

等级头衔

积分成就    金币 : 2857
   泡泡 : 1516
   精华 : 6
   在线时间 : 1317 小时
   最后登录 : 2025-3-19

丰功伟绩

优秀达人突出贡献荣誉管理论坛元老活跃会员

联系方式
发表于 2023-7-28 10:15:27 | 显示全部楼层 |阅读模式
1 问题
/ i: Y! Z& [. a- y* s- V! X' z7 ?链表在python中使用类(相当于C中的结构)实现链表,实现方法也同C语言一样,但是python中没有指针的概念,于是就采用嵌套的方式,将一个实例赋给指针域,效果就同指针一样。但是同C一样,这样的做法,需要实例化对象起指针的作用,这样会降低数据的存储密度。而有关单向链表的实现还存在些许疑点,本次周博客将针对于此问题展开讨论。, i( R  j0 Y- B3 `+ c) v( d, c4 n$ _
2 方法" g, R( q2 g4 B* _4 s9 @
  • 定义一个创建节点的类;
  • 定义一个单向链表类;
  • 实现单向链表的展示功能.
    - W% T2 H9 M# F. ~9 }* _
通过实验、实践等证明提出的方法是有效的,是能够解决开头提出的问题。
( G+ f7 }7 f8 M
class SingleLinkList(object):
   """单链表"""
   def __init__(self):
       self._head = None
   def is_empty(self):
       """判断链表是否为空"""
       return self._head == None
   def length(self):
       """链表长度"""
       # cur初始时指向头节点
       cur = self._head
       count = 0
       # 尾节点指向None,当未到达尾部时
       while cur != None:
           count += 1
           # 将cur后移一个节点
           cur = cur.next
       return count
   def travel(self):
       """遍历链表"""
       cur = self._head
       while cur != None:
           print(cur.item)
           cur = cur.next
   def add(self, item):
       """头部添加元素"""
       # 先创建一个保存item值的节点
       node = SingleNode(item)
       # 将新节点的链接域next指向头节点,即_head指向的位置
       node.next = self._head
       # 将链表的头_head指向新节点
       self._head = node
   def append(self, item):
       """尾部添加元素"""
       node = SingleNode(item)
       # 先判断链表是否为空,若是空链表,则将_head指向新节点
       if self.is_empty():
           self._head = node
       # 若不为空,则找到尾部,将尾节点的next指向新节点
       else:
           cur = self._head
           while cur.next != None:
               cur = cur.next
           cur.next = node
   def insert(self, pos, item):
       """指定位置添加元素"""
       # 若指定位置pos为第一个元素之前,则执行头部插入
       if pos <= 0:
           self.add(item)
       # 若指定位置超过链表尾部,则执行尾部插入
       elif pos > (self.length() - 1):
           self.append(item)
       # 找到指定位置
       else:
           node = SingleNode(item)
           count = 0
           # pre用来指向指定位置pos的前一个位置pos-1,初始从头节点开始移动到指定位置
           pre = self._head
           while count < (pos - 1):
               count += 1
               pre = pre.next
           # 先将新节点node的next指向插入位置的节点
           node.next = pre.next
           # 将插入位置的前一个节点的next指向新节点
           pre.next = node
   def remove(self, item):
       """删除节点"""
       cur = self._head
       pre = None
       while cur != None:
           # 找到了指定元素
           if cur.item == item:
               # 如果第一个就是删除的节点
               if not pre:
                   # 将头指针指向头节点的后一个节点
                   self._head = cur.next
               else:
                   # 将删除位置前一个节点的next指向删除位置的后一个节点
                   pre.next = cur.next
               break
           else:
               # 继续按链表后移节点
               pre = cur
               cur = cur.next
   def search(self, item):
       """链表查找节点是否存在,并返回True或者False"""
       cur = self._head
       while cur != None:
           if cur.item == item:
               return True
           cur = cur.next
       return False
3 结语
) s  X2 M' Q/ `, B* j4 \! M# n4 S2 j针对有关单向链表的实现的问题,提出本次博客所涉及的方法,通过本次Python实验,证明该方法是有效的,本此的方法还存在许多不足或考虑不周的地方,希望可以在未来的学习过程中找到更有效的方法解决此类问题。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|paopaomj.COM ( 渝ICP备18007172号|渝公网安备50010502503914号 )

GMT+8, 2025-4-4 06:46

Powered by paopaomj X3.5 © 2016-2025 sitemap

快速回复 返回顶部 返回列表