数据结构

在计算机科学中，数据是一个比较广泛的概念，所有计算机输入、存储、处理和输出的信息都是数据，如字符、数字、图像、声音、视频等。在数据结构与算法中，数据元素是程序进行处理的一个独立的单位。数据元素可以包含若干子项目，称为数据项。在不同的问题领域，数据元素包含的数据项可能有所不同。

数据结构的研究对象为问题中数据元素及其相互关系。具体来说，数据结构的研究内容包括数据的逻辑结构、数据的存储结构、数据的运算3个方面。

逻辑结构

数据的逻辑结构指数据之间的逻辑关系。

数据元素的逻辑结构可以分两大类：线性结构与非线性结构。

• 集合结构
  • 元素除了处于同一集合外，没有任何其他关联
• 线性结构 元素之间存在一一对应的关系
  • 有且仅有一个数据元素无前驱，且只有一个后继，称为头元素。
  • 有且仅有一个数据元素无后继，且只有一个前驱，称为尾元素。
  • 其余的数据元素有且仅有一个前驱，有且仅有一个后继。
• 非线性结构 每个数据元素可能与0个或多个数据元素有关系。
  • 树形结构
    • 元素之间存在一对多的关系
  • 图形结构
    • 元素之间存在多对多的关系

物理结构

数据的存储结构是指数据元素及数据元素的关系在计算机中的存储（或表示），也叫做数据的物理结构。在数据的存储结构中，不仅要把数据元素存储起来，还要把数据元素之间的关系表达出来。

• 顺序存储
  • 在顺序存储中，数据元素按照其逻辑结构规定的逻辑顺序，依次存储在一组连续、等长的内存单元中。数据元素之间的关系是通过存储单元的物理地址的前后顺序来表达的。
• 链式存储
  • 在链式存储中，数据元素存储在任意的内存单元（可以相邻，也可以不相邻）中。数据元素之间的关系是通过指示数据元素存储地址的指针来表达的。
• 散列存储。
  • 在散列存储中，数据元素的存储位置由数据元素的值确定。数据元素之间的关系通过指针表达。
• 索引存储。
  • 在索引存储中，需要建立索引表和子表。数据元素存储在子表中，索引表存储子表的首地址及相关信息。根据需要，索引表和子表都可以采用顺序存储或者链式存储。

数据的运算

数据的运算是指广义上的运算，不同的数据结构往往具有不同的运算实现。

1. 查找：查找满足给定条件的数据元素。
2. 插入：在指定的位置加入新的数据元素。
3. 删除：删除满足给定条件的数据元素。
4. 修改：修改其中的某些数据元素。
5. 遍历：不重复地访问所有的数据元素。
6. 排序：按照给定的顺序输出所有的数据元素。

对于同一种运算，在不同的数据结构中有着不同的实现方法，且效率也有较大的差异。如在顺序存储的线性结构中实现查找运算效率较高，但是实现插入和删除运算效率较低；而在链式存储的线性结构中实现查找运算效率较低，但是实现插入和删除运算效率较高。

数据结构的表示方法

二元组

在数据结构的二元组表示方法中，将数据结构形式定义为一个二元组（D，R），D是数据元素的有限集合，R是D上关系的有限集合。其中关系的表示方法如下：如x、y是D中的两个数据元素，用有序对<x，y>表示数据元素x和y之间的关系，x是有序对<x，y>的第一个元素，y是有序对<x，y>的第二个元素。

在学生信息表中，如果用d1、d2、d3和d4分别表示学号为20150101、20150102、20150103和20150104的4位学生，则学生信息表的二元组表示为<D，R>，其中D={d1，d2，d3，d4}，R={<d1，d2>，<d2，d3>，<d3，d4>}。

数据结构的二元组表示不是很直观。用图形表示数据结构是一种较直观的方法。

图形

线性结构示意图

树形结构示意图

图形结构示意图
用图形表示数据结构比较形象、直观，方便讨论问题，故常常被人们使用。