• 基本概念与术语
• 数据类型
• 抽象数据类型
• 空间性能
• 时间性能的比较

基本概念与术语

定义：数据结构是一门研究的是非数值计算的程序设计问题中，计算机操作对象以及它们之间关系和操作等的学科。 简化解释：数据结构研究数据与数据之间的关系。

• 数据结构包括两方面内容：
• 逻辑结构(数学模型)
  • 线性结构：数据结构中的元素存在一对一的相互关系
  • 树形结构：数据结构中的元素存在一对多的相互关系
  • 图状结构：数据结构中的元素存在多对多的相互关系
  • 集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系
• 物理结构(存储结构)
  • 顺序映像：借助于元素在计算机存储器中的存储位置来描述元素之间的逻辑关系。
  • 链式映像：借助元素存储地址的指针来表示元素之间的逻辑关系。

• 同一逻辑结构采用不同的存储方法会得到不同的存储结构。

• 数据：是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。。
• 数据元素：数据的基本单位。
• 数据对象：是性质相同的数据元素的集合，是数据的一个子集。
• 数据项：组成数据元素，数据最小单位。
• 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。分为原子类型和结构类型。
• 抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。

与算法的联系:因为数据结构一个重要的内容就是数据结构上面定义的运算，为了描述某种操作常常需要设计算法。

数据类型

• （data type）在高级语言中，每个变量、常量和表达式都有一个确定的数据类型。类型显式或隐式的规定了在程序执行期间变量好表达式所有可能取值的范围和在这些值上所允许的操作。因此数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
• 可分为：原子类型、固定聚合类型、可变聚合类型。

  引入数据类型，从硬件的角度看是解释计算机内存中信息的一种手段，而对使用数据类型是用户来说，则实现了信息的隐藏与封装。

抽象数据类型

*　抽象数据类型是指一个数学模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。

• 特点：带有一组操作的一些对象的集合。

  抽象数据类型的定义是为了专注于考虑数据的逻辑特性，而与其在计算机内部如何表示和实现无关。不论其内部结构如何变化，只要其数学特性不变都不影响其外部的使用。 ```

ADT 抽象数据类型名 { 数据对象 数据关系 基本操作 }ADT

```

• 抽象数据类型可通过固有的数据类型来表示与实现，即利用以存在的数据类型来说明新的结构，用以实现的操作来实现新的操作。
• 每一个操作函数首先要明确需要的输入，和想得到的输出。

从空间性能和时间性能两方面比较

空间性能

1. 存储空间的分配：
   分配的空间利用率高的数据结构性能好
2. 存储密度的大小：
   存储密度=数据本身占用的存储量/结点结构占用的存储量。存储密度越大存储空间利用率越高。

时间性能的比较

就是看基本操作的复杂度分析

1. 存取元素的效率
   随机存取结构的效率存取高；顺序存取的结构存取效率低、

2. 插入和删除的效率
   顺序存储结构效率低；链式存储结构效率高。