标签：索引 元素 list 列表 print 线性 数据结构 math

线性数据结构

标签（空格分隔）： python

目录

• 线性数据结构
  • 1，内建常用数据类型
    • 1.1 分类
  • 2，数值型
    • 2.1 类型转换
    • 2.2 取整
    • 2.3 常用数值处理函数
  • 3，线性数据结构
  • 4，列表list
    • 4.1 概念
    • 4.2 初始化
    • 4.3 索引
    • 4.4 查询
    • 4.5 修改
    • 4.6 增加单个元素
    • 初始化
    • 索引
    • 查询
    • 修改
    • 增加单个元素
    • 增加多个元素
    • 删除
    • 反转
    • 排序
    • in成员操作
    • 列表复制
      • 列表的内存模型和深浅拷贝
  • 随机数
  • 元组tuple
    • 初始化
    • 索引
    • 查询
    • 增删改
  • 字符串str
    • 初始化
    • 索引
    • 连接
    • 字符查找
    • 分割
    • 替换
    • 移除
  • 字节序列
    • 编码与解码
    • ASCII

1，内建常用数据类型

1.1 分类

• 数值型

• int、float、complex、bool

• 序列sequence

• 字符串str、字节序列bytes、bytearray

• 列表list、元组tuple

• 键值对

• 集合set、字典dict

2，数值型

• int、float、complex、bool都是class，1,5.0、2+3j都是对象即实例
• int：python3的int就是长整型，且没有大小限制，受限于内存区域的大小
• float：由整数部分和小数部分组成，支持十进制和科学计数法表示，C的精度型实现
• complex：有实数和虚数部分组成，实数和虚数部分都是浮点数，3+4.2j
• bool：int的子类，仅有两个实例True和False，分别对应的1和0，可以和整数直接运算

2.1 类型转换

• int、float、complex、bool也可以当做内建函数对数据进行类型转换
• int(x) 返回一个整数
• float(x) 返回一个浮点数
• complex(x)、complex(x,y) 返回一个复数
• bool(x)返回布尔值

2.2 取整

math模块的floor()、ceil()函数； 内建函数int()、round(); 运算符//

• round()，四舍六入五取偶
• math.floor()向下取整
• math.ceil()向上取整
• int() 取整数部分
• // 整除且向下取整

# // 向下取整
1//2, 3//2, 5//2, 7//2
(0, 1, 2, 3)
-1//2, -3//2, -5//2, -7//2
(-1, -2, -3, -4)

import math
math.floor(1.1), math.floor(1.4), math.floor(1.5), math.floor(1.7)
(1, 1, 1, 1)
math.floor(-1.1), math.floor(-1.4), math.floor(-1.5), math.floor(-1.7)
(-2, -2, -2, -2)

#向上取整
import math
math.ceil(1.1), math.ceil(1.4), math.ceil(1.5), math.ceil(1.7)
(2, 2, 2, 2)
math.ceil(-1.1), math.ceil(-1.4), math.ceil(-1.5), math.ceil(-1.7)
(-1, -1, -1, -1)

# int +向上 - 向下，截取整数部分，取整
for i in [1.1, 1.4, 1.5, 1.50001, 1.8, 2.1, 2.5, 2.6]:
    print(int(i))
1
1
1
1
1
2
2
2

for i in [1.1, 1.4, 1.5, 1.50001, 1.8, 2.1, 2.5, 2.6]:
    print(int(-i))
-1
-1
-1
-1
-1
-2
-2
-2


# 圆整 四舍六入五取偶 取离它最近的偶数
for i in [1.5, 2.5, 3.5, 4.5]:
    print(round(i))
2
2
4
4

for i in [1.1, 1.4, 1.5001, 1.6, 1.8]:
    print(round(i))
1
1
2
2
2

for i in [1.1, 1.4, 1.5001, 1.6, 1.8]:
    print(round(-i))
-1
-1
-2
-2
-2    

2.3 常用数值处理函数

