数据结构

什么是数据结构

1、数据
数据是描述客观世界的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号集合。简言之，数据就是计算机加工处理的原料，是信息的载体。

2、数据元素
数据元素是能够独立、完整地描述问题世界中的实体的最小单位，它是数据这个集合中的一个一个的元素，数据元素也成为数据结点，或者简称结点
3、数据对象
一个数据对象被定义为具有相同性质的数据元素的集合。
4、结构
数据元素之间必然存在着某种联系，这种联系称为结构。人们不仅要考虑到数据的这种结构，而且还要考虑到将要施加于数据上的各种操作及其种类。从这个意义上来说，数据元素是具有结构的数据元素的集合。
这里也可以给数据结构一个形式化的描述。数据结构是一个二元组Data-Structure=(D,R),其中，D是数据元素的有限集合，R是D上关系的集合。
上述定义中的"关系"通常是指数据元素之间的逻辑关系，也称为数据的逻辑结构。通常把数据结构在计算机中的表示称为数据的物理结构。物理结构又称存储结构，包括数据元素的表示以及关系的表示两个方面。数据的逻辑结构与存储结构是密不可分的两个方面，一个算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构，存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现取决于所选定的存储结构。

数据的存储结构主要有：顺序存储结构、链式存储结构、索引存储结构和散列存储结构。

1、顺序存储结构：顺序存储结构的优点是简单，易理解，并且实际占用最少的存储空间；缺点是需要占用一片地址连续的整块空间，并且存储分配要实现进行；另外，对于一些操作的时间效率较低也是这种存储结构的主要缺陷之一。
2、链式存储结构：链式存储结构是指在计算机存储器中用一片地址任意的(连续的或者不连续的)存放数据元素的信息，一般称每个数据元素占用的若干存储单元的组合作为一个链结点。每个链结点中不仅要存放一个数据元素的元素信息，还要存放一个指出这个元素在逻辑关系中的直接后继元素所在链结点的地址，该地址被称为指针。这就是说，数据元素之间的逻辑关系通过指针间接地反映。由于不要求存储空间地址连续，因此，逻辑上相邻的数据元素在物理上不一定相邻。这种存储结构的优点是存储空间不必事先分配，在需要存储空间时可以临时申请，不会造成存储空间的浪费。像插入和删除这样操作的时间效率采用链式存储结构远比采用顺序存储结构要高。但是在这种情况中，不仅数据元素本身的数据信息需要占用存储空间，而且指针也有存储空间的开销，因此，从这一点来说，链式存储结构要比顺序存储结构的空间开销大。
3、索引结构是利用数据元素的索引关系来确定数据元素的存放位置的一种存储结构，它是由数据元素本身的数据信息以及索引表两个部分组成的。
4、散列结构是由事先构造的散列函数关系及处理冲突的方法来确定数据元素在散列表中的位置。

1、数据的逻辑结构：逻辑结构是指数据元素之间的逻辑关系，即在逻辑上描述数据，它与数据的存储无关，是独立于计算机的，数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合，树，图是典型的非线性结构。
2、数据的存储结构：存储结构是指数据结构在计算机中的表示(又称物理结构)。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有顺序存储结构、链式存储结构、索引存储结构和散列存储结构。
3、数据的运算：施加在数据上的运算包括数据的定义和实现。

因此，数据结构课程所要研究的主要内容可以简要地归纳为以下3个方面：
1、研究数据元素之间固有的客观联系(逻辑结构)
2、研究数据在计算机内部的存储方法(存储结构)
3、研究数据在数据的各种结构(逻辑的和物理的)的基础上如何对数据实施有效的操作或处理(算法)

为此，应该说数据结构是一门抽象的，研究数据之间结构关系的学科。