01线性数据结构
...大约 7 分钟
01线性数据结构
内建常用数据类型
分类
- 数值型
- int、float、complex、bool
- 序列sequence
- 字符串str、字节序列bytes、bytearray
- 列表list、元组tuple
- 键值对
- 集合set、字典dict
数值型
- int、float、complex、bool都是class,1、5.0、2+3j都是对象即实例
- int:python3的int就是长整型,且没有大小限制,受限于内存区域的大小
- float:由整数部分和小数部分组成。支持十进制和科学计数法表示。C的双精度型实现
- complex:有实数和虚数部分组成,实数和虚数部分都是浮点数,3+4.2J
- bool:int的子类,仅有2个实例True、False对应1和0,可以和整数直接运算
类型转换
- int、float、complex、bool也可以当做内建函数对数据进行类型转换
- int(x) 返回一个整数
- float(x) 返回一个浮点数
- complex(x)、complex(x,y) 返回一个复数
- bool(x) 返回布尔值,前面讲过False等价的对象
取整
math模块的floor()、ceil()函数;内建函数int()、round();运算符//
# 整除
print(3//2, 5//2, 7//2)
print(-3//2, -5//2, -7//2)
print(7//2, 7//-2, -7//2, -(7//2))
# int
print('int ------------')
print(int(1.4), int(1.5), int(1.6))
print(int(-1.4), int(-1.5), int(-1.6))
# ceil floor
print('ceil floor ------------')
import math
print(math.floor(2.5), math.floor(-2.5))
print(math.ceil(2.5), math.ceil(-2.5))
# round
print('round ------------')
print(round(1.4), round(-1.4), round(-1.6), round(1.6))
print(round(2.4), round(-2.4), round(2.6), round(2.6))
print('round .5 ---------')
print(round(0.5), round(1.5), round(2.5), round(3.5))
print(round(-0.5), round(-1.5), round(-2.5), round(-3.5))
- round(),四舍六入五取偶
- math.floor()向下取整
- math.ceil()向上取整
- int() 取整数部分 // 整除且向下取整
常用数值处理函数
- min()、max()
- abs()
- pow(x, y) 等于 x ** y
- math.sqrt() 等于 x ** 0.5
- 进制函数,返回值是字符串
- bin()、oct()、hex()
- math模块
- math.pi π
- math.e 自如常数
- math模块中还有对数函数、三角函数等
type(123) # 返回的是类型int
isinstance(456, int)
isinstance(True, (str, int, bool))
type(1 + True)
type(1 + True + 2.0) # 什么类型?
即使是强类型语言,也会有隐式类型转换。
线性数据结构
线性表
- 线性表(简称表),是一种抽象的数学概念,是一组元素的序列的抽象,它由有穷个元素组成(0 个或任意个)
- 顺序表:使用一大块连续的内存顺序存储表中的元素,这样实现的表称为顺序表,或称连续表 在顺序表中,元素的关系使用顺序表的存储顺序自然地表示
- 链接表:在存储空间中将分散存储的元素链接起来,这种实现称为链接表,简称链表
列表如同地铁站排好的队伍,有序,可以插队、离队,可以索引。
链表如同操场上手拉手的小朋友,有序但空间排列随意。或者可以想象成一串带线的珠子,随意盘放在 桌上。也可以离队、插队,也可以索引。
对比一下,这两种数据结构的增删改查。
列表list
- 一个排列整齐的队伍,Python采用顺序表实现
- 列表内的个体称作元素,由若干元素组成列表
- 元素可以是任意对象(数字、字符串、对象、列表等)
- 列表内元素有顺序,可以使用索引
- 线性的数据结构
- 使用 [ ] 表示
- 列表是可变的
列表是非常重要的数据结构,对其内存结构和操作方法必须烂熟于心。
初始化
- list() -> new empty list
- list(iterable) -> new list initialized from iterable's items
- []
- 列表不能一开始就定义大小
ls1 = []
ls2 = list()
ls3 = [2, 'ab', [3, 'abc'], (5, 30, 50)] # 列表是一个容器,元素可以是其它类型
ls4 = list(range(5)) # 非常常用的构造方式,将一个可迭代对象转换为一个列表
索引
- 索引,也叫下标
- 正索引:从左至右,从0开始,为列表中每一个元素编号
- 如果列表有元素,索引范围[0, 长度-1]
- 负索引:从右至左,从-1开始
- 如果列表有元素,索引范围[-长度, -1]
- 正、负索引不可以超界,否则引发异常 IndexError
- 为了理解方便,可以认为列表是从左至右排列的,左边是头部,右边是尾部,左边是下界,右边是上界
- 列表通过索引访问,list[index] ,index 就是索引,使用中括号访问
使用索引定位访问元素的时间复杂度为O(1),这是最快的方式,是列表最好的使用方式。
查询
- index(value,[start,[stop]])
- 通过值value,从指定区间查找列表内的元素是否匹配
- 匹配第一个就立即返回索引
- 匹配不到,抛出异常ValueError
- count(value)
- 返回列表中匹配value的次数
- 时间复杂度
- index和count方法都是O(n)
- 随着列表数据规模的增大,而效率下降
- 如何返回列表元素的个数?如何遍历?如何设计高效?
- len()
修改
- 索引定位元素,然后修改。注意索引不能超界
ls1 = [1,2,3,4]
ls1[2] = 200
增加单个元素
- append(object) -> None
- 列表尾部追加元素,返回None
- 返回None就意味着没有新的列表产生,就地修改
- 定位时间复杂度是O(1)
- insert(index, object) -> None
- 在指定的索引index处插入元素object
- 返回None就意味着没有新的列表产生,就地修改
- 定位时间复杂度是O(1)
- 索引能超上下界吗?
- 超越上界,尾部追加
- 超越下界,头部追加
增加多个元素
- extend(iteratable) -> None
- 将可迭代对象的元素追加进来,返回None
- 就地修改,本列表自身扩展
- + -> list
- 连接操作,将两个列表连接起来,产生新的列表,原列表不变
- 本质上调用的是魔术方法__add__()方法
- * -> list
- 重复操作,将本列表元素重复n次,返回新的列表
ls1 = [1] * 5
ls2 = [None] * 6
ls3 = [1,2] * 3
ls4 = [[1]] * 3
这个重复操作看似好用,如果原理掌握不好,但非常危险
x = [1] * 3
x[0] = 100
print(x) # 结果是什么
y = [[1]] * 3
print(y) # 结果是什么
y[0] = 100
print(y) # 结果是什么
y[1][0] = 200
print(y) # 结果是什么
result
[[1], [1], [1]]
[100, [1], [1]]
[100, [200], [200]] # !!!!!
在Python中一切皆对象,而对象都是引用类型,可以理解为一个地址指针指向这个对象。 但是,字面常量字符串、数值等表现却不像引用类型,暂时可以称为简单类型。 而列表、元组、字典,包括以后学习的类和实例都可以认为是引用类型。 你可以认为简单类型直接存在列表中,而引入类型只是把引用地址存在了列表中。
![image-20240513134537679](/assets/image-20240513134537679-BMQNMhMH.png)
删除
- remove(value) -> None
- 从左至右查找第一个匹配value的值,找到就移除该元素,并返回None,否则ValueError
- 就地修改
- 效率?
- pop([index]) -> item
- 不指定索引index,就从列表尾部弹出一个元素
- 指定索引index,就从索引处弹出一个元素,索引超界抛出IndexError错误
- 效率?指定索引的的时间复杂度?不指定索引呢?
- clear() -> None
- 清除列表所有元素,剩下一个空列表
反转
- reverse() -> None
- 将列表元素反转,返回None
- 就地修改
这个方法最好不用,可以倒着读取,都不要反转。
排序
- sort(key=None, reverse=False) -> None
- 对列表元素进行排序,就地修改,默认升序
- reverse为True,反转,降序
- key一个函数,指定key如何排序,lst.sort(key=function)
如果排序是必须的,那么排序。排序效率高吗?