线性数据结构
一，线性表
线性表（简称表）：是一种抽象的数学概念，是一组元素的序列的抽象，它由有穷个元素组成
1， 顺序表：
使用一块连续的内存顺序的存储表中的元素，这样实现的表称为顺序表，或称连续表。在顺序表中，元素的关系使用顺序表的存储顺序自然的表示 顺序表开辟内存空间后，首地址就固定了，不能再改动 增： - 头部增加insert,引起后面所有元素位置挪动 - 中间插入insert,引起其后所有元素的挪动 - 尾部追加，推荐使用这种方式 删： - 头部删，引起其后元素位置的挪动 - 中间删，引起其后元素位置的挪动 - 尾部删，推荐使用这种 改： - 通过index直接定位元素，覆盖即可，效率很高 查： - 通过index查找，效率很高
2，链接表
在存储空间中将分散存储的元素链接起来，这种实现方式称为链接表，简称链表 增： - 头部增加insert, 把头部标记移动到增加的元素上，新元素与跟原来的头部元素拉手。代价很低 - 中间插入insert,断开手，拉新手。效率相对于顺序表稍微差一点点 - 尾部追加，新增的元素跟原来的尾部元素拉手，尾部标记移动到新的尾部元素上面 删： - 头部删，移动头部标记就行了，代价低 - 中间删，被删除元素两边的元素重新拉手，效率高。但是有个找目标元素的过程，相对于顺序表慢一点 - 尾部删，移动尾部标记就行了，效率高 改： - 通过index直接定位元素，覆盖即可，效率很高 查： - 通过index查找，效率很高
二，队列queue
一般情况下，队列的操作只在某一头，或者两头同时进行，不会在队列中间操作
- FIFO 先进先出 适合使用链接表实现 - LIFO 后进先出 适合使用顺序表实现，也可以选择链接表实现 - stack(栈）就是一种后进先出的
三，列表List
1，列表的简介
- 一个排列整齐的队列，Python采用顺序表实现
- 列表内的个体称为元素，有0个或者若干个元素组成列表
- 元素可以是任意对象（数字，字符，对象，列表等）
- 列表内元素是由顺序的，可以使用索引
- 列表是线性的数据结构
- 使用[]表示
- 列表是可变的
2，列表构建
2.1 通过list()构建函数进行构建
list()：括号内为空或者为一个可迭代对象
list() => 构建一个[]空列表
list(range(5)) => [0, 1, 2, 3, 4]
2.2 通过[]构建
[]:构建一个空列表
[1,'abc',[2,3.4,'admin']] => [1, 'abc', [2, 3.4, 'admin']]
2.3 列表索引(列表索引不能超界)
首地址 +index*字节数就能直接得到目标元素的位置。效率最高，时间复杂度为O(1)
- 正索引 (从前往后找)
索引范围[0,length-1]
- 负索引（从后往前找）
索引范围[-length,-1]
x = [1,'abc',[2,3.4,'admin']]
x[1] => 'abc'
x[-1] => [2,3.4,'admin']
x[-1][1] => 3.4
2.4 查找元素的位置
- index() 查找某个值得索引位置，效率不高，会进行遍历，时间复杂度O(n)
L.index(value, [start, [stop]]) -> integer -- return first index of value.
x=[1,2,3,1,2,3]
x.index(2) => 1 #返回第一个匹配上的元素的索引位置
- count() 统计某个值出现的次数，效率不高，会进行遍历，时间复杂度O(n)
L.count(value) -> integer -- return number of occurrences of value
x.count(2) => 2
- len() 返回对象的长度，时间复杂度O(1),列表有元数据记录了列表的信息
2.5 列表操作
- 增
list. append('value') :在列表的末尾添加元素 ，效率高，时间复杂度O(1)
Docstring: L.append(object) -> None -- append object to end
x.append(100) => [1, 2, 3, 1, 2, 3, 100]
list.insert(index, object):在列表的指定索引位置插入元素。查找快，但是如果在列表开头或者中间部位插入新元素会造成其后元素的位置挪动。插入实际上就是将原先这个位置的元素向后挤。
Docstring: L.insert(index, object) -- insert object before index
x.insert(3,'abc') => [1, 2, 3, 'abc', 1, 2, 3, 100]
x.insert(-1,'whp') => [1, 2, 3, 'abc', 1, 2, 3, 'whp', 100] #将原先-1索引处的100挤到了后面。
正向超索引的作用就相当于append的作用
反向超索引会在列表头部插入
- 删
list.pop() 弹出指定索引出的元素，这个被弹出的元素可以被别的地方使用或引用.默认弹出列表末尾的元素。也可以弹出指定位置的元素，但是会引起后面元素位置的挪动
L.pop([index]) -> item -- remove and return item at index (default last).
x.pop() => 100 x = [1, 2, 3, 'abc', 1, 2, 3, 'whp']
x.pop(3) => 'abc' x = [1, 2, 3, 1, 2, 3, 'whp']
list.remove(value) 删除指定元素，会进行遍历，效率不好
L.remove(value) => None -- remove first occurrence of value
x.remove('whp') => [1, 2, 3, 1, 2, 3]
- 改
x[4]=999 #将索引为4的元素的值修改为999，效率快,定位覆盖
x[4]=999 => [1, 2, 3,1, 999, 3]
- 扩展
list.extend(iterable) 将一个可迭代对象里面的元素添加到列表的后面。就地修改。
Docstring: L.extend(iterable) -> None -- extend list by appending elements from the iterable
x.extend(range(4,7)) => [1, 2, 3, 1, 999, 3, 4, 5, 6]
- 拼接
+ #运算符重载
x = list(range(5))
y = ['a','b']
x + y => [0, 1, 2, 3, 4, 'a', 'b'] #生成新的列表
* #运算符重载
y*3 => ['a', 'b', 'a', 'b', 'a', 'b'] # 用y的元素重复3次，生成新的列表
- 翻转
list.reverse() #元素的位置会发生大挪动，最好不用这个方法，可以使用reversed函数来倒着读。
Docstring: L.reverse() -- reverse *IN PLACE*
x = list(range(5))
x.reverse() => [4, 3, 2, 1, 0]
- 排序
list.sort() #对列表进行排序，就地修改，会改变列表本身
Docstring: L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*
x = [4, 3, 2, 1, 0]
x.sort() => [0, 1, 2, 3, 4]
sorted（）函数
不会改动原列表，返回一个新的列表
Signature: sorted(iterable, /, *, key=None, reverse=False)
Docstring:
Return a new list containing all items from the iterable in ascending order.
sorted(x,reverse=True) => [4, 3, 2, 1, 0]
- in 成员操作
判断一个元素在列表中是否存在，存在返回True,不存在返回False
2 in x => True
5 in x => False
- 一种特殊现象
x = [1] *3
x[1] = 100
print(x) => [1, 100, 1]
y = [[1]] * 3
print(y) => [[1], [1], [1]]
y[1][0]=200
print(y) => [[200], [200], [200]] #为什么是这个结果？而不是 [[1], [200], [1]
复杂数据类型（列表，元组，字典等）作为一个对象的元素时，存在在这个对象中的不是实际的值，而是一个地址，这个地址指向了实际的值。也就是说，上面例子中[[1], [1], [1]]。列表中的元素[1]不是一个实际的值，而是一个地址，这个地址指向了实际的值1
当进行y[1][0]=200修改时，就是修改 [[1], [1], [1]]这个列表中索引为1的这个元素的索引为0这个元素的值为200,
3，列表复制
构建相同的列表
a = list(range(5))
b = list(range(5))
a == b => True # 虽然结果为True，但是并不是说明a和b是同一个。它们只是内容完全一样。 == 是内建函数，对元素进行比较
a[2]=100
a == b => False # 可以看到只要修改了a中元素的值，a和b就不再相等
- copy
Docstring: L.copy() -> list -- a shallow copy of L #浅拷贝
从原列表拷贝一个副本（里面的内容跟原列表一模一样，不管里面的内容是一个真实的值还是一个引用地址），生成一个新的列表
a = list(range(5))
b = a.copy()
a == b => True
a[2]=200
a == b => False # 说明a和b还是两个不同的列表
- =
a = list(range(5))
c = a # 相当于c也指向a所指向的位置
c == a => True
c[2]=200
c == a => True
- copy.deepcopy #深拷贝。如果拷贝的内容里面有引用地址，则将这个引用地址里面的内容也拷贝一份，
import copy
a = [1,[2,3,4],5]
b = copy.deepcopy(a) # b 拷贝a的元素，但是a里面的元素[2,3,4]实际上是个引用地址，此时b根据这个引用地址找到实际存放数据的地方，然后把这个数据拷贝一份放到另外一块内存中，b中保存的就是这个心的内存地址。
a[1][1] = 200
a == b => False
四，随机数
1，random模块 - random.shuffle() 随机打散 Signature: random.shuffle(x, random=None) Docstring: Shuffle list x in place, and return None. x = list(range(5)) x => [0, 1, 2, 3, 4] random.shuffle(x) x => [4, 3, 0, 1, 2] - random.randint(a,b) # 随机返回a,b之间的一个整数 Signature: random.randint(a, b) Docstring: Return random integer in range [a, b], including both end points. random.randint(1,10) => 7 - random.randrange() Signature: random.randrange(start, stop=None, step=1, _int=) Docstring: Choose a random item from range(start, stop[, step]). for i in range(5): print(random.randrange(1,10,2)) 7 9 9 7 9 -random.choice('序列') 随机取一个元素 Signature: random.choice(seq) Docstring: Choose a random element from a non-empty sequence. random.choice(x) => 3 -random.choices('') 随机取一个或者多个元素，并且可以指定元素的权重。返回的是一个列表 Signature: random.choices(population, weights=None, *, cum_weights=None, k=1) Docstring: Return a k sized list of population elements chosen with replacement. for i in range(10): print(random.choices([0,1],[5,1],k=5)) # 从0和1两个元素中选择一个，权重0为5,1为1，选择5个 [0, 0, 0, 1, 0] [0, 1, 0, 0, 1] [0, 0, 0, 0, 1] [1, 0, 1, 1, 0] [0, 0, 0, 0, 1] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0] [1, 0, 0, 0, 0] - random.sample() # 采样，采样长度不能超过列表的长度，且列表中的每个元素每次都只能被采样一次 Signature: random.sample(population, k) Docstring: Chooses k unique random elements from a population sequence or set. random.sample(x,k=3) => [0, 4, 1]
五，元组
元组是不可变的有序序列，是顺序表。元组创建之后就不能在更改，所以没有增，删，改等操作。
1，元组的构建
- （） :小括号构建元组 当小括号里面只有一个元素是，要用逗号分割 （1，）这才是元组，（1）不是元组 - tuple()：括号内为空或者一个可迭代对象 Init signature: tuple(self, /, *args, **kwargs) Docstring: tuple() -> empty tuple tuple(iterable) -> tuple initialized from iterable's items tuple(range(5)) (0, 1, 2, 3, 4)
2，元组的操作
2.1 查找 跟列表的查找方式一样，通过索引查找 a = ([3],) * 3 a => ([3], [3], [3]) a[0] = 300 #报错，因为元组里面的元素不能变动 a[0][0] = 300 #这个修改的不是a这个元组里面的元素，而是元素指向的实际内容，元素其实还是没变的,因为a[0]这个元素实际上指向的是[3]这个列表，所以a[0][0] = 300实际上是对[3]的修改，而列表是可修改的。 a => ([300], [300], [300]) # a[1].append(4) a => ([300, 4], [300, 4], [300, 4])
六，字符串str
1，字符串简介
- 由若干个字符组成的有序的序列（顺序表实现），是字符的集合 - 使用单引号，双引号，三引号引住的字符序列 - 字符串是不可变对象，是字面常量，一旦定义，不可更改 python3起，字符串都是Unicode类型
2，字符串构造
s = 'string' s1 = "string1" s2 = ''' this's a "string" ''' s3 = 'hello n world'
3,字符串操作
因为字符串是不可变字面常量，定义后就不能进行增，删，改操作 - 查 s = 'abcde' for i in s: print(i,type(i)) ab c d e s[-1] => e index,rinex(从右往左找),count,len等用法都跟列表的一样，优劣也一样 - find Docstring: S.find(sub[, start[, end]]) -> int Return the lowest index in S where substring sub is found, such that sub is contained within S[start:end]. Optional arguments start and end are interpreted as in slice notation. s = 'abcdeabcd' s.find('bc') => 1 #返回匹配到的索引位置 s.find('bd') => -1 #如果没有匹配到字串，返回-1 -rfind: 从右往左找，但是返回的索引还是正索引，如果没找到，返回负数 s.rfind('bc') => 6 - 时间复杂度 find,index和count方法的时间复杂度都是O(n) 随着字符串长度的增加，效率会下降 4，字符串拼接 'a' + 'b' => 'ab' 'ab' * 3 => 'ababab' str.join() Docstring: S.join(iterable) -> str Return a string which is the concatenation of the strings in the iterable. The separator between elements is S. 'abc'.join('ABC') => 'AabcBabcC' ':'.join('ABC') => 'A:B:C' ':'.join(("1","2","3")) => '1:2:3' ':'.join(["1","2","3"]) => '1:2:3' 可以看到join的作用就是，用.前面的字符串分割（）内的可迭代对象。可迭代对象里面的元素要是str类型的，如果不是需要转换 5，字符串分割 字符串分割看起来是改变了字符串，但是实际字符串并没有改变，只是给你生成了一个新的符合规则的字符串。 - split S.split(sep=None, maxsplit=-1) -> list of strings ':'.join('ABC').split(":",1) => ['A', 'B:C'] split 使用分割符分割给出的字符串，返回一个列表,可以指定切割次数。 y = ':'.join('ABC').split(":") .append('D') 请问y的值是什么？ 结果时None。因为append函数没有返回，或者说返回的结果是None，所以y的值就被赋为None 特殊例子 ":a:b:c:".split(":") => ['', 'a', 'b', 'c', ''] ":a:b:c:".split("#") => [':a:b:c:'] # 如果切割符在字符串中并不存在，则将整个字符串做为一个元素放到列表中返回 “anbrncrdte n f”.split() =>['a', 'b', 'c', 'd', 'e', 'f'] #不指定切割福，默认就会切割尽可能长的连续的空白字符 “anbrncrdte n f”.split("n") =>[['a', 'br', 'crdte ', ' f'] -rsplit 用法跟split一样，只不过是从右往左执行 Docstring: S.rsplit(sep=None, maxsplit=-1) -> list of strings -splitlines (把n,r等换行符切掉) "anbrncrdte n f".splitlines() => ['a', 'b', 'c', 'dte ', ' f'] - partition Docstring: S.partition(sep) -> (head, sep, tail) "a,b,c,d".partition(',') => ('a', ',', 'b,c,d') 可以看到partition指定分隔符后不管有多少个符合条件的，它都只切割一次，把字符串用分割符分割成两部分后以元组的方式返回 特殊例子： "a:b:c".partition("#") => ('a:b:c', '', '') "a:b:c".rpartition("#") => ('', '', 'a:b:c') 6，字符串替换 - replace Docstring: S.replace(old, new[, count]) -> str "a:b:c".replace(':','#') => 'a#b#c' # 返回的还是一个字符串，原字符串并没有被修改 特殊例子： "www.whp.com".replace('w','m') => 'mmm.mhp.com' # 默认全部替换 "www.whp.com".replace('w','m',2) => 'mmw.whp.com' # 替换两次 "www.whp.com".replace('ww','w') => 'ww.whp.com' # 为什么是这个结果，结果不是还有ww吗，为什么没被替换成w.whp.com? 因为对字符串的处理是一直往前走的，处理过的内容就不再处理，所以第一个w已经不在处理范围内了。 7，字符串移除 - strip (脱) Docstring: S.strip([chars]) -> str 'rna,b '.strip() => 'a,b' # strip默认将字符串两头的空白字符全部去掉。 'a,b,c,b,c'.strip('ac') => ',b,c,b,' # 为什么是这样的结果？ - rstrip(右脱) 'rna,b '.rstrip() => 'rna,b' # rstrip默认将字符串右边的空白字符全部去掉。 - lstrip(左脱) 'rna,b '.lstrip() => 'a,b ' # lstrip默认将字符串左边的空白字符全部去掉。 8，字符串格式化 - printf风格的字符串格式化 "***%d%5.1f***" % (100,1.264) # 5表示字符占5位右对齐，.1表示截取到小数点后一位 返回：'***100 1.3***' "***%d%-5.2f***" % (100,1.264) # -5表示字符占5位，左对齐，.2表示截取小数点后两位 "My name is %s,I'm %d" % ('whp',30) 返回："My name is whp,I'm 30" "My name is %(name)s,I'm %(age)d" % {'name':'whp',"age":30} 返回："My name is whp,I'm 30" - format "{2}:{1}-{0} {b} {a}".format(10,20,30,a='whp',b=200) # {}内的0,1,2代表的是format内元素的索引，a='whp',b=200 不能被索引，所以只能通过a,b标识符来获取到值 返回：'30:20-10 200 whp' "{} +++ {}".format((10,20)) 返回：IndexError: tuple index out of range # 因为（10，20）是一个元组，只能算是一个元素 "{0} +++ {0}".format((10,20)) 返回：'(10, 20) +++ (10, 20)' "{0[0]} +++ {0[1]}".format((10,20)) 返回：'10 +++ 20' "{} +++ {}".format(*(10,20)) # *(10,20) 将元组解构了 返回：'10 +++ 20' format格式化时间 d = datetime.datetime.now() d = datetime.datetime(2021, 10, 31, 22, 6, 41, 68571) "{}".format(d1) 返回：'2021-10-31 22:06:41.068571' "{:%Y-%m-%d %H:%M:%S}".format(d1) 返回：'2021-10-31 22:06:41' "{0:b} {0:X} {0:o} {0}".format(20) 返回: '10100 14 24 20' "{0:#b} {0:#X} {0:#o} {0}".format(20) 返回：'0b10100 0x14 0o24 20' 浮点数处理 "{:<7.3f}".format(1.4454545) # 对1.4454545进行格式化处理，.3表示返回小数点后三位，7表示占7位，<表示向左对齐，默认就是向左对齐 返回：'1.445 ' "{:>7.3f}".format(1.4454545) # 对1.4454545进行格式化处理，.3表示返回小数点后三位，7表示占7位，>表示向右对齐 返回：' 1.445'
