Python数据结构

• 一、数据结构。
• 分类：数值型，int  浮点型 float，复数complex， bool 布尔值。
• 序列对象， 字符串str  列表 list。 Tuple   元祖。
• 键值对：集合set，字典dict。
• 数值型。
• int、float、complex。bool都是class，1,5.0,2+3j都是对象即实例。
• int 长整型，没有大小限制，受限于内存区域的大小。
• float，有整数和小数部分组成，支持十进制和科学计数法表示，只有双精度。
• complex。有实数和虚数部分组成，实数和虚数都是浮点数、3+4.2j。
• bool ：int的子类，仅有两个实例，True  和Flase，对应的1和0，可以和整数直接运算。
• 类型转换。
• int(x)；返回一个整数.查看帮助文档
• float(x)；返回一个浮点数
• complex(x)；返回一个复数。
• bool(x)；返回布尔值，和前面的Flase等价。
• 数字处理函数。
• 导入的math函数（import math ）(floor地板向下取整  ceil .天花板 向上取整数->是math模块中的)
• int() 取整数部分。
• round()函数 四舍六入五取偶。取向他最近的偶数靠近。
• //  正数负数全部往地板走。地板 整除且向下取整。
• min()  max()  pow(x,y)等于x**y。次幂。sqrt()。min（1，2，3，）比较大小的。
• 进制函数：返回的是字符串。

bin（）  oct（）   hex（）   math.pi  3.14    math.e

• 数据类型。数据类型判断，返回的是类型，而不是字符串。

字符串要加单引号。

type（）

type(‘a’)

• 类型判断

type()

isinstance(obj,class_or-tuple)

isinstance()返回布尔值。

隐式转化。。（type（1+true+2.1））float。。type（1+True)  int .      isinstance(1,int)

二、列表list。

一个队列，一个排列整齐的队伍，列表内的个体称作元素，由若干元素组成列表。

元素可以是任意个对象（数字，字符串，对象，列表等）。列表内元素有顺序，可以使用索引(编号在0开始)，线性的数据结构。使用[]表示。 (列表是个对象，列表内的元素也可以是个列表） 列表是可变的..(有编号未必是连续的)

1)list  链表  queue  stack的差异。

list ,(列表)。可以中间插队，前后均可以插队。线性数据结构。

queue ,(队列)。不可以中间插队，先进先出，后进先出都可以。线性模型。

stack. 栈。函数。只能后进先出。（罗盘子）函数中用的最多的。

链表：不连续的。通常是上级指向下级，下级指向上级。手拉手形式。内存中散落着。

2）列表list定义，初始化。

lsit()->new empty list

list(iterable)->

list不能一开始就定义大小。

list()可迭代对象。

lst=list

lst=[]

lst=list[2,6,9,’ab’]

lst=list(range(5))

(使用方式：list（range（1,3）[2,6,9,’ab’] )..

可索引和可迭代两个概念。

list可迭代对象和可索引的。：

迭代（乱拿方式），索引（按照序号拿出）

3）列表的索引，也叫下标。内存上连续的空间。

正索引：从左到右，从0开始，为列表中的每一个元素编号，按照顺序编号。

负索引：从右到左，从-1开始。

正索引不可以超界，否则引发异常IndexError。索引是不可以超界的。

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

列表通过索引访问。

(lst=list(range(5))  lst[-5]

4）、列表查询。

（1）、Index（value，[start,[stop]]]）（[]可以写，可以不写。）通过值value，从指定区间查找列表内的元素是否匹配。匹配第一个就立即返回索引。匹配不到，抛出valueErr 。     lst.index（1，-1）

lst.index()  ( 返回的是索引号)

使用负索引的时候必须要高度注意索引方向。

（2）、count（value）

返回列表中匹配的value的次数。lst.count(1)

（3）、时间复杂度：

index和count方法都是O（n）。建议不常用。

随着列表元素数据规模的增大，而效率下降。

（4）、len()。

用来计数的,计算长度的。。

（5）、查看帮助：

官方帮助文档，搜索关键字；

ipython中：help（keyword），，keyword可以是变量、对象、类名、函数名、方法名。