• min()
• max()
• abs(） # 取绝对值
• pow(x,y)等于x**y
• math.sqrt()等于x**0.5
• 进制函数，返回值是字符串
  • bin()、oct()、hex()
• math模块
  • math.pi # π
  • math.e 自如常数
  • math模块中还有对数函数、三角函数等
  • math.pow(2, 4), 2 ** 4, pow(2, 4) # 次方
  • math.sqrt(2), 2 ** 0.5 # 开方

type(123) # 返回的是类型int
isinstance(456, int)
isinstance(True, (str, int, bool))
type(1 + True)
type(1 + True + 2.0) # 什么类型？ # float类型 4.0

即使是强类型语言，也会有隐式类型转换

3，线性数据结构

线性表

• 线性表分为顺序表和链接表
• 线性表（简称表）：是一种抽象的数学概念，是一组元素的序列的抽象，它由有穷个元素组成（0个或任意个）
• 顺序表：使用一大块连续的内存顺序存储表中的元素，这样实现的表称为顺序表，或称为连续表
  • 在顺序表中，元素的关系使用顺序表的存储顺序自然表示
• 链接表：在存储空间中将分散存储的元素链接起来，这种实现称为链接表，简称链表

列表如同地铁站拍好的队伍，有序，可以插队、离队、可以索引。
链表如同操场上手拉手的小朋友，有序但空间排列随意。或者可以想象成一串带线的珠子，随意盘放在桌上。也可以离队、插队、也可以索引

4，列表list

4.1 概念

• 列表是一个排列整齐的队伍，python采用顺序表实现
• 列表内的个体称作元素，由若干元素组成列表
• 元素可以是任意对象（数字、字符串、对象、列表等）
• 列表内元素有顺序，可以使用索引
• 线性的数据结构
• 使用[]表示
• 列表是可变的

4.2 初始化

• 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)) # 非常常用的构造方式，将一个可迭代对象转换为一个列表

4.3 索引

• 索引，也叫下标

• 正索引：从左至右，从0开始，为列表中每一个元素编号

  • 如果列表有元素，索引范围[0, 长度-1]

• 负索引：从右至左，从-1开始

  • 如果列表有元素，索引范围[-长度, -1]

• 正负索引不可以超界，否则会引发异常IndexError

• 为了理解方便，可以认为列表是从左至右排列的，左边是头部，右边是尾部，左边是上界，右边是下界

• 列表通过索引访问，list[index]，index就是索引，使用中括号访问

4.4 查询

• list_name[index]

  • 通过索引查询列表中该索引的数据，list_name是列表的标识符

• index(value, [start,[stop]])

  • 通过值value，从指定区间查找列表内的元素是否匹配
  • 匹配第一个就立即返回索引
  • 匹配不到，抛出异常ValueError

• count(value)

  • 返回列表中匹配value的次数

• 时间复杂度

  • index和count方法都是O(n)
  • 随着列表数据规模的增大，而效率下降

• len(list)

  • 返回列表元素的个数，因为列表元素的个数是记录在元数据中，所以时间复杂度为O(1)

4.5 修改

索引定位元素，让后修改，注意索引不能超界

ls1 = [1, 2, 3, 4]
ls1[2] = 200

print(ls1)
[1, 2, 200, 4]

4.6 增加单个元素

顺序表

对逻辑概念序列物理存储，前驱、后继
顺序表开辟内存空间后，首地址定死了
[1,2,3,4,5,10]
顺序表首地址 + 索引*4字节

链接表

初始化

• list()
• list(iterable) new list initialized from iterable's items
• []
• 列表不能一开始就定义大小

ls1 = []
ls2 = list()
ls3 = [1,'abc',[1,'aaa'],(1,2,3)]   #列表是一个容器，元素可以是其他类型
ls4 = list(range(5))    #非常常用的构造方式，将一个可迭代对象转换为一个列表
ls4
[0, 1, 2, 3, 4]

索引

• 索引，也叫下标
• 正索引：从左到右，从0开始，为列表中每一个元素编号
  如果列表有元素，索引范围[0,长度-1]
• 负索引：从右到左，从-1开始
  如果列表有元素，索引范围[-长度，-1]
