单链表-Python实现-jupyter->markdown 格式测试

当前位置:

首页 > Python基础教程 >

单链表-Python实现-jupyter->markdown 格式测试

单链表引入

顺序表
理解Python变量的本质: 变量存储的不是值,是值的地址
理解Python的 "="表示的是指向关系
案例: 交换a,b的值, a=10, b=20
- a, b = 20, 10
- t0: a这块内存(也有id), 存储的是10这个值的地址(可能是0x111), b存储的是20这个值(整型4个字节)的地址(可能是0x222)
- t1: a现在指向b的值的地址(a存储0x222), b指向(存储)10的地址(0x111)
Pyhton变量的本质: 指针. 所以Pyhton在定义变量时不必声明变量类型, 因为Pyhton变量根本就不直接存储值, 存储的是值的地址, 通过地址去取值.
真正理解: Pyhton 一切皆对象(存地址嘛, 变量, 容器, 函数, 类...都只是一块地址而已), so 常看到把一个类, 一个函数=给一个变量,就不足为奇了.

a, b = 10, 20 
print('交换前',a,b)
# 交换: 从等号右边开始看, 即把b存储20的地址,现在用a变量存储; 
# 将a变量存储10的地址,现在用b去指向, 从而实现了a,b互相交换
# 本质上, 10,20这两个值的地址并未改变, 只是其被引用的变量改变了而已, 改变的是引用
a, b = b, a
print('交换后',a, b)

交换前 10 20
交换后 20 10

# 函数也是一块内存地址而已

def add(x, y):
    return x + y

print(add(3,4))

f = add  # 将函数赋值给一个变量f, 即用f来指向这块函数的地址
print(f(3,4))

构造节点类

为什么要用类: 节点 = 数据取 + 指针区(指向下一个节点的地址)
类: 属性 + 操作的封装

插入: Python3定义类用不用继承object的区别

# Python3 编写类的是在, object 有无的区别

class A:
    name = "youge"

    
class B(object):
    name = 'youge'
    
    
if __name__ == '__main__':
    
    a, b = A(), B()
    
    print('无object的类拥有:', dir(a))
    print('有object的类拥有:', dir(b))

