- Day02_1单链表代码
- 01_siglelinkList.py
- Day02_1单链表视图
- Day02_1回顾
- Day02_2单链表代码
- 01_siglelinkList.py
- Day02_2单链表视图
- Day02_3栈代码
- 02_listStack.py
- 03_singlelinkListStack.py
- Day02_3图解
"""
单链表
节点对象 --> 类
域 --> 类属性
"""
class Node:
"""
节点类
"""
def __init__(self, value):
self.value = value
self.next = None
class SinglelinkList:
"""
单链表
"""
def __init__(self, node=None):
"""
list01 = list() --> list(xx)
s = SinglelinkList() 表示空链表
s = SinglelinkList(Node(100)) 表示有一个节点的链表
"""
self.head = node
def is_empty(self):
"""
判断链表是否为空
"""
return self.head == None
def add(self, item):
"""
在链表头部添加节点
"""
node = Node(item)
node.next = self.head
self.head = node
def travel(self):
"""
遍历整个链表 ---> 创建游标 移动游标
"""
# 创建游标
cur = self.head
while cur:
print(cur.value)
cur = cur.next
def append(self, item):
"""
在链表尾部增加元素
注意：考虑空链表情况
"""
node = Node(item)
if self.is_empty(): # 空链表情况
self.head = node
return
else: # 非空链表情况
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
if __name__ == '__main__':
s = SinglelinkList()
# 打印1：True
print(s.is_empty())
# 头部添加节点对象
s.add(300)
s.add(200)
s.add(100)
s.add(50)
# 打印2：False
print(s.is_empty())
# 遍历链表 --> 头到尾
s.travel()
# 在链表尾部添加节点
s.append(400)
s.travel()
Day02_1单链表视图
Day02_1回顾
Python 开发：
公司：新创型公司 京东外包
面试题：
你是怎么理解闭包？
你如何理解装饰器？装饰器的应用
迭代器是什么？
生成器是什么？
进程、线程、协程的区别？
GIL是什么?为什么要有GIL？【GIL锁、线程锁】
为什么我们有了GIL,但是在多线程的时候还需要加锁？
MySQL的主键索引和唯一索引有什么区别？【索引、引擎、事务、优化、锁】
【索引的优点：为了加快数据检索的速度，缺点：索引需要动态维护消耗资源，索引需要占用物理存储空间】
MySQL的引擎都有什么?【InnDB：支持外键、支持事务、支持行级锁、适用用于写操作多的表，MyISAM：支持表级锁，适用于读操作多的表，MEMORY：表记录储存在内存中，适用于临时表】
数据库如何优化？如何优化查询？【分组、聚合、排序、筛选、连接查询】
如何开启慢查询？
B树和B+树的优点和使用场景？
【事务：原子性：一致性：隔离性：持久性】
【优化】
DJANGO 的请求流程？
高并发的处理
如何进行会话状态的保持
如何解决跨域问题?
CSRF跨站攻击如何防范?
如何加速数据的查询？如何防范SQL注入？
celery的核心组件有哪些？【消息中间件broker【Redis】、Worker、Backend】【prefork、 -P 】
各种排序算法？
针对于项目，你遇到了那些问题？如何解决？
其他：
编码规范
数据结构和算法：
程序 = 数据结构 + 算法
时间复杂度：大O表示法，最坏情况下面执行的次数
数据结构：
线性结构：
顺序表：
单链表：
栈：
队列：
非线性结构：
Day02_2单链表代码 01_siglelinkList.py
"""
单链表
节点对象 --> 类
域 --> 类属性
"""
class Node:
"""
节点类
"""
def __init__(self, value):
self.value = value
self.next = None
class SinglelinkList:
"""
单链表
"""
def __init__(self, node=None):
"""
list01 = list() --> list(xx)
s = SinglelinkList() 表示空链表
s = SinglelinkList(Node(100)) 表示有一个节点的链表
"""
self.head = node
def is_empty(self):
"""
判断链表是否为空
"""
return self.head == None
def add(self, item):
"""
在链表头部添加节点
"""
node = Node(item)
node.next = self.head
self.head = node
def travel(self):
"""
遍历整个链表 ---> 创建游标 移动游标
"""
# 创建游标
cur = self.head
while cur:
print(cur.value)
cur = cur.next
def append(self, item):
"""
在链表尾部增加元素
注意：考虑空链表情况
"""
node = Node(item)
if self.is_empty(): # 空链表情况
self.head = node
return
else: # 非空链表情况
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""
在指定位置插入节点
"""
node = Node(item)
# 空链表
if not self.head:
self.append(item)
return
# 非空链表
elif pos > self.length() - 1:
self.append(item)
else:
cur = self.head
middle = 0
while middle < (pos - 1):
cur = cur.next
middle += 1
node.next = cur.next
cur.next = node
def length(self):
"""
获取链表长度
"""
if not self.head:
return 0
cur = self.head
count = 1
while cur.next:
cur = cur.next
count += 1
return count
def remove(self, item):
"""
删除一个节点
"""
pre = None # 游标前的一个节点
cur = self.head
# 1. 删除头节点的情况
if self.head.value == item:
self.head = self.head.next
return
# 2. 删除非头结点的情况
while True:
if cur.value == item:
pre.next = cur.next
return
pre = cur
cur = cur.next
if __name__ == '__main__':
s = SinglelinkList()
# 打印1：True
print(s.is_empty())
# 头部添加节点对象
s.add(300)
s.add(200)
s.add(100)
s.add(50)
# 打印2：False
print(s.is_empty())
# 遍历链表 --> 头到尾
s.travel()
# 在链表尾部添加节点
s.append(400)
s.travel()
# 在指定位置插入节点
s.insert(2, 250)
print('---------')
s.travel()
# 删除节点
s.remove(50)
print('---------')
s.travel()
Day02_2单链表视图
Day02_3栈代码 02_listStack.py
"""
栈：
只允许在一端[栈顶]操作数据
特点：
Last In First Out 后进先出
栈是顺序存储：
1. 顺序存储实现栈模型 --> list
栈顶：列表的尾部作为栈顶，负责 入栈[append()] 和 出栈[pop()] 操作
栈底：列表的头部作为栈底，不负责任何操作
2. 链表 ---> SinglelinkList
"""
class ListStack:
def __init__(self):
# 初始化一个空栈
self.elems = []
def is_empty(self):
"""
判断栈是否为空【判断列表是否为空】，为空则返回True，非空返回False
"""
return self.elems == []
def push(self, item):
"""
入栈操作：栈顶操作数据 ---> 列表的尾部增加数据
"""
self.elems.append(item)
def destack(self):
"""
出栈操作：栈顶操作数据 ---> 列表的尾部弹出数据
"""
if self.is_empty():
raise Exception('destack from an empty stack')
return self.elems.pop()
def peek(self):
"""
查看栈顶元素：相当于查看列表最后元素
"""
if self.is_empty():
raise Exception('destack from an empty stack')
return self.elems[-1]
def size(self):
"""
栈大小：相当于查看列表中元素的个数
"""
return len(self.elems)
if __name__ == '__main__':
s = ListStack()
# 判断栈是否为空
print(s.is_empty())
# 入栈操作：300 200 100
s.push(300)
s.push(200)
s.push(100)
print(s.is_empty())
# 出栈操作：100
print(s.destack())
# 查看栈顶元素 200
print(s.peek())
# 查看栈中元素数量 2
print(s.size())
03_singlelinkListStack.py
"""
栈：
只允许在一端[栈顶]操作数据
特点：
Last In First Out 后进先出
栈是顺序存储：
1. 顺序存储实现栈模型 --> list
栈顶：列表的尾部作为栈顶，负责 入栈[append()] 和 出栈[pop()] 操作
栈底：列表的头部作为栈底，不负责任何操作
2. 链表 ---> SinglelinkList
栈顶：链表的头部作为栈顶, 进行 入栈[相当于在链表的头部添加节点] 和 出栈[删除链表的头节点] 操作
栈底：链表的尾部作为栈底，不进行任何操作
"""
class Node:
def __init__(self, value):
self.value = value
self.next = None
class SinglelinkListStack:
def __init__(self):
self.head = None
def is_empty(self):
"""判断栈是否为空：相当于判断链表是否为空"""
return self.head == None
def push(self, item):
"""入栈：相当于在链表的头部添加一个节点"""
node = Node(item)
node.next = self.head
self.head = node
def pop(self):
"""出栈：相当于删除链表的头节点"""
if self.is_empty():
raise Exception('pop from an empty stack')
item = self.head.value
self.head = self.head.next
return item
def peek(self):
"""查看栈顶元素：相当于查看头节点元素"""
if self.is_empty():
raise Exception('from an empty stack')
return self.head.value
def size(self):
"""栈大小:相当于查看链表的元素数量"""
count = 0
cur = self.head
while cur:
count += 1
cur = cur.next
return count
if __name__ == '__main__':
s = SinglelinkListStack()
# 入栈： 300 200 100
s.push(300)
s.push(200)
s.push(100)
# 判断是否为空
print(s.is_empty())
print(s.pop()) # 100
print(s.peek()) # 200
print(s.size()) # 2
Day02_3图解
