下载掌阅APP，畅读海量书库
立即打开
数据结构的内容包含逻辑结构、存储结构和运算三个方面。
逻辑结构指的是数据元素之间的逻辑关系；存储结构指的是数据的逻辑结构如何在计算机的存储器里表示和实现，也称为物理结构；运算在选择了数据结构的存储结构之后就可以实现，不同存储结构的运算性能可能存在一定的差异。
运算在数据的逻辑结构上定义时，描述的是“做什么”；在数据的存储结构上实现时，描述的是“如何做”。运算的实现就是通常所说的算法。算法的设计取决于数据的逻辑结构，算法的实现依赖于指定的物理结构。
按照数据元素之间关系的不同特性，通常可以将数据的逻辑结构分为集合结构、线性结构、树形结构和图形结构四种类型。
集合结构中的数据元素除了同属一个集合外，没有其他关系，各个元素是“平等”的，元素顺序是随意的，每个元素在集合中都是唯一的，该结构类似于数学中的集合，如图1.1所示。
图1.1 集合结构
线性结构中的每个数据元素都可以看作一个节点，数据元素之间是一对一的关系，即除了第一个元素外，每个元素有唯一的前驱；除了最后一个元素外，每个元素有唯一的后继。如图1.2所示。生活中的城市公交路线类是典型的线性结构，其中站点就是数据元素，每一条公交线路都有一个起点和终点，中间各站按先后次序排列。
图1.2 线性结构
逻辑上，具有这种线性的数据结构也称为线性表。表1.1航空客户信息表就是线性结构，每个数据元素由会员卡号、入会时间、第一次飞行日期、性别、年龄、观测窗口结束时间、窗口内的飞行次数、总基本积分等数据项组成。
表1.1 航空客户信息表
树形结构中的数据元素之间存在一对多的层次关系，或是分支关系。一个节点可能包含子节点，也可能不包含。没有子节点的节点称为叶子节点。此外，树形结构有一个特殊的节点，称为根节点，它是整棵树的起点。从根节点出发，可以到达树中的任何其他节点，如图1.3所示。
图1.3 树形结构
在实际应用中，一所学校的组织架构类似于树形结构，如图1.4所示。树根为学校，学校的下一层对应各个学院，各学院下有各个系。因此，学校架构可被抽象成树形结构来进行数据管理。
图1.4 学校的树形架构
图形结构中的数据元素之间存在着多对多的网络关系，数据元素也称为顶点，顶点与顶点之间存在着复杂的网络关系，所以图形结构也称为网状结构，如图1.5所示。
图1.5 图形结构
航空公司的飞行线路图类似于上述结构，如图1.6所示。每一个城市都是一个数据元素，飞行线路是元素之间的关系，一个城市机场可与多个城市通过飞行线路相连，多个城市连接成网状。
图1.6 航空线路图
从逻辑关系上来观察数据，它与数据的存储无关，是独立于计算机的。数据的物理结构则是逻辑结构在计算机存储器里的实现，是依赖于计算机的。
计算机的存储器由有限个存储单元组成，每个存储单元有唯一的地址，各地址是连续编码的。一片相邻的存储单元的整体称为存储区域。通常数据的存储结构有以下四种类型。
顺序存储结构按照给定数据元素的先后次序，逐一存放在连续的物理存储空间上。也就是把逻辑上相邻的节点存储在物理位置也相邻的存储单元中，如图1.7所示。
图1.7 顺序存储结构
顺序存储结构是一种简单且易于实现的存储方式。因为在采用顺序存储结构存储数据元素时，只需要知道数据元素在物理存储空间的位置关系，就可以得到数据元素的逻辑关系。存储的过程中，不需要增加其他的存储单元来记录数据元素的逻辑关系。通常情况下，在高级程序设计语言中可以用数组来实现存储结构。当对数据元素进行访问时，可以通过数组下标直接访问相关数据元素，因此顺序存储结构是一种可以随机访问的存储方式。
顺序存储结构的缺点：一方面当处理数据量很大，即数据元素个数较多时，需要一大块连续的存储空间，有时计算机很难满足其要求；另一方面当数据元素需要进行插入和删除操作时，需要对其他的节点进行移动，这种操作会增加系统开销，增加算法的时间复杂度。
在链式存储结构中，逻辑上相邻的数据元素可以存储在物理位置不相邻的存储单元上，如图1.8所示。也就是说不同的数据元素可以存储在连续的地址空间，也可以存储在不连续的地址空间。通常情况下，在高级程序设计语言中可以用指针类型来实现链式存储中对逻辑关系的描述。
图1.8 链式存储结构
链式存储结构中除了存储数据元素的这部分存储空间外，还有一部分存储空间用来存储数据元素之间的逻辑关系，即指针。由于逻辑关系相邻的元素物理位置不一定相邻，所以链式存储结构不能实现随机访问。链式存储结构的优点是容易修改，在插入、删除数据元素的操作时，只需要对相关指针进行修改，不需要像顺序存储结构一样对数据元素进行移动。
索引存储结构通过索引表来确定数据元素的存储位置，如图1.9所示。索引表包括数据元素的关键字和存储地址，数据元素的关键字能够唯一标识数据元素，通过存储地址可以访问该存储地址上的数据元素。
图1.9 索引存储结构
索引存储结构结合了顺序存储结构和链式存储结构的优点。不但能够实现对数据元素的随机访问，而且当需要对数据进行插入、删除等操作时，只需要修改和移动索引表中的相关节点的存储地址信息，不需要移动存储空间上的数据元素。索引存储结构可以分为两种：一种是稀疏索引，一组数据元素对应一个索引项；另一种是稠密索引，每一个数据元素都对应一个索引项。
散列存储结构将数据元素的关键字通过哈希函数转换成其存储地址，这种结构也称为哈希存储结构。这种结构适用于高速检索，效率近似于随机存取。它的基本设计思想是以数据元素的关键字 K 为自变量，确定一个函数关系 f （称为散列函数），计算出对应的函数值 f ( K )，将这个值解释为数据元素的存储地址，最后将数据元素存入 f ( K )所指的存储位置。查找数据元素时，根据其关键字用同样的函数计算出存储地址即可。
数据和操纵数据的运算是研究数据结构不可分割的两个方面，所以我们在讨论数据结构时，不但要讨论数据的逻辑结构、存储结构，还要讨论在数据结构上执行的运算（operation）以及实现这些运算的算法（algorithm）。
数据运算就是施加于数据的操作。数据运算包括运算的定义和运算的实现，前者确定运算的功能，后者是在存储结构上确定运算的算法。
数据运算包括算术运算（加、减、乘、除）、关系运算（大于、小于、等于）、逻辑运算（与、或、非），以及指数、对数、三角函数等更复杂的运算，还包括特定数据结构的运算，如矩阵运算、集合运算等。此外，在计算机科学中，数据运算还涉及位运算、移位运算等。有时数据运算常常涉及算法问题，常见的有插入、删除、更新、查找和排序等。例如，在数组中插入新元素可能需要移动其他元素以腾出空间；在链表中插入元素则相对简单，只需要调整指针。与此相似，在数组中删除元素可能需要移动其他元素以填补空缺；在链表中删除元素通常涉及重新连接指针。在数组或链表执行更新操作中，可以通过索引或遍历找到元素后直接更新。查找运算中的线性查找需遍历整个数据结构；二分查找则适用于已排序的数组，通过不断缩小查找范围来提高效率。
解决这些问题时，需要综合考虑数据结构的特性、算法的时间复杂度和空间复杂度，以及具体的应用场景和需求。通过优化算法和数据结构，可以显著提高程序的性能和效率。