数据结构的基本概念

01-数据结构与算法 飞快学 406浏览

数据存在两种结构:逻辑结构和存储结构,一种逻辑结构可以有多种存储结构。

数据结构的定义

数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

数据对象:是性质相同的数据元素的集合,是数据的一个子集。

数据结构作为计算机的一门学科,主要研究和讨论以下三个方面:(1) 数据集合中个数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2) 在对数据元素进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3) 对各种数据结构进行的运算。

数据的逻辑结构与存储结构

数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成 B=(D,R),其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。

如下图所示,数据的逻辑结构是线性表,但有两种存储结构(物理结构):顺序存储结构和链式存储结构。

cunchujiegou

一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,选择合适的存储结构是很重要的。

数据结构的图形表示

data-structure-graph

线性结构与非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。

线性结构必须具备下列两个条件:(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。

线性结构又称线性表,在一个线性结构中插入或删除任何一个结点后还应是线性结构。

如果一个数据结构不是线性结构,则称之为非线性结构。