一、链表的封装:
数组和链表的区分:
图示区分:
数组是有下标索引和data两部分组成:
链表是有data和指向下一个数据的指针地址两部分组成
表格区分
** | 链表 | 数组 |
---|---|---|
内存占用 | 不需要连续的内存空间 | 需要连续的内存空间 |
大小可变 | 链表的大小可动态变化 | 数组大小固定,不能动态扩展 |
增删 | 较快,只需要修改前一个元素的指针即可 | 较慢,需要移动修改元素只有的所有元素 |
查询 | 较慢,只能遍历查找 | 较快,可以通过下标直接访问 |
在访问方式上 | 必须是顺序访问,不能随机访问 | 可以随机访问其中的元素 |
空间的使用上 | 可以随意扩大 | 不能 |
时间复杂度的不同
时间复杂度 | 数组 | 链表 |
---|---|---|
增加元素 | O(n) | O(1) |
删除元素 | O(n) | O(1) |
修改元素 | O(1) | O(n) |
查看元素 | O(1) | O(n) |
链表的封装:
val表示值;next表示指向的下一个内存地址
# 封装节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def travel(self, head):
"""遍历链表里面的每一个元素"""
while head: #判断head,也就是下一个内存地址是否存在,不存在的时候即遍历完成
print(head.val, end=',')
head = head.next
两数相加:
代码需求:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def travel(self, head):
"""遍历链表里面的每一个元素"""
while head:
print(head.val, end=',')
head = head.next
def create_l1(): #生成l1链表的函数
# l1 = 2,4,3
l1 = ListNode()
node1 = ListNode(val=2) #生成三个独立的节点
node2 = ListNode(val=4)
node3 = ListNode(val=3)
l1.next = node1 # 通过next把独立的节点连接起来
node1.next = node2
node2.next = node3
return l1.next
def create_l2(): # 生成l2链表的函数
# l2 = 5, 6, 4
l2 = ListNode()
node1 = ListNode(val=5)
node2 = ListNode(val=6)
node3 = ListNode(val=4)
l2.next = node1
node1.next = node2
node2.next = node3
return l2.next
def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode: #求和的函数
res = 0 #定义一个相加的结果
l3 = ListNode() # 定义求和之后的链表l3
cur = l3 # 下文作解释
while(l1 or l2): #l1和l2两者存在一个就可以加到res上
if(l1):
res += l1.val # res=2
l1 = l1.next
if(l2):
res += l2.val # res=2+5=7
l2 = l2.next
l3.next = ListNode(res%10) #有进位时该位置收到的是个位的结果,所以需要取余
l3 = l3.next #移动指针,按次序的输入res的结果,为了防止覆盖数据
# res=8, 进位为0, 8//10=0
# res=14, 进位为1, 14//10=1
res //= 10 #为了防止有进位,即十位数为1,则下次循环的res初始值为1,所以输入res对10整除后的结果
if res == 1:
l3.next = ListNode(1) # 循环结束后,最后一位依然有进位的话,l3会比l1和l2多一位,多出的一位的值就是进位的1
return cur.next
"""
大家就会有疑问了,为什么不直接返回l3?
因为代码中每循环一次,l3的指针就会往后移一位,所以循环结束后指针就会在最后一位
(前提是最后一位没有进位,有进位的话指针就是在倒数第二位),这时直接返回l3的话,
只会输出指针处的值,故将l3的内容存入cur。
此处返回cur.next的原因是:初始定义cur = l3,故第一位为0,是没有意义的。
"""
if __name__ == '__main__': # 在模块内部运行
l1 = create_l1()
l2 = create_l2()
l3 = addTwoNumbers(l1, l2)
l3.travel(l3) #调用ListNode类的遍历所用的方法
运行结果:
二、栈的封装:
- 栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈),允许进行操作的一端称为“栈顶”, 另一固定端称为“栈底”,当栈中没有元素时称为“空栈”。向一个栈内插入元素称为是进栈,push; 从一个栈删除元素称为是出栈,pop。特点 :后进先出(LIFO)。
入栈:如下图,入栈的顺序就是a1->a2->a3->a4->a5
出栈:删除栈顶的元素
栈的封装:
我们用列表的操作模拟实现栈的封装:
class Stack(object):
"""栈的封装"""
def __init__(self):
self.stack = []
def push(self, value):
"""入栈"""
self.stack.append(value) #用列表追加模拟入栈的顺序,即列表的第一位表示栈底,最后一位表示栈顶
print(f"入栈元素为{value}")
def pop(self):
"""出栈"""
if self.is_empty():
raise Exception("栈为空")
item = self.stack.pop() #pop默认删除最后一个元素,即‘栈顶’元素
print(f"出栈元素为{item}")
return item
def is_empty(self):
"""判断栈是否为空"""
return len(self.stack) == 0 #即长度是否为0
def top(self):
"""返回栈顶元素"""
if self.is_empty():
raise Exception("栈为空")
return self.stack[-1] #即列表‘入栈’时追加的最后一位
def __len__(self):
"""魔术方法, len(object)自动执行的方法,查看长度"""
return len(self.stack)
# 上面为栈的封装部分,下面的部分是实际的演示,为了更好的理解。
if __name__ == '__main__':
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3) #入栈三个元素
print(len(stack)) # 3
stack.pop()
print(stack.is_empty()) # False
print(stack.top()) # 2
运行结果:
三、队列的封装:
- 队列是限制在一端进行插入操作和另一端删除操作的线性表,允许进行插入操作的一端称为“队尾”, 允许进行删除操作的一端称为“队头”,,当队列中没有元素时称为“空队”。特点 :先进先出(FIFO)。
队列的封装:
同样我们列表的操作也能模拟实现队列的封装:
class Queue(object):
"""
队列的封装
1. 列表的左侧队尾
2. 列表的右侧队头
"""
def __init__(self):
self.queue = []
def enqueue(self, value):
"""入队"""
self.queue.insert(0, value) #从队尾进,即从列表0的位置插入元素
print("入队元素为:", value)
def dequeue(self):
"""出队"""
if self.is_empty():
raise Exception("队列为空")
item = self.queue.pop() #从队头出,即列表-1的位置删除元素
print("出队元素:", item)
return item
def __len__(self):
"""获取队列的长度"""
return len(self.queue)
def first(self):
"""获取队头元素"""
if self.is_empty():
raise Exception("队列为空")
return self.queue[-1]
def last(self):
"""获取队尾元素"""
if self.is_empty():
raise Exception("队列为空")
return self.queue[0]
def is_empty(self):
"""判断队列是否为空"""
return len(self.queue) == 0
# 上面为队列的封装部分,下面的部分是实际的演示,为了更好的理解。
if __name__ == '__main__':
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.is_empty()) # False
queue.dequeue() # 1出队, 队列只剩32
print(queue.first()) # 2
print(queue.last()) # 3
运行结果:
四、二叉树的封装:
二叉树是树的特殊一种,具有如下特点:
- 1、每个结点最多有两颗子树,结点的度最大为2。
- 2、左子树和右子树是有顺序的,次序不能颠倒。
- 3、即使某结点只有一个子树,也要区分左右子树。
此处主要演示实际二叉树的封装,对二叉树的分类和性质不做过多解释。
二叉树的遍历:
项目 | Value |
---|---|
前序遍历 | 先访问根结点,再先序遍历左子树,最后再先序遍历右子树,即根—左—右。 |
中序遍历 | 先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树,即左—根—右。 |
后序遍历 | 先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点,即左—右—根。 |
以上图二叉树为例:
项目 | Value |
---|---|
前序遍历 | 1,2,4,8,9,5,10,3,6,7 |
中序遍历 | 8,4,9,2,10,5,1,6,3,7 |
后序遍历 | 8,9,4,10,5,2,6,7,3,1 |
二叉树的封装:
class Node(object):
"""节点类"""
def __init__(self, val=None, left=None, right=None): #生成节点时,要定义左节点和右节点
self.val = val
self.left = left
self.right = right
class BinaryTree(object):
"""封装二叉树"""
def __init__(self, root):
self.root = root
def pre_travel(self, root):
"""前序遍历: 根左右"""
if (root != None):
print(root.val, end = ',')
self.pre_travel(root.left)
self.pre_travel(root.right)
def in_travel(self, root):
"""中序遍历: 左根右"""
if (root != None):
self.in_travel(root.left)
print(root.val, end = ',')
self.in_travel(root.right)
def last_travel(self, root):
"""后序遍历: 左右根"""
if (root != None):
self.last_travel(root.left)
self.last_travel(root.right)
print(root.val, end = ',')
实现下图二叉树的遍历:
class Node(object):
"""节点类"""
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree(object):
"""封装二叉树"""
def __init__(self, root):
self.root = root
def pre_travel(self, root):
"""前序遍历: 根左右"""
if (root != None):
print(root.val, end = ',')
self.pre_travel(root.left)
self.pre_travel(root.right)
def in_travel(self, root):
"""中序遍历: 左根右"""
if (root != None):
self.in_travel(root.left)
print(root.val, end = ',')
self.in_travel(root.right)
def last_travel(self, root):
"""后序遍历: 左右根"""
if (root != None):
self.last_travel(root.left)
self.last_travel(root.right)
print(root.val, end = ',')
if __name__ == '__main__':
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
node10 = Node(10) #生成10个独立的节点
bt = BinaryTree(root=node1)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right= node5
node3.left = node6
node3.right = node7
node4.left = node8
node4.right = node9
node5.left = node10 # 建立该二叉树的节点关系
bt.pre_travel(node1)
print('前序遍历')
bt.in_travel(node1)
print('中序遍历')
bt.last_travel(node1)
print('后序遍历')
运行结果: