【python数据结构算法篇】python数据结构

持续更新中。。。。学到哪总结到哪

0. 介绍

没什么说的。。。。当目录用吧。。。

1. python内置数据结构

四件套很基础，大致过一下

1.1 列表

这个。。。就是增删改查。大致复习一下，以后python数据结构和算法基本上都是用列表实现

# 创建列表
li = []
# 从末尾增加数据
li.append(1)
# 从自定义位置增加数据
li.insert(0, 2)
# 修改数据
li[0]= 3
# 从末尾删除数据
li.pop()
# 从指定位置删除数据
li.pop(0)
# 获取长度
len(li)
# 遍历列表
for i in range(len(li)):print(i)

1.2 元组

# 创建元组
tup_single = (50,)

1.3 字典

# 创建字典
dict1 = {"age": 18}
# 添加&修改元素
dict1['age'] = 31 
dict1['name'] = 'xujie'
# 删除元素
del dict1['city']
name = dict1.pop('name')
# 获取键
dict1.keys()
# 获取值
dict1.values()
# 获取键值对
dict1.items()
# 字典赋值
dict1.update({"age":19})
# 清空
dict1.clear()

1.4 集合

# 创建集合
set1 = {1, 2, 3, 4}
set2 = set([1, 2, 3, 4])
# 添加元素
set1.add(5)
# 移除元素
set1.remove(3)
# 随机弹出元素
set_element = set1.pop()
# 清空集合
set1.clear()

2. 线性表

2.1 字符串

字符串是一种线性表，也是python内置数据结构之一，因其性质较多，故规划进线性表内

# 创建
# 单行
string1 = 'hello world'
# 多行
string2 = '''
1
2
3
'''# 拼接
string2 = string1 + string1
# 重复
string2 = "hello "*3
# 索引
string2 = string1[0]# 转小写
string1.lower()
# 转大写
string1.upper()
# 去除两端空白
string1.strip()
# 替换内容
string1.replace("h", "H")
# 查找
string1.find("l")
# 拆分
stirng1.split(" ")
# 连接
'...'.join(string1)
# 判断开头
string1.startswith("h")
# 判断结尾
string1.endswitch("d")# 编码
string1 = string1.encode('utf-8')
# 解码
string1 = string1.decode('utf-8')# 迭代
for i in string1:print(i)

2.2 python栈的实现

栈是一种先进后出的数据结构，可以使用列表append方法实现将元素仅能从列表尾部插入数据(压栈)，并且不能从列表其他位置压入栈，使用列表的pop方法实现仅能从列表尾部(栈顶)弹出数据，并且不可从其他地方弹出。python实现栈的数据结构如下

class Stack:"""栈类"""def __init__(self):self._li = []def push(self, item):"""进栈方法"""self._li.append(item)def pop(self):"""出栈方法"""self._li.pop()def travel(self):"""遍历方法"""_sum = []for i in self._li:_sum.append(i)return _sum	

2.3 python队列的实现

队列是一种先进先出的数据结构

2.3.1 单调队列

可以使用列表append方法实现将元素仅能从列表尾部插入数据(入队)，并且不能从列表其他位置入队，使用列表的pop(0)方法实现仅能从列表头部(队头)弹出数据，并且不可从其他地方弹出。python实现栈的数据结构如下

class Queue:"""单调队列类"""def __init__(self):self._li = []def push(self, item):"""入队列"""self._li.append(item)def pop(self, item):"""出队列"""self._li.pop(0)def travel(self):"""遍历队列"""_num = []for i in range(len(self._li)):_num.append(i)return _num

2.3.2 双端队列

可以从队头和队尾任意一端入队，也可以从队头和队尾任意一端出队
可以使用列表append和insert(0, item)方法实现将元素从列表尾部(头部)插入数据(入队)，并且不能从列表其他位置入队，使用列表的pop()和pop(0)方法实现仅能从列表头部(尾部)弹出数据，并且不可从其他地方弹出。python实现栈的数据结构如下

class Dequeue:"""双端队列类"""def __init__(self):self._li = []def front_push(self, item):"""队头插入数据"""self._li.insert(0, item)def back_push(self, item):"""队尾插入数据"""self._li.append(item)def front_pop(self):"""队头弹出数据"""self._li.pop(0)def back_pop(self):"""队尾弹出数据"""self._li.pop()def travel(self):"""遍历队列"""_num = []for i in range(len(self._li)):_num.append(i)return _num

2.3.3 循环队列

2.3.3.1 什么是循环队列？

循环队列是一种利用数组（或固定长度存储结构）实现的队列，队列的头尾指针在到达数组末尾时会“环绕”到数组的起始位置，实现“首尾相连”的效果。这样可以充分利用数组空间，避免“假满”问题。

2.3.3.2 为什么需要循环队列？

在普通队列中，出队（dequeue）会导致前端空间释放，但队列尾部可能未能回收前端空间，造成空间浪费。而循环队列通过环绕利用空间，实现队列的空间最大化。

2.3.3.3 核心原理

使用一个固定长度的数组（或列表）存放元素。
使用两个指针（或索引）：front（队头指针） 和 rear（队尾指针）。
当队列满时，(rear + 1) % size == front。
当队列空时，front == rear。

class CircleQueue:def __init__(self, size=100):# 我定义100个长度的列表，可自定义self.size = size# 用0站位，不然被回收掉了，可随便更改站位字符self.queue = [0 for _ in range(size)]# 队头指针self.front = 0# 队尾指针self.rear = 0def is_empty(self):"""队列判空"""# 如果队头等于队尾，证明队中没有元素return self.front == self.reardef is_full(self):"""队列判满"""# 如果队尾的下一个元素就是队头，则证明队满了（预留了一个判定位，见图）return (self.rear + 1) % self.size == self.frontdef push(self, item):"""入队方法"""# 如果队没满，可以执行入队if not self.is_full():# 将队尾指针后移一个（取模操作是因为要循环，不然会一直增下去，环不起来）self.rear = (self.rear+1)%self.size# 添加元素self.queue[self.rear] = item# 如果队满了，肯定入不了队了，弹出异常raise IndexError('circle queue is full')def pop(self):"""出队方法"""# 如果队里还有元素，可执行弹出操作if not self.is_empty():# 将队头指针后移一个（取模操作是因为要循环，不然会一直增下去，环不起来）self.front = (self.front + 1) % self.size# 弹出元素return selfqueue[self.front]# 其他方法可自定义，比如说遍历、打印队首（队尾）元素等等

注意：弹出元素方法千万不能 .pop()，不然pop掉的那一个列表位没有元素占位，会被回收掉，造成列表长度-1，环形队列设定好size大小后，在操作中不能随意改变size，也就是列表长度大小