01线性数据结构

PaperDragon2024年5月6日...大约 7 分钟

01线性数据结构

内建常用数据类型

数值型

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中一切皆对象，而对象都是引用类型，可以理解为一个地址指针指向这个对象。但是，字面常量字符串、数值等表现却不像引用类型，暂时可以称为简单类型。而列表、元组、字典，包括以后学习的类和实例都可以认为是引用类型。你可以认为简单类型直接存在列表中，而引入类型只是把引用地址存在了列表中。

删除

remove(value) -> None
- 从左至右查找第一个匹配value的值，找到就移除该元素，并返回None，否则ValueError
- 就地修改
- 效率？
pop([index]) -> item
- 不指定索引index，就从列表尾部弹出一个元素
- 指定索引index，就从索引处弹出一个元素，索引超界抛出IndexError错误
- 效率？指定索引的的时间复杂度？不指定索引呢？
clear() -> None
- 清除列表所有元素，剩下一个空列表