数据结构

数据 data

是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素 data element

是数据的基本单位，也称记录。在计算机程序中作为一个整体进行考虑和处理。

数据项 data item

一个数据元素可由若干个数据项组成，它是一个数据整体中相对独立的单位。

数据结构 data structure

由某一数据元素的集合和该集合中数据元素之间的关系组成。

$$ Data_Structure={D,R} $$

• 逻辑结构：数据元素之间的相关关系称为逻辑结构。
• 存储结构(物理结构)：数据逻辑结构的物理存储方式。
• 数据运算：施加在该数据上的操作。

如何设计软件小组件？

逻辑层面：

• 首先理清楚数据本身是什么？
  • 包含哪些元素？
  • 元素之间的关系？结构！
• 提供哪些功能？

实现层面：

• 数据如何存储？
• 功能如何实现？

数据结构-逻辑结构

• 集合结构：元素除了同属于一个集合外，他们之间没有其他关系
• 现行结构：元素之间是一对一的关系。
• 树形结构：元素之间是一对多的层次关系
• 图形结构：元素之间是多对多的关系。

数据结构-物理结构(存储结构)

• 顺序存储方法：数据元素存放在地址连续的存储单元中，其数据间的逻辑关系和物理关系是一致的。

• 链接存储方法：逻辑上相邻的元素在物理位置不一定相邻，元素之间的逻辑关系由附件指针指示

• 索引存储方法：存储元素信息的同时，还建立附加的索引表。

• 散列存储方法：根据结点的关键码通过一个函数计算直接得到该节点的存储地址。 11 个元素的关键码分别为 18,27,1,20,22,6,10,13,41,15,25 $$ f(key)=key%11 $$

数据结构-数据运算

• 对于一批数据，数据的运算（操作）是定义在数据的逻辑结构之上，而运算（操作）的具体实现就依赖于数据的存储结构。

• 同一逻辑结构可以对应多种存储结构

• 同样的运算，在不同的存储结构中，其实过程是不同的

数据结构的抽象

抽象形式

数据类型：一种类型，一组值的集合以及定义于这个值集合上的一组操作的总称。

分类：

• 原子类型： 不可以在分解的基本类型
• 结构类型： 由若干个类型组合而成，是可以再分解的

抽象数据类型

概念：由基本的数据类型组成，并包括一组相关的服务(或操作)

从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。

特征：使用与实现分离，实行封装和信息隐蔽。

定义：由 元素 、 关系 、 操作 三种要素来进行定义