1.栈
特性：先进后出的数据结构
栈顶，栈尾
- Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。
- push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
- pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
- peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
- isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
- size() 返回栈中的 item 数量。不需要参数，并返回一个整数。
1 class Stack():
2 def __init__(self):
3 self.items = []
4 def push(self,item):
5 self.items.append(item)
6 def pop(self):
7 if self.isEmpty():
8 return None
9 else:
10 return self.items.pop()
11 def isEmpty(self):
12 #空=》True
13 return self.items == []
14 def peek(self):
15 return self.items[len(self.items) - 1]
16 def size(self):
17 return len(self.items)2.队列
特性：先进先出
• Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
• enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
• dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
• isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。size() 返回队列中的项数。它不需要参数，并返回一个整数。
1 class Queue():
2 def __init__(self):
3 self.items = []
4 def enqueue(self,item):
5 self.items.insert(0,item)
6 def isEmpty(self):
7 return self.items == []
8 def dequeue(self):
9 if self.isEmpty():
10 return None
11 else:
12 return self.items.pop()
13 def size(self):
14 return len(self.items)
15 def travel(self):
16 print(self.items)3.顺序表
- 集合中存储的元素是有顺序的，顺序表的结构可以分为两种形式：单数据类型和多数据类型。
- python中的列表和元组就属于多数据类型的顺序表
- 单数据类型顺序表的内存图（内存连续开启）
- 对应的内存空间是连续开辟的
- 顺序表的变量/引用存的的（指向的）是内存空间的首地址
- 多数据类型顺序表的内存图（内存非连续开辟）
重点：
- 想把数据存储到内存中，必须先在内存中开辟指定大小的内存空间（大小，地址：定位）
- 如果一个引用指向了某一块内存空间，则表示该引用存储了该内存空间的地址
- 顺序表的弊端：顺序表的结构需要预先知道数据大小来申请连续的存储空间，而在进行扩充时 又需要进行数据的搬迁。
4.链表
特性：
相对于顺序表，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是每一个结点（数据存储单元）里存放下一个结点的信息（即地址）
- is_empty()：链表是否为空
- length()：链表长度
- travel()：遍历整个链表
- add(item)：链表头部添加元素
- append(item)：链表尾部添加元素
- insert(pos, item)：指定位置添加元素
- remove(item)：删除节点
search(item)：查找节点是否存在
1 #封装节点数据结构
2 class Node():
3 def __init__(self,item):
4 self.item = item
5 self.next = None
6 def __str__(self):
7 return self.item
8 #封装链表数据结构
9 class Link():
10 #初始化一个空链表
11 def __init__(self):
12 #该属性永远指向第一个节点
13 self._head = None
14 def isEmpty(self):
15 return self._head == None
16 def add(self,item):
17 #创建一个新的节点对象
18 node = Node(item)
19 #将节点插入到链表的头部
20 node.next = self._head
21 self._head = node
22 def travel(self):
23 cur = self._head
24 while cur:
25 print(cur.item)
26 cur = cur.next
27 def length(self):
28 count = 0
29 cur = self._head
30 while cur:
31 count += 1
32 cur = cur.next
33 return count
34 def append(self,item):
35 cur = self._head
36 pre = None #cur前面节点的地址
37
38 node = Node(item)
39 #如果链表为空则新节点作为链表中的第一个节点
40 if self._head is None:
41 self._head = node
42 return
43 #链表非空对应的插入情况
44 while cur:
45 pre = cur
46 cur = cur.next
47 pre.next = node
48
49 def insert(self,pos,item):
50 cur = self._head
51 pre = None
52 node = Node(item)
53 length = self.length()
54 #对特殊情况的处理
55 if pos > length:
56 self.append(item)
57 return
58 if pos <= 0:
59 self.add(item)
60 return
61 #正常处理
62 for i in range(pos):
63 pre = cur
64 cur = cur.next
65 pre.next = node
66 node.next = cur
67 def remove(self,item):
68 cur = self._head
69 pre = None
70 #如果删除的是第一个节点
71 if item == cur.item:
72 self._head = cur.next
73 return
74 while cur:
75 if cur.item == item:
76 pre.next = cur.next
77 return
78 else:
79 pre = cur
80 cur = cur.next
81
82
83 def search(self,item):
84 find = False
85 cur = self._head
86 while cur:
87 if cur.item == item:
88 find = True
89 break
90 cur = cur.next
91 return find5.二叉树
构成：根节点，左叶子结点，右叶子结点，子树
广度遍历：层级
深度遍历：前序（跟左右），中序（左根右），后序（左右根）
1 class Node():
2 def __init__(self,item):
3 self.item = item
4 self.left = None
5 self.right = None
6 class Tree():
7 def __init__(self):
8 self.root = None
9 def add(self,item):
10 node = Node(item)
11
12 if self.root is None:
13 self.root = node
14 return
15 queue = [self.root]
16 while queue:
17 cur = queue.pop(0)
18 if cur.left is None:
19 cur.left = node
20 return
21 else:
22 queue.append(cur.left)
23 if cur.right is None:
24 cur.right = node
25 return
26 else:
27 queue.append(cur.right)
28 def travel(self):
29 if self.root is None:
30 return
31 queue = [self.root]
32
33 while queue:
34 cur = queue.pop(0)
35 print(cur.item)
36 if cur.left is not None:
37 queue.append(cur.left)
38 if cur.right is not None:
39 queue.append(cur.right)
40排序二叉树
1 class Node():
2 def __init__(self,item):
3 self.item = item
4 self.left = None
5 self.right = None
6 class Tree():
7 def __init__(self):
8 self.root = None
9
10 def insertByOder(self,item):
11
12 node = Node(item)
13 if self.root is None:
14 self.root = node
15 return
16
17 cur = self.root
18 while True:
19 if item < cur.item:
20 if cur.left is None:
21 cur.left = node
22 return
23 else:
24 cur = cur.left
25 else:
26 if cur.right is None:
27 cur.right = node
28 return
29 else:
30 cur = cur.right
31
32 def forward(self,root):
33 if root is None:
34 return
35 # 根 左 右
36 print(root.item,end=' ')
37 self.forward(root.left)
38 self.forward(root.right)
39 def mid(self,root):
40 if root is None:
41 return
42 #左根右
43 self.mid(root.left)
44 print(root.item,end=' ')
45 self.mid(root.right)
46 def back(self,root):
47 if root is None:
48 return
49 #左右根
50 self.back(root.left)
51 self.back(root.right)
52 print(root.item,end=' ')
536.个数据结构与其时间复杂度