• 正、负索引不可以超界，否则引发异常IndexError
• 为了理解方便，可以认为列表是从左至右排列的，左边是头部，右边是尾部，左边是下界，右边是上界
• 列表通过索引访问，list[index],index就是索引，使用中括号查看
  使用索引定位访问元素的时间复杂度为O(1)，这是最快的方式，是列表最好的使用方式

查询

index(value,[start,[stop]])

• 通过值value,从指定区间查找列表内的元素是否匹配
• 匹配第一个就立即返回索引
• 匹配不到，抛出异常valueError
  count(value)
  返回列表中匹配value的次数
  时间复杂度
• index和count方法都是O(n)
• 随着列表数据规模的增大，而效率下降（能不用则不用）因为index和count都是遍历整个列表的
  如何放回列表元素的个数？如何遍历？如何设计高效？
• len() #元数据中记录了当前列表的个数，所以时间复杂度是O(1)

修改

• 索引定位元素，然后修改（注意：索引不能越界）

ls4
[0, 1, 2, 3, 4]
ls4[2] = 200    #定位直接修改
ls4
ls4
[0, 1, 200, 3, 4]

增加单个元素

append(object)->None

• 列表尾部追加元素，返回None（无返回值）
• 放回None就意味着没有新的列表产生，就地修改
• 定位时间复杂度是O(1)

ls4
[0, 1, 200, 3, 4]
ls4.append(5)
ls4
[0, 1, 200, 3, 4, 5]

insert(index,object)->None

• 在指定的索引index处插入元素object
• 放回None就意味着没有新的列表产生，就地修改
• 定位时间复杂度是O(1)

ls4
[0, 1, 200, 3, 4, 5]
ls4.insert(0,1)
ls4
[1, 0, 1, 200, 3, 4, 5]
ls4.insert(-1,100)
ls4
[1, 0, 1, 200, 3, 4, 100, 5]

索引能超上下界吗？

• 超越上界，尾部追加,相当于 append
• 超越下界，头部追加，相当于 列表.insert(0,value)

增加多个元素

• extend(iteratable)->None
  将可迭代对象的元素追加进来，返回None
  就地修改，本利表自身扩展

ls4
[1, 0, 1, 200, 3, 4, 100, 5]
ls4.extend(range(3))
ls4
[1, 0, 1, 200, 3, 4, 100, 5, 0, 1, 2]

• +- ->list
  连接操作，将两个列表连接起来，产生新的列表，原列表不变
  本质上调用的是魔术方法_add_()方法

x = [1,2,3,4,5]
y = list(range(3))
x
[1, 2, 3, 4, 5]
y
[0, 1, 2]
x + y       #运算符重载，拼接生成全新列表
[1, 2, 3, 4, 5, 0, 1, 2]

• * ->list
  重复操作，将本列表元素重复n次，返回新的列表

ls1 = [1] *5
ls2 = [None] *6 
ls3 = [1,2] *3 
ls4 = [[1]] *3

这个重复操作看似好用，如果原理掌握不好，非常危险

x = [1] *3
x[0] = 100
print(x) # 结果是什么

print(x)
[100, 1, 1]

y = [[1]] *3
print(y) # 结果是什么  [[1], [1], [1]]
y[0] = 100
print(y) # 结果是什么   [100, [1], [1]]
y[1][0] = 200
print(y) # 结果是什么

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

删除

remove(value)->None
从左至右查找第一个匹配value的值，找到就移除该元素，并返回None，否则ValueError
就地修改
效率？

a
[0, 1, 2, 3, 1]
a.remove(1)
a
[0, 2, 3, 1]

pop([index])->item
不指定索引index，就从列表尾部弹出一个元素
指定索引index，就从索引处弹出一个元素，索引你超界抛出IndexError错误
效率？指定索引的时间复杂度？不指定索引呢？

a
[0, 2, 3, 1]
a.pop()
1   #返回弹出的内容
a
[0, 2, 3]

a
[0, 2, 3]
a.pop(2)
3   #弹出的内容
a
[0, 2]

a
[0, 2, 3]
a.pop(3)    #超出索引范围，报错IndexError
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
~\AppData\Local\Temp/ipykernel_16260/1006519368.py in <module>
----> 1 a.pop(3)

IndexError: pop index out of range