5）、列表元素修改：

索引访问权限修改：（修改其元素值）list[index]=value    索引不能超界。  lst[2]=200

6）、列表增加、插入元素。

（1)append(object)->None不会返回有效的值。    lst.append(200)   加几个元素都是依次写。

列表尾部追加元素，返回none值。

返回none就意味着没有新的列表产生，就地修改。

时间复杂度是O（1）

（2)insert（index，object）->None.      lst.insert(4,300)

在指定的索引index处插入元素object

返回None就意味着没有新的列表产生，就地修改。

时间复杂度是O（n）

索引能超上下界吗？

超越上届，尾部追加。

超越下界，头部追加。

（3)extend（iteratable）-> None       lst.extend(range(11,16))

将可迭代对象的元素追加进来，返回none。

就地修改。

简单的类型，引用类型。

（4）+ -> list      lst +list(range(17,20))

连接操作，将两个列表连接起来

产生新的列表，原列表不会改变。

（5)* -> list         [‘a1’]*5

重复操作，将本列表元素重复n次，返回新的列表本质上调用的是__add__(

7）、单支类型，复杂类型（引用类型）*3,相当于复制的是地址，(一个变，三个全部变)。

复杂类型：x = [[1,2,3]]*3

print(x)x[0][1] = 20print(x）

简单类型：y = [1]*5

y[0] = 6

y[1] = 7

print(y)

8）列表删除元素。

（1）remove（value）->none.      remove(200)

从左至右查找第一个匹配value的值，移除该元素，返回none。。。

就地修改。。。

效率。

（2）pop([index])->item.            n=list(range(1,9))     n.pop()

不指定索引index，就从列表尾部弹出一个元素。O（1）

制定索引index，就从索引处弹出一个元素，索引超界抛出IndexErr。O（n）

（3）clear（）->none。         list.clear(n)

清除列表所有元素，剩下一个空列表。慎重使用，会产生大量的垃圾，建议使用方法就是覆盖（重新赋值）避免使用。

9）、列表其它操作。

（1)reverse()->None                n.reverse()

将列表元素反转，返回None。

就地修改。。读取的时候进行调头

列表反转的迭代器。   reversed(n)

for i in reversed(n):

print(i)

能够立刻使用的的可迭代器。list(reversed(n)) 不耽误别人使用。

迭代器是一个可迭代对象。

（2）in

判断成员是否所在元素组里面。[3,4] in [1, 2, [3,4]]

（3)sort（key=None,reverse=Flase）->None

对列表元素进行排序，就地修改，默认升序。

reverse为True，反转，降序。

key一个函数，指定key如何排序。

lst.sort(key=functionname)

（）括号里面有*号必须按照要求写。

lst.sort(key=str)    利用str函数进行排序。

lst.sort（key=int）利用int进行排序。

lst.sort(key=functionname)

sorted(lst,key=str)  不影响原来列表，不会就地修改。生成新的列表。

10）列表复制。

（1)Shadow copy，影子拷贝，也叫浅拷贝，遇到引用类型，只是复制了一个引用而已.

lst1=lst0…只是地址相同，复制的是地址。

Copy（）-》list

Shadow copy  返回一个新的列表。(影子复制)

Id(list)显示的是内存地址。

遇到乘法和copy浅拷贝，只是拷贝的地址，简单类型的就是复制，复杂类型的复制的是地址。

（2)深拷贝，copy模块提供了deepcopy。

import copy

lst0 = [1, [2, 3, 4], 5]

lst5 = copy.deepcopy(lst0)

lst5[1][1] = 20

lst5 == lst0

浅拷贝：简单类型元模原样复制，引用类型复制的是地址。引用类型里面改变一个全部变。

深拷贝：简单类型元模原样复制，引用类型是按照地址重新复制一份。改变一个不影响另外一个。

拷贝总结：lst=[1,2,3,4]

lst1=lst  #同一个对象。

lst2=lst.copy（）#内容相同，不同的对象，遇到引用类型不会复制对象，只会复制地址。

lst3=copy，deepcopy（lst）#内容相同，但不同的对象，如果有引用类型也会复制出不同的对象。

