一、链表
为什么需要链表
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
链表的定义
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。
1.1 单向链表
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置（python中的标识）
变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
1.1.1 节点实现
class SingleNode(object): """单链表的结点""" def __init__(self,item): # _item存放数据元素 self.item = item # _next是下一个节点的标识 self.next = None
1.1.2 单链表的操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
1.1.3链表与顺序表的对比
链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。
链表与顺序表的各种操作复杂度如下所示：
操作 链表 顺序表 访问元素 O(n) O(1) 在头部插入/删除 O(1) O(n) 在尾部插入/删除 O(n) O(1) 在中间插入/删除 O(n) O(n) 注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。
1.1.3单链表的实现
# coding:utf-8
class Node(object):
"""节点"""
def __init__(self, elem):
self.elem = elem
self.next = None
class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head == None
def length(self):
"""链表长度"""
# cur游标，用来移动遍历节点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")
def add(self, item):
"""链表头部添加元素，头插法"""
node = Node(item)
node.next = self.__head
self.__head = node
def append(self, item):
"""链表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素
:param pos 从0开始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 当循环退出后，pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""删除节点"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判断此结点是否是头节点
# 头节点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
if __name__ == "__main__":
ll = SingleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
# 8 1 2 3 4 5 6
ll.insert(-1, 9) # 9 8 1 23456
ll.travel()
ll.insert(3, 100) # 9 8 1 100 2 3456
ll.travel()
ll.insert(10, 200) # 9 8 1 100 23456 200
ll.travel()
ll.remove(100)
ll.travel()
ll.remove(9)
ll.travel()
ll.remove(200)
ll.travel()
#运行结果:
"""
True
0
False
1
9 8 1 2 3 4 5 6
9 8 1 100 2 3 4 5 6
9 8 1 100 2 3 4 5 6 200
9 8 1 2 3 4 5 6 200
8 1 2 3 4 5 6 200
8 1 2 3 4 5 6
"""
1.2 单向循环链表
单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。
1.2.1操作
is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在
1.2.2 代码实现
# coding:utf-8 class Node(object): """节点""" def __init__(self, elem): self.elem = elem self.next = None class SingleCycleLinkList(object): """单向循环链表""" def __init__(self, node=None): self.__head = node if node: node.next = node def is_empty(self): """链表是否为空""" return self.__head == None def length(self): """链表长度""" if self.is_empty(): return 0 # cur游标，用来移动遍历节点 cur = self.__head # count记录数量 count = 1 while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): """遍历整个链表""" if self.is_empty(): return cur = self.__head while cur.next != self.__head: print(cur.elem, end=" ") cur = cur.next # 退出循环，cur指向尾节点，但尾节点的元素未打印 print(cur.elem) def add(self, item): """链表头部添加元素，头插法""" node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next # 退出循环，cur指向尾节点 node.next = self.__head self.__head = node # cur.next = node cur.next = self.__head def append(self, item): """链表尾部添加元素, 尾插法""" node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next # node.next = cur.next node.next = self.__head cur.next = node def insert(self, pos, item): """指定位置添加元素 :param pos 从0开始 """ if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: pre = self.__head count = 0 while count < (pos-1): count += 1 pre = pre.next # 当循环退出后，pre指向pos-1位置 node = Node(item) node.next = pre.next pre.next = node def remove(self, item): """删除节点""" if self.is_empty(): return cur = self.__head pre = None while cur.next != self.__head: if cur.elem == item: # 先判断此结点是否是头节点 if cur == self.__head: # 头节点的情况 # 找尾节点 rear = self.__head while rear.next != self.__head: rear = rear.next self.__head = cur.next rear.next = self.__head else: # 中间节点 pre.next = cur.next return else: pre = cur cur = cur.next # 退出循环，cur指向尾节点 if cur.elem == item: if cur == self.__head: # 链表只有一个节点 self.__head = None else: # pre.next = cur.next pre.next = self.__head def search(self, item): """查找节点是否存在""" if self.is_empty(): return False cur = self.__head while cur.next != self.__head: if cur.elem == item: return True else: cur = cur.next # 退出循环，cur指向尾节点 if cur.elem == item: return True return False if __name__ == "__main__": ll = SingleCycleLinkList() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(2) ll.add(8) ll.append(3) ll.append(4) ll.append(5) ll.append(6) # 8 1 2 3 4 5 6 ll.insert(-1, 9) # 9 8 1 23456 ll.travel() ll.insert(3, 100) # 9 8 1 100 2 3456 ll.travel() ll.insert(10, 200) # 9 8 1 100 23456 200 ll.travel() ll.remove(100) ll.travel() ll.remove(9) ll.travel() ll.remove(200) ll.travel() #运行结果 """ True 0 False 1 9 8 1 2 3 4 5 6 9 8 1 100 2 3 4 5 6 9 8 1 100 2 3 4 5 6 200 9 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 """
1.3双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
1.3.1 操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历链表
add(item) 链表头部添加
append(item) 链表尾部添加
insert(pos, item) 指定位置添加
remove(item) 删除节点
search(item) 查找节点是否存在
1.3.2 代码实现
# coding:utf-8
class Node(object):
"""结点"""
def __init__(self, item):
self.elem = item
self.next = None
self.prev = None
class DoubleLinkList(object):
"""双链表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head == None
def length(self):
"""链表长度"""
# cur游标，用来移动遍历节点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")
def add(self, item):
"""链表头部添加元素，头插法"""
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node
def append(self, item):
"""链表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, pos, item):
"""指定位置添加元素
:param pos 从0开始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
cur = self.__head
count = 0
while count < pos:
count += 1
cur = cur.next
# 当循环退出后，cur指向pos位置
node = Node(item)
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
def remove(self, item):
"""删除节点"""
cur = self.__head
while cur != None:
if cur.elem == item:
# 先判断此结点是否是头节点
# 头节点
if cur == self.__head:
self.__head = cur.next
if cur.next:
# 判断链表是否只有一个结点
cur.next.prev = None
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
break
else:
cur = cur.next
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
if __name__ == "__main__":
ll = DoubleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
# 8 1 2 3 4 5 6
ll.insert(-1, 9) # 9 8 1 23456
ll.travel()
ll.insert(3, 100) # 9 8 1 100 2 3456
ll.travel()
ll.insert(10, 200) # 9 8 1 100 23456 200
ll.travel()
ll.remove(100)
ll.travel()
ll.remove(9)
ll.travel()
ll.remove(200)
ll.travel()
#运行结果
"""
True
0
False
1
9 8 1 2 3 4 5 6
9 8 1 100 2 3 4 5 6
9 8 1 100 2 3 4 5 6 200
9 8 1 2 3 4 5 6 200
8 1 2 3 4 5 6 200
8 1 2 3 4 5 6
"""
二、栈
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。
2.1栈结构实现
栈可以用顺序表实现，也可以用链表实现。
2.1.1的操作
Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数
2.1.2 栈的代码实现
# coding:utf-8 class Stack(object): """栈""" def __init__(self): self.__list = [] def push(self, item): """添加一个新的元素item到栈顶""" self.__list.append(item) def pop(self): """弹出栈顶元素""" return self.__list.pop() def peek(self): """返回栈顶元素""" if self.__list: return self.__list[-1] else: return None def is_empty(self): """判断栈是否为空""" return self.__list == [] # return not self.__list def size(self): """返回栈的元素个数""" return len(self.__list) if __name__ == "__main__": s = Stack() s.push(1) s.push(2) s.push(3) s.push(4) print(s.pop()) print(s.pop()) print(s.pop()) print(s.pop()) #运行结果 """ 4 3 2 1 """
三、队列
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。
3.1队列的实现
同栈一样，队列也可以用顺序表或者链表实现。
3.1.1操作
Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小
3.1.2 队列代码实现
# coding:utf-8 class Queue(object): """队列""" def __init__(self): self.__list = [] def enqueue(self, item): """往队列中添加一个item元素""" self.__list.append(item) def dequeue(self): """从队列头部删除一个元素""" return self.__list.pop(0) def is_empty(self): """判断一个队列是否为空""" return self.__list == [] def size(self): """返回队列的大小""" return len(self.__list) if __name__ == "__main__": s = Queue() s.enqueue(1) s.enqueue(2) s.enqueue(3) s.enqueue(4) print(s.dequeue()) print(s.dequeue()) print(s.dequeue()) print(s.dequeue()) #运行结果 """ 1 2 3 4 """
3.2双端队列
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
3.2.1 操作
Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小
3.2.2 双端队列代码实现
class Deque(object): """双端队列""" def __init__(self): self.__list = [] def add_front(self, item): """往队列中添加一个item元素""" self.__list.insert(0, item) def add_rear(self, item): """往队列中添加一个item元素""" self.__list.append(item) def pop_front(self): """从队列头部删除一个元素""" return self.__list.pop(0) def pop_rear(self): """从队列头部删除一个元素""" return self.__list.pop() def is_empty(self): """判断一个队列是否为空""" return self.__list == [] def size(self): """返回队列的大小""" return len(self.__list) if __name__ == "__main__": s = Deque() s.add_front(1) s.add_rear(2) s.add_rear(3) s.add_front(4) print(s.pop_front()) print(s.pop_rear()) print(s.is_empty()) print(s.size()) #运行结果 """ 4 3 False 2 """
四、树与树算法
4.1.1
树的概念：
树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
4.1.2
树的术语：
节点的度
：一个节点含有的子树的个数称为该节点的度；
树的度
：一棵树中，最大的节点的度称为树的度；
叶节点
或
终端节点
：度为零的节点；
父亲节点
或
父节点
：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点
：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点
：具有相同父节点的节点互称为兄弟节点；节点的
层次
：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；树的
高度
或
深度
：树中节点的最大层次；
堂兄弟节点
：父节点在同一层的节点互为堂兄弟；
节点的祖先
：从根到该节点所经分支上的所有节点；
子孙
：以某节点为根的子树中任一节点都称为该节点的子孙。
森林
：由m（m>=0）棵互不相交的树的集合称为森林；
4.1.3
树的种类
无序树
：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树
：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
二叉树
：每个节点最多含有两个子树的树称为二叉树；
完全二叉树
：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中
满二叉树
的定义是所有叶节点都在最底层的完全二叉树;
满二叉树
的定义是所有叶节点都在最底层的完全二叉树;
平衡二叉树
（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
排序二叉树
（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
霍夫曼树
（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
B树
：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。
4.1.4树的存储与表示
顺序存储：
将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2
4.1.5常见的一些树的应用场景
1.xml，html等，那么编写这些东西的解析器的时候，不可避免用到树2.路由协议就是使用了树的算法3.mysql数据库索引4.文件系统的目录结构5.所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构
4.2二叉树
4.2.1二叉树的基本概念
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
4.2.2二叉树的性质(特性)
性质1:
在二叉树的第i层上至多有2^(i-1)个结点（i>0）
性质2:
深度为k的二叉树至多有2^k – 1个结点（k>0）
性质3:
对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
性质4:
具有n个结点的完全二叉树的深度必为 log2(n+1)
性质5:
对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
4.2.3二叉树的节点表示以及树的创建
通过使用Node类中定义三个属性，分别为elem本身的值，还有lchild左孩子和rchild右孩子
class Node(object): """节点类""" def __init__(self, elem=-1, lchild=None, rchild=None): self.elem = elem self.lchild = lchild self.rchild = rchild
4.3二叉树的遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
4.3.1深度优先遍历
对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。我们来给出它们的详细定义，然后举例看看它们的应用。
先序遍历
：
在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树 根节点->左子树->右子树
中序遍历 ：
在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树 左子树->根节点->右子树
后序遍历 ：
在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点 左子树->右子树->根节点
4.3.2广度优先遍历(层次遍历)
从树的root开始，从上到下从从左到右遍历整个树的节点
4.4 代码实现
# coding:utf-8
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=" ")
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)
tree.add(8)
tree.add(9)
tree.breadth_travel()
print(" ")
tree.preorder(tree.root)
print(" ")
tree.inorder(tree.root)
print(" ")
tree.postorder(tree.root)
print(" ")
#运行结果
"""
0 1 2 3 4 5 6 7 8 9
0 1 3 7 8 4 9 2 5 6
7 3 8 1 9 4 0 5 2 6
7 8 3 9 4 1 5 6 2 0
"""