clear()->None
清除列表所有元素，剩下一个空列表

a
[0, 2, 3]
a.clear()
a
[]

反转

reversed()->None
将列表元素反转，返回None
就地修改

这个方法最好不用，可以到这读取，都不要反转，因为这样的话所有的索引都要换一遍。

排序

sort(key=None,reverse=False)->None
对列表元素进行排序，接地修改，默认升序
reverse为True，反转，降序
key一个函数，指定key如何排序，lst.sort(key=function)
如果排序是必须的，那么排序效率高吗？
排序效率不高，索引要变化

in成员操作

'a' in ['a', 'b', 'c'] 
[3,4] in [1, 2, 3, [3,4]]

for x in [1,2,3,4]:
    pass

列表复制

a = list(range(4))
b = list(range(4))
print(a == b) c = a c[2] = 10
print(a)
print(a == b) # 还相等吗？
print(a == c) # 相等吗？

True
[0, 1, 200, 3]
False
True

问题：

1. 最终a 和 b相等吗？a和b分别存着什么元素
2. a 和 c 相等吗？为什么？ c = a 这一句有复制吗？

下面的程序a和b相等吗？

a = list(range(4))
b = a.copy()
print(a == b) 
a[2] = 10
print(a == b)

True
False

#得出结论：复制时是复制完全独立的复制一份,如果是数字地址，就复制数字地址，因此只要数字地址的指向是相同的，不管指向内容如何改变，有着相同数字地址的指向内容还是相同的

a = [1, [2, 3, 4], 5] 
b = a.copy()
print(a == b) 
a[2] = 10
print(a == b)
a[2] = b[2]
print(a == b)
a[1][1] = 100
print(a == b)
print(a)
print(b)

True
False
True
True
[1, [2, 100, 4], 5]
[1, [2, 100, 4], 5]

列表的内存模型和深浅拷贝

• shadow copy

  影子拷贝，也叫浅拷贝，遇到引用类型数据，仅仅复制一个引用而已

• deep copy
  深拷贝，往往会递归复制一定深度

一般情况下，大多数语言提供的默认复制行为都是浅拷贝。

import copy
a = [1,[2,3],4]
b = copy.deepcopy(a)
print(a == b)
a[1][1] = 100
print(a == b)
print(a)
print(b)

True
False
[1, [2, 100], 4]
[1, [2, 3], 4]

python内建数据类型，内部都实现了 == ，它的意思是内容比较

随机数

random 模块

• randint(a,b)返回[a,b]之间的整数

• randrange(start, stop=None, step=1)从指定范围内，按指定基数递增的集合中获取一个随机数，基数缺省值为1 random.randrange(1,7,2)

• choice(seq) 从非空序列的元素中随机挑选一个元素，比如random.choice(range(10)),从0到9中随机挑选一个整数，random.choice([1,3,5,7])

• python3.6开始提供choices，一次从样本中随机选择几个，可重复选择，可以指定权重

• random.shuffle(list)->None 就地打乱列表元素

• sample(population,k) 从样本空间或总体（序列或者集合类型）中随机取出K个不同的元素，返回一个新的列表

    random.sample(['a','b'],2) 会返回什么结果
    random.sample(['a','a'],2) 会返回什么结果
    每次从样本空间采样，在这一次中不可以重复抽取同一个元素

import random
for i in range(10):
    print(random.randint(1, 5))
print('-' * 30)
for i in range(10):
    print(random.randrange(1, 5))
print('-' * 30) x = [1, 2, 3, 4, 5]
for i in range(10):
    print(random.choice(x))
print('-' * 30)
# 观察下面的0和1的比例
for i in range(10):
    print(random.choices([0, 1], k=6))
print('-' * 30)
for i in range(10):
    print(random.choices([0, 1], [10, 1], k=6)) # 10比1权重
x = [1, 2, 3, 4, 5]
# 采样
for i in range(5):
    print(random.sample(x, 5)) # k能不能是6？

元组tuple

• 一个有序的元素组成的集合
• 使用小括号()表示
• 元组是不可变对象，元组是只读的

初始化

• tuple()->empty tuple
• tuple(iterable)->tuple initialized from iterable's items

