[数据结构与算法]数据结构与算法---第二章

目录

第二章

基本顺序表与元素外围顺序表

顺序表的一体式结构与分离式结构

顺序表数据区替换与扩充

顺序表添加与删除元素_python列表的实现

第二章

基本顺序表与元素外围顺序表

基本数据类型：整型，浮点型，字符串---基本数据类型怎么组织起来？

内存是一个连续的存储空间，以一个字节作为存储单元（一个字节是8位）

查找内存中的地址，就可以得到字节中的信息

不同基本数据类型需要占据多少个存储单元？---对于32位机器，一个基本整型占四个字节

int a =1 #整型
00000000 00000000 00000000 00000001
# 也可以代表4个char，所以在初始要定义数据类型

字符串已经是一个集合，一个char占一个字节（一个存储单元）

一组数据，同样类型，按顺序存储，形成一个顺序表

元素外围顺序表：把元素的地址连续存储起来（占四个字节），找到0×324存储的地址0×100，再找到0×100里面存储的元素------地址空间的顺序，达到元素外置，可以存储不同的数据类型

顺序表的一体式结构与分离式结构

表头信息（顺序表能存多少，当前存了多少）+数据区

?一体式结构：把表头信息和数据做连续存储

Li = [200,390,78]

分离式结构：把表头信息和数据分开存储

一体式结构元素扩充需要整体替换（重新申请一块空间4---5），表头地址变更

分离式结构元素扩充不需要改变表头的地址

考虑未来数据的动态变化，一般都会使用分离式

顺序表数据区替换与扩充

顺序表扩充可以多申请一部分（顺序表预留）

固定申请（每次申请4）

加倍申请（每次申请当前存储位置的n倍）---用空间换时间（预留了更多的空间，但申请次数少了）

顺序表添加与删除元素_python列表的实现

a.尾部加入（删除）元素，时间复杂度O(1)?

b.非保序的加入（删除）元素（不常见），时间复杂度为O(1)?

c.保序的元素加入（删除），时间复杂度为O(n)?

python中的list就是一种采用分离式技术实现的动态顺序表。4倍增的方式，到达50000个元素后改为1倍。保序。