基本概念和术语

本文最后更新于:4 个月前

基本概念和术语

1.2.1 数据,数据元素,数据项和数据对象

数据(Data)

数据 (Data) 是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号

的总称。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、

图像、声音及动画等通过特殊编码定义后的数据。

数据元素(Data Element)

数据元素(Data Element)是数据的基本单位,数据元素用于完整地描述一个对象。

在计算机中通常作为一个整体进行考虑和处理。

数据项(Data Item)

数据项 (Data Item) 是组成数据元素的、有独立含义的、不可分割的最小单位。

例如,学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象(Data Object)

数据对象 (Data Object) 是性质相同的数据元素的集合,是数据的一个子集

例如:学生基本信息表也可以是一个数据对象。

由此可以看出,不论数据元素集合是无限集(如

整数集),或是有限集(如字母字符集),还是由多个数据项组成的复合数据元素(如学生表) 的集合,

只要集合内元素的性质均相同,都可称之为一个数据对象。


1.2.2 数据结构(Data Structure)

数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说数据结构就会带有“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
数据结构包括了逻辑结构和存储结构两个层次

逻辑结构

数据的逻辑结构从逻辑关系上描述数据,它与数据的存储没有关系,独立于计算机。

数据的逻辑结构两个关键要素:

1. 数据元素;
2. 关系;

一般的逻辑结构有四种基本类型结构:

  1. 集合结构(非线性结构)

​ 数据元素之间除了”属于同一个集合”之外,没有其他关系;

  1. 线性结构

​ 数据元素之间存在一对一的关系;

​ 例如:按照学生的入学时间导入学生信息,这里学生的入学时间和学生信息组成了一一对应关系,成为了一个线性机构。

  1. 树结构(非线性结构)

​ 数据元素中存在一对多的关系;

​ 例如:在班级管理中,一个班长管理多个组长,一个组装管理多个组员形成了树形结构。

  1. 图结构或者网状结构(非线性结构)

​ 数据元素中存在多对多的关系;

以上的集合机构,树结构和图结构(网状结构)是非线性结构

线性结构的例子: 线性表(典型的现行结构,比如上述的学生信息), 栈和队列, 字符串, 数组, 广义表;

非线性结构的例子: 树结构和二叉树, 有向图和无向图;

存储结构(物理结构)

将数据结构存储到计算机中时候,不仅仅需要存储数据元素,还要存储数据元素的逻辑关系;

数据元素在计算机中内用一个结点表示。

数据元素在计算机内部有两种基本存储逻辑:

  1. 顺序存储结构

    顺序是要求所有的元素一次存放在一片连续的存储空间中;

    顺序的存储结构是按照元素在存储器中的相对位置来表示元素之间的逻辑关系的。

    所以顺序存储结构通常借用程序设计语言的数组类型来描述;

  2. 链式存储结构

    链式存储无需占用一整块的存储空间;

    但是为了表示结点之间的关系,需要给每个节点附加指针字段,用于存放后继元素存放地址;

    所以链式存储结构通常借用程序设计语言的指针类型来描述;

    如下图中:每个结点占用两个连续单元,一个存放结点信息,一个存放后继结点的首地址:

链式存储结构


1.2.3 数据类型和抽象数据类型

数据类型 (Data Type)

每一个数据都属于某种数据类型;类型明显或者隐含的规定了数据的取值范围,存储方式以及允许进行的运算。

抽象数据类型(Abstact Data Type, ADT)

抽象就是抽取出实际问题的本质。在计算机中使用二进制表示数据,在汇编语言中可以使用各种数据的十进制表示,他们是二进制的抽象,可直接使用不必考虑细节。

抽象数据类型一般由用户定于的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。

抽象数据类型的定义格式如下:

ADT 抽象数据类型名 {

​ 数据对象:(数据对象的定义, 数学符号和自然语言描述)

​ 数据关系:(数据关系的定义,数学符号和自然语言描述)

​ 基本操作: (基本操作的定义)内容格式为 => {

​ 基本操作名(参数表 => 接受两个参数 1.提供的输入值;2.引用参数以“&”开头)

​ 初始条件:(初始条件描述)

​ 操作结果: (操作结果描述)

​ }

}ADT 抽象数据类型名