python数据结构--绪论

1.戏说数据

在对社会进行研究时，我们以单个人为研究对象
每个人都是一个整体，忽略身高、体重和相貌等因素，人就是我们研究的一个单位，这就是数据元素
但是每个人都有身高、体重和相貌，这些是作为人的单位的属性，所有的属性构成我们的基本单位人，这个叫数据项。许多个项构成我们的数据元素
社会研究的时候，我们要调查所有人的身高，身高是所有人都有的属性，也就是所有数据元素都有的数据项，这个就叫数据对象
社会研究中，我们研究其中的结构肯定是人与人的结构，不会是鼻子与鼻子之间的关系，所以我们的数据结构，肯定是基本单位间的结构，即数据元素间的结构关系

2.数据的逻辑结构和储存结构

逻辑结构指的是抽象的关系结构，储存结构即物理的、现实中的存储的结构。
举个例子，"Life is short,I user python"这句话是按单词语法顺序储存在我们内存中，在表面看，is在Life后面，short在is后面，这个就是我们的逻辑顺序，但是这句话储存在我们实际内存中并不一定是连续的，你家中的储物柜空余的格子每次都是连续的吗？所以在我们存储结构(物理)上并不是连续的

2.1 逻辑结构

数据的逻辑结构分为集合、线性结构、树形结构和图状结构
python数据结构--绪论

集合结构：就像一个班里面的同学，只是单纯地放在一起，没有其他关系。当我们判断一个学生是不是这个班级，只需要将这个班看作集合即可
线性结构：在这个班里面，按成绩排名了先后顺序，那么我们要找第三名，就必须先找到第二名，找到第二名就必须先找到第一名，从第一名依次往下找。
树形结构：班主任通知班长检查作业，班长组织各组组长检查作业，由此形成一个树形结构。我们发现每个组长只有一个上级，但是有多个下级，班长也只有一个上级，但是有多个下级。所以树形节点中，除了最开始最高级地节点没有父辈节点外(在这个树形结构中班主任是没有上级的)，其余节点都有且只有1个父辈节点，但是有N个子节点（N=0、1、2、3…）
网状结构：该结构就像蜘蛛网，四通八达，各数据之间的关系都有不同，就像班级中任意两个人的关系，可能有，也可能没有

2.2 数据的存储结构

一句话在逻辑上是顺序结构，但是存在计算机中的时候，刚好有一段合适的空白内存让我们储存吗？大多数是零零散散的空白存储区域，所以存储结构是数据在物理计算机的表示

顺序存储结构：将我们的同学比作数据，将座位比做存储空间。一个班的同学按成绩排名，位置按成绩顺序依次排序，所以逻辑上第10名后面是第11名，那么从座位上看，第10名的座位后面一定是第11名的座位。但是有一天第22名同学转学了，为了维持我们存储空间的连续性，第22名后面的同学全部要向前坐一个位置。同理，插入一个同学，后面的同学都要后退一个位置
链式存储结构：后来我们不按名名次排座了，我们有空位置就坐，这样更符合内存中的真实情况。但是呢这样我们就无法按顺序寻找到第11名的位置了，怎么办？很简单我们给每个同学一个小纸条，小纸条上写着下一名次的同学的位置在哪里，这样我们要找第11名就简单啦，首先假如我们知道了8号的位置，找到8号看他手上的小纸条，写着9号的位置，然后据此找到9号看他手上的纸条，找到10号，依次找下去，最后找到11号。有一天我们22号同学转学了，那么我们只需要修改21号同学手上的小纸条，将指向的地址改成23号就可以了。
索引储存结构：很好理解，每个同学的名字和坐的位置对应列出一张表贴在教室里，每次找谁先看索引表，然后直接找到他的座位即可。我们找数据地址，只需要在索引表中找到该数据对应的地址，即可直接找到
哈希存储结构：使用数据元素关键字，通过事先设计好的哈希函数计算出来一个值，这个值就最为该数据元素的地址

结构方式	优点	缺点
顺序存储结构	只需要存储数据本身	插入或者删除数据都要移动后面的所有数据
链式存储结构	储存情况更符合真实存储	需要储存本身数据和下一个数据的地址
索引存储结构	直接查表找到地址，查找效率高	但是需要存储索引表，空间利用率低
哈希存储结构	快速查找，只存数据本身	不易于插入和删除

3.python的数据类型

数字数据类型、字符串数据类型、列表数据类型、元组数据类型、集合数据类型、字典数据类型
特殊的：抽象数据类型

3.1 列表

创建列表:list=[]

添加元素:
list.append()：只能添加一个且添在末端
list.extned([])：将一个列表添加进去
list.insert(index,sub)：将sub插入到index位置

删除元素：
list.remove(sub)：删除list中的sub
del.list[index]：删除第index个数据
list.pop(index)：删除第index个数据，默认最后一个

获取某个数据：list[index]

交换数据：使用一个空瓶子来交换数据

列表分片
list[start: end:step]：得到[start:end)列表片,strat默认0，end默认最后一个，支持倒数切片

常用操作符 eg.list1=[a,b,c,d] list2=[e,f,g,h]

比较操作符 < > ：ae比较 & bf比较 & cg比较 & dh比较
拼接操作符 + ：双边类型必须相同
复制操作符 * ：list1*2=[a,b,c,d,a,b,c,d]
成员关系 in/not in ：判断数据是否在列表中，只能寻找一层

多层访问 list3=[1,2,[‘小甲鱼’,‘大甲鱼’],3,4]
‘小甲鱼’ in list3[2]
其他常用函数，可使用dir(list)查看
list.count(sub)：计算sub出现的次数
list.index(sub[,start,end])：返回sub的位置,可以限定寻找范围
reversed(list)：翻转list数据，type=迭代器
list.sort()：从小到大排序
list.sort(reverse=true)：从大到小排序,reverse默认false
i*i for i in range(0,10)：列表解析，生成0~9的平方

3.2 元组：不被轻易改写，标志是“,”

1.创建元组：tuple=a,b,c,d 特殊的tuple(是元组)=(1,) tuple(是整数)=(1)
2.更新和删除：
元组本身是不可被修改的，但是可以通过复制拼接更新
tuple=tuple[:2]+(5,)+:tuple[2:]
del tuple:删除元组
3.其他常用符号：< > = * and or

3.3 字符串

eg.str=[‘I love you’]
1.输入格式：
str=r’C:\now’ //即使是转义符也会被忽略
多行源格式字符串：三引号’’‘abcd’’’
2.分片 str[:6]：得到I love
3.索引 estr[5]：得到e
4.奇葩字符串函数：字符串的方法及注释
5.字符串的格式化：字符串格式化符号含义及转义字符含义
“{a} love {b}.{c}”.format(a=“I”,b=“FishC”,c=“com”) //“I love FishC.com”
“%#x” % number

3.4 序列

list()：将可迭代对象转化为列表
max()：返回最大值或对应最大ASCII的字符
min()：参考max()
sum(sequence,sub)：sequence，再加sub
zip(a,b)：返回a匹配b形成的二元组