Python实现数据结构

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 find

5.二叉树

构成：根节点，左叶子结点，右叶子结点，子树

广度遍历：层级

深度遍历：前序（跟左右），中序（左根右），后序（左右根）

 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=' ')
53