# 数据结构

2022年8月25日3分钟阅读

- FormalSciences/ComputerScience

## 概述

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

## 数据

数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

数据项 > 数据元素 >> 数据对象：数据项构成了数据元素，数据元素组合成了数据对象。

## 结构

结构是不同数据元素之间不是独立的，而是存在特定的关系。

### 逻辑结构

逻辑结构是指数据对象 中 数据元素之间的相互关系。

- 集合：集合结构中的数据元素除了属于一个集合外，它们之间没有其他关系。
- 线性：线性结构中的数据元素之间是一对一的关系。
- 树形：树形结构中的数据元素之间存在一种多对多的层次关系。
- 图形：图形结构的数据元素是多对多的关系。

### 物理结构

物理结构是指数据的逻辑结构在计算机中的存储形式。

#### 顺序存储

顺序存储结构是把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

#### 链式存储

链式存储结构是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

## 数据类型

数据类型是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称。

### 定义

- 相同数据对象集合（例如整数 > 整数型，字符 > 字符型）。
- 集合相关联的操作（整数可以加减，字符可以拼接）。

### 分类

- 原子类型（字节型、数值型、字符串型）。
- 结构类型（原子类型的组合）。

## 抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及其定义在该模型上的一组操作。

    ADT 抽象数据类型名
    Data
    	数据元素之间逻辑关系的定义
    Operation
    	操作1
    		初始条件
    		操作结果描述
    	操作2
    		…………
    	操作n
    		…………
    endADT