t1 = () #空元组
t2 = (1,) #必须有这个逗号，要不不是元组了，一个元素的必须有逗号
t3 = (1,) * 4
t4 = (1,2,3)
t5 = 1,'a'
t6 = (1,2,3,1,2,3)
t7 = tuple()
t8 = tuple(range(5))
t9 = tuple([1,2,3])

索引

索引和列表规则一样，不可以超界

查询

查询方法和列表一样，index、count、len等

增删改

元组元素的个数在初始化的时候已经定义好了，所以不能为元组增加元素、也不能从中删除元素、也不能修改元素的内容。
但是要注意下面的这个例子：

t1 = ([1]) * 3
t1[1] = 100 # ?


# 注意下面的例子
t2 = ([1],) * 3
print(t2)
t2[1] = 100
t2[0][0] = 100
print(t2)

上例说明t2是可变的吗？不是说元组不可变吗？到底什么不可变

字符串str

• 一个个字符组成的有序的序列，是字符的集合
• 使用单引号、双引号、三引号引住的字符序列
• 字符串是不可变对象，是字面常量

python3起，字符串都是Unicode类型

初始化

s1 = 'string'
s2 = "string2"
s3 = '''this's a "String" '''
s4 = 'hello \n magedu.com'
s5 = r"hello \n magedu.com"
s6 = 'c:\windows\nt'
s7 = R"c:\windows\nt"
s8 = 'c:\windows\\nt'
name = 'tom'; age = 20 # python代码写在一行，使用分号隔开，不推荐
s9 = f'{name}, {age}' # 3.6支持f前缀
sql = """select * from user where name='tom' """

r前缀：所有的字符都是本来的意思，没有转义
f前缀：3.6开始，使用变量插值

索引

字符串是序列，支持下标访问，但不可变，不可以修改元素。

sql = "select * from user where name='tom'"
print(sql[4]) # 字符串'c'
sql[4] = 'o' # 不可以

连接

+加号

• 将两个字符串连接起来
• 返回一个新的字符串

join方法

• sep.join(interable)
• 使用指定字符串作为分隔符，将可迭代对象中字符串使用这个分隔符拼接起来
• 可迭代对象必须是字符串
• 返回一个新的字符串

x = 'ab'
x = x + 'cd'
print(','.join(x))
print('\t'.join(x))
print('\n'.join(x))
print('-'.join(range(5))) # 可以吗

字符查找

• find(sub[,start[,end]])->int

  • 在指定的区间[start,end),从左至右，查找子串sub
  • 找到返回正索引，没找到返回-1

• rfind(sub[,start[,end]])->int

  • 在指定的区间[start,end)(前包后不包)，从右至左，查找子串sub
  • 找到返回正索引，没找到返回-1

s = 'magedu.edu'
print(s.find('edu'))
print(s.find('edu', 3))
print(s.find('edu', 4))
print(s.find('edu', 6, 9))
print(s.find('edu', 7, 20))
print(s.find('edu', 200))
s = 'magedu.edu'
print(s.rfind('edu'))
print(s.rfind('edu', 3))
print(s.rfind('edu', 4))
print(s.rfind('edu', 6, 9))
print(s.rfind('edu', 7, 20))
print(s.rfind('edu', 200))

这两个方法知识找字符串的方向不同，返回值一样，找到第一个满足要求的子串立即返回，特别注意返回值，找不到返回的是负数-1
这两个方法效率高吗？要不要用？
这两个方法效率真不高，都是在字符串中遍历搜索，但是如果找子串工作必不可少，那么必须这么做，但是能少做就少做。

• index(sub[,start[,end]])->int

  • 在指定的区间[start,end),从左至右，查找子串sub
  • 找到返回正索引，没找到抛出异常ValueError

• rindex(sub[start[,end]])->int

  • 在指定的区间[start, end)，从右至左，查找子串sub
  • 找到返回正索引，没找到抛出异常ValueError

index方法和find方法很像，不好的地方在于找不到哦啊抛异常，推荐使用find方法

