[数据结构与算法]2021-09-17数据结构与算法--第二天

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

上述表格是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同。
根据上表可知，访问指定元素时无需从头遍历，通过计算便可过得对应地址，其时间复杂度为O(1）

（上图的c为实际地址信息所需要的的存储量，每个地址信息的存储单元都是均匀分配的，方便管理）
如果元素的大小不同意，则需采用如上图的元素外置的形式，将实际元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即连接），而后顺着链接找到实际存储的数据元素，实际上也就是索引结构

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

区别：
在需要添加新的元素进入表中时，如果原表的申请的内存空间不够了的话
对于一体式结构：
表头的地址信息会改变（需要重新申请一个表，而地址信息也需要放入新的表中）
对于分离式结构：
表头的地址信息不会改变，仅仅只需要重新申请一个表用来存放数据

顺序表数据区替换与扩充

两种方式：
1.每次扩充固定存储区域
2.每次翻倍存储区域

list的基本实现技术

链表的提出

数据不同于顺序表的顺序结构，而是一个个‘节点’，上一个节点会保存下一个节点的地址信息，从而可以离散的保存数据

单链表：是链表中最简单的一种形式，它的每个节点包含两个域，一个是信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个控制

python中变量标识的本质

不同于其他语言，在Python中，变量保存的是值的地址信息
如a,b=b,a，是交换ab的引用，并不是直接交换数值