Python算法图解（一）数据结构的分类和基本运算

本系列内容来自何韬编著的《Python算法图解》。

1 数据结构的分类和基本运算

数据是信息的载体.
数据元素是数据的基本单位，通常作为一个整体考虑，一个数据元素可由若干数据项组成，也称为节点或记录。比如一条购物清单就是一个数据元素，包括购买物品的数量、单价、名称等数据项。

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。在任何问题中，数据元素都不是独立存在的,它们之间存在某种关系,这种关系称为结构。
数据结构包含逻辑结构、存储结构(物理结构)、运算三个要素。
数据结构的逻辑结构和存储结构密不可分，一个算法的设计取决于所选的逻辑结构,算法的时间则依赖于所采用的存储结构。

1.1 逻辑结构

逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。
逻辑结构可分为线性结构（ N个数据元素有序排列的集合，元素前后是1对1的关系）和非线性结构（除线性结构之外，一对多或多对多）。

线性结构应该符合的特征：

1. (必选项)集合中必存在唯一的一个“第一个元素”。
2. (必选项)集合中必存在唯一的一个“最后的元素”。
3. (可选项)除最后的元素之外,其他数据元素均有唯一的“后继”,即指向后一个元素的方式。
4. (可选项)除第一个元素之外,其他数据元素均有唯一的“前驱”,即指向前一个元素的方式。

线性结构的数据元素之间存在”一对一“的线性关系。符合线性结构的数据结构包括一维数组、栈、队列、链表等：

非线性结构相对于线性结构有一个最明显的区别:各个数据元素不再保持在一个线性序列中,每个数据元素可能与零个或多个其他数据发生联系，这就是一对多或多对一的关系。
根据关系的不同,可将非线性结构分为层次结构和群结构两种类别。
常见的非线性结构有二维数组、多维数组、广义表、树(二叉树)结构、图结构等：

1.2 存储结构

数据的存储结构分为4种：

1. 顺序存储结构：逻辑上相邻的元素在计算机内也相邻。采用一段连续的存储空间。此结构可以快速定位第几个元素的地址，但是插入和删除数据需要移动大量元素，使用一整块存储单元可能产生较多的外部碎片。
   

2. 链式存储结构：逻辑上相邻的元素，在计算机内存中的存储位置不要求必须相邻，相邻逻辑元素借助元素存储地址的指针域定位下一个元素的地址。
   优点：可以利用碎片位置，可以实现快速增加和删除数据；
   缺点：需要额外空间存储指针域，不能实现随机访问（下标访问）。
   

3. 散列存储结构（哈希Hash存储结构）：由节点的关键码值决定节点的存储位置。用散列函数确定数据元素的存储位置与关键码值之间的对应关系。

4. 索引存储结构：除建立在存储节点信息外，还建立附加的索引表来表示节点的地址，索引表是由若干索引项组成。所引向的一般形式是键的关键字对应值的内存地址。
   优点：检索速度快；
   缺点：附加的索引表额外占用存储空间，且增加和删除数据，也需要修改索引表，会花费多余时间。
   

1.3 基本运算

数据结构的基本运算包括：创建数据结构，清除数据结构，插入数据元素，删除数据元素，更新数据元素，查找数据元素，按序重新排列数据，判定某个数据结构是否为空，或者是否已达到最大允许容量，统计数据元素的个数等。