Question

数据结构基本概念

Answer 1

数据结构概念包含三方面：数据的逻辑结构、数据的存储结构、对数据的操作
一、数据的逻辑结构

1、数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系表示。

2、数据结构分为三种：线性结构、树结构、图
其中树和图是非线性结构。
（1）线性结构：是具有线性关系的数据结构，线性表的元素是有序数列，每个元素（除了头和尾）有且仅有一个前驱和后继。
（2）树结构：数据元素之间具有层次关系的一种非线性结构，树种数据元素通常称为结点。树结构的层次关系是指---->根结点没有前驱结点，除了根以外的其他结点有且仅有一个父母结点，所有结点可有多个或零个后继结点，或称孩子结点。
（3）图：每个数据元素可有多个前驱元素和多个后继元素。

3、数据元素及其关系在计算机中的存储表示或实现称为“数据的存储结构”，也称物理结构

二、数据的存储结构

1、数据的逻辑结构从逻辑关系的角度观察数据，它与数据的存储无关，独立于计算机，而数据的存储结构是逻辑结构在计算机内存中的实现，依赖于计算机。

2、数据的存储结构基本形式有两种：顺序存储结构、链式存储结构
（通常数组实现顺序存储结构、链表实现链式存储结构）
（1）顺序存储结构：使用一租连续的内存单元一次存放数据元素，数据元素在内存中的物理存储顺序与他们的逻辑顺序相同，即每个元素与其前驱元素以及后继元素的存储位置相邻。
（2）链式存储结构：使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素之间的关系需要采用附加信息特别指定。通常像链表那样，采用指针变量来记录前驱和后继元素的地址，c语言采用指针，Java采用引用。

三、对数据的操作

1、每中数据结构都需要一组对其元素实现特定功能的操作：
比如：初始化、判空、存、取、插入、删除、排序等等操作。

四、数据类型与抽象数据类型

1、数据类型
类型是具有相同意义的一组值的集合，数据类型是指一个类型和定义在这个类型上的操作集合，数据类型定义了数据的性质，取值范围以及对数据所能进行的各种操作。
（Java的基本数据类型包括：整数类型，浮点类型等等）

2、抽象数据类型
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
比如复数的抽象数据类型：

3、数据抽象
是指“定义”和“实现”相分离，类似与接口的定义与实现。
四、数据结构基本区别