# 数据结构基本概念

## 基本概念：

  1、**数据**

  数据就是信息的载体，其实通俗来讲就是计算机输入，处理和输出的东西。

  2、**数据元素**

  数据元素就是数据的基本单位，**数据项**就是构成数据元素的不可分割的最小单位。举个例子，学生记录由学号，姓名和性别构成，那么学生记录就是一个数据元素，学号，姓名，性别就是数据项。

  3、**数据对象**

  数据对象就是有相同性质的数据元素的集合。

  4、**数据类型**

  数据类型是一个值的集合和定义在此集合上的一组操作的总称。

  1）原子类型。其值不可再分的数据类型。像int，float，double。

  2）结构类型。其值可以再分。例如结构体，它的值就可以再分。

  3）抽象数据类型。抽象数据组织及与之相关的操作。

  5、**抽象数据类型**（ADT，abstract Data Type）

  是指一个数学模型及定义在该模型上的一组操作。通常用（数据对象，数据关系，基本操作集）这样的三元组来表示。

  6、**数据结构**

  数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

## 三要素：

  1、**数据的逻辑结构**

  逻辑结构就是数据元素与元素之间的逻辑关系。它与计算机存储数据的方式无关，是独立与计算机的。

  常见的逻辑结构有：**线性结构**和**非线性结构**。

  线性结构：数据元素之间只存在一对一的关系。（线性表）

  非线性结构：

    1）集合（同属于一个集合）

    2）树形结构（一对多）

    3）图状结构（多对多）

  2、**数据的存储结构**

  存储结构其实就是数据在计算机中的表示方法，又称**物理结构**。

  分类：

    1）顺序存储：逻辑上相邻的元素物理上也相邻。

       优点：随机存储，每个元素占用最少的存储空间。

       缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

    2）链式存储：不要求逻辑上相邻的元素在物理上也相邻。

       优点：不会出现碎片现象，能充分利用所有存储单元。

       缺点：每个元素因存储指针而占用额外的存储空间，而只能实现顺序存取。

    3）索引存储：在存储元素信息的同时，还建立附加的索引表。索引表的每项称为索引项，索引项的一般形式是（关键字，地址）。

       优点：检索速度快

       缺点：增加附加的索引表后会占用较多的存储空间，在增加删除数据的时候要修改索引表，花费的时间较多。

    4）散列存储：根据元素的关键字直接计算出该元素的存储地址，又称hash存储。

       优点：检索、增加和删除结点的操作都很快

       缺点：若散列函数不好，则可能出现元素存储单元冲突，而解决冲突会增加时间和空间开销

  3、**数据的运算**

  包括运算的定义与实现。定义是针对逻辑结构的，指出运算的功能；实现是针对存储结构的，指出运算的具体操作步骤。