11）random模块

（1）导入import random。

（2）randint（a，b）之间返回一个随机数.

（3）choice（seq）从非空序列的元素中随意挑选一个元素，random.choice（range（10）。random([1,3,5,7]).

（4）randrange ([start,] stop [,step]) 从指定范围内,按照指定基数递归的一个集合中获取一个随机数，基数缺省值为1.     random.randrange(1,7,2)

（5）random.shuffle(list) ->None 就地打乱列表元素  random.shuffle(lst0)

（6）sample(population, k) 从样本空间或总体（序列或者集合类型）中随机取出k个不同的元素，返回一个新的列表.random.sample([‘a’,’a’,’a’,’a’],2)

for i in range（10）

Print（random.randint（1,6）)

三、元组tuple

1、元组的介绍。

1）一个有序的元素组成的集合。可迭代，可索引。

使用小括号表示。（）

元组是不可变的对象。（放的对象是不可变的，不可以给予赋值）。表达形式t1=（1，）

地址不可以改变，里面的内容可以改变。元组地址不允许更改。只是只读数据，不可以进行修改。

2）Map函数按照字符串一一转换。字节。\n  10    \r  13

• —127，按照表比较。比较的是一个个字节。
• 有out才有返回值。

A=print()   print只会打印到屏幕。不会给其值。

A=tuple（）   给其值 ，但是返回的是空值。

2、元组的定义 初始化

1)定义

2)tuple() -> empty tuple

3)tuple(iterable) -> tuple initialized from iterable’s items

t = tuple() # 工厂方法

t = ()

t = tuple(range(1,7,2)) # iteratable

t = (2,4,6,3,4,2)

t = (1,) # 一个元素元组的定义，注意有个逗号

t = (1,)*5

t = (1,2,3) * 6

3、元组元素的访问

支持索引（下标）。

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

负索引：从右至左，从-1开始。不可变的所以不能进行赋值。

正负索引不可以超界，否则引发异常。

元组通过索引访问。tuple[index],index就是索引，使用中括号访问。t[-2]

4、元组查询

• index(value,[start,[stop]])
• count(value).
• 时间复杂度…index和count的方法都是O（n）。随着列表数据规模的增大，而效率下降。
• len(tuple)返回元素的个数。

5、元组其它操作。

元组是只读的，所以增，改，删方法都没有。

6、命名元组namedtuple，（面向对象）。

namedtuple，更改元组名字。

Import collectios

Point=collections.Namedtuple（‘_Point’，【‘x’，‘y’】）

P=Point(11,22)

(point只是标示符）

四、冒泡法。

1）属于交换排序。

2）两两比较大小，交换位置。如同水泡。

3）结果分为升序和降序。

4）总结。

*冒泡法需要数据一轮轮的比较。

*可以设定一个标记判断此轮是否有数据交换发生，如果没有发生交换，可以结束排序，如果发生交换，继续下一轮排序

*最差的排序情况是，初始顺序与目标顺序完全相反，遍历次数1,…,n-1之和n(n-1)/2

*最好的排序情况是，初始顺序与目标顺序完全相同，遍历次数n-1

*时间复杂度O(n**2)（是由于两层循环得来的。）

*空间复杂度。O(1)

五、字符串

1）字符串是不可变的对象。（可变的是重新拼接组成的新的字符串）

• 一个个字符组成的有序的序列，是字符的集合。
• 使用单双号、双引号、三引号引住的字符序列。描述字符串，没有放字符的为空字符串，长度为0，等同于None。
• Python3中字符串就是unicode—-8类型的。
• 生成新的值。Utf-8。
• 字符串定义初始化。  s2=”string”   s3=”’this is a”string””’    s5=’c:\windows\nt’打印带出斜杠的。
• 字符串元素访问—–下标。
• 字符串支持使用索引访问。  sql[3].
• join 把可迭代对象的一个个字符串连接起来。

可迭代对象本身元素都是字符串。  “string”.join(iterbale)->str

返回一个新的字符串。      ‘—‘.join(map(str,lst))

• map(str.lst)转换为字符串的方式。
• 字符串+连接
• + -》str。将两个字符串拼接在一起，返回一个新的字符串。‘a’*2
• 字符串的分割。分为两类。
• Split() 没有指定，尽可能多的空白字符作为一个空白分隔符。’’+

Split（sep=none,maxsplit=1）。不指定分隔符的时候，默认以空白字符进行分割。

“a   b\tc”.split()        从左至右

p sep 指定分割字符串，缺省的情况下空白字符串作为分隔符

p maxsplit 指定分割的次数，-1 表示遍历整个字符串.

切的函数都是一刀两断。      “a,b,c,d,e”.split(‘,’,2)         不支持正则表达式。

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

*从右向左

*sep 指定分割字符串，缺省的情况下空白字符串作为分隔符

* maxsplit 指定分割的次数，-1 表示遍历整个字符串.

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

* 按照行来切分字符串

* keepends 指的是是否保留行分隔符

* 行分隔符包括\n、\r\n、\r等

()括号里面的添加True，切割后显示分隔符。False不显示分隔符。

4）Partition(seq)->(head,seq,tail)切割。切割完成后返回的是三元组。

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

Seq必须界定分隔符，必须制定。

5)rpartition(seq)->(head,seq,tail),从右至左，到分隔符就把分隔符分割成两部分，返回头、分隔符、尾三部分的三元组。如果没找到分隔符，就返回头，2个空元素的三元组。

