数据结构与算法基本概念

r囧r小猫 2022-05-28 07:39 230阅读 0赞

#### 数据 ####

> 数据（Data）是能够被计算机程序识别、存储、加工和处理的描述客观事物的数字等符号集合的总称。

#### 数据项 ####

> 数据项（Data Item）是具有独立含义的、数据不可分割的最小标识单位，是数据元素的组成部分，也可称为字段和域。

#### 数据元素 ####

> 数据元素（Data Element）是数据的基本单元，又可称为元素、结点、顶点和记录，是一个数据整体中可以标识和访问的数据单元。

#### 数据对象 ####

> 数据对象（Data Object）是性质相同的数据元素的集合，也叫做数据元素类，是数据的一个子集，数据元素是数据对象的一个实例。

#### 数据结构 ####

> 数据结构（Data Structure）是相互之间存在着一种或者多种关系的数据元素的集合，数据结构包含3个方面的内容，即数据的逻辑结构、数据的存储结构和数据的操作，只有3个方面的内容相同才能成为完全相同的数据结构。

##### 逻辑结构 #####

*  （1）集合：集合中元素的关系极为松散，关系为“属于同一个集合”。
 *  （2）线性结构：线性结构是数据结构中具有线性关系的数据结构，线性结构中的结点存在“一对一”的关系。
 *  （3）树形结构：树形结构是数据元素之间具有层次关系的一种非线性结构，树形结构中的结点存在“一对多”的关系。
 *  （4）图形结构：图形结构也是一种非线性结构，图形结构中的结点存在“多对多”的关系。

##### 存储结构 #####

> 逻辑结构在计算机中的存储表示或实现叫数据的存储结构，也叫物理结构。数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立于计算机的；而数据的存储结构是逻辑关系在计算机中的实现，依赖于计算机。

*  （1）顺序存储结构

> 顺序存储结构在连续的存储单元中存放数据元素，元素的顺序存储次序和逻辑次序一致，即物理位置相邻的元素在逻辑上也相邻，每个元素与其前驱元素和后继元素的存储位置相邻，数据元素的物理存储结构体现它们之间的逻辑关系。顺序存储结构可通过程序设计语言的数组实现。

*  （2）链式存储结构
    
    > 链式存储结构使用地址分散的存储单元存放数据元素，逻辑上相邻的数据元素的物理位置不一定相邻，数据元素间的逻辑关系通常由附加的指针表示，指针记录前驱元素和后继元素的存储地址。数据元素由数据元素和存放逻辑关系的指针共同构成，通过指针将相互直接关联的结点链接起来，结点间的链接关系体现数据元素之间的逻辑关系。
 *  （3）索引存储结构
    
    > 索引存储结构在存储数据元素的基础上增加索引表。索引表的项由关键字和地址构成，其中关键字唯一标识一个数据元素，地址为该数据元素存储地址的首地址。
 *  （4）散列存储结构
    
    > 散列存储结构也叫哈希存储结构，数据元素的具体存储地址根据该数据元素的关键字值通过散列函数直接计算出来。

##### 数据操作 #####

> 数据操作是指对数据结构中的数据元素进行运算或处理。数据操作定义在数据逻辑结构上，每种逻辑结构都需要一组对其数据元素进行处理以实现特定功能的操作，如插入、删除、更新等。数据操作的实现依赖于数据的存储结构。