一、链表
在 Python 中，列表是动态数组。这意味着列表和链表的内存使用都非常相似。
二、栈
1.栈(stack)，有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素
2.特点：只能允许在容器的一端(称为栈顶端指标—— top) 进行加入数据(push)和输出数据(pop) 的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
3.由于栈数据结构只允许在一端进行操作，因而按照先进后出（后进先出）的原理运作。
-
2.1 栈结构的实现
（1）Stack()创建一个新的空栈
（2）push(item)添加一个新的元素item到栈顶
（3）pop()弹出栈顶元素
（4）peek()返回栈顶元素
（5）is_empty()判断栈是否为空
（6）size()返回栈的元素个数 -
2.2.代码实现：
class Stack(object):
#定义初始化方法
def __init__(self):
#初始化一个空列表
self._list=[]
#压栈
def push(self,item):
self._list.append(item)
#弹出元素
def pop(self):
return self._list.pop()
#返回栈顶元素
def peek(self):
return self._list[len(self._list)-1]
#判断栈顶是否为空
def is_empty(self):
return self._list==[]
#计算栈的大小
def size(self):
return len(self._list)
if __name__=="__main__":
stack=Stack()
print("栈是否为空：",stack.is_empty())
#压栈
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print("栈是否为空：",stack.is_empty())
print("栈的长度：",stack.size())
#弹出
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
栈是否为空： True
栈是否为空： False
栈的长度： 4
4
3
2
1
三、队列是什么？
1.队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
2.队列是遵循先进先出的原理简称，允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作
-
3.1队列的实现
1.实现步骤：
（1）Queue()创建一个空的队列
（2）enqueue(item)向队列中添加元素item
（3）dequeue()从队列头部删除一个元素
（4）is_empty判断一个队列是否为空
（5）size()返回队列大小
- 3.2.代码实现
class Queue(object):
#定义初始化方法
def __init__(self):
self._list=[]
#进队
def enqueue(self,item):
#self._list.append(item)
self._list.insert(0,item)
#出队
def dequeue(self):
#return self._list.pop()
return self._list.pop()
#判断是否为空
def is_empty(self):
return self._list==[]
#计算队列大小
def size(self):
return len(self._list)
if __name__=="__main__":
queue=Queue()
print("队列是否为空：",queue.is_empty())
#进队
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("队列是否为空：", queue.is_empty())
#出队
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
队列是否为空： True
队列是否为空： False
1
2
3
四、树
image.png
-
结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图 1（A）中，数据元素 A 就是一个结点；
-
父结点（双亲结点）、子结点和兄弟结点：对于图 1（A）中的结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子结点（也称“孩子结点”）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。
-
结点A就是整棵树的根结点。
-
一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。
4.1树的种类
- 无序树：树中任意节点的子节点之间没有顺序关系，称为无序树
- 有序树：树中任意节点的子节点之间有顺序关系，称为有序树
- 二叉树：每个节点最多含有两个子树的树称为二叉树
- 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其他各层的节点数目均已达到最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树称为完 全二叉树，其中满二叉树的定义是所有叶子节点都在最底层的完全二叉树
- 平衡二叉树（AVL树）：当且仅当任何节点的两颗子树的高度差不大于1的二叉树
- B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树
image.png
简单地理解，满足以下两个条件的树就是二叉树：
本身是有序树；
树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
4.2 树的实现
# 定义二叉树节点
class Node(object):
"""二叉树结点的定义"""
def __init__(self, item):
self.elem = item
self.lChild = None
self.rChild = None
class Tree(object):
"""二叉树"""
def __init__(self):
self.root = None # 根结点
def add(self, item):
"""添加结点"""
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 队列
while queue:
cur_node = queue.pop(0)
if cur_node.lChild is None:
cur_node.lChild = node
return
else:
queue.append(cur_node.lChild)
if cur_node.rChild is None:
cur_node.rChild = node
return
else:
queue.append(cur_node.rChild)
def breadth_travel(self):
"""利用队列实现树的层次遍历（广度遍历）"""
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem, end=" ")
if cur_node.lChild is not None:
queue.append(cur_node.lChild)
if cur_node.rChild is not None:
queue.append(cur_node.rChild)
def preorder(self, node):
"""前序遍历（深度遍历）(中 -> 左 -> 右)"""
if node is None:
return
print(node.elem, end=" ")
self.preorder(node.lChild)
self.preorder(node.rChild)
def inorder(self, node):
"""中序遍历（深度遍历）(左 -> 中 -> 右)"""
if node is None:
return
self.inorder(node.lChild)
print(node.elem, end=" ") # 此处可认为 node.elem 就是我们要处理的结点
self.inorder(node.rChild)
def postorder(self, node):
"""后序遍历（深度遍历）(左 -> 右 -> 中)"""
if node is None:
return
self.postorder(node.lChild)
self.postorder(node.rChild)
print(node.elem, end=" ")
if __name__ == "__main__":
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
print("广度优先遍历")
tree.breadth_travel()
print("先序遍历")
tree.preorder(tree.root)
print("中序遍历")
tree.inorder(tree.root)
print("后序遍历")
tree.postorder(tree.root)
image.png
网友评论