数据结构与算法(第二节)

数据结构

1. 概念
   数据结构指数据对象中数据元素之间的关系
2. python数据结构
   内置数据结构：列表、元组、集合、字典等
   扩展数据结构：栈、队列、链表等(需用户自定义)
3. 算法与数据结构的关系
   数据结构是静态描述数据元素之间的关系。算法是为解决实际问题而设计的方法。高效的程序需要在数据结构的基础上设计和选择算法。用一个公式体现二者的关系：
   程序 = 算法 + 数据结构
   总结：算法是为解决实际问题设计的，数据结构是算法处理问题(数据)的载体。
4. 抽象数据类型(abstract data type)
   将数据类型及其相关的操作捆绑到一起。这样有助于将数据类型的使用与普通程序相分隔，方便用户操作与使用。
5. 线性表
   描述一组元素序列的数据关系，元素在序列中有相应的位置和顺序，线性表包含顺序表和链表两种。
6. 顺序表
   定义：将元素按顺序存放在一块连续的存储区，元素的顺序对应存储的顺序
   特点：元素访问高效，但对内存利用不充分，当内存占用较大时，存储大量数据可能无法实现
   布局：顺序表的布局分为元素内置和元素外置两种布局方式，对于元素内置的布局方式，是直接将数据存放到预先定义的顺序表中，这种方式只能存储单一的数据类型；对于元素外置的布局方式，表中存储的是实际数据的地址，通过地址链接数据，因此可以在实际地址空间中存储任意的数据类型。下图为两种方式的示意图，a)代表元素内置布局，b)代表元素外置布局：
   
   结构：顺序表由表头、表体两部分组成，表头包含表的容量和实际存储的元素个数，表体则存储实际的数据元素。根据表头和表体的不同组织结构，顺序表结构可分为一体式结构和分离式结构。一体式结构，表头、表体共同分布于同一块连续的存储区；而分离式结构的表头、与表体分别存储于不同的存储区，通过表头存储区中存储的链接数据，与表体关联。具体看下图：
   
   存储区替换：由于顺序表是预先为其分配一块连续存储空间用于存储数据元素，当存放数据个数超过预先定义的可存放容量个数时，只能将存储区替换为更大的存储区。
   对于一体式结构，表头与表体共用一块连续存储区，想要替换表体存储区，只能将其整体搬迁，即整个顺序表对象(表头存储区)被改变；
   对于分离结构，表头和表体分离，想要替换表体存储区，无需改变存储区对象(表头存储区),只需要将表体存取区替换并更新表头链接数据即可。由于该结构无需改变对象，调用程序无需做任何修改，即可实现扩容，因此也被称为动态顺序表。
   存储区扩充：存储区扩充有两种扩充策略。一种是线性增长策略，一种是加倍增长策略。
   线性增长策略：每次以固定值扩充存储位置，特点是节省空间，但操作频繁降低了效率
   加倍增长策略：每次扩充容量加倍，特点是减少操作次数提高了效率，但可能导致资源浪费，属于以空间换时间。实际使用配合一些限制条件更佳，如当达到一定容量后，降低加倍的倍数。
   python中的顺序表：在python中列表和元组都是采用顺序表实现。其中列表由采用分离式结构、元素外置的动态顺序表实现，这就是为什么在列表中可以存储任意类型数据并随时可以添加或删除的原因。而元组被定义为不可变类型，不支持修改数据，但其他方面与列表类似。