一、链表
class Node(object):
def __init__(self, value):
# 元素域
self.value = value
# 链接域
self.next = None
class LinkedListOneway(object):
def __init__(self, node=None):
self.__head = node
def __len__(self):
# 游标，用来遍历链表
cur = self.__head
# 记录遍历次数
count = 0
# 当前节点为None则说明已经遍历完毕
while cur:
count += 1
cur = cur.next
return count
def is_empty(self):
# 头节点不为None则不为空
return self.__head == None
def add(self, value):
"""
头插法
先让新节点的next指向头节点
再将头节点替换为新节点
顺序不可错，要先保证原链表的链不断，否则头节点后面的链会丢失
"""
node = Node(value)
node.next = self.__head
self.__head = node
def append(self, value):
"""尾插法"""
node = Node(value)
cur = self.__head
if self.is_empty():
self.__head = node
else:
while cur.next:
cur = cur.next
cur.next = node
def insert(self, pos, value):
# 应对特殊情况
if pos <= 0:
self.add(value)
elif pos > len(self) - 1:
self.append(value)
else:
node = Node(value)
prior = self.__head
count = 0
# 在插入位置的前一个节点停下
while count < (pos - 1):
prior = prior.next
count += 1
# 先将插入节点与节点后的节点连接，防止链表断掉，先链接后面的，再链接前面的
node.next = prior.next
prior.next = node
def remove(self, value):
cur = self.__head
prior = None
while cur:
if value == cur.value:
# 判断此节点是否是头节点
if cur == self.__head:
self.__head = cur.next
else:
prior.next = cur.next
break
# 还没找到节点，有继续遍历
else:
prior = cur
cur = cur.next
def search(self, value):
cur = self.__head
while cur:
if value == cur.value:
return True
cur = cur.next
return False
def traverse(self):
cur = self.__head
while cur:
print(cur.value)
cur = cur.next
二、队列
class Queue:
#初始化队列
def __init__(self):
self.items=[]
#加入队列
def inqueue(self,item):
self.items.append(item)
#出队列
def dequeue(self):
return self.items.pop(0)
#判断是否为空
def empty(self):
return self.size()==0
#返回长度
def size(self):
return len(self.items)
附个实例：约瑟夫斯问题
#约瑟夫斯问题
def josephus(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.inqueue(name)
while simqueue.size() > 1:
for i in range(num):
simqueue.inqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
def josephus(namelist,num):
squeue = Queue()
for name in namelist:
squeue.inqueue(name)
while squeue.size()>1:
for i in range(num):
squeue.inqueue(squeue.dequeue())
squeue.dequeue()
return squeue.dequeue()
if __name__ == '__main__':
print(josephus(["Java", "Python", "C++", "C", "PHP", "Html5"], 5))
三、堆栈
# 后进先出
class Stack():
def __init__(self,size):
self.size=size
self.stack=[]
self.top = -1
# 压入数据
def push(self,x):
if self.isfull():
raise eecception("栈满...")
else:
self.stack.append(x)
self.top = self.top + 1
# 弹出数据
def pop(self):
if self.isempty():
raise exception("栈空...")
else:
self.top = self.top -1
self.stack.pop()
def isfull(self):
return self.top+1 == self.size
def isempty(self):
return self.top == '-1'
def showStack(self):
print(self.stack)
if __name__ == "__main__":
s=Stack(10)
for i in range(10):
s.push(i)
s.showStack()
for i in range(3):
s.pop()
s.showStack()
"""
类中有top属性，用来指示栈的存储情况，初始值为1，一旦插入一个元素，其值加1，利用top的值乐意判定栈是空还是满。
执行时先将0,1,2,3,4依次入栈，然后删除栈顶的前三个元素
"""
四、AVL树（平衡二叉树）
详细关于AVL树请阅读：浅谈【树】：红黑树、AVL树、B树、B+树
class Node(object):
def __init__(self, key, parent=None, left=None, right=None):
self.key = key # 存储的数据
self.parent = parent # 父节点
self.left = left # 左孩子节点
self.right = right # 右孩子节点
self.bf = 0 # 平衡因子 等于左子树高度减去右子树高度
def l_rotate(self, par, cur):
"""
左单旋转
:param par: 平衡因子为2|-2的节点
:param cur: 作为轴心旋转的节点(平衡因子不为2)
:return: None
"""
p = cur.left # 辅助引用p指向cur的左节点
cur.left = par # cur的左节点指向par
par.right = p # par的右节点指向cur的左节点
if p:
p.parent = par # cur的左节点不为空时更新该节点的父节点
if par == self.root:
self.root = cur # 判断平衡因子为2的par是否为根
else:
if par == par.parent.left: # 更新par父节点的子节点信息
par.parent.left = cur
else:
par.parent.right = cur
cur.parent = par.parent # 当前cur的父节点指向原来par的父节点
par.parent = cur # par变为cur的左子节点
cur.bf = par.bf = 0 # 插入操作中, 操作的两个节点旋转后平衡因子恢复为0
def r_rotate(self, par, cur):
"""右单旋转"""
p = cur.right
cur.right = par
par.left = p
if p:
p.parent = par
if par == self.root:
self.root = cur
else:
if par == par.parent.left:
par.parent.left = cur
else:
par.parent.right = cur
cur.parent = par.parent # 更新父节点信息
par.parent = cur
cur.bf = par.bf = 0 # 更新平衡因子
def lr_rotate(self, par, cur):
"""左右双旋转"""
# 先左旋转 cur 和 cur的右子节点
cur_right = cur.right # 获得cur的右子节点的引用
bf = cur_right.bf
self.l_rotate(cur, cur_right)
# 继续右旋转
self.r_rotate(par, cur_right)
if bf == 0: # 根据cur_right的平衡因子更新操作的3个节点
cur.bf = cur_right.bf = par.bf = 0
elif bf == -1:
par.bf = 1
cur.bf = cur_right.bf = 0
else:
cur.bf = -1
cur_right.bf = par.bf = 0
def rl_rotate(self, par, cur):
"""右左双旋转"""
# 先右旋转 cur 和 cur的左子节点
cur_left = cur.left # 获得cur的右子节点的引用
bf = cur_left.bf
self.r_rotate(cur, cur_left)
self.l_rotate(par, cur_left) # 继续右旋转
if bf == 0: # 根据cur_left的平衡因子更新操作的3个节点
cur.bf = cur_left.bf = par.bf = 0
elif bf == -1:
cur.bf = 1
par.bf = cur_left.bf = 0
else:
par.bf = -1
cur_left.bf = cur.bf = 0
def find(self, key):
"""寻找键值"""
p = self.root
while p:
if p.key == key:
return p
if key < p.key:
p = p.left
else:
p = p.right
return None
五、红黑树
详细关于红黑树请阅读：浅谈【树】：红黑树、AVL树、B树、B+树
#定义红黑树
class RBTree(object):
def __init__(self):
self.nil = RBTreeNode(0)
self.root = self.nil
class RBTreeNode(object):
def __init__(self, x):
self.key = x
self.left = None
self.right = None
self.parent = None
self.color = 'black'
self.size=None
#左旋转
def LeftRotate( T, x):
y = x.right
x.right = y.left
if y.left != T.nil:
y.left.parent = x
y.parent = x.parent
if x.parent == T.nil:
T.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
#右旋转
def RightRotate( T, x):
y = x.left
x.left = y.right
if y.right != T.nil:
y.right.parent = x
y.parent = x.parent
if x.parent == T.nil:
T.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
#红黑树的插入
def RBInsert( T, z):
y = T.nil
x = T.root
while x != T.nil:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.parent = y
if y == T.nil:
T.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
z.left = T.nil
z.right = T.nil
z.color = 'red'
RBInsertFixup(T, z)
return z.key, '颜色为', z.color
#红黑树的上色
def RBInsertFixup( T, z):
while z.parent.color == 'red':
if z.parent == z.parent.parent.left:
y = z.parent.parent.right
if y.color == 'red':
z.parent.color = 'black'
y.color = 'black'
z.parent.parent.color = 'red'
z = z.parent.parent
else:
if z == z.parent.right:
z = z.parent
LeftRotate(T, z)
z.parent.color = 'black'
z.parent.parent.color = 'red'
RightRotate(T,z.parent.parent)
else:
y = z.parent.parent.left
if y.color == 'red':
z.parent.color = 'black'
y.color = 'black'
z.parent.parent.color = 'red'
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
RightRotate(T, z)
z.parent.color = 'black'
z.parent.parent.color = 'red'
LeftRotate(T, z.parent.parent)
T.root.color = 'black'
def RBTransplant( T, u, v):
if u.parent == T.nil:
T.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
def RBDelete(T, z):
y = z
y_original_color = y.color
if z.left == T.nil:
x = z.right
RBTransplant(T, z, z.right)
elif z.right == T.nil:
x = z.left
RBTransplant(T, z, z.left)
else:
y = TreeMinimum(z.right)
y_original_color = y.color
x = y.right
if y.parent == z:
x.parent = y
else:
RBTransplant(T, y, y.right)
y.right = z.right
y.right.parent = y
RBTransplant(T, z, y)
y.left = z.left
y.left.parent = y
y.color = z.color
if y_original_color == 'black':
RBDeleteFixup(T, x)
#红黑树的删除
def RBDeleteFixup( T, x):
while x != T.root and x.color == 'black':
if x == x.parent.left:
w = x.parent.right
if w.color == 'red':
w.color = 'black'
x.parent.color = 'red'
LeftRotate(T, x.parent)
w = x.parent.right
if w.left.color == 'black' and w.right.color == 'black':
w.color = 'red'
x = x.parent
else:
if w.right.color == 'black':
w.left.color = 'black'
w.color = 'red'
RightRotate(T, w)
w = x.parent.right
w.color = x.parent.color
x.parent.color = 'black'
w.right.color = 'black'
LeftRotate(T, x.parent)
x = T.root
else:
w = x.parent.left
if w.color == 'red':
w.color = 'black'
x.parent.color = 'red'
RightRotate(T, x.parent)
w = x.parent.left
if w.right.color == 'black' and w.left.color == 'black':
w.color = 'red'
x = x.parent
else:
if w.left.color == 'black':
w.right.color = 'black'
w.color = 'red'
LeftRotate(T, w)
w = x.parent.left
w.color = x.parent.color
x.parent.color = 'black'
w.left.color = 'black'
RightRotate(T, x.parent)
x = T.root
x.color = 'black'
def TreeMinimum( x):
while x.left != T.nil:
x = x.left
return x
#中序遍历
def Midsort(x):
if x!= None:
Midsort(x.left)
if x.key!=0:
print('key:', x.key,'x.parent',x.parent.key)
Midsort(x.right)
if __name__ == "__main__":
nodes = [11,2,14,1,7,15,5,8,4]
T = RBTree()
for node in nodes:
print('插入数据',RBInsert(T,RBTreeNode(node)))
print('中序遍历')
Midsort(T.root)
RBDelete(T,T.root)
print('中序遍历')
Midsort(T.root)
RBDelete(T,T.root)
print('中序遍历')
Midsort(T.root)
网友评论