6）字符串大小写

1)upper全是大写。    lower全是小写。 swapcase()交互式大小写。if a.lower()=’abc’:

7）字符串排版

title() 标题的每个字母首字母都大写。

capitalize()首个单词大写。

center(width[,fillchar])  ->str    width打印的宽度，，，fillchar填充的字符。

zfill(didth)   width打印宽度，居右。）

8）、字符串修改。

（1)replace(old,new[,count])—->str**

字符串中查找到匹配替换为新字串，返回新的字符串。

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

（2)Strip（[chars]）->str

把两头的符合要求的字符串全部去掉。char作为集合，去掉字符集。

如果char没有指定字符，那么就去掉两头的空白字符。

s=’very very very good’…..s.strip(‘ very’)

lstrip([chars]) -> str

从左开始

rstrip([chars]) -> str

从右开始

9）find();

找得到返回的是索引，未找到返回的是-1.

find(sub[, start[, end]]) -> int    s.find(‘very’)

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

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

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

10）字符串查找

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

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

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

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

• 字符串查找。
• 时间复杂度，index和count方法都是O（n）。
• 随着列表数据规模的增大，而效率下降。
• len（string）返回字符串的长度，即字符串的个数。

11）、count(sub[, start[, end]]) -> int

在指定的区间[start, end)，从左至右，统计子串sub出现的次数。。。s.count(‘very’)

• count(sub[])->int.
• 字符串判断：

endswith(suffix[, start[, end]]) -> bool

在指定的区间[start, end)，字符串是否是suffix结尾

startswith(prefix[, start[, end]]) -> bool

在指定的区间[start, end)，字符串是否是prefix开头

12）、字符串判断 is系列

isalnum() -> bool 是否是字母和数字组成    “abc123″.isalnum()

isalpha() 是否是字母

isdecimal() 是否只包含十进制数字

isdigit() 是否全部数字(0~9)

isidentifier() 是不是字母和下划线开头，其他都是字母、数字、下划线

islower() 是否都是小写

isupper() 是否全部大写

isspace() 是否只包含空白字符       返回的都是bool值。

Sections(有序的)(常见的面试是排序方法是冒泡法）。

13）字符串格式化。

字符串格式化是一种拼接字符串输出样式的手段，更灵活方便。

1）join拼接只能使用 分隔符，且要求被拼接的是可迭代的对象。

2）+拼接字符串比较方便，但是字符串需要先转换为字符串才能拼接。

printf-style formatting，是来自于c语言风格的print输出。

3）格式要求：占位符。。使用%和格式字符组成，例如%s，%d。

S调用str,   r调用repr().所有对象都可以被这两个转换。‘a’使用ascii。%

占位符中还可以插入修饰字符，例如%03d表示打印3个位置。不够前面补0.

format % values.格式字符串和被格式化的值之间使用%分隔。

Values只能是一个对象，或者是一个和格式字符串数目相等的元组，或一个字典。

用法：”i am %01s”  %(3,)

‘i like %s.’%’Python’

4)’%3.2f%% , 0x%x, 0X%02X’ % (89.7654, 10, 15)

