当前位置:
首页 > Python基础教程 >
-
单链表-Python实现-jupyter->markdown 格式测试(2)
"""单链表"""
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
def search(self, item):
"""查找元素"""
cur = self.__head
# 循环遍历比较值即可
while cur != None:
if cur.data == item:
return True
else:
# 记得移动游标 ,不然就死循环了
cur = cur.next
return False
remove实现
- 删除某个元素, 删掉第一次找到的那个元素哦
- 原理: cur找到该节点后, 用pre.next -> cur.next 即可
- 即需要两个游标: pre 和cur
但其实, 只需要pre就能达到效果呢
- pre.next -> node.next 即** pre.next -> pre.next.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
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
def search(self, item):
"""查找元素"""
cur = self.__head
# 循环遍历比较值即可
while cur != None:
if cur.data == item:
return True
return False
def remove(self, item):
"""删除首次找到的该元素-两个游标"""
pre = None
cur = self.__head
while cur != None:
if cur.data == item:
# 判断是否为 head
if cur == self.__head:
self.__head = cur.next
else:
# 删除: pre.next -> cur.next
pre.next = cur.next
break
else:
# 移动: pre移动一次, cur也移动一次, 顺序: 必须先移动pre, 才能跟上cur的节奏哦
pre = cur
cur = cur.next
# 测试
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()
l.remove(999)
# l.remove('aaa')
True
0
False
1
999 0 6699 1 2 cj 3 4 5 6 7 999
l.travel()
0 6699 1 2 cj 3 4 5 6 7 999
l.remove(999)
l.travel()
0 6699 1 2 cj 3 4 5 6 7
单链表完整实现
- object Python3是默认继承的
- 理解指向在Python中就是"=", 从右往左看
- 要在头脑中有画面感, 毕竟, "="就是'->'指针呀
class Node:
"""节点类"""
def __init__(self, data=None):
self.data = data
self.next = None
class SingleLinkList:
"""单链表类"""
def __init__(self, node=None):
"""构造链表的头节点"""
self.__head = node
@property
def is_empty(self):
"""链表是否为空"""
return self.__head == None
@property
def length(self):
"""链表中元素的个数"""
current = self.__head
count = 0
while current is not None:
count += 1
# 游标不断向后移动
current = current.next
return count
def travel(self):
"""遍历列表元素"""
current = self.__head
while current != None:
print(current.data)
current = current.next
def append(self, item):
"""尾部插入元素"""
node = Node(item)
current = self.__head
if self.is_empty:
self.__head = node
else:
while current.next is not None:
current = current.next
current.next = node
def add(self, item):
"""头部插入元素"""
node = Node(item)
if self.is_empty:
self.__head = node
else:
# 插入顺序,脑海里要有画面感
node.next = self.__head
self.__head = node
def insert(self, position, item):
"""从指定位置插入元素"""
if position <= 0:
self.add(item)
elif position > (self.length-1):
self.append(item)
else:
node = Node(item)
prior = self.__head
count = 0
while count < (position-1):
count += 1
prior = prior.next
# 此时prior已定位到当前位置前一个节点
node.next = prior.next
prior.next = node
def search(self, item):
"""搜索元素并范围其位置-首次被找到"""
position = 0
current = self.__head
while current:
position += 1
if current.data == item:
return position-1
else:
# 记得移动游标,不然就死循环了
current = current.next
return False
def remove(self, item):
"""删除元素-首次被找到"""
# 删除: prior.next -> prior.next.next 或者: prior.next = cur.next
# prior = self.__head
# position = self.search(item)
# if position:
# count = 0
# while prior:
# count += 1
# if count == position-1
# prior = prior.next
# return
# 这里采用: prior.next = cur.next
prior = None
current = self.__head
while current:
if current.data == item:
# 判断是否为头节点
if current == self.__head:
self.__head = current.next
else:
prior.next = current.next
break
else:
# prior先移动一次,到current的位置, 然后current再往后移动一次
prior = current
current = current.next
l = SingleLinkList()
l.is_empty
True
l.append(1)
l.add(0)
l.append('cj')
l.insert(999,666)
l.travel()
l.search('cj')
0
1
cj
666
2
l.add(333)
l.travel()
333
333
333
0
1
cj
666
耐心和恒心, 总会获得回报的.
栏目列表
最新更新
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.
前端设计模式——观察者模式
前端设计模式——中介者模式
创建型-原型模式