VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 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))
7
f = add  # 将函数赋值给一个变量f, 即用f来指向这块函数的地址
print(f(3,4))
7

构造节点类

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

插入: 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):