可以是 元组，可以是字典。

0x    0X只是提示符。

5）字符串格式化。

format函数格式。

“{}{***}”。format（args，kwargs）。

Args是位置参数，是一个元组。

Kwargs关键字参数，是一个个字典。   {}花括号代表占位符。{{}}表示打印花括号。

{}表示按照顺序匹配位置参数，{n}标示取位置参数索引为n的值。

{****}表示在关键字参数中搜索名称一致的。

6）字符串格式化。

p 位置参数

“{}:{}”.format(‘192.168.1.100’,8888)，这就是按照位置顺序用位置参数替换前面的格式字符串的占位符中

p 关键字参数或命名参数

“{server} {1}:{0}”.format(8888, ‘192.168.1.100’, server=’Web Server Info : ‘) ，位置参数按照序号匹配，

关键字参数按照名词匹配

p 访问元素

“{0[0]}.{0[1]}”.format((‘magedu’,’com’))

p 对象属性访问

from collections import namedtuple

Point = namedtuple(‘Point’,’x y’)

p = Point(4,5)

“{{{0.x},{0.y}}}”.format(p)

• “{:^10x}”.format(97)居中对齐。'{0}*{1}={2:<2}’.format(3,2,2*3)
• 进制。”int: {0:d}; hex: {0:x}; oct: {0:o}; bin: {0:b}”.format(42)

 

• 1
• a  97

 

权重。

显示时间的。

 

有效数字。。（）

六、bytes、bytearray

字符串是字符组成的有序序列，字符可以使用编码来理解。

1)bytes是不可变的字节，是字节组成的有序的不可变序列。

2)bytearray 是可变的字节，是字节组成的有序的可变序列。

3）编码与解码

字符串按照不同的字符集编码encode返回字节序列bytes。

encode(encoding=’utf-8’ ,errors=’strict’)->bytes

b’abcdef’.replace(b’f’,b’k’)

字节序列按照不同的字符集解码decode返回字符串

bytes.decode(encoding=”utf-8″, errors=”strict”) -> str

4）bytes定义

Bytes() 空的bytes。 Bytes（int）指定字节的bytes，被0填充。

Bytes（iterable_of_ints)->[0,255]的internet组成的可迭代的对象。

Bytes(string,encoding[,errors])->bytes等价于string。Encode（）

Bytes(bytes_or_buffer)->immutable cpoy of bytes_or_buffer从一个字节序列或者buffer复制出一个新的不可变的bytes对象。

使用b前缀定义：

只允许基本ASCII使用字符形式b’abc9’

使用16进制表示b“、x41、x61”

 

5）ASCII表。ASCII（American StandardCode for InformationInterchange，美国信息交换

标准代码）是基于拉丁字母的一套单字节编码系统

6）bytes操作

和str类型类似，都是不可变类型，所以方法都一样，只不过bytes输入是bytes，输出也是bytes。

类方法bytes。Formhex（string）

String必须是2个字符的16进制的形式，bytes.fromhex(‘6161 09 6a 6b00’)

Hex()返回十六进制的字符串。

‘abc’.encode().hex()

索引 b‘abcdef’[2]

7）bytearray定义

定义：bytearray()空的bytearray

Bytearray(int)指的是字节的bytearray，被0填充。

Bytearray（iterable_of_ints)->bytearray[0,255]的int组成的可迭代对象。

Bytearray（string，encoding[,errors])->bytearry近似string。Encode（）不过返回可变对象，

Bytearray（bytes_or_buffer)从一个字节序列或者buffer复制出一个新的改变的对象。

B前缀的定义的类型是bytes类型。

8）byearray操作

和bytes类型方法相同。

Bytearray(b’abcdef’).replace(b’f’,b’k’)