无object的类拥有: ['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'name']
有object的类拥有: ['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'name']

class Node(object):
    """"节点类""""
    def __init__(self, data=None):
        self.data = data
        self.next = None  # Pyhton 的 "=" 就直接想象成 ----> 指向即可(指向下一个节点对象)

node1 = Node(123)  # 实例化一个节点对象

print('这是一个节点对象, 包含属性和操作', node1)

print(f'该节点的数据是:{node1.data}, 指向的节点对象是:{node1.next}')

这是一个节点对象, 包含属性和操作 <__main__.Node object at 0x0000021B939406A0>
该节点的数据是:123, 指向的节点对象是:None

单链表类ADT

is_empty() 判断链表是否为空
lenghth() 链表的长度(元素个数)
travel 遍历整个链表
add(item) 从链表头部增加元素(值)
append(item) 从链表尾部增加元素
insert(pos, item) 从指定位置(下标)增加元素
remove(item) 删除节点
search(item)
都是对象方法, 非类方法, 实现时先结构化写出来pass慢慢去实现

class Node(object):
    """节点类""""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def is_empty(self):
        pass
    
    def length(self):
        pass
    
    def travel(self):
        pass
    
    def add(self, item):
        pass
    
    def append(self, item):
        pass
    
    def insert(self, pos, item):
        pass 
    
    def remove(self, item):
        pass 
    
    def search(item):
        pass
    

    
# 调用  
s_lst = SingleLinkList()
s_lst.is_empty()
s_lst.length()
s_lst.travel()
s_lst.add(123)
....

头节点: 将一个节点挂在到单链表中来

链表必须要有一个对象属性来作为头节点

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  


class SingleLinkList(object):
    """单链表"""
    
    # 头节点可能为空
    # 用户可能是先创建一个节点, 作为链表的头节点
    def __init__(self, node=None):
        self.head = node  # 内部使用维护的,不用给外部访问, 应该设为私有变量
        self.next = None
        
        
# call
node1 = Node(111)
sl_obj = SingleLinkList(node1)  # 将head节点作为链表的头节点

print('将节点对象传给链表的head属性:', sl_obj.head)
print('属性是一个对象, 访问值用对象.属性来访问:', sl_obj.head.data)

将节点对象传给链表的head属性: <__main__.Node object at 0x0000021B93710828>
属性是一个对象, 访问值用对象.属性来访问: 111

为什么需要两个类

理解Node类和SingleListLink类的运作过程
- 节点类创建节点, 链表类"串联"上节点

# 分析:

link = SigleLinkList()  # 包含一个 __head -> None
node = Node(111)  # 包含 (111,None) 
# 目的: 让链表的 __head属性去指向(111, None)这个节点
# 让 __head -> None 变为 __head -> (111,None), 正好Python的 --> 指向关系, 其实就是 "="

is_empyt 实现

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node 
        self.next = None
    
    def is_empty(self):
        """链表是否为空"""
        # 只要 __head指向的节点是None即链表为空
        return self.__head == None
    
    def length(self):
        """链表的长度"""
        pass

length实现

# 分析

# (__head)-> (111, None)->(222,None)->(333,None)->(444,None)

# 需要一个游标(指针)cur 从头数到尾, 并对节点计数
# cur->__head, 计数, cur->111, 计数,判断111的next是否存在, 存在则cur->nex....循环

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node 
        self.next = None
    
    def is_empty(self):
        """链表是否为空"""
        # 只要 __head指向的节点是None即链表为空
        return self.__head == None
    
    def length(self):
        """链表的长度"""
        # 让指针(游标cur)有首先指向头节点对象 cur -> __head 
        # 即 cur, __head 都指向了头节点对象
        cur = self.__head
        # 开始计数, 让指针一边移动, 则一边计数
        count = 0 
        # while 循环,让游标移动, 停止条件是当指针指向当前节点的next值为None时
        # 关于count取值, 0:cur=None, 1:cur.next == None (指针指向哪为位置)
        while cur != None:
            count += 1 
            # 实现指针的"移动": Python中其实就是"="表示 "->" , 注意'='要从右往左看
            cur = cur.next  # 右到左: 将当前节点的next, 让cur去指向
        return count

travel 实现

也是变量每个节点, 打印出该节点的数据而已

# 分析

# 也是游标移动, while的终止条件是当 cur==None时即可

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node 
        self.next = None
    
    def is_empty(self):
        """链表是否为空"""
        # 只要 __head指向的节点是None即链表为空
        return self.__head == None
    
    def length(self):
        """链表的长度"""
        # 让指针(游标cur)有首先指向头节点对象 cur -> __head 
        # 即 cur, __head 都指向了头节点对象
        cur = self.__head
        # 开始计数, 让指针一边移动, 则一边计数
        count = 0 
        # while 循环,让游标移动, 停止条件是当指针指向当前节点的next值为None时
        # 关于count取值, 0:cur=None, 1:cur.next == None (指针指向哪为位置)
        while cur != None:
            count += 1 
            # 实现指针的"移动": Python中其实就是"="表示 "->" , 注意'='要从右往左看
            cur = cur.next  # 右到左: 将当前节点的next, 让cur去指向
        return count
            
        
    def travel(self):
        """元素遍历"""
        # cur->__head
        cur = self.__head
        # 移动, 然后print节点的元素, 当cur==None时终止
        while cur != None:
            print(cur.data)
            cur = cur.next

append 实现(尾插法)

尾部插入元素: 即遍历到最后一节点, 将其next指向插入的元素节点即可
首先要将用户给定的元素(值), 作为一个节点对象(data,next)
__ head -> 111 ->222 ->None -> (333, None)

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node 
        self.next = None
    
    def is_empty(self):
        """链表是否为空"""
        # 只要 __head指向的节点是None即链表为空
        return self.__head == None
    
    def length(self):
        """链表的长度"""
        # 让指针(游标cur)有首先指向头节点对象 cur -> __head 
        # 即 cur, __head 都指向了头节点对象
        cur = self.__head
        # 开始计数, 让指针一边移动, 则一边计数
        count = 0 
        # while 循环,让游标移动, 停止条件是当指针指向当前节点的next值为None时
        # 关于count取值, 0:cur=None, 1:cur.next == None (指针指向哪为位置)
        while cur != None:
            count += 1 
            # 实现指针的"移动": Python中其实就是"="表示 "->" , 注意'='要从右往左看
            cur = cur.next  # 右到左: 将当前节点的next, 让cur去指向
        return count
            
        
    def travel(self):
        """元素遍历"""
        # cur->__head
        cur = self.__head
        # 移动, 然后print节点的元素, 当cur==None时终止
        while cur != None:
            print(cur.data, end=' ' )
            cur = cur.next
        
    def append(self, item):
        """尾部添加元素"""
        node = Node(item)  # 用户只关心值, 不关心指针
        # 从头往后遍历
        cur = self.__head
        # 考虑空链表情况 if cur is None:
        if self.is_empty():
            # 直接将 __head -> node即可
            self.__head = node
        else:
            while cur.next != None:
                cur = cur.next
            # 将尾节点的next -> node
            cur.next = node

is_empty, length, travel 测试

# 测试
l = SingleLinkList()

print(l.is_empty())
print(l.length())

l.append(0)
print(l.is_empty())
print(l.length())

for i in range(8):
    l.append(i)

l.travel()

True
0
False
1
0 0 1 2 3 4 5 6 7

add 实现(头插法)

构建要插入的节点对象
头插的顺序是先让新元素的next->其余节点, 然后链表的__ head -> node

# 分析
# link:  head->(111, None)->(222,None)

# 目标: head->(000, None)->(111, None)->(222,None)
# 1. (000, Next)->(111, None)->(222,None)
# 2. __head -> (000, Next)->.....

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node 
        self.next = None
    
    def is_empty(self):
        """链表是否为空"""
        # 只要 __head指向的节点是None即链表为空
        return self.__head == None
    
    def length(self):
        """链表的长度"""
        # 让指针(游标cur)有首先指向头节点对象 cur -> __head 
        # 即 cur, __head 都指向了头节点对象
        cur = self.__head
        # 开始计数, 让指针一边移动, 则一边计数
        count = 0 
        # while 循环,让游标移动, 停止条件是当指针指向当前节点的next值为None时
        # 关于count取值, 0:cur=None, 1:cur.next == None (指针指向哪为位置)
        while cur != None:
            count += 1 
            # 实现指针的"移动": Python中其实就是"="表示 "->" , 注意'='要从右往左看
            cur = cur.next  # 右到左: 将当前节点的next, 让cur去指向
        return count
            
        
    def travel(self):
        """元素遍历"""
        # cur->__head
        cur = self.__head
        # 移动, 然后print节点的元素, 当cur==None时终止
        while cur != None:
            print(cur.data, end=' ' )
            cur = cur.next
        
    def append(self, item):
        """尾部添加元素"""
        node = Node(item)  # 用户只关心值, 不关心指针
        # 从头往后遍历
        cur = self.__head
        # 考虑空链表情况 if cur is None:
        if self.is_empty():
            # 直接将 __head -> node即可
            self.__head = node
        else:
            while cur.next != None:
                cur = cur.next
            # 将尾节点的next -> node
            cur.next = node

    def add(self, item):
        """从头部插入元素"""
        node = Node(item)
        # 顺序很关键, 先node的next指向原先 __head所指向的节点, 然后再更新__head->node
        node.next = self.__head.next
        self.__head = node

# 测试
l = SingleLinkList()

print(l.is_empty())
print(l.length())

l.append(0)
print(l.is_empty())
print(l.length())

for i in range(8):
    l.append(i)

# 头插入一个 666 
l.add(666)
l.travel()

True
0
False
1
666 0 1 2 3 4 5 6 7

insert 实现

从任意位置插入元素: 如何定位pos(下标)
找到要插入的位置下标: count计数
用该位置的该node的next->当前位置节点, 前一个节点的Next指向该node, 注意顺序哦

# 分析
# link: (111, None)->(222,None)->(333,None)

# 目标: (111, None)->(222,None)->(444,None)->(333,None)

# 顺序: (444,None)->(333,None); ...(222,None)->(444,None)

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node 
        self.next = None
    
    def is_empty(self):
        """链表是否为空"""
        # 只要 __head指向的节点是None即链表为空
        return self.__head == None
    
    def length(self):
        """链表的长度"""
        # 让指针(游标cur)有首先指向头节点对象 cur -> __head 
        # 即 cur, __head 都指向了头节点对象
        cur = self.__head
        # 开始计数, 让指针一边移动, 则一边计数
        count = 0 
        # while 循环,让游标移动, 停止条件是当指针指向当前节点的next值为None时
        # 关于count取值, 0:cur=None, 1:cur.next == None (指针指向哪为位置)
        while cur != None:
            count += 1 
            # 实现指针的"移动": Python中其实就是"="表示 "->" , 注意'='要从右往左看
            cur = cur.next  # 右到左: 将当前节点的next, 让cur去指向
        return count
            
        
    def travel(self):
        """元素遍历"""
        # cur->__head
        cur = self.__head
        # 移动, 然后print节点的元素, 当cur==None时终止
        while cur != None:
            print(cur.data, end=' ' )
            cur = cur.next
        
    def append(self, item):
        """尾部添加元素"""
        node = Node(item)  # 用户只关心值, 不关心指针
        # 从头往后遍历
        cur = self.__head
        # 考虑空链表情况 if cur is None:
        if self.is_empty():
            # 直接将 __head -> node即可
            self.__head = node
        else:
            while cur.next != None:
                cur = cur.next
            # 将尾节点的next -> node
            cur.next = node

    def add(self, item):
        """从头部插入元素"""
        node = Node(item)
        # 顺序很关键, 先node的next指向原先 __head所指向的节点, 然后再更新__head->node
        node.next = self.__head.next
        self.__head = node
        
    def insert(self, pos, item):
        """从任意位置插入元素"""
        # 考虑pos特殊情况
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):  # 不能包含 ==, 因为insert是前插入哦
            self.append(item)
        else:
            node = Node(item)
            # 前一个节点, 引入一个游标 pre 表示前一个节点
            pre = self.__head

            count = 0
            while count < (pos-1):  # 到该位置的前一个节点时终止
                count += 1
                pre = pre.next  # 移动
            # 当循环结束后,pre指向(pos-1) 对该位置的前一个节点操作: 
            # 1. 先用node.next -> 原先节点指向的node
            # 2. pre的next -> node
            node.next = pre.next
            pre.next = node

# 测试
l = SingleLinkList()

print(l.is_empty())
print(l.length())

l.append(0)
print(l.is_empty())
print(l.length())

for i in range(8):
    l.append(i)

# 头插入一个 666 
l.add(666)

# inset
l.insert(-1, 999)
l.insert(2, 6699)
l.insert(888,999)
l.insert(5,'cj')

l.travel()

True
0
False
1
999 0 6699 1 2 cj 3 4 5 6 7 999

search实现

游标去遍历, 比对值

class Node(object):
    """节点类"""
    def __init__(self, data=None):
        self.data = data
        self.next = None  

class SingleLinkList(object):


  
  
   
    共2页: 
上一页
1
2
下一页


 
 
  
 
 
  

  
 
 
 
栏目列表
  
      
      
      
      
    
    
    

    
    
    


 




 





 



 






 




 
  
 
         
    最新更新
        

    
                      
              nodejs爬虫
     
Python正则表达式完全指南
     
爬取豆瓣Top250图书数据
     
shp 地图文件批量添加字段
     
爬虫小试牛刀（爬取学校通知公告）
     
【python基础】函数-初识函数
     
【python基础】函数-返回值
     
HTTP请求：requests模块基础使用必知必会
     
Python初学者友好丨详解参数传递类型
     
如何有效管理爬虫流量？
     



    
                  SQL SERVER中递归
     
2个场景实例讲解GaussDB(DWS)基表统计信息估
     
常用的 SQL Server 关键字及其含义
     
动手分析SQL Server中的事务中使用的锁
     
openGauss内核分析：SQL by pass & 经典执行
     
一招教你如何高效批量导入与更新数据
     
天天写SQL，这些神奇的特性你知道吗？
     
openGauss内核分析：执行计划生成
     
[IM002]Navicat ODBC驱动器管理器 未发现数据
     
初入Sql Server 之 存储过程的简单使用
     



              这是目前我见过最好的跨域解决方案！
     
减少回流与重绘
     
减少回流与重绘
     
如何使用KrpanoToolJS在浏览器切图
     
performance.now() 与 Date.now() 对比
     
一款纯 JS 实现的轻量化图片编辑器
     
关于开发 VS Code 插件遇到的 workbench.scm.
     
前端设计模式——观察者模式
     
前端设计模式——中介者模式
     
创建型-原型模式






 




相关教程





python基础教程
软件开发
PHP教程
sql教程
vb.net教程
sql语句大全
asp.net教程
dreamweaver教程
javascript教程
flash教程
vb教程
计算机二级vfp
access教程
html5教程
C#教程
web前端 
python入门教程 





关于我们--广告服务--免责声明--本站帮助-友情链接--版权声明--联系我们

  
  
黑ICP备07002182号