数据结构基础

点击打开在线编译器,边学边练

1. 基本概念和术语

1)数据

数据(Data)是信息的载体,是可以被计算机识别,存储并加工处理的描述客观事物的信息符号的总称。数据不仅仅包括了整形,浮点数等数值类型,还包括了字符甚至声音,视频,图像等非数值的类型。

2)数据元素

数据元素(Data Element)是描述数据的基本单位,也被称为记录。一个数据元素有若干个数据项组成。

如禽类,鸡鸭都属于禽类的数据元素。

3)数据项

数据项(Data Item)是描述数据的最小单位,其可以分为组合项和原子项:

a)组合项

如果数据元素可以再度分割,则每一个独立处理单元就是数据项,数据元素就是数据项的集合。

b)原子项

如果数据元素不能再度分割,则每一个独立处理的单元就是原子项。

如日期2019年4月25日就是一个组合项,其表示日期,但如果单独拿25日这个数据出来观测,这就是一个原子项,因为其不可以再分割。

4)数据对象

数据对象(Data Object)是性质相同的一类数据元素的集合,是数据的一个子集。数据对象可以是有限的,也可以是无限的

5)数据结构

数据结构(Data Structures)主要是指数据和关系的集合,数据指的是计算机中需要处理的数据,而关系指的是这些数据相关的前后逻辑,这些逻辑与计算机储存的位置无关,其主要包含以下四大逻辑结构。


2. 四大逻辑结构(Logic Structure)

1) 集合结构

集合结构(Set Structure)中所有数据元素除了同属于一个集合外,并无其他关系。

如图:

51.png

2) 线性结构

线性结构(Linear Structure)指的是数据元素之间存在“一对一的关系”

如图:

52.png

3) 树形结构

树形结构(Tree Structure)指的是数据元素之间存在“一对多”的层次关系。

如图:

53.png


4) 图形结构

图形结构(Graphic Structure,也称:网状结构)指的是数据元素之间存在“多对多的关系”(注:此时的“多对多”中的多表示,至少有一个)

图示:

54.png





3.数据类型

1) 数据类型

数据类型(Data Type)是高级程序设计语言中的概念,是数据的取值范围和对数进行操作的总和。数据类型规定了程序中对象的特性。程序中的每一个变量,常量或者表达式都属于一种数据类型。

2) 抽象数据类型

抽象数据类型(Abstract Data Type,ADT)只是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象,定义了数据的取值范围以及对数据操作的集合。

抽象数据类型的特征是实现与操作分离,从而实现封装。

我们拿《魂斗罗》做比方:我们给予主角打,跳,移动的基本操作,这些操作就可以看作是抽象数据类型,这一组操作就属于一个模型,这组抽象的数据类型可以在《魂斗罗》这个环境中使用。


上一课:算法基础 下一课:理解复杂度概念
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记