673 views
Python开发 / 数据结构与算法

3.单链表操作

文章目录

单链表操作,具体实施

#!/usr/bin/env python
# coding:utf8
# ++++++++++++description++++++++++++#
"""
@author:ying
@contact:1074020480@qq.com
@site:
@software: PyCharm
@file: ttt.py
@time: 2019/11/8 上午10:08
"""

# +++++++++++++++++++++++++++++++++++#
# 创建单链表
class SingleNode(object):
    def __init__(self, arg):
        """初始化一个单链表,且只有一个值"""
        self.arg = arg
        self.next = None

# SingleNode(100)


# 单链表操作
class SingleNodeContorl(object):
    def __init__(self, node=None):
        """初始化参数,将节点当成参数传入进来"""
        self.__head = node

    def lenght(self):
        """判断长度"""
        cur = self.__head  # 定位当前游标位置
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def is_empt(self):
        """判断是否为空"""
        if self.__head == None:
            return True
        else:
            return False

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur != None:
            print(cur.arg, end=' ')
            cur = cur.next
        print()

    def append(self, arg):
        """尾部新增数据"""

        node = SingleNode(arg)  # 新的单链表
        if self.is_empt():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def add(self,arg):
        """头部新增数据"""
        node = SingleNode(arg)  # 新的单链表
        node.next=self.__head   # 新表的next地址指向当前的头地址__head
        self.__head=node        # 新的头地址为新表node

    def insert(self,pos,arg):
        """任意索引位置插入数据"""
        cur = SingleNode(arg)  # 新的单链表,带索引
        pre=self.__head
        if pos <=0:            #当索引为0,直接add
            self.add(cur.arg)
        elif pos > self.lenght()-1: #当索引大于总长度,直接append
            self.append(cur.arg)
        else:
            count=0
            while count < pos-1: #定位到索引的上一个节点
                # print(count)
                count+=1
                pre=pre.next
            # 先定尾部再定头部,将pre.next付给cur.next,然后再将cul的值付给pre.next,形成首尾相连
            cur.next=pre.next
            pre.next=cur

    def search(self, arg):
        """查找节点是否存在"""
        cur = self.__head
        while cur != None:
            if cur.arg == arg:
                return True
            else:
                # 让游标继续执行
                cur = cur.next
        return False

    def remove(self, arg):
        """删除节点"""
        cur = self.__head
        pre = None
        while cur != None:
            # 锁定需要删除的值
            if cur.arg == arg:
                # 删除第一个
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    # 直接将上一个节点的下一个值指向当前节点的下一个值,等于就是将当前节点从中脱离出来,删除(因为上下都没有链接)
                    pre.next = cur.next
                break
            else:
                # 没找到就一直往下走,此时上节点的游标与当前节点的游标都要往下走,不然就玩脱了
                pre = cur
                cur = cur.next

    def pop(self):
        """删除最后一个"""
        cur = self.__head
        if cur != None:
            while cur.next != None:
            # 游标一直往下走,知道next为none,就将当前的值删除,因为他就是最后一个
                cur=cur.next
            self.remove(cur.arg)


snc=SingleNodeContorl()
snc.append(1111)
print('is_empt: ',snc.is_empt())
print('lenght: ',snc.lenght())
snc.add(2222)
snc.add(333)
snc.remove(333)
snc.insert(3,999)
print('search: ',snc.search(5555))

snc.pop()
snc.pop()


print('travel:',end='' )
snc.travel()
影子专属博客 赣ICP备17013143号