内容：
1.数组
2.链表
3.字典
4.二叉树(搜索树)
5.set集合实现
1.数组
数组在python中是以列表的形式存在，基本上每一个语言中都有数组形式的数据结构存在
数组一般存储在连续的一块内存，数组存取元素时间是 O(1)，插入、删除是 O(n)，另外可以用数组实现栈和队列，栈：先进后出，队列：先进先出
另外python list中有两个部件：
- 数组 存储数据在链表中的地址
- 链表 实际存储数据
列表：
lt = [1, 2, 3, 4, 5, 5] # 存取
print(lt[0])
lt[1] = 666
print(lt) # 插入元素
lt.insert(0, 333)
print(lt) # 删除元素
# 按值删除:
lt.remove(5)
print(lt)
# 按索引删除:
lt.pop(0)
print(lt)
del lt[0]
print(lt)
用python中的list相关操作实现栈和列表如下：
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/28 class Stack(object):
def __init__(self):
self.lt = [] def empty(self):
"""
判断栈是否为空
:return:
"""
return len(self.lt) == 0 def top(self):
"""
查看栈顶的对象，但不移除
:return:
"""
if not self.empty():
return self.lt[-1]
return None def push(self, obj):
"""
把对象压入栈顶
:return:
"""
self.lt.append(obj) def pop(self):
"""
移除栈顶对象，并返回该对象的值
:return:
"""
if not self.empty():
return self.lt.pop()
return None def search(self, obj):
"""
返回对象在栈中的位置，以1为基数
:param obj:
:return:
"""
if not self.empty():
return self.lt.index(obj) + 1
return -1 class Queue(object):
def __init__(self):
self.lt = [] def empty(self):
"""
判断队列是否为空
:return:
"""
return len(self.lt) == 0 def first(self):
"""
查看队首的对象，但不移除
:return:
"""
if not self.empty():
return self.lt[0]
return None def enqueue(self, obj):
"""
将指定元素加入队列的尾部
:param obj:
:return:
"""
self.lt.append(obj) def dequeue(self):
"""
移除队首对象，并返回该对象的值
:return:
"""
if not self.empty():
return self.lt.pop(0)
return None def search(self, obj):
"""
返回对象在队列中的位置，以1为基数
:param obj:
:return:
"""
if not self.empty():
return self.lt.index(obj) + 1
return -1
用python list实现python中的set：
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/29 class Set(object):
def __init__(self, *args):
self.table_size = 10007
self.data = [0] * self.table_size
for i in args:
self.add(i) def __repr__(self):
"""
调用str及输出的魔法方法
:return:
"""
lt = set()
for i in range(0, len(self.data)):
if self.data[i] != 0:
item = self.data[i]
lt.add(item[0])
return str(lt) def __eq__(self, other):
"""
判断相等的魔法方法
:param other:
:return:
"""
if type(other) == type(self):
return str(self.data) == str(other.data)
else:
return False def remove(self, x):
index = self._index(x)
self.data[index] = 0 def _index(self, obj):
index = hash(obj) % self.table_size
return index def _insert_at_index(self, index, key):
v = self.data[index]
if v == 0:
self.data[index] = [key]
else:
return False def add(self, key):
# 先计算出下标
index = self._index(key)
# 在下标处插入元素
self._insert_at_index(index, key) # for i in range(0, len(self.data)):
# if self.data[i] == x:
# return False
# self.data.append(x) def has(self, key):
index = self._index(key)
# 取元素
v = self.data[index]
if isinstance(v, list):
if v[0] == key:
return True
return False # for i in range(0, len(self.data)):
# if self.data[i] == x:
# return True
# return False def testSet():
a = Set(1, 2, 2, 3, 4, 4)
b = Set(1, 2, 2, 3, 4)
c = Set(1, 3, 4, 2)
d = Set(2, 3)
assert (str(a) == '{1, 2, 3, 4}')
print(a, b, c, d)
assert (a == b)
assert (a == c)
assert (a != d)
assert (a.has(1) is True)
a.remove(1)
assert (a.has(1) is False)
a.add(1)
assert (a.has(1) is True) if __name__ == '__main__':
testSet()
2.链表
我们可以将链表比作手拉手的盒子，一个盒子只能访问左右手的盒子
以下标方式读取元素的时间是 O(n)，插入、删除是 O(1)，栈和队列可以用链表实现，栈：先进后出，队列：先进先出
链表简单实现：
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/27 class Node():
def __init__(self, element=None):
self.e = element
self.next = None def append(node, element):
"""
append: 添加一个元素到末尾
:param node: 是一个 Node 实例
:param element: 任意类型的元素
"""
n = node
while n.next is not None:
n = n.next
# n 现在是最后一个元素
new_node = Node(element)
n.next = new_node def prepend(head_node, element):
"""
prepend: 添加一个元素到开头
:param head_node: 头元素
:param element: 任意类型的元素
:return:
"""
n = Node(element)
n.next = head_node.next
head_node.next = n def pop(head_node):
"""
pop是stack的两个操作之一
push 入栈
pop 出栈
prepend + pop 就实现了 队列 的 入队(enqueue)和出队(dequeue)操作
append + pop 就实现了 栈 的 入栈(push) 和 出栈(pop)操作
:param head_node: 头部节点
:return:
"""
tail = head_node
while tail.next is not None:
tail = tail.next
# 现在 tail 是最后一个元素了
n = head_node
while n.next is not tail:
n = n.next
# 现在 n 是 tail 之前的元素了
n.next = None
return tail.e def log_list(node):
n = node
s = ''
while n is not None:
s += (str(n.e) + ' > ')
n = n.next
print(s[0: -2]) head = Node()
n1 = Node(111)
n2 = Node(222)
n3 = Node(333)
n1.next = n2
n2.next = n3 head.next = n1 log_list(n1)
append(n1, 'gua')
log_list(n1)
prepend(head, 'hello')
log_list(head)
print('pop head: ', pop(head))
log_list(head)
链表封装成类：
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/27 # 节点类
class Node(object):
def __init__(self, element=-1):
self.element = element
self.next = None # 链表类
class LinkedList(object):
def __init__(self):
self.head = None def is_empty(self):
"""
判断链表是否为空
:return:
"""
return self.head is None def length(self):
"""
获得链表长度(包含head)
:return:
"""
index = 0
node = self.head
while node is not None:
index += 1
node = node.next
return index def find(self, element):
"""
查找元素
:param element: 元素值
:return:
"""
node = self.head
while node is not None:
if node.element == element:
return node
node = node.next
return None def _node_at_index(self, index):
"""
返回某个节点
:param index: 索引 -> 从0开始 0是head
:return:
"""
i = 0
node = self.head
while node is not None:
if i == index:
return node
node = node.next
i += 1
return None def element_at_index(self, index):
"""
返回某个节点的值
:param index: 索引 -> 从0开始 0是head
:return:
"""
node = self._node_at_index(index)
return node.element def first_object(self):
"""
返回第一个节点 -> head
:return:
"""
return self._node_at_index(0) def last_object(self):
"""
返回最后一个节点
:return:
"""
i = 0
while self._node_at_index(i) is not None:
i += 1
return self._node_at_index(i - 1) def insert_before_index(self, position, element):
"""
在节点之前插入元素
:param position: 节点位置
:param element: 元素值
:return:
"""
insert_node = Node(element)
# 错误情况判断:
if position == 0:
print("不能在head之前插入元素")
return False
if self._node_at_index(position) is None:
print("节点顺序超了!请输入正确的节点顺序!")
return False
node = self._node_at_index(position - 1)
# 插入元素
insert_node.next = node.next
node.next = insert_node def insert_after_index(self, position, element):
"""
在节点之后插入元素
:param position: 节点位置
:param element: 元素值
:return:
"""
insert_node = Node(element)
node = self._node_at_index(position)
# 错误情况判断:
if node is None:
print("节点顺序超了!请输入正确的节点顺序!")
return False
# 在节点之后插入元素
insert_node.next = node.next
node.next = insert_node def append(self, element):
"""
在最后插入节点
:param element: 节点值
:return:
"""
node = Node(element)
if self.head is None:
self.head.next = node
else:
last_node = self.last_object()
last_node.next = node
node.front = last_node def prepend(self, element):
"""
在开头插入节点
:param element: 节点值
:return:
"""
node = Node(element)
node.next = self.head.next
self.head.next = node def pop(self):
"""
删除最后一个节点
:return:
"""
tail = self.first_object()
while tail.next is not None:
tail = tail.next
# 现在 tail 是最后一个元素了
n = self.first_object()
while n.next is not tail:
n = n.next
# 现在 n 是 tail 之前的元素了
n.next = None
return tail.element def log_list(self, msg=""):
"""
输出链表
:param msg: 输出链表之前显示的信息
:return:
"""
n = self.head.next
s = msg + ''
while n is not None:
s += (str(n.element) + ' > ')
n = n.next
print(s[0: -2]) # 测试链表初始化及输出链表:
def test_log():
head = Node(0)
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
lt = LinkedList()
lt.head = head
head.next = n1
n1.next = n2
n2.next = n3
lt.log_list("输出链表: ")
return lt # 测试链表判空及链表长度:
def test_empty_length(lt):
if lt.is_empty() is True:
print("链表为空")
return None
else:
length = lt.length()
print("链表不为空, 链表长度为: ", length)
return length # 测试find
def test_find(lt):
if lt.find(5) is None:
print("链表中不存在5")
else:
print("链表中存在5")
node = lt.find(5)
return node if lt.find(3) is None:
print("链表中不存在3")
else:
print("链表中存在3")
node = lt.find(3)
return node # 测试element_at_index
def test_element_at_index(lt):
print(lt.element_at_index(0))
print(lt.element_at_index(1))
print(lt.element_at_index(2))
print(lt.element_at_index(3)) # 测试first_obj和last_obj
def test_first_last(lt):
print(lt.first_object().element)
print(lt.last_object().element) # 测试插入
def test_insert(lt):
lt.insert_before_index(0, "在节点0之前插入")
lt.log_list()
lt.insert_before_index(1, "在节点1之前插入")
lt.log_list()
lt.insert_after_index(0, "在节点0之后插入")
lt.log_list()
lt.insert_after_index(2, "在节点2之后插入")
lt.log_list()
lt.append("在最后插入节点")
lt.log_list()
lt.prepend("在开头插入节点")
lt.log_list() # 测试pop
def test_pop(lt):
lt.pop()
lt.log_list("删除最后一个元素: ") # 单元测试
def test():
linked_list = test_log() # 测试空链表:
# test_empty_length(LinkedList()) # 测试非空链表:
# test_empty_length(linked_list) # 测试find
# test_find(linked_list) # 测试element_at_index
# test_element_at_index(linked_list) # 测试first_obj和last_obj
# test_first_last(linked_list) # 测试insert
# test_insert(linked_list) # 测试pop
# test_pop(linked_list) if __name__ == '__main__':
test()
另外，关于栈和队列的实现：
上述链表实现中prepend + pop 就实现了 队列 的 入队(enqueue)和出队(dequeue)操作，append + pop 就实现了 栈 的 入栈(push) 和 出栈(pop)操作
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/28 """
数据结构的核心是，一个结构只有特定的操作，可以实现特定的功能 栈的特点是「先进后出」，一般有这几个操作
# push 将一个元素存入栈中
# pop 将一个元素从栈中取出，并在栈中删除它 # top 将一个元素从栈中取出
# is_empty 查看栈是否是空的 """ # Node类是一个节点，有两个属性，一个存储元素，一个存储指向另一个节点的引用
class Node:
def __init__(self, element=None, next=None):
self.element = element
self.next = next # 这个函数是会在print的时候被自动调用，就是把这个Node显示出来
def __repr__(self):
return str(self.element) class Stack:
# 初始化函数，自动被调用
# 初始化Stack()类的时候，它有一个head属性，值是一个空的Node
def __init__(self):
self.head = Node() # 如果head的next属性为空，则说明栈是空的
def is_empty(self):
return self.head.next is None # 创建一个node，并让它指向当前head.next指向的元素，再把head.next指向它
def push(self, element):
self.head.next = Node(element, self.head.next) # 取出head.next指向的元素，如果栈不是空的，就让head.next指向node.next，这样node就不在栈中了
def pop(self):
node = self.head.next
if not self.is_empty():
self.head.next = node.next
return node # head.next就是栈里面第一个元素
def top(self):
return self.head.next # 测试函数
def test():
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()) if __name__ == '__main__':
# 运行测试函数
test()
链表实现栈
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/28 """
队列的特点是「先进先出」，一般有这几个操作 # enqueue 将一个元素存入队列中
# dequeue 将一个元素从队列中取出，并在队列中删除它 # empty 查看栈是否是空的 可以把队列看做排队，银行叫号机就是队列，先取号的先入队，叫号的时候也就先出队
""" # Node类是一个节点，有两个属性，一个存储元素，一个存储指向另一个节点的引用
class Node:
def __init__(self, element=None, next=None):
self.element = element
self.next = next # 这个函数是会在print的时候被自动调用，就是把这个Node显示出来
def __repr__(self):
return str(self.element) class Queue:
# 初始化函数，自动被调用
# 初始化Queue()类的时候，它有2个属性，分别指向头尾
def __init__(self):
self.head = Node()
self.tail = self.head # 如果head的next属性为空，则说明队列是空的
def empty(self):
return self.head.next is None # 创建一个node
# 让tail.next指向它
# 让tail指向它，tail现在就是新的队尾了
def enqueue(self, element):
n = Node(element)
self.tail.next = n
self.tail = n # 取出head.next指向的元素，如果队列不是空的，就让head.next指向node.next，这样node就不在队列中了
def dequeue(self):
node = self.head.next
if not self.empty():
self.head.next = node.next
return node # 测试函数
def test():
q = Queue() q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4) print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue()) if __name__ == '__main__':
# 运行测试函数
test()
链表实现队列
3.字典(哈希表、对象、Map)
python中的字典把字符串转为数字作为下标存储到数组中，字符串转化为数字的算法是 O(1)，所以字典的存取操作都是 O(1)
除非对数据有顺序要求，否则字典永远是最佳选择
字符串转化为数字的算法：
- 确定数据规模，这样可以确定容器数组的大小 Size
- 把字符当作 N 进制数字得到结果
- eg：'gua' 被视为 g * 1 + u * 10 + a * 100 得到结果 n，n % Size 作为字符串在数组中的下标(通常 Size 会选一个 素数)
- 当下标冲突时，有标准的解决碰撞方法(链接法)
实现字典(哈希表)：
class HashTable(object):
def __init__(self):
# table 是用来存储数据的数组
# 先让它有 10007 个格子好了
# 上课的时候说过, 这个尺寸最好选素数
# 这样可以得到更为合理的下标分布
self.table_size = 10007
self.table = [0] * self.table_size # 这个魔法方法是用来实现 in not in 语法的
def __contains__(self, item):
return self.has_key(item) def has_key(self, key):
"""
检查一个 key 是否存在, 时间很短, 是 O(1)
如果用 list 来存储, 需要遍历, 时间是 O(n)
"""
index = self._index(key)
# 取元素
v = self.table[index]
if isinstance(v, list):
# 检查是否包含我们要找的 key
for kv in v:
if kv[0] == key:
return True
# 如果得到的是 int 0 说明没找到, 返回 False
# 如果得到的是 list 但是遍历结果没有我们要找的 key 也是没找到
return False def _insert_at_index(self, index, key, value):
# 检查下标处是否是第一次插入数据
v = self.table[index]
data = [key, value]
# 也可以用这个判断 if v == 0:
if isinstance(v, int):
# 如果是第一次, 得到的是 int 0
# 那么就插入一个 list 来存, 以后相同 key 的元素都放这里面
# 注意我们把 key value 作为一个数组保存进去了, 这是因为
# 会出现相同 hash 值的 key
# 这时候就需要比较原始信息来找到相应的数据
self.table[index] = [data]
else:
# 如果不是, 得到的会是 list, 直接 append
self.table[index].append(data) def add(self, key, value):
"""
add 函数往 hashtable 中加入一对元素
我们先只支持字符串当 key
"""
# 先计算出下标
index = self._index(key)
# 在下标处插入元素
self._insert_at_index(index, key, value) def get(self, key, default_value=None):
"""
这个和 dict 的 get 函数一样
"""
index = self._index(key)
# 取元素
v = self.table[index]
if isinstance(v, list):
# 检查是否包含我们要找的 key
for kv in v:
if kv[0] == key:
return kv[1]
# 如果得到的是 int 0 说明没找到, 返回 default_value
# 如果得到的是 list 但是遍历结果没有我们要找的 key 也是没找到
return default_value def _index(self, key):
# 先计算出下标
return self._hash(key) % self.table_size def _hash(self, s):
"""
下划线开始的函数被我们视为私有函数
但实际上还是可以在外部调用, 这只是一个给自己看的标记
"""
n = 1
f = 1
for i in s:
n += ord(i) * f
f *= 10
return n def test():
import uuid
names = [
'gua',
'xiao',
'name',
'web',
'python',
]
ht = HashTable()
for key in names:
value = uuid.uuid4()
ht.add(key, value)
print('add 元素', key, value)
for key in names:
v = ht.get(key)
print('get 元素', key, v)
print('魔法方法', 'gua' in ht) if __name__ == '__main__':
test()
4.二叉树(搜索树)
二叉树(又叫搜索树)：
# encoding: utf-8
# __author__ = "wyb"
# date: 2018/9/28 class Tree(object):
def __init__(self, element=None):
self.element = element
self.left = None
self.right = None def traversal(self):
"""
树的遍历, 是一个递归操作
"""
print(self.element) # 前序遍历
if self.left is not None:
self.left.traversal()
# print(self.element) # 中序遍历
if self.right is not None:
self.right.traversal()
# print(self.element) # 后序遍历 def reverse(self):
"""
翻转二叉树
:return:
"""
self.left, self.right = self.right, self.left
if self.left is not None:
self.left.reverse()
if self.right is not None:
self.right.reverse() def test():
# 手动构建二叉树
t = Tree(0)
left = Tree(1)
right = Tree(2)
t.left = left
t.right = right
# 遍历
t.traversal() if __name__ == '__main__':
test()
5.set集合实现
(1)题目要求
# 作业一：
# 写一个 set 的类, 无序且元素不重复，内部使用数组来存储元素，具有以下成员函数
# 1. remove ，删除元素
# 2. add， 增加元素
# 3. has，判断元素是否存在
# 形式如下：
# class Set(object)：
# def __init__(self, *args)
# self.data = []
# # ...
# def remove(self, x):
# pass
# def add(self, x):
# pass
# def has(self, x):
# pass
#
#
# 作业二：
# 在作业一的基础上，在Set类里增加 __repr__ 和 __eq__ 两个成员函数。
# 并通过附带 testSet() 函数的测试。
# 形式如下：
# class Set(object)：
# # ...
# def __init__(self, *args)
# self.data = []
#
# def __repr__(self):
# pass
#
# def __eq__(self, other):
# pass
#
# def remove(self, x):
# pass
# def add(self, x):
# pass
# def has(self, x):
# pass
#
# def testSet():
# a = Set(1, 2, 2, 3, 4, 4)
# b = Set(1, 2, 2, 3, 4)
# c = Set(1, 3, 4, 2)
# d = Set(2, 3)
# assert (str(a) == '{1, 2, 3, 4}')
# print(a, b, c, d)
# assert (a == b)
# assert (a == c)
# assert (a != d)
# assert (a.has(1) == True)
# a.remove(1)
# assert (a.has(1) == False)
# a.add(1)
# assert (a.has(1) == True)
#
#
# 作业三：
# 参考第17课板书 hash_table 的代码，写一个类 Set，实现时间复杂度为O(1) 的 add,remove 函数 。
# 形式如下：
# class Set(object):
# # ...
# def add(self, x):
# pass
#
# def remove(self, x):
# pass
(2)实现