一、python递归函数深度限制

python使用递归函数会受到递归深度的限制,大概是900多点(因为100次的时候就会报错:maximum recursion depth exceeded in comparison),嘿嘿嘿

解决方法

导入python中 sys模块,import sys

然后使用 sys 下的 setrecursionlimit去重新规定它的限制

**ps:但是要注意一点设置Python解释器堆栈的最大深度以限制。此限制可防止无限递归导致C堆栈溢出并导致Python崩溃。

最高可能的限制取决于平台。当用户需要深度递归的程序和支持更高限制的平台时,用户可能需要设置更高的限制。这应该小心,因为太高的限制可能导致崩溃

二、栈stack

1、栈的操作

**· stack()创建一个空栈

· push()添加一个新的元素item到栈顶

· pop()弹出栈顶元素

· peek()返回栈顶元素

· is_empty()判断栈是否为空

· size()返回栈的元素个数**

2、栈的代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Stack(object):
'''栈'''
def __init__(self):
self.__list = [] # 建立私有容器
def push(self,item):
''添加一个新的元素到栈顶''
self.__list.append(item)
# self.__list.insert(0,item) 在栈顶插入时复杂度为n,相反在尾部时复杂度就为1
def pop(self):
'''弹出栈顶元素'''
self.__list.pop()
# self.__list.pop(0)
return
def peek():
'''返回栈顶元素'''
if self.__list:
return self.__list[-1]
else:
None
def is_empty(self):
'''判断栈是否为空'''
return not self.__list
def size(self):
'''返回栈中元素的个数'''
return len(self.__list



if __name__ == "__main__":
s = Stack()

三、队列queue

1、只允许在一端进行插入操作,另一端进行删除操作的线性表
2、队列的实现

· queue()创建一个空的队列

· enqueue(item)添加一个新的元素item到队列中

· dequeue()从队头删除一个元素

· is_empty()判断队列是否为空

· size()返回队列中的元素个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Queue(object):
'''队列'''
def __init__(self)
self.__list = []
def enqueue(self,item):
'''往队列中添加一个item元素'''
self.__list.append(item)
# self.__list.insert(0,item)
# 无论选择哪个总有一个的复杂度是O(1),另一个是O(n),具体选择根据自己功能哪个用的多
def dequeue(self):
'''从队列中删除一个元素'''
return self.__list.pop()
def is_empty(self):
'''判断一个队列是否为空'''
return self.__list == []
def size(self):
'''返回队列的大小'''
return len(self.__list)

if __init__ == "__main__":
s = Queue()
s.enqueue(1)
s.enqueue(2)

四、双端队列

**· deque创建一个空的双端队列

· add_front(item)从队头加入一个item元素

· add_rear(item)从队尾加入一个item元素

· remove_front()从队头删除一个item元素

· remove_rear()从队尾删除一个item元素

· is_empty()判断双端队列是否为空

· size()返回双端队列的大小**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Deque(object):
'''双端队列'''
def __init__(self)
self.__list = []
def add_front(self,item):
'''往双端队列的头部添加一个item元素'''
self.__list.insert(0,item)
def add_rear(self):
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)

五、链表

1、单向链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Node(object):
'''节点'''
def __init__(self,elem):
self.elem = elem
self.next = None
# 同样可以利用python的二元组进行操作(elem)
class Single_LinkList(object):
'''单链表'''
def __init__(self,node=None): # 就是一个内部的使用,规定一个头结点,而且这个头结点应该是私有的,因为在封装后的SingleLinkList对象中,外部能够调用的就是以下的几个函数,其他的是无法使用的,所以私有化处理了,纯粹是自己的内部函数去使用;
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)
cur = cur.next
print("\n")
def add(self,item):
'''链表头部添加元素,头插法'''
node = Node(item)
node.next = self.__head.next
self.__head = node
def append(self,item): # 这里的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): # 在任意位置添加元素,pos表示需要添加元素的位置,item表示要添加的数据
'''在某个位置插入元素'''
if pos <= 0:
self.add(item)
elif pos > (self.length-1):
self.append(item)
else:
pre = self.__head # pre的用法和cur一样
count = 0
while count < pos-1:
count += 1
pre = pre.next
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self,item):
'''删除节点'''
cur = self.__head
pre = None
while cur != item:
if cur.elem == item:
# 要判断此节点是不是头节点
if cur == self.__head:
self.__head = cur.next
break
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self,item):
'''查找节点是否存在'''
cur = self.__head
while cur is not None:
if cur.elem == item:
return True
else:
cur = cur.next
return False

链表和顺序表的比较

操作 链表 顺序表
访问元素 O(1) O(1)
头部插入 or 删除元素 O(1) O(n)
尾部插入 or 删除元素 O(n) O(1)
在中间插入 or 删除元素 O(n) O(n)

六、双向链表

1、操作

**· is_empty()链表是否为空

· length()链表长度

· travel()遍历整个链表

· add(item)链表头部添加信息

· append(item)链表尾部添加信息

· insert(pos, item)在特定位置添加元素

· remove(item)删除节点

· search(item)查找节点是否存在**

2、代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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 is None
def length(self):
'''双链表长度'''
cur = self.__head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
'''遍历双链表'''
cur = self.__head
while cur != None:
print(cur.elem)
cur = cur.next
print("\n")
def add(self,item):
'''头部添加元素'''
node = Node(item)
node.next = self.__head.next
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):
'''在双向链表的某个位置插入元素'''
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 = node
cur.prev.next = node
def remove(self,item):
'''删除节点'''
# cur 游标指向头结点的时候,pre指向空,相差一个单位的距离
cur = self.__head
pre = None
while cur != None:
if cur.elem is item:
# 判断当前游标cur指向是不是在1处
if cur is self.__head:
self.__head = cur.next
# 判断cur.next是否为空,因为空的元素是没有prev的
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 serch(self,item):
'''查找节点'''
cur = self.__head
whilt cur != None:
if cur.elem is item:
return True
else:
cur = cur.next
return False