s = 'magedu.edu'
print(s.index('edu'))
print(s.index('edu', 3))
print(s.index('edu', 4))
#print(s.index('edu', 6, 9)) # 抛异常
print(s.index('edu', 7, 20))
#print(s.index('edu', 200)) # 抛异常

• count(sub[,start[,end]])->int

  • 在指定的区间【start,end),从左至右，统计子串sub出现的次数

s = 'magedu.edu'
print(s.count('edu'))
print(s.count('edu', 4))

• 时间复杂度

  • find、index和count方法都是O(n)
  • 随着字符串数据规模的增大，二效率下降

• len(string)

  • 返回字符串的长度，及自负的个数，时间复杂度是O(1)

分割

• split(sep=None,maxsplit=-1)->list of strings

  • 从左至右
  • sep指定分割字符串，缺省的情况下空白字符串作为分隔符
  • maxsplit 指定分隔的次数，-1表示遍历整个字符串
  • 立即返回列表

• rsplit(sep=None,maxsplit=-1)->list of strings

  • 从右至左开始切，但是输出的字符串字符不会反
  • sep指定分割字符串，缺省的情况下空白字符串作为分隔符
  • maxsplit指定分割的次数，-1表示遍历整个字符串
  • 立即返回列表

• splitlines([keepends])->list of strings

  • 按照行来切分字符串
  • keepends指的是 是否保留行分隔符
  • hang分隔符包括\n、\r\n、\r等

s = ','.join('abcd')
print(s.split(','))
print(s.split())
print(s.split(',', 2))
s1 = '\na b \tc\nd\n' # 注意下面3个切割的区别
print(s1.split())
print(s1.split(' '))
print(s1.split('\n'))
print(s1.split('b'))
print(s1.splitlines())

• partition(sep)->(head,sep,tail)

  • 从左至右，遇到分隔符就把字符串分割成两部分，返回头、分隔符、尾三部分的三元组
  • 如果没有找到分隔符，就返回头、2个空元素的三元组
  • sep分隔字符串，必须指定

• rpartition(sep)->(head,sep,tail)

  • 从右至左，遇到分隔符就把字符串分割成两部分，返回头、分隔符、尾三部分的三元组
  • 如果没有找到分隔符，就返回两个空元素和尾的三元组

s = ','.join('abcd')
print(s.partition(','))
print(s.partition('.'))
print(s.rpartition(','))
print(s.rpartition('.'))

"a,b,c,d".partition(':')    #还是返回三段
('a,b,c,d', '', '')
"a,b,c,d".split(':')    #返回一个元素的列表
['a,b,c,d']

"a,b,c,d".rpartition(':')
('', '','a,b,c,d')
"a,b,c,d".rsplit(':')
['a,b,c,d']

替换

• replace(old, new[, count]) -> str

• 字符串中找到匹配替换为新子串，返回新字符串

• count表示替换几次，不指定就是全部替换

s = ','.join('abcd')
print(s.replace(',', ' '))
print(s.replace(',', ' ', 2))
s1 = 'www.magedu.edu'
print(s1.replace('w', 'a'))
print(s1.replace('ww', 'a'))
print(s1.replace('ww', 'w')) # 返回什么？
print(s1.replace('www', 'a'))

移除

·
··
·
·
待完成

字节序列

编码与解码

• 编码：str => bytes,将字符串这个字符序列使用的指定字符集encode编码为一个个字节组成的序列bytes
• 解码：bytes或bytearray => str,将一个个字节按照某种指定的字符集解码为一个个字符串组成的字符串

print("abc".encode())
b'abc'

print("abc".encode('utf8'))
b'abc'

print("啊".encode('utf8'))
b'\xe5\x95\x8a'

print("啊".encode('gbk'))
b'\xb0\xa1'

print(b'abc'.decode('utf8'))
abc

print(b'\xb0\xa1'.decode('gbk'))
啊

ASCII

ASCII(American Standard Code for Information Interchange,美国信息交换标准代码)是基于拉丁字母的一套单字节编码系统。

ascii码由0-127组成
FF 是 255
FFFF 是 65535

标签：索引,元素,list,列表,print,线性,数据结构,math
From： https://www.cnblogs.com/wangerrui/p/16998428.html