Bytearray(b’abc’).find(b’b’)

类方法bytearray.formhex(string)

String必须是2个字符的16进制的形式。

Bytearray。Formhex(‘6162 09 60 6b00’)

hex()

返回16进制表示的字符串。

Bytearray（‘abc’.enconde（））。Hex（）

索引

Bytearray（b’abcdef’）[2]返回该字节对应的数，int类型。

9）bytearray操作。

Append（int）尾部追加一个元素。

Insert（index，int）在指定索引位置插入元素。

Extend(iterable_of_ints)将一个可迭代对象的整数集合追加到当前bytearray

Pop（index=-1）在指定索引上移除元素，默认从尾部移除。

Remove（value）找到第一个value移除，找不到抛出异常。

Clear（）清空

Reverse（）翻转bytearray，就地修改。

10)提到字符串就得有编码的概念。

11)字节

12)字节0-255之间。

13)可以索引的数据结构，列表，tuple   str   bytearray.

七、切片。

• 线性结构。

可迭代。。。for。。。In。。

len()可以获取长度。

通过下标可以访问。可以切片。

• 学过的线性结构：

列表、元组、字符串、bytes  bytearray.

• 切片：

通过索引区间访问线性结构的一段数据。

Sequnence[start:stop]表示返回[start,stop]区间的字序列。

支持负索引。

Start为0，可以省略

Stop为末尾，可以省略。

超过上界（右边界），就取到末尾；超过下界（左边界），取到开头。

Start一定要在stop的左边。

[:]…表示从头至尾，全部元素被取出，等效于copy（）方法。

生产新的拷贝。

 

练习方法：’www.magedu.com'[:10]   —-‘www.magedu’

bytearray(b’www.magedu.com’)[-4:10]     —  bytearray(b”)

‘www.magedu.com'[:]  ——-‘www.magedu.com’

tuple(‘www.magedu.com’)[-10:10]  ——-(‘m’, ‘a’, ‘g’, ‘e’, ‘d’, ‘u’)

list(‘www.magedu.com’)[-10:-4] ——-  [‘m’, ‘a’, ‘g’, ‘e’, ‘d’, ‘u’]

• 切片

步长切片

[start:stop:step]

Step为步长，可以正负整数，默认是1；

Step要和start;stop同向，否则返回空序列。

练的例题：’www.magedu.com'[4:10:2]

‘mgd’

 

list(‘www.magedu.com’)[-4:-10:-2]

[‘.’, ‘d’, ‘g’]

八、练习题

1、#求100以内的素数。

b=[2]
for i in range(3,101,2):
for a in b:
if i%a==0:
break
else:
b.append(i)

2、#杨辉三角

n=6
pre=[1]
print(pre)
pre.insert(0,0)
pre.append(0)
for i in range(1,n):
newline=[]
for j in range(i+1):
val=pre[j]+pre[j+1]
newline.append(val)
print(newline)
pre=newline
pre.insert(0,0)
pre.append(0)

#第二种

c=[[1],[1,1]]
for i in range(2,6):
newline=[1]
pre=c[i-1]
for j in range(i-1):
val=pre[j]+pre[j+1]
newline.append(val)
newline.append(1)
c.append(newline)
print(c)

3、#比较三个数大小

nums=[]
for i in range(3):
nums.append(int(input(‘{}:’.format(i))))
while True:
cur=min(nums)
print(cur)
nums.remove(cur)
if len(nums)==1:
print(nums[0])
break

4、#冒泡法排序

#冒泡法排序。
nums=[0,1,3,5]
length=len(nums)
for i in range(length):
for j in range(length-i-1):
if nums[j]>nums[j+1]:
tmp=nums[j]
nums[j]=nums[j+1]
num[j+1]=tmp
print(nums)

5、#输入5个数字，打印每个数字的位数，将这些数字排序打印，要求升序打印

nums=[]
for i in range(5):
nums.append(int(input(‘{}:’.format(i))))
length=len(str(nums[i]))
print(length)
length=len(nums)
for i in range(length):
for j in range(length-i-1):
if nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
print(nums)