栈
class Node:
def __init__(self, value):
self.value = value
self.next = None
class MyStack():
def __init__(self, *args):
self.top = None
for i in args:
self.append(i)
def append(self, x):
node = Node(x)
node.next = self.top
self.top = node
def pop(self):
node = self.top
if node is None:
raise Exception('This is an empty stack')
self.top = node.next
return node.value
def remove(self, x):
node = self.top
if node is None:
raise Exception('This is an empty stack')
if node.value == x:
self.pop()
while node.next is not None:
p = node
node = node.next
if node.value == x:
p.next = node.next
return node.value
raise Exception('It does not include x')
def index(self, x):
node = self.top
index = len(self)
while node is not None:
if node.value == x:
return index
index -= 1
node = node.next
return -1
def __len__(self):
node = self.top
count = 0
while node is not None:
count += 1
node = node.next
return count
def __eq__(self, other):
if len(self)!=len(other):
return False
if len(self)==0:
return Ture
sNode = self.top
oNode = other.top
count = 0
while sNode is not None:
if sNode.value != oNode.value:
return False
count += 1
sNode = sNode.next
oNode = oNode.next
return True
def __str__(self):
node = self.top
if node is None:
res = '[]'
res = '{r}'.format(r=node.value)
while node.next is not None:
node = node.next
res = '{v},{r}'.format(r=res, v=node.value)
return '[{r}]'.format(r=res)
if __name__ == '__main__':
a = MyStack(1, 2, 3)
assert len(a) == 3
x = a.pop()
assert x == 3
a.append(4)
print(a)
# [1, 2, 4]
a.remove(2)
print(a)
# [1, 4]
i = a.index(4)
assert i == 2
b = MyStack(1, 4)
c = MyStack(4, 1)
assert a == b
assert b != c
集合
class Node:
def __init__(self, value):
self.value = value
self.next = None
class MySet():
def __init__(self, *args):
self.top = None
for i in args:
self.add(i)
def add(self, x):
pNode = self.top
while pNode is not None:
if pNode.value == x:
return -1
pNode = pNode.next
node = Node(x)
node.next = self.top
self.top = node
def remove(self, x):
node = self.top
if node is None:
raise Exception('This is an empty stack')
if node.value == x:
self.pop()
while node.next is not None:
p = node
node = node.next
if node.value == x:
p.next = node.next
return node.value
raise Exception('It does not include x')
def has(self, x):
node = self.top
while node is not None:
if node.value == x:
return True
node = node.next
return False
def issubset(self, other):
Node = self.top
while Node is not None:
if other.has(Node.value) == False:
return False
Node = Node.next
return True
def union(self, other):
uSet = MySet()
Node = self.top
while Node is not None:
uSet.add(Node.value)
Node = Node.next
Node = other.top
while Node is not None:
uSet.add(Node.value)
Node = Node.next
return uSet
def __len__(self):
node = self.top
count = 0
while node is not None:
count += 1
node = node.next
return count
def __eq__(self, other):
if len(self)==len(other) and (self.issubset(other)):
return True
return False
def __str__(self):
node = self.top
if node is None:
res = '\{\}'
res = '{r}'.format(r=node.value)
while node.next is not None:
node = node.next
res = '{v},{r}'.format(r=res, v=node.value)
return '{'+'{r}'.format(r=res)+'}'
if __name__ == '__main__':
a = MySet(1, 2, 3)
# assert len(a) == 3
assert a.has(1)
assert not a.has(4)
a.add(4)
assert a.has(4)
print(a)
# {1, 2, 3, 4}
a.remove(2)
print(a)
# {1, 3, 4}
b = MySet(1, 3)
assert b.issubset(a)
c = MySet(2, 3, 5)
d = a.union(c)
print(d)
# {1, 3, 4, 2, 5}
b = MySet(1, 4)
c = MySet(4, 1)
assert a != b
assert b == c
类的方法
类有一个名为 init() 的特殊方法（构造方法），该方法在类实例化时会自动调用，像下面这样：
def __init__(self):
self.data = []
类的专有方法：
__init__ : 构造函数，在生成对象时调用
__del__ : 析构函数，释放对象时使用
__repr__ : 打印，转换
__setitem__ : 按照索引赋值
__getitem__: 按照索引获取值
__len__: 获得长度
__cmp__: 比较运算
__call__: 函数调用
__add__: 加运算
__sub__: 减运算
__mul__: 乘运算
__truediv__: 除运算
__mod__: 求余运算
__pow__: 乘方
